CS141 Lab 2



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


For the labs of the second week:

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

    Solve it in two ways:
1. Recursively using the 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.
  • Can you obtain the asymptotic complexity of each algorithm? This may be continued in the third lab.
    TA: Keep track of which students completed the exercise. Encourage students who could not finish this to continue in the next lab session.

            Take a singly linked list e.g. a->b->c->d and reverse it to d->c->b->a, by
a. anyway you want (by possibly copying the list)
b. without using any additional memory (in place)

For part b, you may want to consider (i) a recursive method by making recurisve calls sequentially from left to right and (ii) a non-recursive method using the so called pointer-flipping technique.