CS 401 Computer Algorithms

Autumn, 2017
Intructor: Anastasios Sidiropoulos, sidiropo@uic.edu, office hours: Tue 1:00pm-2:00pm, SEO 1240
Time and location: Mon Wed 3:00-4: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:00pm-5:00pm, ERF 3028
Chainarong Amornbunchornvej, camorn2@uic.edu, office hours: Thu 10:30am-12:30pm, ERF 3028
Vahid Noroozi, vnoroo2@uic.edu, office hours: Tue 11:00am-1:00pm, SEO 1218
Wei Xing, wxing3@uic.edu, office hours: Mon 11:00am-1: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 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.

Lectures

Week 1

Week 2

Week 3

Week 4

Week 5

Week 6

Week 7

Week 8

Week 9

Week 10

Week 11

Week 12

Week 13

Week 14

Week 15