Lecture Summaries for COMP
course home page
Text: Algorithm Design, J.
Kleinberg and E. Tardos, Pearson 2006.
Jan 9 : Introduction.
stable marriage problem. Read: Section 1.1 and this fun article.
Exercises: P. 22, Ex. 2,
P.23 Ex. 4
Jan 11: Review of basics of
algorithm analysis. All of this was covered in COMP250. Read:
Exercises: P.67 Ex. 2,3
Jan 16, 18 Review of
theory: undirected and directed graphs.Breadth first search and
applications. Testing bipartiteness, connectivity, acyclic graphs
topological ordering. Read: Chapter 3. slides
Exercises: P. 107 Ex
4, P. 110 Ex 10. For each problem give an non-trivial example
that illustrates your algorithm
Assignment 1: All exercises from Jan
9,11,16,18 above, collected on January 23 in class.
Jan 23: Greedy algorithms- I. Three scheduling problems solvable
optimally by a greedy algorithm. Three types of proof techniques: stay ahead, exchange, structure.
Read: Sections 4.1, 4.2 slides (first 24 slides)
Exercises: P. 189 Ex. 3, P. 190 Ex 5. In both cases you
include a proof of correctness using one of the three techniques
Jan 25: Dijkstra's shortest
algorithm. Efficient implementation by heap. Read 4.4 and review
pp.59-65 slides 34-40, demo heapsort
Exercise: P.198 Ex. 19.
Graded assignments will be
back at the tutorials:
Tutorial 1A: 2pm Tues January 31, TR 3060
Tutorial 1B: 4pm Wed February 1, TR 3060
Jan 30. Minimum spanning
Prim and Kruskal's algorithms. Read 4.5. slides
Exercise: P. 200 21,22
Feb 1: Solution
to the bandwidth problem: P. 198 Ex. 19 (password: birds). Divide
conquer. Review of mergesort.Counting inversions.
Read: Sections 5.1-3. slides
Exercise: P. 192, Ex.
9. P. 246, Ex 2.
Assignment 2: All exercises from Jan
23, 25, 30 and Feb 1 collected on Feb 13 in class.
Feb 6: Three more problems
by divide and conquer: closest pair, integer multiplication, matrix
No exercise, but please read carefully the text Sections 5.4, 5.5
review the slides.
Feb 8: Introduction to dynamic
programming: weighted interval selection. Dijkstra fails with
Read Sections 6.1,6.2 slides
Feb 13: Bellman-Ford shortest
path algorithm. Negative weight cycles. Read Sections 6.8, 6.9. slides
Exercise: Ch 6, P. 314,
Feb 15: We solved Ch 6 Ex. 17.
solution. Segmented least
Knapsack AKA sushi
problem. Read: Sections 6.3,6.4, slides
Tutorial 2A: 4pm Wed February 15, TR
3060 Wanru Lin
Tutorial 2B: 2pm Thurs February
16, TR 3060 Yam Chettri
Feb 27: Pseudopolynomial time
polynomial time. RNA secondary structure. Sequence alignment. Read:
Sections 6.5,6.6 slides
Exercises: (a) Compute
OPT(i,j) values (similar to those shown in Figure 6.16, p. 277) for
RNA sequence CACCGGUAGU
(b) Compute the OPT(i,j) values (similar to those shown in Figure
p. 284) for aligning the words "clean" and "lance". Show the
paths as a tree as in Figure 6.18.
Feb 29: Can computers think
I). Computer game playing programs, min-max trees, alpha-beta
Read: Luc Devroye's
A documentary on the Kasparov-Deep Blue match is Endgame. A
fascinating movie giving Kasparov's viewpoint is Game
Mar 7: Midterm. All material and
exercises above up to and including Feb 15.
Mar 12: Introduction to
flows and Min Cut. Ford-Fulkerson algorithm. Read: pp.
337-341 first few slides
Exercises: Ch 7, Ex.
Mar 14: Ford-Fulkerson
and optimality conditions using min-cut. Read: pp 341-350. Up to
25 of slides
Exercises: Ch 7, Ex 3,4.
For Ex.3 also try starting with a zero flow and run the
algorithm to optimality and find the min cut.
Mar 19: Applications to
bipartite matching and network connectivity. Read sections
7.5,7.6 and first 21 slides
Exercises: Ch 7, Ex 14,
Mar 21: Circulations and lower
bounds. Applications to survey design and census rounding. Read
sections 7.7,7.8 and slides
Exercise: Ch 7, Ex 39
Mar 26: The complexity of the
Ford-Fulkerson method. Exponential time example. Polynomial time
algorithm via scaling. Read: Section 7.3
(26-34). (Scaling for the approximate knapsack problem is in Section
11.8 but not covered on the final exam)
Exercise: Consider the
network in Fig. 7.27, P. 416 and reset all flow values to zero. Now
solve the max flow problem using the scaling approach using values
Delta=4,2,1. For each value of Delta show the maximum flow/min cut
the end of the outer loop of the algorithm on pp.
(or slide 31)
Mar 28: Data structures for
traversal: stack for DFS, queue for BFS, priority queue for Prim's
algorithm. Introduction to Union-Find. Read 17.3,4,5 of Jeff
Exercise: Do Ex. 6 of
graphs and see how to
Apr 2: Tree-structures for
find and path compression. slides
invaders variant. problem.
Exercise: Do exercise 1
Jeff Erickson's notes.
covers all material above (except Feb 29 and if otherwise noted)
Apr 4: Can computers think
Turing test and Loebner
prize. Read: Turing's historic 1950 paper.
the Turing test yourself with the 2008 winner Elbot . Elbot seemed to be pretty
lazy today, a transcript of the more interesting Tohoku 2010 test is
which were Elbot's answers but will try to reconstruct
them and post them later.
4pm Wed April 4, TR
Tutorial 4B: 2pm Thurs April 5,
2012.4.5 Assignment 5: Exercises from
Mar 26, 28, Apr 2,4 collected on April
11 in class.
9 is a holiday)
this assignment will be given by Rami and Raphael, in
class, April 16.
Apr 11: Mark Wilde's guest
lecture on quantum computation
Apr 16: In class tutorial on
Assignment 5. Any written
material (midterms, assignments) that you did not pick up yet have
be available at this time.
Apr 30: Final exam at 2 pm.
luck! The announcements page
has a Final Exam FAQ.