CS473 Fundamental Algorithms

Fall 2014

UNIVERSITY OF ILLINOIS, URBANA - CHAMPAIGN

META


Subject

This course teaches techniques for the design and analysis of efficient algorithms. Some of the topics covered are: sorting; trees; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; computational-complexity.

Instructor

Alexandra Kolla (akolla [at] illinois [dot] edu) 3222 SC [AK]

Teaching Assistants

Farzaneh Khajouei (khajoue2 [at] illinois [dot] edu) [FK]
Konstantinos Koiliaris (koiliar2 [at] illinois [dot] edu) [KK]
Anirbit Mukherjee (amukher4 [at] illinois [dot] edu) [AM]
Yipu Wang (ywang298 [at] illinois [dot] edu) [YW]

Resources

Moodle - Piazza - 473.sty - 473extra.sty

Navigation

Textbook - Schedule - Homework - Policies

TIMES


Lectures Discussion Sessions Office Hours
1404 SC T 11:00 - 12:15 1214 SC T 16:00 - 16:50: [FK] 3222 SC [AK]: W 14:00
T 17:00 - 17:50: [YW] Theory Lounge (3rd fl. SC) [FK]: F 11:00
R 11:00 - 12:15 W 14:00 - 14:50: [KK] [KK]: M 14:00
W 15:00 - 15:50: [KK] [AM]: R 16:00
W 17:00 - 17:50: [AM] [YW]: M 13:00

SCHEDULE


# Date Lecture Slides Lecture Videos Reading Material
1 T August 26 L1: Class Overview, Basic Graph Theory Recording L1 Dasgupta et al Book Chapter 0, section 1.1 and 1.2
2 R August 28 L2: DFS, Strongly Connected Components, DAGs Recording L2 Dasgupta et al Book Chapter 3
3 T September 2 L3: BFS, Bipartite Graphs, Shortest Paths Recording L3 Dasgupta et al Book Chapter 4, sections 4.1-4.5
4 R September 4 L4: Shortest Paths with Negative Weights, Bellman-Ford, Shortest Paths in DAGs - Dasgupta et al Book Chapter 4, sections 4.4-4.7
5 T September 9 L5: Shortest Paths with Negative Weights, Bellman-Ford, Shortest Paths in DAGs, continued (see previous slides). Recording L5
6 R September 11 L6: Reductions, Recursion, and Divide and Conquer - Dasgupta et al Book Chapter 2, Sections 2.1 - 2.3
7 T September 16 L7: Recurrences, Closest Pair, and Selection Recording L7 Dasgupta et al Book Chapter 2
8 R September 18 L8: Binary Search, Introduction to Dynamic Programming Recording L8 Dasgupta et al Book Chapter 6
9 T September 23 L9: Longest Increasing Subsequence, Weighted Interval Scheduling Recording L9 Dasgupta et al Book Chapter 6
- R September 25
Midterm #1
10 T September 30 L10: Maximum Weight Independent Set on Trees, DAGs and Dynamic Programming, Edit Distance Recording 10 Dasgupta et al Book Chapter 6
11 R October 2 L11: All-Pairs Shortest Path, Knapsack, TSP Recording 11 Dasgupta et al Book Chapter 6
12 T October 7 L12: Greedy Algorithms, Interval Scheduling, Interval Partitioning, Minimizing Lateness Recording 12 Dasgupta et al Book Chapter 5
13 R October 9 L13: Greedy Algorithms, Minimum Spanning Tree Recording 13 Dasgupta et al Book Chapter 5
14 T October 14 L14: Introduction to Randomized Algorithms, Quicksort and QuickSelect Recording 14 Dasgupta et al Book Randomized Algorithms: A Virtual Chapter
15 R October 16 L15: Randomized Algorithms: Quicksort and QuickSelect Recording 15 Dasgupta et al Book Randomized Algorithms: A Virtual Chapter
16 T October 21 L16: Hashing Recording 16 Dasgupta et al Book Chapter 1
17 R October 23 L17: Network Flows Recording 17 Dasgupta et al Book Chapter 7, Section 7.2
18 T October 28 L18: Network Flow Algortihms Recording 18 Dasgupta et al Book Chapter 7, Section 7.2
19 R October 30 L19: Network Flow Applications Recording 19 Dasgupta et al Book Chapter 7, Sections 7.2 - 7.3
20 T November 4 L20: More Network Flow Applications Recording 20 Dasgupta et al Book Chapter 7, Sections 7.4 - 7.7
- R November 6
Midterm #2
21 T November 11 L21: Polynomial Time Reductions Recording 21 Dasgupta et al Book Chapter 8
22 R November 13 L22: Reductions and NP Recording 22 Dasgupta et al Book Chapter 8
23 T November 18 L23: NP-Completeness and the Cook Levin Theorem Recording 23 Dasgupta et al Book Chapter 8
24 R November 20 L24: More NP-Complete Problems Recording 24 Dasgupta et al Book Chapter 8
- November 22-29
Thanksgiving Break
25 T December 2 L25: co-NP, Self Reductions Recording 25
26 R December 4 L26: Introduction to Linear Programming Recording 26 Dasgupta et al Book Chapter 7
27 T December 9 Review Session Recording 27 -
- M December 15
Final Exam

