Lab 2 Fall 2014

This lab is to review parts of Chapter 1 of the text book. Please go to your lab, do the problems to get your full credit for the lab.
  1. Implement modexp algorithm in C++. Do exercise 1.25
  2. Optional Do exercise 1.11
  3. Do exercise 1.12 using your program.
  4. Using pencil and paper find x,y and d such that 55*x+34*y=1 using Extended Euclidean Algorithm (Here a is 55 and b is 34 - 55, 34 are Fibonacci Numbers) - Try both cases d = 1*a - 0*b and d = 1*a + 0*b
  5. Implement primality testing algorithm in C++. Generate all prime numbers between 3 and 1000.
  6. (Please do not believe all the code you found in the Web) Please see a C langauge implementation of Karp-Rabin String matching here. This code has many problems. In particular do you see a problem with this code segment. 
     /* Main comparison loop */
    for (i = 0; i < num_iterations; i) {
        if (pattern_hash == text_hash && 
            !strncmp(pattern, &(text[i]), pattern_len)) return i;
}
    Your instructor created working version of this C code     here. Your job is to get a C++ version running. Test with three text strings and three pattern strings.