MTH4300 Home

MTH 4300: Final Practice 1

Problem 1.

Create the class Mountain with two private attributes: The attribute name has to be of type std::string and the attribute height has to be of type double. Create the public methods that can be used to set the values to the attributes and to read the values from the attributes. Write a program that reads a positive integer n from the user input and properly allocates the memory for a sequence sM of n objects of class Mountain using the operator new. The program should then receive n pairs of strings and numbers from std::cin and store these values in the sequence sM. The program should then read a positive real number r and print all terms of the sequence sM whose attribute height is smaller than r.

Problem 2.

Assume that we have a supercomputer and that the type bigInt can store all integers smaller than \(10^{1000}\). The class Elephant has public attributes alpha, beta, and gamma of type bigInt. Assume that the class Elephant has a properly implemented comparison operator operator< and that std::set<Elephant> can be used in programs.

The declaration of the class Bird and the implementation of its methods are given below

class Bird{
private: 
   bigInt num;
public:
   Bird();
   Bird(const Elephant& );
   Bird(std::set<Elephant>::const_iterator );
   bigInt getNum() const;
};
Bird::Bird(){num=0;}
Bird::Bird(const Elephant& abc){
   num=0;
   if (( abc.alpha < 700) && (abc.beta < 700) && (abc.gamma < 700) ){ num=3; }
}
Bird::Bird(std::set<Elephant>::const_iterator abc){
   num=0;
   if (( abc->alpha < 3500) && (abc->beta < 3500) && (abc->gamma < 3500) ){ num=8; }   
}
bigInt Bird::getNum() const{return num;}
It is known that the variables first and second are of type std::set<Elephant>. The set first contains all possible objects of type Elephant whose components alpha, beta, and gamma are non-negative integers divisible by \(5\) and smaller than \(10^{1000}\). The set second contains all possible objects whose components alpha, beta, and gamma are non-negative integers divisible by \(7\) and smaller than \(10^{1000}\). What is the value of sing(first,second), where the function sing is implemented below? Provide a rigorous justification for your answer.
bigInt sing(const std::set<Elephant>& a, const std::set<Elephant>& b){
   bigInt res=0;
   std::set<Elephant>::const_iterator i;
   i=a.begin();
   while(i!=a.end()){
      if(b.find(*i)!=b.end()){
         Bird temp(*i);
         res += temp.getNum();
      }
      ++i;
   }
   return res;
}

Problem 3.

The objects of the class SN are nodes of a stack. The components are real numbers of type double. The function stackOperations is implemented below, but it is missing one line of code. The word MISSING_LINE is placed instead of that line. The function has to reverse the order of the elements in the stack a2 and move them to the top of the stack a1.

SN* stackOperations(SN* a1, SN* a2){
   SN* nTop;
   nTop=a1; SN* runner=a2;
   while(runner!=nullptr){
      nTop=push(nTop,runner->content); runner=runner->aNext;
   }
   MISSING_LINE
   return nTop;
} 

The call of the function inside main() would be made with the following code

   SN* aNewStack=stackOperations(aTop1,aTop2); 

You can assume that before the call, the pointers aTop1 and aTop2 contain the addresses of the top terms of two properly created stacks. After the call, the stack that was originally pointed at by aTop2 should be empty and its terms placed on top of the first stack.

Which of the following commands should be placed instead of MISSING_LINE to prevent the function from producing a memory leak?

  • (A) delete runner->aNext;
  • (B) delete a2;
  • (C) delete[] runner;
  • (D) while(a2!=nullptr){a2=pop(a2);}
  • (E) delete[] a2;
  • (F) delete a1;
  • (G) The text MISSING_LINE should be erased and no command should be put instead of it. The code does not produce memory leaks.
  • (H) delete[] a1;

Problem 4.

Create a program that counts the total number of recipes that are provided by the user. User input consists of multiple lines. Each line starts with an integer \(n\). If \(n\) is negative, then this is the signal that the input is over. If \(n\) is positive, then \(n\) is the number of ingredients in the recipe. After the number \(n\), the line consists of \(n\) different strings that represent the names of the ingredients.

Two recipes are considered the same if they have the same ingredients. For example, these two recipes are the same

3 strawberry chocolate banana
3 chocolate banana strawberry
Example
Input
3 strawberry chocolate banana 
2 chocolate strawberry
2 chocolate banana
3 chocolate banana strawberry
2 strawberry chocolate
The corresponding output should be 3.

Problem 5.

The declaration of the class whose objects are nodes of a tree is

class TN{
public:
  long content;
  TN* aLeft;
  TN* aRight;
};
The tree is damaged. The leaves that should contain the null pointers are now pointing to some other nodes. The picture of this damaged tree is shown below.

The implementation of the functions f and g are given below

long f(TN* t){
   t=t->aLeft;
   t->content += 1;
   return t->content;
}
long g(TN*& t){
   t=t->aRight;
   t->content += 2;
   return t->content;
}

The pointer aHead initially contains the address of the root of the tree (the root contains the number \(40\)). What is the output of the following code? Provide a rigorous justification for your answer.

   aHead=aHead->aLeft;long sum=0;
   for(long i=0;i<3;++i){
      sum+=f(aHead); sum+=g(aHead);
   }
   std::cout<<sum<<"\n";

Problem 6. Each square of the table \(m\times n\) (the number of rows is \(m\) and the number of columns is \(n\)) contains an airport. Every airport has a fee that an airplane must pay if it lands on it. The landing fee for the airport \((0,0)\) is \(0\). Unless specified otherwise by the user, the landing fee for every other airport is \(100\) dollars. After taking off from the cell with coordinates \((x_0,y_0)\) (with \(0 \leq x_0 \leq m\) and \(0 \leq y_0 \leq n\)) the airplane can land on any cell whose coordinates \((x_1,y_1)\) satisfy \begin{eqnarray*} 0\leq x_1 \leq m,\quad 0\leq y_1 \leq n,\quad x_0 \leq x_1 \leq x_0+5,\quad\mbox{and}\quad y_0 \leq y_1 \leq y_0+5.\end{eqnarray*} Create the program that determines the path from \((0,0)\) to \((m,n)\) that the plane should take to minimize the total sum of all landing fees. The user input consists of two positive integers \(m\) and \(n\), an integer \(b\) that represents the number of airports whose landing fees are different from \(100\), and the sequence of \(b\) triplets \((x,y,f)\) of positive integers such that \(f\neq 100\). Each triplet \((x,y,f)\) represents that the landing fee for the airport \((x,y)\) is equal to \(f\).
Your program should use data structures based on binary search trees to achieve the polynomial complexity.
Example: \(m=10\), \(n=6\); The fees at the airports \((3,0)\), \((7,0)\), \((9,2)\) are 5; The fees at the airports \((3,3)\) and \((3,4)\) are \(1\); The fees at all other airports are \(800\). Then the cheapest flight has the cost \(815\). The path is \((0,0) \to (3,0) \to (7,0) \to (9,2) \to (10,6)\).