Instructor
Jeff Erickson (jeffe)
Assistants
Chao Xu (chaoxu3)
Hsien-Chih Chang (hchang17)
Tana Wattanawaroon (wattana2)

Abigail Steitz
Alex Steiger
Connor Clark
Grant Czajkowski
Junqing Deng
Nick Bachmair

### Announcements

January 1
• All homework and exam solutions have been removed from the website. Thanks to everyone for a great semester, and I hope to see many of you in Theory II!
December 22
• As many have already noticed, the final exam has been graded, and scores have been posted to Canvas. If you have questions about your final exam, please contact Jeff after the winter break. In particular, I'm happy to show (but not give) students their final exams and to consider regrade requests during the month of January.

Here is the distribution of final exam scores. There was no significant difference between the grade distributions of the regular exam and the conflict exam, and there were no outliers above 95% or below 25%.

 A 65 63 62 62 60¾ 60½ 60½ 60¼ 60 58 58 57½ 57⅛ 56¾ 56⅛ 55¾ 55 54⅛ 54 52⅝ 52½ 51⅝ 51½ 50⅛ 50 49½ 49½ 49 48½ 47½ 46 45⅞ 45¼ 44½ 43½ 42¼ 41½ 41 40¾ 39 38⅝ 38½ 38¼ 38 38 36⅝ 36½ 35½ 34⅞ 34⅝ 34½ 33½ 33 32⅞ 32½ 32 32 31¾ 30½ 29⅞ 29½ 29 27⅞ 26⅞ 26⅛ 26 25½ 25¼ 25⅛ 22⅞ 20⅝ 18⅝

Problem 1 2 3 4 5 6 sum
Mean 14.02  4.86  7.39  6.06  4.40  6.58 43.31
Stdev 2.22 3.25 2.48 3.22 3.15 3.72 12.18

• All course grades have been computed and submitted to Banner. In partcular, all outstanding regrade requests have been processed and updated on Canvas; however, only regraded exams have been updated on Canvas. I did not enforce any CrowdGrader requirements. Because of the new the 4-point grading scale for homeworks, I did not enforce the 50% homework rule. Here is the overall grade distribution. Yes, everyone passed; no, that first number is not a typo.

 A 94.17% 83.97% 82.13% 81.80% 81.53% 81.03% 80.69% 80.44% 79.21% 78.62% 78.26% 78.05% 77.54% 75.95% 75.13% 74.56% 71.87% 71.84% 71.78% 71.47% 71.07% 70.34% 70.30% 69.76% 68.71% 67.50% 67.44% 66.77% 66.66% 66.22% 65.54% 64.62% 64.31% 62.71% 62.64% 62.41% 62.17% 61.88% 60.78% 60.24% 59.70% 59.56% 59.50% 58.64% 58.18% 57.83% 56.69% 55.26% 55.02% 54.64% 53.96% 53.46% 53.43% 53.40% 53.14% 52.91% 52.66% 52.30% 51.96% 51.11% 49.61% 48.63% 47.59% 47.56% 46.47% 46.45% 46.43% 45.44% 43.78% 41.99% 40.97% 38.18%

December 17
December 16
December 15
• The conflict final will be held tomorrow morning in 3401 Siebel.
December 14
• As I mentioned at the last class meeting on Tuesday: Each student may bring two (2) US letter (8½"×11") double-sided cheat sheets to the final exam, with anything written, printed, xeroxed, faxed, engraved, or mimeographed on both sides. I strongly recommend writing your cheat sheet by hand, using multiple colors. Otherwise, the exam is closed-everything. In particular, no medically unnecessary electronic or optical devices may be used during the exam. We will provide paper; you should bring only your cheat sheet and writing tools.
• We will provide a list of standard NP-hard problems and a list of standard undecidable languages on the exam itself. Nevertheless, we strongly recommend creating your own lists yourself on your cheat sheets.
December 12
• Jeff is running a final-exam review session this Sunday, December 14, 2-4pm, in 2405 Siebel. Please bring lots of questions!
December 7
• The conflict final exam will be held Tuesday, December 16, 8-11am. If you want or need to take the conflict exam, please fill out the registration form, even if you already filled out the scheduling survey. The registration form closes on Sunday, December 14; we will announce the location of the conflict exam on Monday, December 15.

