## CS 401 Computer Algorithms

Autumn, 2018
Time and location: Tuesday Thursday 3:30-4:45pm, Burnham Hall, Room 308
Intructor: Anastasios Sidiropoulos, sidiropo@uic.edu, office hours: Tuesday 2:00pm-3:00pm, SEO 1240
TA: Mao Li, mli206@uic.edu, office hours: Thursday 11:00am-1:00pm, SEO 1326

### Overview

The goal of this course is to present fundamental techniques in the design and analysis of algorithms, including the greedy method, dynamic programming, and divide and conquer. These methods are presented in the context of various algorithmic problems, such as shortest paths, minimum spanning trees, and network flows. The course also discusses limitations in the design of algorithms for certain computationally intractable problems, using the language of NP-completeness.

### Textbook

Algorithm Design, by Jon Kleinberg and Eva Tardos.

### Evaluation

There will be one midterm, a final exam, and several homeworks. The final exam will be comprehensive. The homeworks will be posted on piazza. Each homework will be due before the beginning of a predetermined lecture. No late assignments will be accepted. The final score is computed using the formula: 0.35 × homeworks + 0.3 × midterm + 0.35 × final. The final letter gade will be curved. All the scores and grades will be posted on blackboard.

### Final exam

The final exam will take place on Friday 12/14/18 at 1:00-3:00pm in LC D2.

### Lectures

• Aug 28, 2018. Lecture 1: Introduction (Chapter 1). [Slides, Stable matching demo]
• Aug 30, 2018. Lecture 2: Analysis of algorithms (Chapter 1). [Slides]
• Sep 4, 2018. Lecture 3: Review of big-O notation (Chapters 2.1, 2.2, 2.3, 2.4).
• Sep 6, 2018. Lecture 4: Review of recurrence tree and Master theorem. [Slides]
• Sep 11, 2018. Lecture 5: Review of graphs (Chapter 3). [Slides]
• Sep 13, 2018. Lecture 6: Greedy algorithms (Chapter 4.1). [Slides]
• Sep 18, 2018. Lecture 7: Greedy algorithms (Chapters 4.2, 4.3).
• Sep 20, 2018. Lecture 8: Greedy algorithms (Chapter 4.3).
• Sep 25, 2018. Lecture 9: Greedy algorithms: Minimum Spanning Tree (Chapter 4.4, 4.5). [Slides]
• Sep 27, 2018. Lecture 10: Divide and conquer (Chapter 5). [Slides]
• Oct 2, 2018. Lecture 11: Dynamic programming (Chapters 6.1, 6.2, 6.4, 6.6). [Slides]
• Oct 4, 2018. Lecture 12: Dynamic programming.
• Oct 9, 2018. Lecture 13: Dynamic programming.
• Oct 11, 2018. Lecture 14: Midterm review.
• Oct 16, 2018. Midterm.
• Oct 18, 2018. Lecture 15: Network flows (Chapter 7.1, 7.2). [Slides]
• Oct 23, 2018. Lecture 16: Network flows.
• Oct 25, 2018. Lecture 17: Network flow applications (Chapter 7.5, 7.6). [Slides]
• Oct 30, 2018. Lecture 18: Network flow applications (Chapter 7.7, 7.8).
• Nov 1, 2018. Lecture 19: Network flow applications (Chapter 7.7, 7.8).
• Nov 6, 2018. Lecture 20: Intractability (Chapter 8.1, 8,2). [Slides]
• Nov 8, 2018. Lecture 21: Intractability.
• Nov 13, 2018. Lecture 22: NP-completeness (Chapter 8.3, 8.4). [Slides]
• Nov 15, 2018. Lecture 23: NP-completeness.
• Nov 20, 2018. Lecture 24: Polynomial-time reductions (Chapter 8.5). [Slides]
• Nov 27, 2018. Lecture 25: Coping with NP-completeness: Approximation algorithms.
• Nov 29, 2018. Lecture 26: Coping with NP-completeness: Fixed-parameter algorithms.
• Dec 4, 2018. Lecture 27: Randomized algorithms.
• Dec 6, 2018. Lecture 28: Final review.