CS 473: Undergraduate Algorithms (Fall 2012)

Instructor

Jeff Erickson (jeffe@illinois.edu)

Teaching Assistants

Akash Gautam (agautam3@illinois.edu)
Ashish Vulimiri (vulimir1@illinois.edu)
Kyle Jao (fjao2@illinois.edu)
Nirman Kumar (nkumar5@illinois.edu)

Graders

Dan Rasmussen
Eric Shahkarami

Resources

Detailed schedule with lecture notes
Coursework (homework, exams, solutions, etc.)
Moodle site (guest password: algorithms)
Piazza signup (access code: algorithms)
Other useful resources

Administrivia

About this course
Weekly schedule — lectures, head-banging sections, and office hours
Course policies: Homework, Grading, Academic integrity
Some stuff you already know

Announcements

January 2

All homework and exam solutions have been removed from the course web site.

December 23

All course grades have been uploaded to Banner. Thanks and have a fantastic break!

• Several students reported missing scores on Moddle. Many of these scores were updated in Jeff's final spreadsheet, but to account for scores we may have missed, we forgave up to four missing homeworks for each student, not including HW10. As promised, we also dropped the five lowest homework scores (not counting forgiven homeworks).

• We dropped the lowest two quiz scores.

• Since Midterm 2 was more difficult than we expected, overall averages were calculated both by dropping the lowest three exam scores (as promised) and by dropping the lowest four exam scores (and weighting the remaining scores more). Each student was assigned the higher of the two resulting course grades. Dropping 3 questions was better for 3 students; dropping 4 questions was better for 9 students; for the other 155 students, there was no difference.

• Here are the grade cutoffs under both grading systems and the number of students in each range.

  Grade	Min %  drop 3	Min %  drop 4	#
  A+	95.00%	95.00%	5
  A	88.56%	89.89%	19
  A-	84.12%	85.48%	12
  B+	79.67%	81.08%	20
  B	75.22%	76.68%	17
  B-	70.78%	72.28%	16
  C+	66.33%	67.88%	13
  C	61.89%	63.48%	21
  C-	57.44%	59.08%	10
  D+	52.99%	54.67%	15
  D	48.55%	50.27%	6
  D-	44.10%	45.87%	9
  F	0.00%	0.00%	4

• Final exam grades are available on Moodle; grade distributions and estimated letter-grade cutoffs are given below. There was no significant difference in the overall grade distributions for the regular final and the conflict final.

  A	67½ 67 66½ 66 65½ 65½ 65 64½ 64¼ 64 63½ 63 62½ 62 61½ 61 60 59½ 59½ 59½ 59 59 59 58½ 58½ 58¼ 58 58 57½ 56¾ 55½ 55½ 55½ 55½
  B	55 55 54½ 54 54 53 53 53 52½ 52½ 52½ 52 52 51½ 51½ 51½ 51 50½ 50¼ 50 49¼ 49 48¾ 48½ 48¼ 48 48 48 47½ 47 47 47 47 47 45½ 45¼ 44½ 44½ 44½ 44 43½ 43½ 43½ 43½
  C	42¾ 42½ 42¼ 41½ 41 41 41 41 41 40½ 40½ 40½ 40¼ 40 39½ 39½ 39½ 39¼ 39¼ 39¼ 39 39 38¾ 38 37¾ 37¼ 37 36¾ 36½ 36½ 36¼ 36¼ 36 35½ 35¼ 35¼ 35 35 35 34¾ 34½ 34½ 34½ 34½ 34¼ 34 34 33½ 33 33 32 31½ 31½ 31½ 31
  D	30½ 29¾ 29¾ 29½ 29¼ 27¾ 27¾ 27½ 27½ 26¾ 26½ 26¼ 25¾ 25¼ 25 24¾ 24½ 24½ 24¼ 23¾ 23½ 23½ 21¾ 21½ 21¼ 20¼ 20¼ 19¼
  F	18½ 16½ 15

  Problem		1	2	3	4	5	6	7	sum
  Mean		7.82	7.27	4.76	6.88	4.90	4.29	6.95	42.90
  Stdev		2.15	2.87	3.56	2.80	4.17	2.96	2.57	12.19

December 13

The final exam will be held Tuesday, December 18, 8-11 am. Please go to the following rooms (by last name):

