CS 401 Computer Algorithms
Autumn, 2017
Intructor:
Anastasios Sidiropoulos,
sidiropo@uic.edu,
office hours: Tue 1:00pm2:00pm, SEO 1240
Time and location:
Mon Wed 3:004:15pm, SES 238
TAs:
The following TAs are joint for all CS sections of the course.
You are welcome to see any of them:
Ivan Brugere,
ibruge2@uic.edu,
office hours: Fri 3:00pm5:00pm, ERF 3028
Chainarong Amornbunchornvej,
camorn2@uic.edu,
office hours: Thu 10:30am12:30pm, ERF 3028
Vahid Noroozi,
vnoroo2@uic.edu,
office hours: Tue 11:00am1:00pm, SEO 1218
Wei Xing,
wxing3@uic.edu,
office hours: Mon 11:00am1:00pm, SEO 1218
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, 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.
Lectures
Week 1

Aug 28, 2017. Lecture 1: Introduction (Chapter 1). [Slides, Stable matching demo]

Aug 30, 2017. Lecture 2: Analysis of algorithms (Chapter 1).
Week 2

Sep 4, 2017. Labor Day holiday.

Sep 6, 2017. Lecture 3: Review of bigO notation (Chapter 2.1, 2.2, 2.3, 2.4). [Slides]
Week 3

Sep 11, 2017. Lecture 4: Review of recurrence tree and Master theorem. [Slides]

Sep 13, 2017. Lecture 5: Review of graphs (Chapter 3). [Slides]
Week 4

Sep 18, 2017. Lecture 6: Greedy algorithms (Chapter 4.1). [Slides]

Sep 20, 2017. Lecture 7: Greedy algorithms (Chapter 4.2, 4.3).
Week 5

Sep 25, 2017. Lecture 8: Greedy algorithms (Chapter 4.3).

Sep 27, 2017. Lecture 9: Greedy algorithms: Minimum Spanning Tree (Chapter 4.4, 4.5). [Slides]
Week 6

Oct 2, 2017. Lecture 10: Greedy algorithms: Minimum Spanning Tree (Chapter 4.5).

Oct 4, 2017. Lecture 11: Divide and conquer (Chapter 5). [Slides]
Week 7

Oct 9, 2017. Lecture 12: Divide and conquer (Chapter 5).

Oct 11, 2017. Lecture 13: Divide and conquer (Chapter 5).
Week 8

Oct 16, 2017. Lecture 14: Dynamic programming (Chapter 6.1, 6.2). [Slides]

Oct 18, 2017. Lecture 15: Dynamic programming (Chapter 6.1, 6.2).
Week 9

Oct 23, 2017. Midterm in class.

Oct 25, 2017. Lecture 16: Dynamic programming (Chapter 6.6).
Week 10

Oct 30, 2017. Lecture 17: Dynamic programming (Chapter 6.4).

Nov 1, 2017. Lecture 18: Dynamic programming: BellmanFord (Chapter 6.8). [Slides]
Week 11

Nov 6, 2017. Lecture 19: Network flow (Chapter 7.1, 7.2). [Slides]

Nov 8, 2017. Lecture 20: Network flow applications (Chapter 7.5, 7.6). [Slides]
Week 12

Nov 13, 2017. Lecture 21: Network flow applications (Chapter 7.7, 7.8).

Nov 15, 2017. Lecture 22: Network flow applications (Chapter 7.7, 7.8).
Week 13

Nov 20, 2017. Lecture 23: Intractability (Chapter 8.1). [Slides]

Nov 22, 2017. Lecture 24: Intractability (Chapter 8.2).
Week 14

Nov 27, 2017. Lecture 25: NPcompleteness (Chapter 8.3, 8.4). [Slides]

Nov 29, 2017. Lecture 26: Polynomialtime reductions (Chapter 8.5). [Slides]
Week 15

Dec 4, 2017. Lecture 27: NPhard problems (Chapter 8.5).

Dec 6, 2017. Lecture 28: TBA.