For the labs of the second week:
-
Review summations and how to deal with them as given in Levitin Ch 2.3 and
Appendix A.
Go over Ex. 1 on page 67 of Levitin. If there is sufficient interest, more
elaborate treatment of summations is given in Appendix A of CLRS Ch 2.3.
The TA could
go over Ex. A.1-1 and A.1-6 on p. 1062 of CLRS, and Ex. A-1(c) on p. 1069
(by splitting the summation).
-
Discuss the big-O, big-Omega, and Theta notations. Go over Ex. 1 and 2
in Levitin, pp. 59-60.
-
Discuss how to analyze the worst-case running time of
algorithms (pseudo-codes) using the Theta/big-O notations. Show how to
estimate the running time of (nested) for-loops using summations.
Here are some examples that can be used.
-
If time allows, discuss recursive algorithms and programming, and the
advantages. Use Towers-of-Hanoi as an example. Give the recurisve
algorithm (pseudo-code). Challenge the students to
write a non-recurisve algorithm for it.
-
An in-lab exercise: Calculate the n-th Fibonnaci number.
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.
-
Additional stuff for keen students:
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.