• A-F: 106B1 Engineering Hall
• G-Sh: 1404 Siebel Center
• Si-Z: 119 Materials Science & Engineering

The conflict exam will be held Friday, December 14, 1-4pm in 2405 Siebel Center.

The final exam will cover the entire semester, with slightly more emphasis on material from the last third of the course. At a high level, we have covered seven topics: recursion, dynamic programming, randomized algorithms, amortized analysis, basic graph algorithms, flow and cuts, and NP-hardness. The final exam will have seven questions.

Material in the lecture notes that was not explicitly covered in class, in homework, and in quizzes will not be on the exam. For example, we will not ask questions about computing flows with demands, the analysis of the Edmonds-Karp flow algorithm, or details of the reduction from vertex cover to Hamiltonian cycle.

You may bring two 8.5"x11" double-sided cheat sheets. Otherwise the exam is closed-everything; in particular, no electronic devices will be allowed. We will ask you to turn in your cheat sheets with your answers as usual. We will provide a list of standard NP-hard problems will be provided, as in Homework 10.

If you want to take the CS 473 final exam for proficiency credit, just show up to the regular final (not the conflict) and write PROFICIENCY in large friendly letters across the top of the front page of the exam. You do not need to register with Jeff in advance.

December 11

Homework 10 solutions are available.

At the end of today's review session, a representative of the Engineering Graduate Student Advisory Committee (EGSAC) announced their online CS course evaluations. The survey is open until December 31, 2012; you need an anonymous one-time code (distributed in class) to access the survey for each CS course. Unlike ICES scores, which are deliberately limited to instructors and their department heads, results of EGSAC course evaluations will be available to students at the same URL, after January 1, 2013. Please fill out EDSAC surveys for all your CS classes.

The TAs are running review sessions during this week's head-banging sessions. Please go to the section for which you are registered. The TAs will bring all your graded work to your section.

All office hours will be held as usual this week. Jeff will also hold extra office hours on Monday, December 17, from 3pm to 5pm.

The conflict final will be held Friday, December 14, from 1pm to 4pm, in 2405 Siebel. You do not need to register in advance for the conflict final; just show up.

December 6

Homework 9 solutions are available.

December 4

Homework 10 is due Tuesday, December 11. This homework is optional. We will grade whatever problems you submit; we will forgive whatever problems you do not submit.

There is no quiz this week.

November 27

Welcome back!
Quiz 7 is due Monday, December 3.
Homework 9 is due Tuesday, December 4.

I will distribute ICES forms at the end of class on Tuesday, December 4. Please come to 1404 Siebel to fill out the forms even if you have already dropped the class. Your feedback is extremely important to me and to the department.

The final exam is on Tuesday, December 18, from 8am to 11am. If you need to take a conflict exam, please send email to Jeff with your complete exam schedule as soon as possible. I will do my best to find a time a few days before the regular exam.

November 16

Next semester's sections of CS 473 hit their registration limit of 200 two days ago. Wheeee!

November 15

Homework 8 solutions are available.
Midterm 2 solutions have been updated.

Midterm 2 has been graded. Grades are available on Moodle. Exams will be available to pick up after today's lecture and in headbanging sessions after Thanksgiving break. Grade distributions and estimated letter-grade cutoffs are given below. Green scores are above 95% and red scores are below 25% (equivalent to "I don't know" on every page); those outliers were excluded when computing statistics and cutoffs.

A	50 49 47½ 47 44½ 44 44 42½ 42½ 42 41½ 41 40½ 40 39½ 39 39 38¾ 38½ 38½ 38½ 38 37¾ 37½ 37½ 36½ 36½ 36 36 35¼ 35
B	34½ 34½ 34¼ 34 34 34 33¾ 33¾ 33¾ 33½ 33½ 33½ 33¼ 33¼ 33 32½ 32¼ 32 32 32 31½ 31½ 31 31 30¼ 30¼ 29¾ 29½ 29½ 29½ 29¼ 29¼ 29 29 29 28¼ 28¼ 28 27½ 27¼
C	27 27 26¾ 26½ 26½ 26½ 26¼ 26¼ 26 26 26 26 25¾ 25½ 25½ 25½ 25¼ 25¼ 25¼ 25 24¾ 24½ 24¼ 24 24 24 23½ 23½ 23¼ 23 23 22¾ 22½ 22½ 22¼ 22¼ 22¼ 22¼ 22 22 22 22 21½ 21½ 21½ 21½ 21½ 21½ 21½ 21½ 21½ 21¼ 21 21 20¾ 20¾ 20¾ 20½ 20½ 20½ 20½ 20¼ 20 20 20 19¼
D	19 19 19 19 19 18½ 18 18 18 17¾ 17¾ 17½ 17½ 17 16½ 16¼ 16 15½ 15 14¾ 14½ 13½ 13¼ 13 12¾
F	12½ 11 8½ 6½

