Photo

Home

Publications

Selected talks

Teaching

Curriculum vitæ

School of Computer Science, Carleton University
Design and Analysis of Algorithms I
COMP/MATH 3804, Fall 2015

Classroom: 306 Southam Hall
Class times: Wednesdays and Fridays, 11:35 to 12:55

Instructor: Giovanni Viglietta
Contact:
Office: 5331 Herzberg Building
Office hours: Wednesdays and Fridays, 14:00 to 16:00

Teaching assistant: Arash Nouri
Contact:
Office: 1175 Herzberg Building
Office hours: Mondays, 15:30 to 17:30

Course description
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.

Prerequisites
Either COMP 2402 or SYSC 2100, and either COMP 2804 or both of MATH 2007 and MATH 2108 or equivalents.

Textbooks
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).

Lectures
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's cypher, 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.

Assignments
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

Evaluation
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.