Mini Hacks

  • Complete all uncompleted code segments
  • Answer all questions in the code
  • complete the activities in the lesson blogs
  • will be scaled to 0.2 depending on the completion of your code

Main Hack

  • Use topics from 3 out of 4 of the Units
  • It has to be a 2 part style question, A and B
  • Will Be graded out of 4 points
  • Write a scoring sheet for what you have done out six points
  • Your real grade for the assigment will be based of two things
  • How creative, unique, cool your question and code is
  • Did you acheive 4/4 points for your code
  • That will be scaled to 0.8 of 1 for all your hacks

Answer to Hacks (1999 #3)

3.a

Write a new BigInt member function Div2, as started below. Div2 should change the value of the BigInt to be the original value divided by 2 (integer division). Assume the BigInt is greater than or equal to 0. One algorithm for implementing Div2 is:

1. Initialize a variable carryDown to 0.
2. For each digit, d, starting with the most significant digit,
    2.1 replace that digit with (d/2) + carryDown
    2.2 let carryDown be (d%2) * 5
3. Normalize the result

Complete member functionDiv2 below

void BigInt::Div2()
// precondition: BigInt >= 0

void BigInt::Div2(){
    int carrDown = 0
    int d;

    for(int i = myNumDigits - 1, i >= 0, i--){
        d = GetDigit(i);
        changeDigit(i, (d/2) = carryDown);
        carryDown = (d % 2) * 5;
    }
    Normalize();
}

3.b

1. Initialize low to 0 and high to dividend.
2. For each iteration, 
    2.1 compute mid = (low + high + 1)
    2.2 divide mid by 2
    2.3 if mid * divisor is larger than dividend (mid is too large to be the quotient) then set high equal to mid - 1 else set low equal to mid.
3. when low == high the search terminates, and you should return low.

BigInt operator/ (const BigInt & dividend, const BigInt & divisor){
    BigInt low(0), high(dividend), mid;
    while(low != high)
    {
        mid = (low + high + 1);
        mid.Div2();
        if (mid * divisor > dividend){
            high = mid - 1;
        }
        else{
            low = mid;
        }
    }
    return low;
}