Take one step forward and you're a better person.


4. Think about a problem
5. Prepare to fly

CS 473: Undergraduate Algorithms (Fall 2013)

Instructor
Jeff Erickson (jeffe@illinois.edu)
Teaching Assistants
Hsien-Chih Chang (hchang17@illinois.edu)
Daniel Khashabi (khashab2@illinois.edu)
Kent Quanrud (quanrud2@illinois.edu)
Subhro Roy (sroy9@illinois.edu)
Graders
Anonymous by request
Resources
Detailed schedule with lecture notes
Coursework (homework, exams, solutions, etc.)
Moodle site (enrollment password: algorithms)
Piazza site (access code: algorithms)
Other useful resources
Administrivia
About this course
Weekly schedule — lectures, sections, and office hours
Course policies: Homework, Grading, Academic integrity
Some stuff you already know

Help! The course is full!



Announcements

January 12
All homwwork and exam solutions have been removed.
December 30
I discovered a systematic error in my grade calculations that impacted about 20 students. I have submitted grade corrections and emailed the affected students; it may take several days for the corrected grades to appear on unofficial transcripts. Nobody's grade went down.
December 28
All course grades were uploaded on December 24 (as promised). Everyone should be able to see their course grade on Self Service.

All further questions about the course should be directed to Jeff; the TAs and grader are officially done. In particular, if you have specific questions about your final exam, please come talk to me (Jeff) no later than January 31. (I will be on-campus only sporadically until January 3 and then out of town until January 13.)

Please double- and triple-check that all your grades are recorded correctly on Moodle and report any discrepancies to me as soon as possible. I applied some last-minute regrades downloading the raw grades into my own spreadsheet for the final grade computation; these grade changes do not (and will not) appear on Moodle.

Here is the distribution of final exam scores, including all seven questions.

 A  65½ 65 61 61 61 60½ 59 58½ 58 56 56 55½ 55½ 55½ 55½ 55 54¾ 54¼ 54 54 54 54 54 54 53¾ 53½ 53½ 53½ 53½ 53½ 53¼ 53 52½ 52½ 52½ 52½ 51½
B 51 51 51 51 50½ 50 49½ 49¼ 49 48¾ 48½ 48½ 48 48 48 47¾ 47½ 47 47 47 47 46½ 46½ 46 46 45½ 45½ 45½ 44¾ 44½ 44¼ 44¼ 44 44 44 44 44 44 43¾ 43¾ 43½ 43 43 43 43 43 42¾ 42½ 42½ 42½ 42 42 42 42 41¾
 C  41½ 41½ 41½ 41 41 41 41 41 40¾ 40¾ 40¾ 40½ 40¼ 40 40 39¾ 39¾ 39¾ 39¾ 39½ 39 39 38½ 38¼ 38 37¾ 37¾ 37½ 37¼ 37 37 37 36¾ 36½ 36½ 36¼ 36 36 36 36 36 35½ 35½ 35½ 35½ 35 34¾ 34½ 34½ 34¼ 33½ 33½ 33½ 32¾ 32¼
D 32 31½ 31½ 31¼ 31 30¾ 30¾ 30½ 30½ 30¼ 30¼ 30 30 29¾ 29½ 29¼ 29 28¾ 28¾ 28½ 28½ 28 27¼ 27 26 26 25¾ 25½ 25½ 25¼ 25 24 23¾ 23¾ 23½ 23½ 23
 F  22 20½ 14

Problem 1 2 3 4 5 6 7 sum
Mean 5.39 4.33 2.12 8½0 6½8 7.20 41.71
Stdev 2.40 3.07 1.99 2.21 2.45 3½6 1.94 9.60

Finally, here is the distribution of total exam scores, first including all 17 problem scores, and then after dropping the 3 lowest problem scores. The letter grades reported here are not the overall course grades. Because of homework and quiz scores, overall grades differ from grades predicted by exams by up to 2/3 of a letter grade (for example, B instead of C+, or B instead of A-). However, for about 85% of the students, course grades are either equal to or 1/3 letter higher than overall exam grades.

