CS 401 Computer Algorithms
Fall, 2020
Time and location:
Tuesday Thursday 3:304:45pm, Blackboard Collaborate Ultra
Intructor:
Anastasios Sidiropoulos,
sidiropo@uic.edu,
office hours: Thursday 4:45pm5:45pm, Blackboard Collaborate Ultra
TA:
Danyal Saeed,
dsaeed3@uic.edu,
office hours: Wednesday 2:004:00pm.
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 NPcompleteness.
Textbook
Algorithm Design, by Jon Kleinberg and Eva Tardos.
Evaluation
There will be one midterm, a final exam, several homeworks, and several programming assignments.
The final exam will be comprehensive.
All lectures and office hours will take place over Blackboard Collaborate Ultra.
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.25 × homeworks + 0.25 × programming assigmnents + 0.25 × midterm + 0.25 × final.
The final letter gade will be curved.
All the scores and grades will be posted on Blackboard.
Final exam
TBA
Lectures

Aug 25, 2020. Lecture 1: Introduction (Chapter 1).

Aug 27, 2020. Lecture 2: Greedy algorithms (Chapter 4.1). Asymptotic analysis.

Sep 1, 2020. Lecture 3: Greedy algorithms (Chapter 4.2).

Sep 3, 2020. Lecture 4: Shortest paths (Chapter 4.4).

Sep 8, 2020. Lecture 5: Shorterst paths (Chapter 4).

Sep 10, 2020. Lecture 6: Shorterst paths (Chapter 4).

Sep 15, 2020. Lecture 7: Minimum Spanning Tree (Chapter 4).

Sep 17, 2020. Lecture 8: Minimum Spanning Tree (Chapter 4).

Sep 22, 2020. Lecture 9: Dynamic Programming (Chapter 6).

Sep 24, 2020. Lecture 10: Dynamic Programming (Chapter 6).

Sep 29, 2020. Lecture 11: Dynamic Programming (Chapter 6).

Oct 1, 2020. Lecture 12: Divide and Conquer (Chapter 5).

Oct 6, 2020. Lecture 13: Divide and Conquer (Chapter 5).

Oct 8, 2020. Lecture 14: Network Flows (Chapter 7).

Oct 13, 2020. Lecture 15: Network Flows (Chapter 7).

Oct 15, 2020. Lecture 16: Network Flows (Chapter 7).

Oct 20, 2020. Lecture 17: Network Flows (Chapter 7).

Oct 22, 2020. Lecture 18: Intractability (Chapter 8).

Oct 27, 2020. Lecture 19: Intractability (Chapter 8).

Oct 29, 2020. Lecture 20: Intractability (Chapter 8).

Nov 5, 2020. Lecture 21: Approximation Algorithms (Chapter 11).

Nov 10, 2020. Lecture 22: Approximation Algorithms (Chapter 11).

Nov 12, 2020. Lecture 23: Approximation Algorithms (Chapter 11).

Nov 17, 2020. Lecture 24: Randomized Algorithms (Chapter 13).