HOMEWORKS


# Due Reading Material Discussion Practice Problems Homework Solutions
0 [pdf], [tex] September 02 12:00 Prerequisites Session 0 [pdf] HW#0 [Moodle]
1 [pdf], [tex] September 09 12:00 L2, L3 Session 1 [pdf] HW#1 [Moodle]
2 [pdf], [tex] September 16 12:00 L4, L5 Session 2 [pdf] HW#2 [Moodle]
3 [pdf], [tex] September 23 12:00 L6, L7 Session 3 [pdf] HW#3 [Moodle]
- - - Session 4 [pdf] -
4 [pdf], [tex] October 7 12:00 L8, L9, L10 Session 5 [pdf] HW#4 [Moodle]
5 [pdf], [tex] October 14 12:00 L10, L11 Session 6 [pdf] HW#5 [Moodle]
6 [pdf], [tex] October 21 12:00 L12, L13, L14 Session 7 [pdf] HW#6 [Moodle]
7 [pdf], [tex] October 28 12:00 L14, L15, L16 Session 8 [pdf] HW#7 [Moodle]
8 [pdf], [tex] November 4 12:00 L17, L18 Session 9 [pdf] HW#8 [Moodle]
- - - Session 10 [pdf] -
9 [pdf], [tex] November 18 12:00 L19, L20, L21 Session 11 [pdf] HW#9 [Moodle]
10 [pdf], [tex] December 2 12:00 L22, L23 Session 12 [pdf] HW#10 [Moodle]
- - - Session 13 [pdf]
- - - Session 14 [pdf]

POLICIES




Grading
Grade DistributionGrad and undergrads will be graded on different scales.

Adjusted Course Average (ACA)