As promised, I computed averages and grade cutoffs twice, once using "all 17" exam scores and once using "top 14" exam scores; each student received the higher of the two resulting letter grades.

All 17 mean 104.30, stdev 22.65
 A  157½ 149¼ 146½ 145½ 144½ 144 143 138½ 138½ 138 137¼ 134½ 134 134 134 133½ 133¼ 133 133 132½ 132 131¾ 131¼ 131 130½ 130½ 129 128¾ 128 128 127¾ 127½ 127 127
B 126½ 126 125½ 125 124¼ 124 124 123½ 123¼ 123 120¾ 120¾ 120½ 120½ 120 120 120 119½ 119 119 118½ 118½ 118 118 117¾ 117¾ 117½ 117¼ 117 117 117 116¾ 116½ 116¼ 116 116 115½ 115 114¾ 114¼ 114 113½ 112¾ 112¼ 112 112 110 109½ 109½ 109¼ 108½ 107¾ 107¼ 105½ 104¼
 C  104 104 102¾ 102¼ 101¾ 101¼ 101 100¾ 100¼ 100 99½ 99½ 99 98¼ 98 98 97¾ 97½ 97¼ 97¼ 97 96¾ 96¾ 96½ 96¼ 96¼ 96 96 95½ 95¼ 95 94¾ 94¼ 94 94 93¾ 93½ 93 92¾ 92¾ 92 91½ 91¼ 91¼ 90¾ 89¾ 89½ 89¼ 88½ 88½ 88½ 88 88 87¾ 87 86¾ 86¼ 85 84¾ 84½ 84¼ 84¼ 84 82¾ 82
D 81 77¾ 77 76¾ 76½ 76¼ 75¼ 74 72½ 72½ 72½ 71¾ 71¼ 70¼ 70 68¾ 66¼ 66¼ 65½ 65¼ 63½ 63¼ 63¼ 60½ 59½
 F  58¾ 58½ 54¾ 48¼

Top 14 mean 97.11, stdev 19.46
 A  135½ 134½ 134¼ 132½ 131½ 129½ 128½ 128 127½ 125½ 125 124½ 124½ 123½ 123 122½ 122¼ 122 122 121½ 121½ 121½ 121 121 120½ 120 120 119¼ 119 119 118½ 118¼ 118 118 117¾ 117 117
B 116½ 116¼ 115¾ 115½ 115½ 115 114½ 114 114 113¾ 113½ 112½ 111½ 111 111 111 111 111 110¾ 110¾ 110½ 110 110 110 110 110 109 109 108¾ 108¼ 108 107¾ 107½ 107½ 107 107 107 106¾ 106¾ 106½ 105¾ 105¾ 105½ 103½ 102½ 100½ 100½ 100½ 100½ 100 99¾ 99 98¾ 98½
 C  96¾ 96 95¾ 95½ 95¼ 95¼ 94½ 94 93¾ 93¾ 93½ 93½ 93¼ 93¼ 93¼ 93 93 92½ 92 91¾ 91½ 91½ 91 91 90¾ 90½ 90½ 90½ 90½ 90¼ 90 89¾ 89¾ 89½ 89¼ 89 88¾ 88½ 88½ 88 87¼ 87 86½ 85½ 85 83¾ 83½ 83¼ 83¼ 83 82½ 82½ 82½ 82½ 81 80¾ 80¾ 80¼ 80 80 78¾ 78½
D 76½ 74½ 74¼ 74¼ 74 72¾ 71¾ 71½ 71½ 70½ 70¼ 70 69½ 69¼ 69 67 66¼ 64¼ 62¼ 61¼ 61¼ 61 60¼ 58¾ 58½ 57¾
 F  56½ 54½ 52¾ 48

December 23
All final exams have been graded. Everyone's exam grades should be available on Moodle. We will post statistics here later tonight.

Solutions and rubrics for the final and conflict final are available (for a short time).

