Giovanni Viglietta

An introduction to the design and analysis of algorithms. Topics include: arithmetic algorithms, divide-and-conquer algorithms, dynamic programming, linear programming, greedy algorithms, graph algorithms, NP-hardness.
Either COMP 2402 or SYSC 2100, and either COMP 2804 or both of MATH 2007 and MATH 2108 or equivalents.
• Algorithms, by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, published by McGrawHill (2007).
• Introduction to Algorithms, by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, published by MIT Press (2009).

Date	Content	Book chapters
September 02	Course outline, preliminary questionnaire. Introduction, time and space complexity, big-O notation.	0
September 09	Correction of Assignment 0. Basic arithmetic operations.	1.1
September 11	Modular arithmetic operations, Euclid's algorithm. Primality testing, generation of random primes.	1.2, 1.3
September 16	Cryptography: Caesar cipher, one-time pad, RSA. Universal hashing.	1.4, 1.5
September 18	Divide-and-conquer algorithms: integer and matrix multiplication, finding medians, selection. Master theorem.	2.1, 2.2, 2.4, 2.5
September 23	Correction of Assignment 1. Mergesort, binary search.	2.3
September 25	Fast Fourier transform, polynomial multiplication. Representation of graphs.	2.6, 3.1
September 30	Graph algorithms: depth-first search, connected components in undirected graphs, linearizations of directed acyclic graphs.	3.2, 3.3
October 02	Correction of Assignment 2. Strongly connected components in directed graphs.	3.4
October 07	Breadth-first search, Dijkstra's algorithm, Bellman-Ford algorithm.	4
October 09	Greedy algorithms: Kruskal's algorithm, Huffman encoding, Horn formulas.	5.1, 5.2, 5.3
October 14	Correction of Assignment 3. Approximation of Set Cover.	5.4
October 16	Dynamic programming: longest increasing subsequence, edit distance, independent sets in trees.	6.1, 6.2, 6.3, 6.7
October 21	Knapsack, chain matrix multiplication, advanced shortest paths.	6.4, 6.5, 6.6
October 23	Correction of Assignment 4.
November 04	Midterm exam simulation.
November 06	Correction of the midterm exam simulation.
November 11	Linear programming: introduction. Review and exercises.	7.1
November 13	Midterm exam.
November 18	Linear Programming: duality, simplex algorithm.	7.4, 7.6
November 20	NP-completeness: definitions, Cook-Levin theorem. Circuit SAT, 3-SAT, ILP, Independent Set, Vertex Cover, Clique.	8
November 25	Correction of Assignment 5. Coping with NP-hardness: exhaustive search, local search heuristics.	9.1, 9.3
November 27	Approximation algorithms: Vertex Cover, metric TSP. Inapproximability of general TSP.	9.2.1, 9.2.3
December 02	Correction of Assignment 6.
December 04	Review and exercises.
December 18	Final exam.

Due date	Exercises
September 09	All exercises at the end of Chapter 0, including the part after exercise 0.4(e).
September 23	1.4, 1.13, 1.19, 1.29, 1.33, 1.34, 1.35, 1.42, 1.45(b), 1.46.
October 02	2.23, 2.27, 2.31, 2.32, 2.33.
October 14	3.18, 3.22, 3.25, 3.28, 4.4, 4.11.
October 23	5.16, 5.20 (5.21 if you have the paper book), 5.34, 6.8, 6.21.
November 25	Assignment 5
December 02	Assignment 6

Students will be evaluated according to the following table.

Item	Weight	Date
Assignment 0	0%	September 09, before class
Assignment 1	5%	September 23, before class
Assignment 2	5%	October 02, before class
Assignment 3	5%	October 14, before class
Assignment 4	5%	October 23, before class
Midterm exam	20%	November 13, during class
Assignment 5	5%	November 25, before class
Assignment 6	5%	December 02, before class
Final exam	50%	December 18, 14:00 to 17:00
Bonus: class participation	10%	During class

You must hand assignments to me in class prior to the lecture, or e-mail them to me before the lecture starts, or submit them through cuLearn. Late assignments will not be accepted.
For bonus points, you should participate in class, either during the lectures, or by presenting solutions to problems during the exercise sessions.