Skillrack PPS 7

CSE 1002 PPS7

Total time : 600 mins

Challenges : 5

Question 1(Solar vehicle)

There are ‘n’ bags in a corner of a city and they have to be moved to the centre of the city by a solar vehicle. The vehicle starts shunting from morning, the vehicle can carry more load in the mornings than in the evening when sunlight would be dimmer. Given the details of items in the bag, sort the bag in descending so that the vehicle can safely carry it to the centre of the city. Use vector and map in STL. Also use the sort algorithm defined in STL.

Hint: Use total weight of bag as key and object of bag as value, insert total weight of each bag into a vector. Use STL sort algorithm to sort it and print the details of bag in order

Input Format

Number of bags ‘n’

Name of bag1

Number of types of items in bag1, ‘t’

Weight of item1 in bag1

Number of item1 in bag1

Weight of item2 in bag1

Number of item2 in bag1

Weight of itemt in bag1

Number of itemt in bag1

….

….

Name of bagn

Number of types of items in bagn, ‘t’

Weight of item1 in bagn

Number of item1 in bagn

Weight of item2 in bagn

Number of item2 in bagn

Weight of itemt in bagn

Number of itemt in bagn

Output Format

Print name of bags in sorted order.

Sorting must be done in descending order based on the weight of the bag

Solution

#include

#include

 

#include

#include

using namespace std;

class bag

{

char name[30];

int num_Of_Items;

float item_Wt[20];

float item_Count[20];

public:

void get();

//print only name of bag

void print();

//Compute weight from details given

float compute();

};

bool wayToSort(int i, int j);

class solar

{

map<float,bag> m1;

vector v;

int num_Bags;

public:

//get details of bags and insert into map and vector

// In map, key – weight and value – details of bag

// In vector, weight of bags

void get();

void sort_Vec();

//print name of bags in sorted order

void print_In_Order();

};

void bag :: get()
{
    cin>>name>>num_Of_Items;
    for(int i=0;i < num_Of_Items;i++)  
    cin>>item_Wt[i]>>item_Count[i];
}
void bag :: print()
{
    cout<<name<<"\n";
}
float bag :: compute()
{
    float total=0;
    for(int i=0;i < num_Of_Items;i++)  
    total+=item_Count[i]*item_Wt[i];  
    return(total);  
}  
void solar :: get()  
{  
    bag b;  
    cin>>num_Bags;
    for(int i=0;i < num_Bags;i++)
    {
        b.get();
        m1.insert(pair < float,bag > (b.compute(),b));
        v.push_back(b.compute());
    }
}
void solar :: sort_Vec()
{
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
}
void solar :: print_In_Order()
{
    for(vector < float > :: iterator i=v.begin();i!=v.end();i++)
    m1[*i].print();
}

int main()

{

solar s;

s.get();

s.sort_Vec();

s.print_In_Order();

}

Input

INPUT :

for(int i=0;i < num_Bags;i++)
{
    b.get();
    m1.insert(pair < float,bag > (b.compute(),b));
    v.push_back(b.compute());
}

Procssing

sort(v.begin(),v.end());
reverse(v.begin(),v.end());

Output

OUTPUT :

for(vector < float > :: iterator i=v.begin();i!=v.end();i++)
m1[*i].print();

Pseudocode

BEGIN

Read input
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
for(vector < float > :: iterator i=v.begin();i!=v.end();i++)
m1[*i].print();

END

Question 2(Generic queue)

Design a generic class queue to maintain a list of elements. Queue is a linear data structure that follow FIFO ordering of elements. It is a special kind of list where elements can be inserted at one end and deleted at the end. There are two end points called front and rear. Front is the point of deletion and that move for each deletion but always points to the element that was inserted first among the elements remaining in the queue. Rear is the point of the insertion and move for each insertion but always points to the element that was inserted last among the elements remaining in the queue. Provide member functions to check if a queue is empty, queue is full, enqueue and dequeue.

Enqueue – if queue is not full, increment rear and place the element

dequeue – If queue is not empty, return element pointed by front and increment front

isempty – Return true when front is greater than rear or when both are -1

isfull – return true when rear is capacity – 1

Extended the class queue to create another generic class deque which represents a double ended queue. In deque, elements can be added to or removed from either the front or rear. The operations in a deque are defined as follows:

push_back – Insert an element at the rear (enqeue in Queue)

push_front – Insert an element at the front, if queue is not full push all elements forward and place new element, change rear also