We expect to upload course grades to Banner by tomorrow; we will also post some crude statistics here.

December 12
The conflict final on Monday, December 16, 8am–11am, will be held in 3401 Seibel. The room is big enough to hold everyone who registered. If you registered for the conflict exam but don't show up, we will simply assume that you are taking the regular final exam.
December 10
Homework 10 solutions are available.

Today's class meeting is a question and answer session. Feel free to ask me about anything. In particular, don't feel constrained to exam review questions; see below.

Final exam review:

  • This week's head-banging sessions (the last of the semester) will review Jeff's last two CS 473 final exams.
  • There will be a review session on Sunday, November 15, from 1pm to 3pm, in 1404 Siebel. Please bring lots of questions.
  • Office hours will continue until Wednesday afternoon, but possibly at slightly different times; watch Piazza for announcements from the TAs. Jeff will hold office hours next Tuesday from 11 to 12:30 instead of Monday morning.

Final exam logistics:

  • The regular final exam is Wednesday, November 18, from 1:30 to 4:30. Please go to the following rooms, based on your last name.
    • A-L: 1404 Siebel Center
    • M-Z: 151 Everitt Lab
    (Both rooms are large enough to leave an empty seat between any two students.)
  • The final exam will cover the entire course, with slightly more emphasis on material introduced after Midterm 2 (flows and NP-hardness). As usual, topics in the lecture notes that were not explicitly covered in class will not appear on the final exam. As in past semesters, the final exam will have 7 questions, each worth 10 points.
  • You may bring two 8.5"x11" sheets of paper with anything you want written, printed, photocopied, engraved, torn, or burnt onto it on both sides. Otherwise, the exam is closed-everything. Please bring only your cheat sheets, writing implements, and your student ID. We will ask you to submit your "cheat sheets" with your answers.
  • By far the best way to study is to practice: Take one of Jeff's old final exams (at the bottom of this web page), in as close to exam conditions as possible (three hours, working alone, with a cheat sheet but no other books, notes, or electronic devices), and then discuss your solutions in a group with other studnets who did the same thing. Do not confuse knowing the solution to old exam problems with being able to solve them yourself under exam conditions. This is the difference between P and NP!
December 8
The conflict final exam will be held Monday, December 16, 8am–11am. All students who regsiter in advance are welcome to take the conflict exam. To register for the conflict exam, fill out this form by Tuesday, December 10. Please register even if you filled out the previous survey.
November 30
As many of you have already noticed, Midterm 2 has been graded. Grades are available on Moodle; exams will be returned in next week's head-banging sections. Grade distributions and estimated letter-grade cutoffs are given below. The total scores include all 5 questions; grade cutoffs and statistics exclude outliers with scores above 95% or below 25%. There was no significant difference between grade distributions for the regular exam and the conflict exam.

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

Problem 1 2 3 4 5 sum
Mean 8.76 6.43 4.94 5.90 6.85 32.63
Stdev 1.30 2.97 1.95 2.48 3.37 7.11

Here are grades for both midterms combined, including all 10 questions. Letter grades are based on an average (stdev) of 60.04 (13.83); there are no scores above 95% or below 25%. Only students who took both midterms are included here. These letter grades are likely to be within half a letter grade of the overall course grade for most students; however, differences of up to a full letter grade (in both directions) are not that uncommon.

 A  94½ 93¼ 91 90 88 87½ 87¼ 86½ 84½ 84 84 83¼ 83 82 82 81½ 80½ 80 79½ 79¼ 78¾ 78¼ 78 77¾ 77½ 77 77 77 76½ 76½ 76½ 76¼ 76 76 76 76 76 75¼ 75 74½ 74
