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**

**Prerequisites**

**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**

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.