pop_back – Remove an element at the rear, if queue is not empty, return element pointed by rear and decrement rear

pop_front – Remove an element at the front (dequeue in Queue)

print – print elements of queue from first to last

Input Format

Choice of queue and data type (1 – integer linear queue, 2 – String deque)

Choice of operation

For queue – 1 – isempty, 2 – isfull, 3 – enqueue, 4 – dequeue, 5 – Print content of queue, 6 – exit

for enqueue option 3, element to be inserted will follow the choice

For deque – 1 – isempty, 2 – isfull, 3 – push_back, 4 – push_front, 5 – pop_back, 6 – pop_front 7 – Print content of deque, 8 – exit

for both the push options 3 and 4, element to be inserted will follow the choice

Output Format

Print the content of queue after each operation, print elements from first to last

Solution

#include

using namespace std;

#include

//global error flag for dequeue

bool ERR_Flag = false;

template

class queue

{

protected:

int front;

int rear;

int capacity;

T *ele;

public:

//constructor to allocate memory and initialize data members

queue();

bool isempty();

bool isfull();

//Check if queue is full before insertion

//if queue is full return false

// insert element and return true otherwise

bool enqueue(T data);

//funtion to remove an element and return

T dequeue();

~queue();

void print();

};

template

class deque:public queue

{

public:

bool push_Back(T data);

bool push_Front(T data);

T pop_Front();

T pop_Back();

};

template < class T >
queue < T > :: queue()
{
    front=rear=-1;
    capacity=10;
    ele=new T[10];
}
template < class T >
bool queue < T > :: isempty()
{
    if(rear==-1)
    return(true);
    return(false);
}
template < class T >
bool queue < T > :: isfull()
{
    if(rear+1==capacity)
    return(true);
    return(false);
}
template < class T >
bool queue < T > :: enqueue (T data)
{
    if(!isfull())
    {
        ele[++rear]=data;
        return(true);
    }
    return(false);
}
template < class T >
T queue < T > :: dequeue ()
{
    T temp=ele[0];
    if(!isempty())
    {
        for(int i=0;i < rear;i++)
        ele[i]=ele[i+1];
        rear--;
        ERR_Flag=false;
        return(temp);
    }
    ERR_Flag=true;
    return(temp);
}
template < class T >
void queue < T > :: print()
{
    if(!isempty())
    for(int i=0;i <=rear;i++)
    cout<<ele[i]<<"\n";
    else
    cout<<"Queue is empty\n";
}
template < class T >
queue < T > :: ~queue(){}
template < class T >
bool deque < T > :: push_Back(T data)
{
    if(!this->isfull())
    {
        this->ele[++(this->rear)]=data;
        return(true);
    }
    return(false);
}
template < class T >
bool deque < T > :: push_Front(T data)
{
    if(!this->isfull())
    {
        this->rear++;
        for(int i=this->rear;i > 0;i--)
        this->ele[i]=this->ele[i-1];
        this->ele[0]=data;
        return(true);
    }
    return(false);
}
template < class T >
T deque < T > :: pop_Front()
{
    T temp=this->ele[0];
    if(!this-> isempty())
    {
        ERR_Flag=false;
        for(int i=0;i < this->rear;i++)
        this->ele[i]=this->ele[i+1];
        this->rear--;
        return(temp);
    }
    ERR_Flag=true;
    return(temp);
}
template < class T >
T deque < T > :: pop_Back()
{
    if(!this-> isempty())
    {
        ERR_Flag=false;
        return(this->ele[this->rear--]);
    }
    ERR_Flag=true;
    return(this->ele[0]);
}

int main()