Problem		1	2	3	4	5	sum	–outs
Mean		4.66	4.98	4.96	4.60	7.86	27.05	27.08
Stdev		2.74	3.18	2.97	2.62	2.34	8.66	7.84

The next table shows the combined distribution of both midterms after dropping the two lowest problem scores. These letter grades are rough predictions, based on only 40% of your overall coursework. Past experience suggests that most final course grades will be within about 1/2 of a letter grade of these estimates. For example, if your estimated grade is in the middle of the B range, your final grade will probably be between a low A- and a high C+.

A	79 79 79 79 76½ 76 74½ 74 74 73½ 73 72½ 71½ 71 71 71 70½ 70 70 69 69 69 68 67½ 67½ 66½ 66¼ 66 65¾ 65½ 65½ 65¼ 64¾ 64½ 64½ 64
B	63¾ 63¾ 63½ 63¼ 63 62½ 62½ 62½ 62½ 61½ 61½ 61½ 61½ 61½ 60½ 60¼ 60 59¾ 59 58¾ 58¾ 58½ 58½ 58 57¼ 57¼ 57 57 56½ 56 56 55½ 55½ 55 55 55 54¼ 53½ 53½ 53½ 52½ 52½ 52¼ 52¼ 52
C	50¾ 50¼ 50¼ 50 49½ 49½ 49½ 49½ 49½ 49¼ 49¼ 49 48¾ 48½ 48½ 48½ 48¼ 48 47¾ 47¾ 47¾ 47¼ 47¼ 47 46½ 46½ 46 45½ 45½ 44¾ 44½ 44½ 44¼ 44¼ 43½ 43½ 43¼ 43¼ 43 43 43 42¼ 42¼ 42 41½ 41½ 41½ 41½ 41½ 41½ 41 41 41 41 40¾ 40½ 40¼ 39½
D	38¾ 37½ 37 36½ 36 35¾ 35½ 34½ 34½ 34¼ 33¼ 32½ 31¾ 31¾ 31¼ 30½ 29¾ 29¾ 29¼ 29 29 27½
F	26 25½ 21

November 6

Homework 8 is due Tuesday, November 13. This is the last homework due before Thanksgiving break.

November 5

Quiz 6 is due next Monday, November 12, at noon. Yes, quizzes again.
Solutions for Midterm 2 are available; gray text (mostly proofs) is not required for full credit. Grading rubrics are still tentative.

November 1

Midterm 2 was held this evening from 7pm to 9pm.

• Please go to the following rooms based on the first letter of your last name:
  • A–I: 124 Burrill Hall
  • J–L: 165 Everitt Lab
  • M–S: 269 Everitt Lab
  • T–Z: 1092 Lincoln Hall
• The exam covered randomized algorithms and data structures, amortized analysis, and graph traversal. There were no questions about dags, topological sorting, or minimum spanning trees (because those lectures were too recent) and no questions about the material in the second hashing lecture on October 4 (because there are no notes). You may have needed tools from earlier in the semester (like recursion and dynamic programming), but those were not the main focus of the exam.
• You were allowed one 8.5"x11" sheet of paper with anything you want written, printed, photocopied, engraved, torn, or burnt onto it on both sides. Otherwise, the exam was closed-everything. We asked you to submit your "cheat sheet" with your answers.
• There was no lecture today. Instead, Jeff held an optional review session from 11 to 12:15 in 1404 Siebel. Students brought lots of questions.

Also, Homework 7 solutions are available.

October 29

Homework 6 solutions are finally available. (Sorry for the delay.)

New notes for the material covered in last Tuesday's lecture (depth-first search, directed acyclic graphs, and topological sorting) are also available. Unfortunately, I won't have time to talk about strong components or Kosaraju-Sharir algorithm in class this semester, but it's all in the notes.

October 23