All students are welcome to take the conflict exam, even if you do not have an official conflict, but space is limited. If we cannot accommodate everyone who wants to take the conflict exam, students with official conflicts will have priority, followed by other students in order of registration.

• All regular office hours will continue until the final exam next Tuesday evening. Jeff will hold additional office hours this Thursday 12:30-2:00 (the regular lecture time) and Monday 10-12 (instead of Wendesday).
• Jeff will hold a review session this weekend, most likely Sunday afternoon. Stay tuned for details.
• Homework 11 solutions are available.
December 6
• Next semester Jeff is teaching a pilot revision of CS 473, under the official rubric CS 498 DL1 (CRN: 61859). The revision will cover all material from the current CS 473 that is not already taught in CS 374 (this course) plus some more advanced material previously covered only in CS 573. Here is a tentative syllabus (which is probably far too ambitious): This revision will replace the current CS 473 (which is being taught for the last time next semester) as a new upper-division elective. It will also replace CS 573 (which is being taught for the last time this semester) as the standard algorithms course for graduate students.

If you're interested in taking this class (and being a guinea pig for one more semester), please register soon!

December 5
• Problem 3 on Homework 11 is now an extra credit problem. It's still doable, but it isn't quite as straightforward as we thought.
December 2
• Homework 11 is due Tuesday, December 9 at noon.
• Homework 10 solutions are available.
• Jeff will distribute ICES forms at the end of class on Thursday, December 4. Please come to at least the last 15 minutes of Tuesday's lecture to fill out the forms, even if you have already dropped the class. The teaching assistants will also distribute ICES forms in lab this week. These forms are your opportunity to offer official feedback on the course, the instructor, and the teaching assistants. Your feedback is extremely important to me and to the department, especially because this is a new course.
• At the last "lecture" on Tuesday, December 9, Jeff will answer arbitrary questions from the class (and ask a few in return). We plan to hold a review session the weekend before the final exam, so please don't limit your questions next Tuesday to exam material.
November 20
• The final exam will be held Tuesday, December 16, 7-10pm, in Psychology 23.
• If you want or need to take the conflict final exam, please fill out the conflict scheduling form no later than Tuesday, December 2, even if you do not have an official conflict. For scheduling purposes, students with official conflicts—another final exam at the same time, or more than two final exams in any 24-hour period—will have priority, but we will accommodate as many unofficial conflicts as we can. Once the conflict exam is scheduled, anyone can take it; there will be a separate registration form.
November 18
• Homework 10 is due Tuesday, December 2 at noon (after Thanksgiving break). Everyone should also submit their solution to Problem 3 on CrowdGrader by the same deadline; reviews will be due the following Thursday at noon.
• Homework 9 solutions are available.
• At the request of several students, some study/practice questions for the final exam are already available. We will add more problems to this list over time.
November 13
• Midterm 2 has been graded. Individual grades are available on Canvas, and the graded exams themselves will be returned in lab on Friday. Please carefully double-check your exam to verify that your scores have been recorded correctly.

Here is the distribution of scores. The statistics and letter-grade cutoffs exclude outliers above 95% and below 25%. Conflict exams are included in the overall statistics and letter-grade cutoffs, but not in the statistics for individual problems. (There was no significant difference between overall grade distributions for the two exams.)

 A 41½ 39½ 39½ 35½ 34½ 34 33½ 33½ 33½ 32½ 32½ 32 31½ 31½ 31½ 31 31 30½ 30 29 28½ 28½ 28½ 28 27¾ 27½ 27½ 27 27 27 26½ 26¼ 25¾ 25½ 25½ 25½ 25½ 25 25 25 25 24½ 24 23½ 23 22¼ 22⅛ 21¼ 21 21 20½ 20 20 19½ 19¼ 19¼ 18½ 18 17 17 16½ 16¼ 16¼ 15 15 14¾ 14½ 13½ 11½ 9

