CS141 Lab 3

Class Webpage:  http://www.cs.ucr.edu/~jiang/141-homepage.html

For the labs of the third week:

• Go over the  first programming assignment and the test files test 1, test 2, test 3, test 4, and test 5. (Note that the data for tests 4 and 5 are released to the students only after the assignment is graded.) Also go over the sample output for tests 1 to 3. Here are results are for all tests. Mention a sample C++ code for reading an input file will be availble next week for those who need it.

• Address questions concerning the  first homework.

• Review recurrence relations, i.e. how to solve them using the forward/backforward substitution (also called iteration) method and the Master Theorem (Levitin Ch 2.4, Ch 4, and Appendix B), and how to use them to analyze time complexity. Use Ex. 4-1(a,b) on page 85 of CLRS as examples. Refer to the  tutorial on recurrence relations and my old lecture notes based on CLRS.

• Give a recursive algorithm for sequential search in a list (although it's not natural). Derive the recurrence relation for its time complexity, and solve it to obtain O(n).

• Continue the in-lab exercise: Calculate the n-th Fibonnaci number; But this time, emphasize the time complexity analysis.

printFib(n): Given a number n print the nth Fibonacci number

    Do it in two ways:

1. Recursively using recurrence: fib(n) = fib(n-1) + fib(n-2)

2. Iteratively:

    printFib(n)
        x = 0
        y = 1
        for i = 2 to n
            z = x + y
            x = y
            y = z
        Print z

• Implement both algorithms and count time difference as a function of n.  Create a table and observe the trend.
  

• Obtain the asymptotic complexity of each algorithm as functions of n, using a recurrence relation for the recurisve one. For simplicity, approximate the recurrence relation with T(n) <= 2*T(n-1). Compare the complexity functions and correlate with the observed execution times.

TA: Keep track of which students completed the exercise.