Class was cancelled today because Jeff was sick.
There is no quiz this week.
Homework 7 is due Tuesday, October 30, at noon.
Homework 5 solutions have been revised.
Homework 6 solutions will be posted tomorrow.

October 18

Homework 6 has been revised. In both problems, supporting REVERSE in O(1) time, in addition to the other operations, is worth 5 extra credit points.

October 16

There is no quiz this week.
Homework 6 is due Tuesday, October 23, at noon.
Homework 5 solutions are available.

October 9

Quiz 5 is due Monday, October 15, at noon.
Homework 5 is due Tuesday, October 16, at noon.
Homework 4 solutions are available.
Updated Midterm 1 solutions are available.

October 9

Midterm 1 has been graded. Grades are available on Moodle, and exams will be returned in this week's headbanging sessions. Grade distributions and estimated letter-grade cutoffs are given below, computed in two different ways. In the table below, green scores are above 95% and red scores are below 25% (equivalent to "I don't know" on every page); those outliers were excluded when computing statistics and cutoffs.

Please keep in mind that these letter grades are very rough predictions, based on only 20% of your overall coursework. Based on past experience, we expect most students' final course grades to be within one letter grade of these estimates, but differences of up to a full letter grade (in either direction) are fairly common.

A	50 49 48 48 47½ 46 45 45 45 44½ 44 44 43½ 43¼ 43 43 43 42¾ 42 42 41½ 41½ 41 41 41 41 39½ 39½ 39 38½ 38½ 38½ 38½ 38 38 37½
B	37 37 36½ 36½ 36 36 36 35¾ 35 35 34½ 34½ 34½ 34½ 34½ 34¼ 34 34 34 34 33½ 32¾ 32½ 32½ 32½ 32¼ 32¼ 32 32 32 31¾ 31¾ 31½ 31½ 31½ 31¼ 31 30½ 30 30 29½ 29¼
C	29 28¾ 28¾ 28¾ 28¾ 28½ 28½ 28 28 28 27¾ 27½ 27½ 27½ 27½ 27½ 27½ 27½ 27¼ 27 27 26¾ 26¾ 26½ 26 26 25½ 25½ 25½ 25½ 25 25 24¾ 24½ 24¼ 24 24 24 23½ 23½ 23½ 23½ 23¼ 23¼ 23¼ 23 23 23 22¾ 22¾ 22¾ 22½ 22½ 22½ 22½ 22½ 22¼ 22 22 22 21¾ 21½ 21½ 21¼ 21 21 20¾
D	20½ 20 20 20 19½ 19¼ 19 19 18½ 18½ 18¼ 18 17¾ 17½ 17 16½ 15¾ 15½ 15½ 15 14½ 14¼ 13¾ 12¾ 12½
F	10¾ 10½ 10½ 8 7½ 7½

Problem		1	2	3	4	5	sum	–outs
Mean		6.53	6.58	4.61	6.91	4.23	28.85	29.09
Stdev		2.55	3.12	2.87	3.16	2.98	9.42	8.38

October 2

Homework 4 is due Tuesday, October 9 at noon.
Quiz 4 is also due Tuesday, October 9 at noon, because we didn't post it until today.

September 28

Solutions and (tentative) rubrics for Midterm 1 are available.

September 27

Midterm 1 was held this evening from 7pm to 9pm.

• Please go to the following rooms based on the first letter of your last name:
  • A–G: 165 Everitt Lab
  • H–L: 223 Gregory Hall
  • M–S: 217 Noyes Lab
  • T–Z: 144 Loomis Lab
• The exam covered prerequisite material (esp. big-Oh notation, induction, and divide-and-conquer recurrences), recursive algorithms (including divide-and-conquer, backtracking, and dynamic programming), and greedy algorithms. Topics in the lecture notes that are not explicitly covered in class, in homework, and in quizzes will not be on any exam. (For example, nothing on the exam required FFTs, fast exponential algorithms, clever dynamic programming tricks, or matroids.) Also, there were no questions about randomized algorithms; we're saving those for Midterm 2.
• You may bring one 8.5"x11" sheet of paper with anything you want written, printed, photocopied, engraved, torn, or burnt onto it on both sides. Otherwise, the exam is closed-everything. We will ask you to submit your "cheat sheet" with your answers.
• There was no lecture today. Instead, Jeff ran an optional review session from 11:00 to 12:15 in 1404 Siebel. People brought lots of questions.
• A large archive of Jeff's past exams is available at the bottom of this web page. This semester's exam will have the general same structure as these previous exams: 5 questions, each worth 10 points. Please keep in mind that the exact topical coverage changes from year to year, so some old exams cover topics that are not relevant for this exam. Also, exam problems for graduate classes (473G and 573) tend to be slightly more difficult. You can also find several practice problems in the lecture notes themselves.

