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 |
| 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 | ||||
| # | 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] |
| Grading | |
|---|---|
| Grade Distribution | Grad 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.
|
| Finally, all academic integrity cases will be reported to the student's department and college. Multiple offenses can result in suspension or dismissal. |
Recommended textbooks: You are not required to buy these books.
|
Other recommended readings:
|
| 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. |