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.
- 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);
- 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
- 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)
- Use the fact in 2 to calculate the size of unsigned int and unsigned long long
- 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