September 26

Homework 3 solutions are available. (We will add the extra-credit O(mn)-time solution for problem 2 later.)

September 21

Unfortunately, Jeff omitted a single word from Homework 3, problem 3, which made the problem significantly more difficult. For full credit, you may assume that the company hierarchy is represented by a binary tree; that is, each node in the input tree T has at most two children. The homework has been updated to reflect this assumption.

A correct solution for arbtirary rooted trees is worth 10 points extra credit. However, if you decide to attempt the more general problem, we strongly recommend that you first write a complete solution for binary trees, and then separately describe the necessary modifications for arbitrary trees. Staple both solutions together for submission.

Sorry for the confusion!

September 18

Starting with Homework 3, please clearly indicate your discussion section at the top of your homework solutions, just after your name and NetID. Please list only one section, even if your group members are enrolled in different sections. We will return your graded solutions in the section you indicate. (This way, we don't have to bring everybody's solutions to every section.)

• Quiz 3 is due Mon Sep 24 at noon.
• Homework 3 is due Tue Sep 25 at noon.
• Homework 2 solutions are available.
• Last week's head-banging problems are available.

September 11

Most of the Homework 0 problems have been graded. Grades are available on Moodle. You can pick up your graded solutions in discussion sections.

• Quiz 2 is due Mon Sep 17 at noon.
• Homework 2 is due Tue Sep 18 at noon. Link fixed!
• Homework 1 solutions are available.

September 4

Homework 0 solutions are available.

For future reference, let me remind everyone that the 25% partial credit for "I don't know" does not apply to extra credit problems!

September 3

New stuff:

• Quiz 1 (due Mon Sep 10 at noon)
• Homework 1 (due Tue Sep 11 at noon)
• Last week's headbanging questions
• Videos for last week's lectures. (All videos appear automatically on this web page a few hours after each lecture.)

August 30

It appears that everyone who needs the class to graduate has already registered, so we can relax the criteria for the waiting list. However, students for whom CS 473 is a degree requirement will have first priority for late registration; these students will be added in decreasing order of their Homework 0 score. Once all those students are in, then other students will be added, again in order by decreasing HW0 score. (If you don't submit Homework 0, we will assume that you're no longer interested in adding the class.)

August 28

Welcome to CS 473!

• The class is full. If you are graduating in December, you need CS 473 to satisfy a degree requirement, and you were unable to register, please contact Jeff as soon as possible. Unfortunately, we just don't have the resources to open the course to anyone else this semester.
• Two things you should do right now:
  • Please confirm that you have access to the course Moodle site, which we will use for weekly quizzes and grades. If registered students should already have access. Please contact Jeff as soon as possible if you are unable to log in.
  • Please register for access to the course Piazza site, using your favorite email address and the the access code algorithms. We will use Piazza as a discussion forum for the students and instructional staff.
• Other stuff to do this week:
  • Homework 0 is due Tuesday, September 4, at noon. LaTeX source is available for students who want to typeset their solutions. You may find Jeff's notes on induction and solving recurrences helpful.
  • Quiz 0 (on Moodle) is due Tuesday, September 4, at noon. Future quizzes will be due Mondays at noon.
  • Yes, there are head-banging sessions during the first week!

Weekly schedule

Lectures

Tue Thu 11:00-12:15
1404 Siebel Center

Head-banging

Tue 4-5, Tue 5-6, Wed 2-3, Wed 3-4, and Wed 6-7
1214 Siebel Center

Office hours

All in the open area outside 3303 Siebel Center

• Jeff: Wed 10-11 and Fri 2-3, or by appointment
• Ashish: Thu 5-6
• Akash: Tue 6-7
• Kyle: Thu 4-5
• Nirman: Wed 4-5

Online quizzes

Due Mondays at noon; available on Moodle

Homework

Due Tuesdays at noon in the drop boxes outside 1404 Siebel