B 73¾ 73¼ 73¼ 73 73 72¾ 72½ 72½ 72 72 72 71¾ 71½ 71½ 71 71 71 70½ 70 70 69½ 69 69 69 68½ 68½ 68½ 68 67¾ 67½ 67½ 67 67 67 67 66¾ 66½ 66 66 65¼ 65¼ 65¼ 65¼ 64¾ 64¾ 64¼ 64 64 63¾ 63½ 63¼ 63¼ 63¼ 63 63 62¾ 62 62 62 61¾ 61¼ 61¼ 61 60¾ 60¾ 60¾ 60¼ 60¼ 60
 C  59¾ 59 59 58 57¾ 57¼ 57 57 57 56½ 56¼ 56 56 55¾ 55¾ 55 55 55 55 54¾ 54¾ 54 54 53½ 53½ 53¼ 52¾ 52 51¾ 51¾ 51¾ 51¼ 51¼ 51 51 50¾ 50¾ 50¾ 50 49¾ 49 49 48¾ 48¾ 48 48 47½ 47 46½ 46¼ 46¼ 46¼
D 46 46 45 44¾ 44 44 43¼ 41¾ 40¾ 40¾ 40¼ 39¾ 39½ 36 35½ 34¼ 33¼ 32¾ 32¾
 F  32 31¾ 31¼ 27¾

According to the official grading policies, dropping the two lowest exam problem scores would give a more accurate estimate of final course grades. However, this recalculation yields higher letter grades (for example, B+ instead of B, or C- instead of D+) for only 10 students, but lower letter grades for 60 students (inluding one change from B to C+). Dropping the three lowest problems increases this effect. Yay statistics. I reserve the right to compute your final course grade without dropping any exam scores, but only if it that recalculation improves your grade.

November 25
Homework 10 has been revised to remove some editing errors and to clarify problem 3.

Closing out the semester

  • We have now covered all course material that will appear on the final exam. There are three more class meetings after Thanksgiving break. Jeff will give lectures on something cool (most likely Bloom filters) during the first two (Dec 3 and 5); the last class meeting (Dec 10) will be a question-and-answer session.
  • Jeff will distribute ICES forms at the end of class on Thursday, December 5. Please come to at least the last 15 minutes of class on December 5, and please encourage your classmates to come, even if they have already dropped the class.
  • Head-banging seesions will continue on their regular schedule through Wednesday, December 11.
  • Office hours will continue on their regular schedule until everyone has taken the final exam.

Conflict final exam

  • The regular final exam will be held Wednesday, December 18, from 1:30 to 4:30. The Student Code allows you to take a conflict exam if you have more than one exam scheduled at the same time, or if you have three consecutive exams in one 24-hour period. (In such cases, the course with the largest enrollment must offer a conflict exam, but I assume that always means CS 473.)
  • If you want to take the conflict final exam, please fill out this survey by Friday, December 6, even if you do not meet the university requirements. We will schedule the conflict exam to accommodate the largest number of students who absolutely require it, according to the Student Code; we will also try to accommodate students with three exams in four consecutive slots, and then as many other students as possible.
  • Once the conflict exam is scheduled, all students will be allowed to take it by registering in advance (using a separate form). We will do our best to schedule the conflict exam before the regular exam, and we will make separate arrangements with students who require a conflict exam but cannot take it at the scheduled time. However, we will not schedule additional exams just to accommodate conflicting travel plans, including job interviews, even if you have already purchaed plane tickets.
November 21
Homework 9 solutions are available.
November 20
Homework 10 is due Tuesday, December 10.
November 15
Quiz 8 is due next Friday, November 22, before midnight.
November 12
Homework 9 is due Tuesday, November 19. There will be one more homework, due after Thanksgiving break.

Midterm 2 solutions are available.

November 11
The conflict exam took place tonight from 6pm to 8pm in 4405 Siebel Center.
November 6
Midterm 2 was held tonight, Thursday, November 6, from 7pm to 9pm.
  • Students went to the following rooms, based on their last name.
    • A–B: 4405 Siebel Center
    • C–Me: 103 Transportation Building
    • Mi-Z : 114 Transportation Building
  • The exam focused on material that was introduced after the first midterm: randomized algorithms (including treaps and hash tables), amortized analysis (including scapegoat trees and hash tables), graph traversal, topological sort, dynamic programming in dags, minimum spanning trees, and shortest paths. There will be no questions about flows and cuts; we're saving those for the final exam.
  • You were allowed to 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 was closed-everything. We asked 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.
