## CS 401 Computer Algorithms

Spring, 2020
Time and location: Monday Wednesday Friday 1:00-1:50pm, ARC 136
Intructor: Anastasios Sidiropoulos, sidiropo@uic.edu, office hours: Wednesday 11:30am-12:30pm, location SEO 1240
TA: Mohammad Arvan, marvan3@uic.edu, office hours: Tuesday 9:30-11:30am, location Thomas Beckham Hall 175

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

TBA

### Lectures

• Jan 13, 2020. Lecture 1: Introduction (Chapter 1). [Slides, Stable matching demo]
• Jan 15, 2020. Lecture 2: Analysis of algorithms (Chapter 1). [Slides]
• Jan 17, 2022. Lecture 3: Analysis of algorithms (cont.).
• Jan 22, 2020. Lecture 4: Review of big-O notation (Chapters 2.1, 2.2, 2.3, 2.4).
• Jan 24, 2020. Lecture 5: Review of recurrence tree and Master theorem. [Slides]
• Jan 27, 2020. Lecture 6: Review of graphs (Chapter 3). [Slides]
• Jan 29, 2020. Lecture 7: Review of graphs (cont.).
• Jan 31, 2020. Lecture 8: Greedy algorithms (Chapter 4.1). [Slides]
• Feb 3, 2020. Lecture 9: Greedy algorithms (Chapters 4.2, 4.3).
• Feb 5, 2020. Lecture 10: Greedy algorithms (Chapter 4.3).
• Feb 7, 2020. Lecture 11: Greedy algorithms: Minimum Spanning Tree (Chapter 4.4, 4.5). [Slides]
• Feb 10, 2020. Lecture 12: Divide and conquer (Chapter 5). [Slides]
• Feb 12, 2020. Lecture 13: Divide and conquer (cont.).
• Feb 14, 2020. Lecture 14: Dynamic programming (Chapters 6.1, 6.2, 6.4, 6.6). [Slides]
• Feb 17, 2020. Lecture 17: Dynamic programming.
• Feb 19, 2020. Lecture 18: Dynamic programming.
• Feb 21, 2020. Lecture 19: Dynamic programming.
• Feb 24, 2020. Lecture 20: Network flows (Chapter 7.1, 7.2). [Slides]
• Feb 26, 2020. Lecture 21: Network flows.
• Feb 28, 2020. Lecture 22: Network flows.
• Mar 2, 2020. Lecture 23: Network flow applications (Chapter 7.5, 7.6). [Slides]
• Mar 4, 2020. Lecture 24: Network flow applications (Chapter 7.7, 7.8).
• Mar 6, 2020. Lecture 25: Network flow applications.
• Mar 9, 2020. Lecture 26: Network flow applications.
• Mar 11, 2020. Lecture 27: Midterm review.
• Mar 13, 2020. Midterm.
• Mar 16, 2020. Lecture 28: Network flow applications.
• Mar 30, 2020. Lecture 29: Network flow applications.
• Apr 1, 2020. Lecture 30: Intractability (Chapter 8.1, 8,2). [Slides]
• Apr 3, 2020. Lecture 31: Intractability.
• Apr 6, 2020. Lecture 32: Intractability.