6% for online quizzes,
22% for homework (after dropping each student's lowest homework grade),
42% (2 x 21%) for midterm exams,
30% for the final exam (covers full course content).

An extra 2% of their grade will be awarded to students that have typeset in LaTeX at least 75% of their submitted homeworks (starting HW#1).

Getting an A+Given for exceptional performance as judged by the instructor.
Getting an F Undergrads - Anyone with a homework average below 40% or a ACA below 30%, automatically gets an F.
Graduates - Any student with a homework average below 50% or an ACA below 40%, automatically gets an F.
Any student with an exam average <= 25%.

Determining Grade Cutoffs
(Excluding extreme outliers at both ends of the curve.)
Undergrads - the mean is a borderline B- / C+, and each standard deviation is worth a full letter grade.
Thus, the B+ / B cutoff is 2/3 standard deviations above the mean. That is, the range that corresponds to
the grade B itself has length of 1/3 of a standard deviation.
Graduates - the mean is a borderline A-/B+, and each standard deviation is half a letter grade.
The above is a guideline - the thresholds will be adjusted by the instructor within reason.
Quizzes
Quizes will be assigned on a weekly basis. It will be available every Tuesday and it will be due by the midnight of the coming Sunday.

We strongly advise students to do the quizzes before attempting the homework.

Homework
Homework will be assigned on a weekly basis. It will be available every Tuesday and it will be due the next Tuesday at noon before class.

Except for HW0, the rest can be turned in in groups of up to 3 students.

We will not accept late homeworks for any reason. To offset this rather draconian policy, we will drop your lowest homework score.

Submit a paper copy of your homework in the homework boxes in the basement of Siebel Center. They are in the lower-level next to the snack machines. You should turn in each question separately; one stapled copy per problem per homework in the appropriate box. (so, for example if HW0 has 5 problems, then you should make 5 different submissions, one per problem.) We highly recommend you typeset your homework, if you do, we strongly recommend you use latex.

For a single problem, a single submission per group suffices. It is not necessary that everybody in the group submits his/her own copy separately.

Clearly print/type your name(s), your NetID(s), the homework number, and the problem number at the top of every page. For example: "John Smith (smith01) HW0 #5". For group homework solutions, print the name and NetID of every group member on.

Don't babble! Answering "I don't know" or "IDK" (and nothing else) to any homework or exam question is automatically worth 25% partial credit for that question. Synonyms like "No idea" or "WTF" are also acceptable, but you must write something; a blank page is worth nothing.

Academic Integrity
Each student (or homework group) must write their own homework solutions, in their own words, and must properly credit all sources. These include but are not limited to: Books, Papers, Web pages, Solutions from prior course material, Fellow students, Friends and/or family members.

Citing your sources will not lower your homework grade.

Every member of the group receives credit for the entire assignment, hence every member of the group is responsible for the entire assignment. If a submitted homework contains plagiarized material, every member of the group will be given the same penalty.

Avoiding plagiarism is really very simple: Never present someone else's words or ideas as your own.

Violations of academic integrity will incurse serious penalties.
  • The default penalty for a first offense is a grade of zero on the entire homework or exam. (such a homework which will not be dropped as mentioned earlier.)
  • The penalty for a second offense, or a particularly egregious first offense, is an F in the course.
These penalties are consistent with the CS department's recommendations.

Finally, all academic integrity cases will be reported to the student's department and college. Multiple offenses can result in suspension or dismissal.

TEXTBOOK


Recommended textbooks: You are not required to buy these books.
  • Algorithms by Dasgupta, Papadimitriou, Vazirani.
  • Algorithm Design by Jon Kleinberg and Eva Tardos.


Other recommended readings:
  • Jeff Erickson's algorithms material (highly recommended).
  • Course material from Spring 2013 with pointers to past semesters.
  • Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein.
  • Computers and Intractability by Garey and Johnson.


DISCUSSION SESSIONS


Every on-campus student must register for one of the four discussion sections.

Attending the discussion section is strongly encouraged.

Discussion sections are opportunities for you to practice your problem-solving and presentation skills. You will work on problems on the material taught that week, with feedback and suggestions from the TAs. The TAs may also review some material from lectures as necessary.

We are happy to provide feedback on your attempted solutions —- that's precisely what the discussion sections are for. However, we do not plan to provide official solutions to the problems show in the discussion, either during the sections themselves, on the course web site, or during office hours. We encourage you to present your own solutions to your friends. Presenting your solutions will help you master the course material (so you'll do better on later homeworks and exams) and develop your presentation skills (for later oral homeworks).

We encourage you to ask questions about discussion section problems in office hours and on the course newsgroup, and to continue working on them on your own and with your study partners.

You should attend the discussion section that you registered for. This helps keep the load balanced. If you do wish to change, please contact the TAs.

Top