November 6
Homework 8 solutions are available.
November 1
Homework 7 solutions are available.
October 29
Homework 8 and Quiz 7 are both due Tuesday, November 5.

Homework 6 solutions have been available for a while.

October 23
Homework 7 is due Wednesday, October 30. There is no quiz this week.
October 16
Homework 6 is due Wednesday, October 23, because we posted it a day late.

Quiz 6 is still due Tuesday, October 22, because we released it yesterday.

Homework 5 solutions are available. As announced on Piazza, we are making problem 2 extra credit, because the pseudocode in the homework has several small (but deadly) errors. These errors have since been fixed.

October 10
Midterm 1 has been graded. Grades are available on Moodle. Exams will be returned in next week's head-banging sections. Grade distributions and estimated letter-grade cutoffs are given below. The total scores include all 5 questions; grades for problem 2 include the 2 extra credit points; and the grade cutoffs and statistics do not exclude outliers with scores above 95% or below 25%. Also, conflict exams scores are not listed here or included in the statistics.

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  47 46½ 43¼ 43 43 43 42½ 42½ 42 40½ 40½ 40½ 40 40 40 40 40 39½ 39½ 39¼ 38¾ 38½ 38½ 38½ 38½ 38 38 38 38 37¾ 37¾ 37½ 37
B 36½ 36¼ 36¼ 36 35¾ 35¼ 35 35 35 34½ 34½ 34½ 34½ 34½ 34½ 34¼ 34¼ 34 34 34 33½ 33 33 33 33 32½ 32½ 32½ 32 32 32 32 32 31½ 31½ 31½ 31½ 31½ 31 30½ 30 30 30 30 29¾ 29¾ 29½ 29½ 29½ 29½ 29¼ 29¼ 29 29 29 28¾ 28¾ 28½ 28½ 28½ 28½ 28½
 C  28 27¾ 27½ 27 27 27 27 26½ 26¼ 26 26 26 26 25¾ 25¾ 25½ 25½ 25½ 25½ 25¼ 25¼ 25 25 24¾ 24½ 24½ 24½ 24½ 24½ 24¼ 24¼ 24 23¾ 23¾ 23½ 23 22¾ 22½ 22¼ 22¼ 22¼ 22 22 22 22 21¾ 21½ 21½ 21¼ 21¼ 21¼ 21¼ 21 21 20¾ 20½ 20½ 20½ 20½ 20½ 20 20
D 19½ 19¼ 19 19 18½ 18¼ 18¼ 18¼ 18 17 16¾ 16 15½ 15½ 15½ 14¾ 14¾ 14½ 14¼ 13 13
 F  12½ 11½ 11½ 10¾ 9½ 6¾

Problem 1 2 3 4 5 sum
Mean 6.27 4.38 5.79 6.16 5.63 28.22
Stdev 2.35 1.81 3.26 2.35 3.51 8.33

October 8
Homework 5 and Quiz 5 are both due Tuesday, October 15.

Solutions for Homework 4 are available (except for the extra-credit problem).

Jeff will be out of town the entire week of October 14–18. Two of the TAs will give the lectures on October 15 and 17.

October 3
We have updated the midterm solutions to correct a bug in one of the solutions for problem 2. Everybody gets 2 extra credit points on the exam. Yes, even the conflict.
October 1
Solutions and tentative rubrics for Midterm 1 are available. Solutions for the conflict midterm will be posted shortly.

Homework 4 is due next Tuesday, October 8.

Quiz 4 is also due next Tuesday, October 8.