{

int d_Choice;

int op_Choice;

deque d;

queue q;

cin>>d_Choice;

if(d_Choice==1)

{

while(1)

{

cin>>op_Choice;

if(op_Choice==1)

{

if(q.isempty())

cout<<“Queue is empty”<<endl;

else

cout<<“Queue is not empty”<<endl;

}

else if(op_Choice==2)

{

if(q.isfull())

cout<<“Queue is full”<<endl;

else

cout<<“Queue is not full”<<endl; } else if(op_Choice==3) { int data; cin>>data;

if(!q.enqueue(data))

cout<<“Queue full insertion not possible”;

}

else if(op_Choice==4)

{

q.dequeue();

if(ERR_Flag)

cout<<“Queue is empty”; } else if(op_Choice==5) { q.print(); } else if(op_Choice==6) { break; } } } else if(d_Choice==2) { string s_Data; while(1) { cin>>op_Choice;

if(op_Choice==1)

{

if(d.isempty())

cout<<“Queue is empty”<<endl;

else

cout<<“Queue is not empty”<<endl;

}

else if(op_Choice==2)

{

if(d.isfull())

cout<<“Queue is full”<<endl;

else

cout<<“Queue is not full”<<endl; } else if(op_Choice==3) { cin>>s_Data;

if(!d.push_Back(s_Data))

cout<<“Queue full insertion not possible”; } else if(op_Choice==4) { cin>>s_Data;

if(!d.push_Front(s_Data))

cout<<“Queue full insertion not possible”;

}

else if(op_Choice==5)

{

d.pop_Back();

if(ERR_Flag)

cout<<“Queue is empty”;

}

else if(op_Choice==6)

{

d.pop_Front();

if(ERR_Flag)

cout<<“Queue is empty”;

}

else if(op_Choice==7)

{

d.print();

}

else if(op_Choice==8)

{

break;

}

}

}

}

Input

INPUT :

insert()
push_Back()
push_Front()

Procssing

deqeue()
pop_Back()
pop_Front()

Output

OUTPUT :

print()

Pseudocode

BEGIN

Read input
deqeue()
pop_Back()
pop_Front()
print()

END

Question 3(Reverse vector)

Design a class charVector that has a character vector as datamember. Provide member functions in the class to createVector, duplicateVector, duplicateRevVector and print. Functions shall be defined as follows:

initializeVector – read a string and create a vector of characters

duplicateVector – Add the content of the vector once at the end. For example if the content of charVector is “bat” then after the function is called the content must “batbat”

duplicateRevVector – Add the content of the vector in reverse at the end. For example if the content of charVector is “bat” then after the function is called the content must “battab”

print – Print content of vector, use iterators for traversal

Use the vector class defined in STL for the implementation. Use [] operator in functions duplicateVector, duplicateRevVector and use iterator in print and initializeVector functions.

Input Format

String to be stored in vector1

String to be stored in vector2

Output Format

Print duplicateVector of vector1

Print duplicateRevVector of vector2

Solution

#include

#include

#include

using namespace std;

class charVector

{

vector cv;

public:

//Function to initialize vector by characters in a string

void initializeVector(string);

//Function to duplicate a vector at its back

void dupVector();

//Function to add reverse of a vector at its back

void dupRevVector();

void print();

};

void charVector :: initializeVector(string s)
{
    for(int i=0;s[i]!='\0';i++)
    cv.push_back(s[i]);
}
void charVector :: dupVector()
{
    vector < char > new_cv=cv;
    for(vector < char > :: iterator i=new_cv.begin();i!=new_cv.end();i++)
    cv.push_back(*i);
}
void charVector :: dupRevVector()
{
    vector < char > new_cv=cv;
    for(vector < char > :: iterator i=new_cv.end();i!=new_cv.begin();i--)
    cv.push_back(*(i-1));
}
void charVector :: print()
{
    for(vector < char > :: iterator i=cv.begin();i!=cv.end();i++)
    cout<<*i;
}

int main()

{

charVector ch1,ch2;

string s1,s2;

cin>>s1>>s2;

ch1.initializeVector(s1);

ch2.initializeVector(s2);

ch1.dupVector();

ch2.dupRevVector();

ch1.print();

cout<<endl;

ch2.print();

cout<<endl;

}

Input

INPUT :

for(int i=0;s[i]!='\0';i++)
cv.push_back(s[i])

Procssing

for(vector  :: iterator i=new_cv.end();i!=new_cv.begin();i--)
cv.push_back(*(i-1));

Output

OUTPUT :

for(vector  :: iterator i=cv.begin();i!=cv.end();i++)
cout<<*i;

Pseudocode

BEGIN

Read input
for(vector  :: iterator i=new_cv.end();i!=new_cv.begin();i--)
cv.push_back(*(i-1));
print()

END

Question 4(Symmetric matrix)

Given a square matrix check if it is symmetric or not. Represent a matrix as a vector of vectors. Use vector in STL to represent a matrix.

Hint: To create a matrix with ‘r’ rows and ‘c’ columns

vector m1(r,vector(c,0));

Input Format

Dimension of matrix, ‘n’

Element in row1 col1

Element in row1 col2

Element in row1 coln

Element in row2 col1

Element in row2 col2

Element in row2 coln

Element in rown col1

Element in rown col2

Element in rown coln

Output Format

Print Symmetric or Not symmetric

