**Text: ***Algorithm Design, *J.
Kleinberg and E. Tardos,* Pearson 2006.*

Discussion
group
to
be
set
up
on * WebCT *

Jan 9 : Introduction. The stable marriage problem. Read: Section 1.1 and this fun article. demo slides

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: Sections 2.1-2.4 slides

Exercises: P.67 Ex. 2,3

Jan 16, 18 Review of graph theory: undirected and directed graphs.Breadth first search and applications. Testing bipartiteness, connectivity, acyclic graphs and 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 should include a proof of correctness using one of the three techniques discussed.

Jan 25: Dijkstra's shortest path 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 handed back at the tutorials:

Tutorial 1A: 2pm Tues January 31, TR 3060 Wanru Lin

Tutorial 1B: 4pm Wed February 1, TR 3060 Bentley Oakes

Jan 30. Minimum spanning trees. Prim and Kruskal's algorithms. Read 4.5. slides animation animation

Exercise: P. 200 21,22

Feb 1: Solution to the bandwidth problem: P. 198 Ex. 19 (password: birds). Divide and conquer. Review of mergesort.Counting inversions.

Read: Sections 5.1-3. slides (up to slide 20)

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 solved by divide and conquer: closest pair, integer multiplication, matrix multiplication slides (Slides 21-47)

No exercise, but please read carefully the text Sections 5.4, 5.5 and review the slides.

Feb 8: Introduction to dynamic programming: weighted interval selection. Dijkstra fails with negative edge weights.

Read Sections 6.1,6.2 slides 1-16

No exercise.

Feb 13: Bellman-Ford shortest path algorithm. Negative weight cycles. Read Sections 6.8, 6.9. slides

Exercise: Ch 6, P. 314, Ex. 3.

Feb 15: We solved Ch 6 Ex. 17. solution. Segmented least squares. 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 vs polynomial time. RNA secondary structure. Sequence alignment. Read: Sections 6.5,6.6 slides 29-46

Exercises: (a) Compute the OPT(i,j) values (similar to those shown in Figure 6.16, p. 277) for the RNA sequence CACCGGUAGU

(b) Compute the OPT(i,j) values (similar to those shown in Figure 6.18, p. 284) for aligning the words "clean" and "lance". Show the shortest paths as a tree as in Figure 6.18.

Feb 29: Can computers think (part I). Computer game playing programs, min-max trees, alpha-beta search, Nim, computer chess.

Read: Luc Devroye's notes

A documentary on the Kasparov-Deep Blue match is Endgame. A fascinating movie giving Kasparov's viewpoint is Game Over.

Mar 5: Review session. Please send suggestions in advance to avis@cs.mcgill.ca.

Mar 7: Midterm. All material and exercises above up to and including Feb 15.

Mar 12: Introduction to Network flows and Min Cut. Ford-Fulkerson algorithm. Read: pp. 337-341 first few slides

Exercises: Ch 7, Ex. 1,2, p 415

Mar 14: Ford-Fulkerson algorithm and optimality conditions using min-cut. Read: pp 341-350. Up to slide 25 of slides and demo

Exercises: Ch 7, Ex 3,4. For Ex.3 also try starting with a zero flow and run the Ford-Fulkerson 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, 15.

Mar 21: Circulations and lower bounds. Applications to survey design and census rounding. Read sections 7.7,7.8 and slides 22-32, 58-62.

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

slides (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 of Delta=4,2,1. For each value of Delta show the maximum flow/min cut at the end of the outer loop of the algorithm on pp. 353,354 (or slide 31)

Mar 28: Data structures for graph traversal: stack for DFS, queue for BFS, priority queue for Prim's algorithm. Introduction to Union-Find. Read 17.3,4,5 of Jeff Erickson's notes. He has lots of other useful materials here.

Exercise: Do Ex. 6 of the notes. Hint: try DFS on some small examples of directed graphs and see how to modify it.

Apr 2: Tree-structures for union find and path compression. slides Read: Sections 16.1-3 of Jeff Erickson's notes. We also looked at problem 6.8, a space invaders variant. problem. solution

Exercise: Do exercise 1 of Jeff Erickson's notes.

Final exam covers all material above (except Feb 29 and if otherwise noted)

Apr 4: Can computers think (part II). The Turing test and Loebner prize. Read: Turing's historic 1950 paper. Try 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 here. I forgot which were Elbot's answers but will try to reconstruct them and post them later.

Tutorial 4A: 4pm Wed April 4, TR 3060 Rami Aladdin

Tutorial 4B: 2pm Thurs April 5, TR 3060 Raphael Mannadiar

2012.4.5 Assignment 5: Exercises from lectures Mar 26, 28, Apr 2,4 collected on April 11 in class. (April 9 is a holiday)

A tutorial on 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 will be available at this time.

Apr 30: Final exam at 2 pm. Good luck! The announcements page has a Final Exam FAQ.