Problem 1 2 3 4 5 sum
Mean 6.87 6.00 2.35 5.18 4.60 24.90
Stdev 2.25 3.30 1.38 2.81 2.88 5.92

• Here are grades for both midterms combined. Letter grades are based on an average (stdev) of 54.15 (11.48), which omits a small number of outliers at the top of the curve (since otherwise only five people would have As). 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 84 81 79½ 76½ 72½ 68½ 68 67½ 67¼ 67 67 66 65¾ 65½ 65½ 65¼ 64½ 64½ 63¾ 63 63 62½ 62 60½ 60 59½ 59¼ 59 58½ 57¾ 57¾ 57¾ 56¾ 56½ 56¼ 56 55¾ 53¾ 53¾ 52⅝ 52½ 52¼ 51¾ 51½ 51 50 49¼ 49¼ 46½ 46 46 46 44¾ 44¾ 42½ 42½ 42½ 42 37¾ 36¾ 34 33½ 33 31½ 29½ 27½

November 10
• Homework 9 is due next Tuesday, November 18. Everyone should also submit their solution to Problem 2 on CrowdGrader by next Tuesday at noon; reviews will be due next Thursday at noon.
November 7
November 5
• Homework 8 solutions are available. I've been posing variants of problem 1 for more than 15 years, to more than 1000 students, and I just now noticed that the underlying graph is actually a dag! That means we can compute shortest paths in O(E) time by dynamic programming, avoiding the log factor in the running time of Dijkstra's algorithm. Sheesh! Anyone else who noticed that gets extra credit!!

• As I mentioned in class yesterday: Each student may bring one (1) US letter (8½"×11") double-sided cheat sheet to the midterm tomorrow, with anything written, printed, xeroxed, faxed, engraved, or mimeographed on both sides. I strongly recommend writing your cheat sheet by hand, using multiple colors. Otherwise, the exam is closed-everything. In particular, no medically unnecessary electronic or optical devices may be used during the exam. We will provide paper; you should bring only your cheat sheet and writing tools.
November 3
• Midterm 2 will be held next Thursday, November 6, from 7pm to 9pm, in 1404 Siebel Center. The exam will cover all material presented through Wednesday, October 29, but specificlly emphasizing the following:
• Recursive algorithms: Divide-and-conquer, backtracking, dynamic programming, greedy
• Graph algorithms: whatever-, breadth- and detph-first search; topological sorting, minimum spanning trees, shortest paths.
• Study/practice problems for Midterm 2 are available. This list intentionally includes a few problems that are too long or too difficult for exam conditions. I strongly recommend solving as many of these questions as you can under exam conditions. Please discuss these questions in your study groups, in office hours, on Piazza, and in the review sessions Wednesday and Thursday. You may also want to crowd-source solutions, for example via Google Docs.

• There will be a conflict exam, which will be offered either on Friday, November 7 or the morning of Thursday, November 6 (yes, before/during the review session). If you cannot take the regular exam for any reason, please fill out the registration survey no later than Wednesday at 5pm. Please fill out the form even if you have already talked to or emailed Jeff. We will announce the time and place by email after everyone has had a chance to register.
October 28
• Homework 8 is due next Tuesday, November 4. Because of the midterm on November 6, we are not using CrowdGrader for this homework.
• Homework 7 solutions are available.
October 24
• In addition to submitting written solutions as usual, everyone should also submit HW7 Problem 1 to CrowdGrader by next Tuesday at noon. Reviews for these CrowdGrader submissions will be due Thursday, October 30 at noon. We will follow the same submit-by-Tuesday/review-by-Thursday schedule for all future CrowdGrader assignments.
October 23
October 21
October 20
• Jeff is traveling today and tomorrow, but will hopefully be back in time for Wednesday's office hours. Hsien will give Tuesday's lecture on depth-first search.
October 15
October 14
• Homework 6 is due next Tuesday, October 21.
• In addition to turning in paper solutions as usual, each student should also submit an individual solution to Problem 2 on CrowdGrader. Detailed instructions are now available.
• To make sure everyone understands the protocols for CrowdGrader, we are holding a test run, with the question "What is 2+2?". Submissions for the test run are dues Friday, October 17 at noon, and reviews for the test run are due Monday, October 20 at noon. See the CrowdGrader instructions for details.
October 10
October 6
• Homework 5 is due next Tuesday, October 14.

