MTH 4300: Final Practice 8

The names y and z refer to the same memory location. The pointers q and p contain the address of the variable x, while the pointer r contains the address of the memory location y (which is the same as the memory location z). After the command *q=2; the memory location x contains the value 2. After the command z=y+7; the memory location y (which is the same as the memory location z) contains the value 10. The command *r=y+z; changes the content from 10 to 20. The correct answer is 42.

• (a) Stack is a data structure where each node contains two components. The first component is the content and the second component is the pointer to the next node. We only keep the record of the top node of the stack. The stack supports adding an element to the top. Such operation is called push. The stack also supports the removal of the top node (such operation is called pop). The declaration of the stack and the implementations of the functions pop and push are given below:

  struct SN{
  public:
    long cont; 
    SN* aNext;
  };
  SN* pop(SN* a){
    if(a==nullptr){return nullptr;}
    SN* n=(*a).aNext;
    delete a;
    return n;
  }
  SN* push(SN* a, long x){
    SN* n=new SN;
    (*n).cont=x;
    (*n).aNext=a;
    return n;
  }

• (b) We will first count the number of terms in the stack that need to be copied to the sequence. Once we know the correct number of terms, we allocate the sufficient memory. Then we go again over the entire stack and put the required terms in the sequence. The correct code is:

  Sequence fromStackToSequence(SN* aTop){
     Sequence result;
     result.n=0;
     SN* runner=aTop;
     while(runner!=nullptr){
        if(((runner->cont)>49) && ((runner->cont)<501)){
           ++result.n;
        }
        runner=runner->aNext;
     }
     result.a=nullptr;
     if(result.n>0){
        result.a=new long[result.n];
        runner=aTop;
        long i=0;
        while(runner!=nullptr){
           if(((runner->cont)>49) && ((runner->cont)<501)){
              result.a[i]=runner->cont;
              ++i;
           }
           runner=runner->aNext;
        }
     }
     return result;
  }

The function will visit and sum all the elements of the tree, except for the tree whose root is 5. The correct answer is 240.

The number \(x\) satisfies \begin{eqnarray*} x&=&1\cdot 3^4+2\cdot 3^3+0\cdot 3^2+1\cdot 3+0=138. \end{eqnarray*}

There are \(5\) bits for the exponent. Therefore, the exponent shift is \(2^{5-1}-1=2^4-1=15\). The first bit is the sign. Since the first bit is \(1\), the sign is negative.

The next \(5\) bits are \(10011\). They represent the shifted exponent. The binary number \(10011\) corresponds to \(19\). This means that the shifted exponent is \(19\). The unshifted, actual value for the exponent is \(19-15=4\).

The mantissa is normalized. The bits that correspond to the mantissa are \(101101\). These \(6\) bits do not include the first bit \(1\). Every normalized mantissa in binary has the first bit \(1\) omitted in the storage. Thus, although \(101101\) is the stored value for the mantissa, the actual mantissa is \(\overline{1.101101}_2\). The mantissa corresponds to the following number in decimal system \begin{eqnarray*} \overline{1.101101}_2 &=&1+1\cdot 2^{-1}+0\cdot 2^{-2}+1\cdot 2^{-3} + 1 \cdot 2^{-4}+0\cdot 2^{-5}+1\cdot 2^{-6}. \end{eqnarray*} The last number is equal to \(1.703125\), but the expansion \(1+1\cdot 2^{-1}+0\cdot 2^{-2}+1\cdot 2^{-3} + 1 \cdot 2^{-4}+0\cdot 2^{-5}+1\cdot 2^{-6}\) is more convenient to work with. The required number is \begin{eqnarray*}-\left(1+1\cdot 2^{-1}+0\cdot 2^{-2}+1\cdot 2^{-3} + 1 \cdot 2^{-4}+0\cdot 2^{-5}+1\cdot 2^{-6}\right)\cdot 2^{4} &=&2^4+2^3+2+1+2^{-2}\\ &=& -\left( 16+8+2+1+0.25\right)=-27.25 \end{eqnarray*}

The answer is 158.

In the beginning of the main function the objects x and z are created using the default constructor. These operations result in \(4\) printings.

In each of the \(10\) iterations of the for loop the following happens: The argument x of the function is passed by reference and the copy constructor is not called. The object y is created using copy constructor applied to the object x. The copy constructor prints \(5\) letters. The copy assignment is applied to the object y with argument x. When the function reaches the return statement it first creates a temporary object using the move constructor with argument y. The move constructor prints \(2\) letters e. The local variable y is destroyed and its destructor prints \(2\) letters. The move assignment is called by the object z from the main program with the argument that is the temporary object. The move assignment prints \(1\) letters. The destructor is used for the temporary object. Since the argument x of the function is passed by reference the destructor is not called. Therefore in each iteration of the for loop there are \(15\) printings.

After the for loop the destructors are called for objects z and x. Each of the destructors causes a printing of \(2\) numbers.

We will use a recursive function to calculate the best possible value that can be stored in the backpack. The recursive function will return the pair of integers. The first integer in the pair will be the best value that can be stored. The second component will be the index of the last item that should be put in the backpack. One argument of the recursion will be the map knowledge that is passed by reference. The map will contain all the cases that were previously solved. This will make sure that recursive calls are not repeated. The complete code is given below.

#include<iostream>
#include<set>
#include<map>
struct MPair{
public:
  long f;
  long s;
  MPair();
  int operator<(const MPair& ) const;
};
MPair::MPair(){
  f=0;s=-1;
}
int MPair::operator<(const MPair& x) const{
  if(f<x.f){return 1;}
  if(f>x.f){return 0;}
  if(s<x.s){return 1;}
  return 0;
}
MPair bestValue(std::map<MPair,MPair>& knowledge, long* x, long* w, long n, long M){
  //keys are pairs (n,M)
  // values are pairs (bestValue, lastItem)
  MPair result, searchKey;
  if(n < 1){
    return result;
  }
  if(M < 1){
    return result;
  }
  searchKey.f=n; searchKey.s=M;
  std::map<MPair,MPair>::const_iterator it;
  it=knowledge.find(searchKey);
  if(it!=knowledge.end()){
    return it->second;
  }
  if(w[n-1]<=M){
    if(n>2){
      result=bestValue(knowledge,x,w,n-2,M-w[n-1]);
    }
    result.f += x[n-1];
    result.s = n-1;
  }
  MPair resAlternative=bestValue(knowledge,x,w,n-1,M);
  if(resAlternative.f > result.f){
    knowledge[searchKey]=resAlternative;
    return resAlternative;
  }
  knowledge[searchKey]=result;
  return result;
}
int main(){
  long n,M, *x, *w;
  std::cin>>n>>M;
  x=new long[n];w=new long[n];
  std::map<MPair,MPair> knowledge;
  for(long i=0;i<n;++i){
    std::cin>>x[i];
  }
  for(long i=0;i<n;++i){
    std::cin>>w[i];
  }
  MPair finalResult=bestValue(knowledge,x,w,n,M);
  std::cout<<"Best value is: "<<finalResult.f<<"\n";
  std::cout<<"Items to take: ";
  while(finalResult.s>-1){
    std::cout<<finalResult.s<<" "; 
    M-=w[finalResult.s];
    finalResult=bestValue(knowledge,x,w,finalResult.s-1,M);
  }
  std::cout<<"\n";
  delete[] x; delete[] w;
  return 0;
}