#### about the problem sets

- Most of the problem set questions are routine exercises.
- Solutions to selected typical problem set problems are often
presented in the lectures.
- If you have difficulties, your TA or prof will be happy to give you hints.
- After the quizzes are over, the TAs will be happy
(in the seminar, time permitting)
to go over solutions which are of particular interest.

#### problem sets

- problem set #1:
postscript
pdf

loop invariant, insertion-sort, merge-sort,
[selection-sort, bubble-sort,]
asymptotic notations
- problem set #2:

recurrences, heaps
- problem set #3:

heap-sort, priority-queue, quick-sort, sorting lower bound
- problem set #4:

dynamic programming concepts,
matrix chain multiplication,
longest common subsequence,
disjoint-sets and union-find,
graph traversal: BFS and DFS
- problem set #5:

biconnected component, MST: Kruskal and Prim,
Dijkstra's SSSP algorithm,
Strassen's algorithm,
decision problems, P, NP

#### old tests

#### check your
marks
in this course