• Midterm 1 has been graded. Individual grades are available on Canvas, and the graded exams themselves will be returned in lab on Wednesday. Please carefully double-check your exam to verify that your scores have been recorded correctly.

Here is the distribution of scores. The statistics and letter-grade cutoffs exclude outliers above 95% and below 25%, but include scores from the conflict exam (because they did not significantly change the outcome).

Please keep in mind that these letter grades are extremely rough predictions, based on only 20% of your overall coursework. Based on past experience (in CS 473), 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, and differences of up to two letter grades (in either direction) are are still possible.

 A 50 48 45 41 41 40 39½ 39½ 39½ 39 39 37 37 36¼ 35½ 35½ 34¾ 34½ 34½ 34 33¾ 33¾ 33¾ 33½ 32½ 32½ 32 32 31¾ 31½ 31½ 31½ 31½ 31¼ 31 31 30½ 30½ 30 30 29½ 29½ 29¼ 29 28¾ 28¼ 27¾ 27¾ 27½ 27½ 26½ 26¼ 26¼ 26 25½ 25¼ 25¼ 25¼ 24¾ 23¼ 23 22 21¼ 21 20½ 19½ 18¼ 18 17 16½ 15½ 15½ 13¼ 10¾ 9½

Problem 1 2 3 4 5 sum
Mean 7.10 6.56 6.45 2.89 6.56 29.56
Stdev 2.16 2.19 2.73 2.29 3.02 6.98

September 30
• Homework 3 solutions have been revised to correct an error in problem 3(a). Everyone will get full credit for that subproblem.
September 29
September 23
• Study/practice problems for Midterm 1 are available. This should give you a good idea of the types of questions that we will ask on the exam—in particular, there will be a series of True/False questions—but the actual exam questions may or may not be taken from this list. These problems intentionally include a few that are too long or too difficult for exam conditions. I strongly recommend solving as many of these questions as you can under exam conditions. Please discuss these questions in your study groups, in office hours, on Piazza, and in the review sessions tomorrow and Thursday. You may also want to crowd-source solutions, for example via Google Docs.

• Each student may bring one (1) US letter (8½"×11") double-sided cheat sheet to the midterm, with anything written, printed, xeroxed, faxed, engraved, or mimeographed on both sides. Otherwise, the exam is closed-everything. In particular, no medically unnecesary electronic or optical devices may be used during the exam. We will provide paper; you should bring only your cheat sheet and writing tools. I recommend multiple colors.

