Lab 1 Fall 2014

This lab is to review Chapters 0 and 1 of DG and bitwise operations. Please go to your lab, do the problems to get your full credit for the lab.
  1. Arrange the following functions in increasing order of their growth rate.
    (3/2) n;n; (n/2)!; 104 ; 7; 4 n; 4 sqrt(log(n)); n n; n log(n) ; 3 n; n 4/5 ; 3 3 n ; n 4 ; log(log(n)); 0.6 n log(n+5);
  2. Convince yourself x & (x-1) is = 0 iff x is a power of 2 and & is a bitwise "AND" operation. Here is a program that tests it ; Bitwise operations are important for doing computations fast. Wikipedia article on bitwise operators including & (AND) operator
  3. Use the above fact to write a program to calculate the number of one bits in an integer. (another usefulness of this function is to calculate the Hamming distance between two bit vectors) - What is the running time of your algorithm (Big Oh notation will suffice - You may want to calculate the number of times the inner loop is executed)
  4. Use the fact in 2 to calculate the size of unsigned int and unsigned long long
  5. Implement the divide algorithm given in DG (page ) in C++ and test it for a few input values. Example of a multiply program from DG