Solution

#include< iostream >
#include< vector >
using namespace std;
int main()
{
    int n,val;
    cin>>n;
    vector < vector < int > >mat (n,vector < int > (3,0));
    for(int i=0;i < n;i++)
    for(int j=0;j < n;j++)  
    {  
        cin>>val;
        mat[i][j]=val;
    }
    bool flag=true;
    for(int i=0;i < n;i++)
    for(int j=i+1;j < n;j++)
    if(mat[i][j]!=mat[j][i])
    {
        flag=false;
        break;
    }
    flag==true?cout<<"Symmetric":cout<<"Not symmetric";
    return(0);
}

Input

INPUT :

for(int i=0;i < n;i++)
for(int j=0;j < n;j++)  
{  
    cin>>val;
    mat[i][j]=val;
}

Procssing

for(int i=0;i < n;i++)
for(int j=i+1;j < n;j++)
if(mat[i][j]!=mat[j][i])
{
    flag=false;
    break;
}

Output

OUTPUT:

flag==true?cout<<"Symmetric":cout<<"Not symmetric";

Pseudocode

BEGIN

Read input
for(int i=0;i < n;i++)
for(int j=i+1;j < n;j++)
if(mat[i][j]!=mat[j][i])
{
    flag=false;
    break;
}
flag==true?cout<<"Symmetric":cout<<"Not symmetric";

END

Question 5(Mobile tower)

Design a class point with datamembers: name of the point(string), value of the x-coordinate and the value of  y-coordinate. Here, value of the x-coordinate and the value of the y-coordinate should be an even integer. Provide functions to get the details of a point, print the details of a point and a function to compute the  squared distance between the point and a given point(passed to the function as an argument). Design a class mobileSpace, with a list of points(both the coordinates must be even integers) that represent the position of the mobile towers and a point that  represents the  position of mobile phone. With the position of the mobile towers and mobile phone given as input,   provide member functions to get the details and determine the tower  with which the mobile phone can be connected based on the `longest squared distance between the phone and the tower’ Use STL for implementation.

Input Format

Number of towers, ‘n’

Name of tower1

X-coordinate  of tower1

Y-coordinate of tower1

Name of tower-n

X-coordinate of tower-n

Y-coordinate  of tower-n

Name of mobile

X-coordinate  of mobile phone

Y-coordinate  of mobile phone

Output Format

Name of the tower to which the phone has to be connected

Solution

Note : Has been updated

#include

#include

#include

#include

#include

using namespace std;

class point

{

char name[30];

int x;

int y;

public:

void get();

void print();

int dist(point p);

};

class mobile

{

int num_Tower_Pts;

list tower_Pts;

point mobile_Pt;

public:

void get();

point find_Max();

};

void point :: get()
{
    cin>>name>>x>>y;
}
void point :: print()
{
    cout<<name; } int point :: dist(point p)  
{  
    if(p.x%2!=0 || p.y%2!=0 || x%2!=0 || y%2!=0)
    {
        cout<<"Invalid input";
        exit(0);
    }  
    return(pow(x-p.x,2)+pow(y-p.y,2));    
}  
void mobile :: get()  
{  
    point p;  
    cin>>num_Tower_Pts;
    for(int i=0;i < num_Tower_Pts;i++)
    {
        p.get();
        tower_Pts.push_back(p);
    }
    mobile_Pt.get();
}
point mobile :: find_Max()
{
    point p;
    int max=-1;
    for(list < point > :: iterator i=tower_Pts.begin();i!=tower_Pts.end();i++)
    if(max < mobile_Pt.dist(*i))
    {
        max=mobile_Pt.dist(*i);
        p=*i;
    }
    return(p);
}

int main()

{

mobile m;

m.get();

(m.find_Max()).print();

}

Input

INPUT :

get()
cin>>name>>x>>y;

Procssing

for(list < point > :: iterator i=tower_Pts.begin();i!=tower_Pts.end();i++)
if(max < mobile_Pt.dist(*i))
{
    max=mobile_Pt.dist(*i);
    p=*i;
}

Output

OUTPUT :

print()
cout<<name;

Pseudocode

BEGIN

Read input
for(list < point > :: iterator i=tower_Pts.begin();i!=tower_Pts.end();i++)
if(max < mobile_Pt.dist(*i))
{
    max=mobile_Pt.dist(*i);
    p=*i;
}
cout<<p.name;

END
Advertisements

2 thoughts on “Skillrack PPS 7

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s