• Homework 3 solutions are available.
September 20
• Midterm 1 will be held next Thursday, September 25, from 7pm to 9pm, in the following rooms:
• The exam will cover all material presented through Wednesday, September 17, specifically including the following:
• Induction on strings and languages
• Regular expressions
• Context-free grammars
• DFAs and NFAs (including product and subset constructions)
• Nonregularity via infinite fooling sets
• There will be a conflict exam on Monday, September 29. If you cannot take the regular exam for any reason, please fill out the registration form at least 24 hours before the exam. (Please fill out the form even if you have already talked to or emailed Jeff.) We will announce the time and place after everyone has registered.
September 18
September 15
• Homework 3 is due next Tuesday, September 23.
• We are extending the submission deadline for the extra credit problem in HW2 to next Tuesday; the same problem appears as problem 4 in HW3. (The problem becomes easier to solve if you apply techniques used elsewhere in HW3.)
September 14
September 12
September 10
• Homework 2 is due Wednesday, September 17 at noon. Sorry for posting this late. (Hopefully I'll have a new laptop soon.)
• Today's lab handout is available.
• HW1 solutions will be posted soon.
September 2
• Homework 0 solutions are available.
• Homework 1 is due Tuesday, September 9 at noon.
• I'm still catching up on teaching this stuff for the first time, so there is still no quiz this week.
• Please make sure to submit your homework in the correct box. A few CS 374 students apparently submitted their homework into the dropboxes for CS 473. We only noticed because CS 473's Homework 0, which was also due today, has only two questions, so the only submissions for "CS 473 Hw0.3" were actually from CS 374. The rest of those students HW0s are probably lost for good; we really can't expect the 473 staff to sort through 200+ of their own submissions to find stray 374 homework.
August 26
• Homework 0 is due Tuesday, September 2 at noon. A LaTeX solution template is available for students who want to typeset their solutions.
• Yes, discussion sections will meet tomorrow.
• Canvas quizzes will start next week.
August 25
One day before class begins, only 81 students have actually registered, making this the first time since 1998 that I'm starting a required course with fewer students than seats. The 1:00 and 2:00 discussion sections are full, but there is plenty of room in the 3:00 section. If you want to take CS 374 and you have taken CS 225 but not CS 373, please come to class this week, add your name to the waiting list, and submit HW0. All majors are welcome. Students on the waiting list will be added in decreasing order of their HW0 scores. After this week, only students on the waiting list who have submitted HW0 will be allowed to register.
August 19
Welcome! We're working hard to get everything set up here before the semester begins. Meanwhile, you may notice a few broken links or pages that refer to previous courses.

If you are interested in taking this class this semester: This is only the second pilot offering of CS 374. We have deliberately limited registration to 100 CS and CE majors who filled out an interest survey in April 2014 and who have taken CS 225 but not CS 373.

If you are interested in taking this class in the future: CS 374 will be offered at full scale, with an expected registration limit of 400 students per semester, starting in Spring 2015. CS and CE majors will have first priority, but we hope that there will also be room for students with other majors.

If you are a graduate student: You should take CS 573.

### Weekly schedule (by event)

Lectures
Tue Thu 12:30-1:45
1310 Digital Computer Lab
Labs
Section 1: Wed Fri 1–2 — Tana
Section 2: Wed Fri 2–3 — Hsien
Section 3: Wed Fri 3–4 — Chao
All in 1105 Siebel Center
Office hours
In the open area outside 3304 Siebel, unless otherwise specified.
• Jeff: Wed 10–11 and Fri 4–5
• Chao: Tue 3:30–4:30
• Hsien: Wed 4–5
• Tana: Mon 12–1
Quizzes
Available on Canvas; usually due Fridays at 5pm.
Quizzes released Thursday, one week before the due date.
Homework
Due Tuesdays at noon in the drop boxes outside 1404 Siebel.
Homeworks released Monday, one week before the due date.
Graded homeworks will be returned in section on Wednesday, one week after submission.

### Weekly schedule (by day)

Monday
Homework $n+1$ released
12:00–1:00: Tana's office hours
Tuesday
12:00: Homework $n$ due in dropboxes outside 1404 Siebel
12:30–1:45: Lecture
3:30–4:30: Chao's office hours
Wednesday
Graded Homework $n-1$ returned in section
10:00–11:00: Jeff's office hours
1:00–2:00: Lab Section 1 — Tana + Connor
2:00–3:00: Lab Section 2 — Hsien + Grant
3:00–4:00: Lab Section 3 — Chao
4:00–5:00: Hsien's office hours
Thursday
Quiz $n+1$ released
12:30-1:45: Lecture
Friday
12:00: Quiz $n$ due
1:00–2:00: Lab Section 1 — Tana + Gail + Junqing
2:00–3:00: Lab Section 2 — Hsien + Nick + Alex
3:00–4:00: Lab Section 3 — Chao
4:00–5:00: Jeff's office hours

 Si maintenant vous me donnez une équation que vous aurez choisie à votre gré, et que vous desirez connaître si elle est ou non soluble par radicaux, je n’aurai rien à y faire que de vous indiquer le moyen de ré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