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