September 26
This week's and last week's headbanging problems are available.
September 25
Homework 3 solutions are available.
September 24
Midterm 1 will be held Thursday, September 26, from 7pm to 9pm.
  • Please go to the following rooms, based on your last name.
    • A-Le: 165 Everitt Lab
    • Li-T: 223 Gregory Hall
    • U-Z: 3405 Siebel Center
  • There will be a conflict exam on Monday, September 30, from 4pm to 6pm. If you need to take the conflict exam, please contact Jeff as soon as possible. (If you have already asked Jeff about taking the conflict but haven't received a reply, please email him again.) The location will be announced by email to the students who sign up.
  • The exam will cover 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 were not explicitly covered in class, in homework, and in quizzes will not appear on any exam. (For example, nothing on the exam will require fast Fourier transforms, fast exponential algorithms, clever dynamic programming tricks, or matroids.) Also, there will be 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.
  • Please being your student ID.
  • There will be no lecture on Thursday. Instead, Jeff will run an optional review session from 11:00 to 12:15 in 1404 Siebel. Please bring 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 same general 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 20
Homework 1 solutions have been updated with a solution to the extra-credit problem.
September 19
Homework 2 solutions (except for the extra credit problem from HW1) are available.

Subhro's office hours have moved to 12:30-1:30 Thursdays.

September 17
Homework 3 and Quiz 3 are both due Tuesday, September 23. The first problem on HW3 has an extra-credit component.

Midterm 1 will be held Thursday, September 25. The midterm covers all material through today's lecture. Stay tuned for exam locations and other information.

September 16
Because of severe ongoing problems with the Engineering Workstations, we are giving everyone a 24-hour extension on Homework 2. Homework 2 is now due Wednesday, September 18, at 12:30pm. We strongly encourage everyone who normally works on the EWS systems to do as much work on paper as possible, so if the systems become usable again, you only have to type, and if they don't, you have a handwritten solution to submit. Homework 3 will be due next Tuesday as usual.

Several students complained that the printers in Siebel were not working just before the HW1 submission deadline last Tuesday. We tried to offer an extension, but we screwed it up. If (and only if) you were unable to submit HW1 on time because of these printing issues, please give your printed HW1 solutions to Jeff in class tomorrow. Put them directly into Jeff's hands, not in the homework drop boxes. We will accept such solutions as though they were submitted on time. Update: Nobody turned in HW1 late.

In the future, if the print servers are not working after about 10am on a homework due date, we will automatically extend the submission to 4pm the same day. That should be enough time to find a working printer elsewhere on campus after class and bring the printout back to Siebel, or to wait until the print servers are brought back online.

Why yes, I do work in a top-5 computer science department; why do you ask?

September 12
We have revised Problem 2 in Homework 2. In the revised version, all tiles with the same letter have the same value, and the letters on the tiles are the standard 26 letters of the Roman/English alphabet. (The original version allowed tiles with the same letter to have different values, and it did not assume a fixed alphabet.) Both versions can be solved by dynamic programming, but we believe the revised version is much easier. You can get full credit for solving either version, but please state which version you are solving. Sorry for the late update; we will try very hard never to do that again.

Jeff is permanently moving his Monday office hours to 9-10am, starting next Monday, September 16.

September 10
Quiz 2 is due Tuesday, September 17, at noon.

Homework 1 solutions (except for the extra credit problem) are available.

September 9
Homework 2 is due Tuesday, September 17 at 12:30pm. This homework (and most future homeworks) has only two questions. The extra credit problem in HW1 is also due Tuesday, September 17.
September 5
This week's headbanging problems are now available.
September 3
HW0 solutions (with grading rubrics) are available.

Quiz 1 is now due Tuesday, September 10, at noon. (We forgot to make the quiz visible yesterday, so we're extending the deadline by 24 hours. Sorry!)

Jeff's Monday office hours are moving from 10-11 to 11-12, starting next week.

Hsien's office hours are moving from Tue 3-4 to Wed 4-5, starting tomorrow.

September 1
Homework 1 is due Tuesday, September 10 at 12:30pm. Groups of up to three students can submit common solutions. This homework includes an extra-credit problem, which is actually due one week later, with Homework 2.

Quiz 1 is due Monday, September 9 at noon. All future Moodle quizzes will be due Mondays at noon.

Some people had trouble with the posted LaTeX solution template. I've posted a revision that should fix the problem; please let me know if it still doesn't work.

Several clarifications on HW0 have been posted on Piazza and discussed in office hours:

  • In problem 1, you can assume part (a) in your proof of part (b), or you can assume part (b) in your proof of part (a), but don't do both. You can also prove (a) and (b) by mutual induction, using an if-and-only-if inductive hypothesis. Or you can do something else.
  • Besides the raw definitions, you can use facts about erasable and/or balanced strings if and only if you prove them first. Your proofs for problem 1 should still be proofs if we replace every instance of "balanced" with "wiggly" and every instance of "erasable" with "stupid".
  • If Jeff posts a proof of something on Piazza, you can include that proof in your solution without citing it, or you can use the theorem and write "Jeff proved this on Piazza", or you can write your own proof, but don't just assume the theorem is true. Don't assume the grader reads Piazza!
  • In problem 2, "either X or Y" means "X or Y", not "X exclusive-or Y". The homework is long enough already!
August 29
This week's headbanging problems are now available.

A LaTeX solution template for HW0 is now available.

August 27
All registered students should already be enrolled on the Moodle site. You should also be able to enroll yourself with the password algorithms.
  • Please read and understand the course policies on this site and then indicate your understanding.
  • Quiz 0 is due Tuesday, September 4, at noon. Future quizzes will be due Mondays at noon.

Homework Zero is due Tuesday, September 4, at 12:30pm (immediately after class). We will post a LaTeX solution template soon.

Yes, there are head-banging sessions this week! Please attend only the section for which you are officially registered.

August 26
Welcome! We're working hard to get everything set up here before the semester begins. Meanwhile, you may notice a few pages that refer to last year's course.

The course is full; registration is closed. If you are a CS major graduating in December 2013 and you need CS 473 to graduate, please talk to Holly Bagwell or Steve Herzog in the CS academic office as soon as possible. Otherwise, if you want to register, please add yourself to the waiting list by 5pm Tuesday, and add your name to the paper form in 1404 Siebel on Tuesday, and submit Homework 0 and Quiz 0.

Unfortunately, we do not have space to accommodate non-registered students in lectures or in head-banging sessions, at least for the first few weeks. Even if we could let people sit in the aisles (violating the fire code), there would not be enough room to fit everyone we expect to show up on the first day. Video for each lecture will be available a few hours after the lecture ends; head-banging problems will be be available each Thursday morning; anyone can sign up on the Moodle and Pizza sites; and everyone is welcome at office hours. We are also looking for an overflow room to allow non-registered students to watch the lectures live. Thanks for your patience and understanding.


Weekly schedule

Lectures
Tue Thu 11:00-12:15
1404 Siebel Center
Head-banging
Daniel and Hsien: Tue 4-5, Tue 5-6
Kent and Subhro: Wed 2-3, Wed 3-4, and Wed 5-6 
All in 1214 Siebel Center
Office hours
All in the open area outside 3303 Siebel Center
  • Jeff: Mon 9-10 and Fri 2-3, or by appointment
  • Daniel: Fri 9:30–11
  • Hsien: Wed 4-5
  • Kent: Mon 3-4
  • Subhro: Thu 12:30-1:30
Online quizzes
Usually due Mondays at noon; available on Moodle
Homework
Due Tuesdays at 12:30 in the drop boxes outside 1404 Siebel

 
Si maintenant vous me donnez une équation que vous aurez choisie à votre gré, et que vous desirez connaître si elle est ou non soluble par radicaux, je n’aurai rien à y faire que de vous indiquer le moyen de répondre à votre question, sans vouloir charger ni moi ni personne de la faire. En un mot les calculs sont impracticables.
Évariste Galois
For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run.
Alan Perlis
Algorithms are for people who don't know how to buy RAM.
Clay Shirky