CS/ECE 374
Instructors
Alexandra Kolla (akolla)
Jeff Erickson (jeffe)
Assistants
Alex Steiger
Chao Xu
Charles Carlson
Konstantinos Koiliaris
Mark Idleman
Spencer Gordon
Tana Wattanawaroon
Yipu Wang
Charles Shang Matthew Faust
Edward Chou Osayd Abdu
Eun Jae Kim Ping-Ko Chiu
Fanbo Xiang Qixuan Li
Graham Ellis Robert Andrews
Kevin K. Lin Roy Young Li
Krishna Mittal Sushan Jiang
Maidi Lin Yisong Yue


Announcements

December 28
December 15
Tonight's final exam will be held in the following rooms. Please go to the room indicated by the first few letters of your last name:
December 13
December 7
A large collection of study problems on NP-hardness and undecidability is available. The final exam will also cover material from earlier in the semester; please see the practice problems for Midterm 1 and Midterm 2.
December 6
Jeff's office hours this afternoon and next Wednesday are 3pm-4pm, instead of 4pm-5pm. Jeff will also be available this afternoon from 5 to 5:30. Sorry for the late notice!
December 5
December 1
Here is the distribution of scores from Midterm 2. The letter-grade cutoffs were computed after excluding outliers above 95% and below 25%.

 A  46¼ 45 44½ 44 44 44 43½ 43¼ 43 43 42¾ 42½ 42¼ 42 41¾ 41 41 41 40¾ 40¾ 40¾ 40½ 40 40 40 39¾ 39¾ 39½ 39¼ 39 39 39 39 39 39 38¾ 38¾ 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 35¾ 35¾
 B  35½ 35½ 35½ 35½ 35½ 35½ 35⅜ 35¼ 35¼ 35¼ 35 34¾ 34¾ 34¾ 34¾ 34½ 34½ 34½ 34½ 34½ 34¼ 34¼ 34 34 34 34 34 33¾ 33½ 33½ 33½ 33½ 33¼ 33¼ 33¼ 33 33 33 33 33 33 32¾ 32¾ 32¾ 32¾ 32¾ 32¾ 32½ 32½ 32½ 32¼ 32¼ 32⅛ 32 32 31¾ 31¾ 31¾ 31⅝ 31½ 31½ 31½ 31¼ 31¼ 31 31 31 31 30⅞ 30¾ 30¾ 30¾ 30½ 30½ 30½ 30½ 30½ 30½ 30½ 30½ 30½ 30½ 30½ 30¼ 30 30 30 30 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½ 28¼
 C  28 28 28 28 28 27¾ 27¾ 27¾ 27¾ 27¾ 27¾ 27¾ 27½ 27½ 27½ 27½ 27½ 27⅜ 27⅜ 27¼ 27¼ 27¼ 27¼ 27⅛ 27 27 27 27 27 27 26¾ 26¾ 26¾ 26¾ 26¾ 26¾ 26½ 26½ 26½ 26½ 26½ 26½ 26½ 26½ 26½ 26½ 26⅜ 26¼ 26⅛ 26 26 26 25¾ 25¾ 25½ 25½ 25½ 25½ 25¼ 25⅛ 25 25 25 25 24⅞ 24¾ 24½ 24½ 24¼ 24¼ 24⅛ 24⅛ 24 24 23¾ 23¾ 23¾ 23¾ 23⅝ 23½ 23½ 23½ 23⅜ 23¼ 23¼ 23¼ 23⅛ 23⅛ 23 23 23 23 23 23 23 22¾ 22½ 22¼ 22¼ 22¼ 22⅛ 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¾
 D  20½ 20½ 20½ 20½ 20⅜ 20¼ 20⅛ 20⅛ 20 20 20 20 20 19⅞ 19¾ 19¾ 19¾ 19¾ 19⅝ 19½ 19 19 19 19 19 19 19 18⅞ 18¾ 18¾ 18¾ 18¾ 18⅝ 18½ 18½ 18½ 18½ 18⅛ 18 18 18 18 17⅞ 17⅞ 17⅝ 17½ 17½ 17¼ 17 16⅞ 16⅝ 16½ 16½ 16½ 16¼ 16⅛ 16 16 16 15¾ 15¾ 15¼ 15 15 14¼ 14⅛ 14 14 14 14 13⅝ 13½ 13¼ 13¼
 F  12½ 12½ 12⅜ 10½ 10 9⅞ 9½ 9¼ 9¼ 8 7⅛ 3

Here is the distribution of combined midterm scores, counting all ten problems. Again, letter-grade cutoffs were computed after excluding outliers above 95% and below 25%. Please remember that these are still very crude estimates of your overall course grades, based on only 40% of your graded work. Past experience suggests that most students’ final course grade will be within one letter grade of this estimate, but larger differences (in both directions) are still fairly common.

 A  94 93¾ 93 93 92½ 92 90½ 90 88½ 88 87¼ 86¼ 86¼ 86¼ 85½ 84½ 84¼ 84 83¾ 83¾ 83½ 83½ 83 82¾ 82⅝ 82½ 82¼ 82⅛ 81½ 80¾ 80¾ 80¾ 80½ 79½ 79 78¼ 78 78 78 78 77¾ 77¾ 77¼ 77¼ 77¼ 77 76¾ 76½ 76 76 75¾ 75½ 74¾ 74½ 74½ 74⅜ 74¼ 74 73¾ 73½ 72¾ 72½ 72½ 71¾ 71¼ 71 71 70¾ 70¾ 70¼ 69¾ 69 69 68¾ 68¾ 68½ 68½ 68¼
 B  68 68 67½ 67½ 67¼ 67 66¾ 66¼ 66¼ 66 66 65¾ 65½ 65⅜ 65¼ 65¼ 65 65 64½ 64½ 64½ 63¾ 63⅝ 63¼ 63¼ 63⅛ 63 62½ 62¼ 62 61¾ 61¾ 61¾ 61⅝ 61⅝ 61½ 61¼ 61¼ 61 61 60¾ 60½ 60½ 60¼ 60¼ 60¼ 59¾ 59¾ 59⅝ 59½ 59½ 59½ 59¼ 59¼ 59¼ 59¼ 59⅛ 59 59 58½ 58¼ 58 57¾ 57¾ 57¾ 57¾ 57¾ 57¾ 57⅝ 57½ 57½ 57¼ 57¼ 57 57 56⅞ 56⅞ 56¾ 56½ 56½ 56½ 56¼ 56¼ 56¼ 56⅛ 56 56 56 56 55½ 55¼ 55 55 55 55 54¾ 54¾ 54¾ 54½ 54⅜ 54¼ 54⅛ 54 54 54 53⅜ 53¼ 53 53
 C  52¾ 52¼ 52¼ 52 51¾ 51½ 51½ 51½ 51½ 51½ 51⅛ 51 51 51 50⅞ 50¾ 50¾ 50¾ 50⅝ 50½ 50¼ 50 49⅞ 49¾ 49¾ 49¾ 49¼ 49¼ 49⅛ 49 48⅞ 48⅞ 48¾ 48⅝ 48½ 48¼ 48 47⅞ 47¾ 47¾ 47⅝ 47½ 47¼ 47⅛ 47 47 47 46⅞ 46¾ 46¾ 46¾ 46¾ 46¾ 46¾ 46½ 46½ 46½ 46½ 46½ 46¼ 46 45⅞ 45¾ 45¾ 45⅜ 45¼ 45¼ 45¼ 45 45 45 44¾ 44¾ 44½ 44½ 44½ 44¼ 44¼ 44¼ 44¼ 44¼ 44 43½ 43½ 43⅜ 43¼ 43¼ 43¼ 43⅛ 42¾ 42¾ 42¾ 42½ 42½ 42¼ 42¼ 42 41½ 41½ 41½ 41¼ 41 41 40⅞ 40¾ 40¾ 40¾ 40¾ 40¾ 40¾ 40½ 40¼ 40¼ 40¼ 40 40 39⅝ 39½ 39¼ 39¼ 39 39 39 38⅞ 38⅞ 38¾ 38½ 38½ 38¼ 38⅛ 38 38 38 37¾ 37¾ 37¾ 37⅝ 37½ 37½ 37⅛ 37⅛ 36⅞ 36¾ 36¾ 36⅜
 D  36⅛ 36⅛ 36 36 36 35⅞ 35¾ 35⅝ 35¼ 34¾ 33⅞ 33¾ 33¾ 33⅜ 33¼ 32¾ 32¾ 32¼ 32¼ 32⅛ 32 31⅞ 31½ 31½ 30¾ 30½ 30½ 30½ 30 29⅞ 29¾ 29¾ 29¾ 29¾ 29¾ 29⅝ 29½ 29¼ 29¼ 29 29 29 28¾ 28⅝ 28⅜ 28¼ 27¾ 27⅝ 27½ 26¾ 26½ 26½ 26½ 26¼ 26¼ 25⅞
 F  24¾ 24¾ 24½ 23½ 22⅞ 21¼ 20¾ 20¾ 18¾ 18¾

Finally, here is a scatter plot showing the surprisingly weak correllation between Midterm 1 and Midterm 2 scores. For both exams, scores have been normalized to the number of standard deviations above or below the mean, or equivalently, the number of letter grades above or below the B–/C+ boundary. (I recomputed the letter-grade cutoffs after excluding outliers in the sum-of-midterms distribution.) Notice that several students’ midterm scores differ by more than two full letter grades, in both directions.

November 30
November 29
We will distribute ICES forms in lecture this Thursday and in labs this Friday. Please come to at least the last 15 minutes of Thursday's lecture and your regular Friday lab section to fill out the forms, even if you do not regularly attend class/lab, and even if you have already dropped the class. These forms are your opportunity to offer official feedback on the course, the instructors, and the teaching assistants. Your feedback is extremely important to us and to the department, especially because this course is still relatively new.
November 23
Homework 9 solutions have been updated. As many people pointed out, the reductions in problem 2 were reversed in the original posted solutions. Following course policy, everyone will get a perfect score for HW9.2 as extra credit. Hanny Thanksgiving!
November 16
November 8
Solutions and tentative rubrics are available for Midterm 2:
November 7
November 3
Homework 8 solutions are available.
October 31
Midterm 2 will be held next Monday, November 6, from 7pm to 9pm.
October 29
Homework 5 grades are now available on Gradescope.
October 27
October 26
Homework 7 solutions are available.
October 25
October 19
October 13
The drop deadline is this Friday, October 14, at 5pm. Jeff will hold extra office hours from 9am to noon on Friday in 3304 Siebel, specifically for students who are trying to decide whether to drop the class and/or who are concerned about their midterm performance. (No questions about homework or recent course material, please.)
October 12
October 11
October 10
October 6
October 4
Homework 5 is due Tuesday, October 11, at 8pm.
September 28
Solutions and tentative rubrics for Midterm 1 are available.
September 27
September 24
All conflict exams for Midterm 1 have now been scheduled. If you registered for a conflict exam and have not received email telling you when and where your conflict exam will be held, please send Jeff email as soon as possible.
September 21
Homework 1 grades are now available on Gradescope.

We noticed several Homework 1 submissions where the person who submitted the homework did not also submit their other group members’ names. If you did not submit your group’s homework, please double-check that you actually received a grade, and if you didn’t ask the person who submitted the homework to updat the group list. (Yes, you can still do this now.) It is your responsibility to make sure the person who submits your group’s homework also submits your name. We cannot give you credit if your name is not attached to your work.

September 20
Homework 3 solutions are available.
September 18
Midterm 1 will be held next Monday, September 26, from 7pm to 9pm.
September 14
Earlier today, Jeff requested registration overrides for ALL remaining students on the waiting list who submitted HW0, HW1, and HW2.

Some of those overrides will be offered immediately, but most will have to wait until more students drop the class. But because less than 390 students submitted HW2, we are confident that everyone on the waiting list will eventually get in. (The self-imposed September 19 deadline will not be enforced.)

A few students on the waiting list did not submit HW1 and/or HW2; those students were removed from the waiting list.

If you believe you are still on the waiting list and you do not receive email from Jeff today, please let us know as soon as possible!

September 14
September 13
Homework 3 is due next Tuesday, September 20, at 8pm. This is the last homework before Midterm 1.
September 7
Homework 1 solutions are available.
September 6
Homework 2 is due next Tuesday, September 13, at 8pm.
September 2
August 31
August 30
Apparently squirrels* got into the projector cables in ECEB 1002, so Alexandra had to lecture at the blackboard. Unfortunately, the lecture video does not pick up the board work, but it does include the audio, and lectures slides are still available.

*No, not really. It was actually aliens.

August 29
August 27

August 25
August 22
There are no office hours today. Regular Monday office hours start next week.
August 18
August 15

Regular weekly schedule

Lectures
Tue Thu 11:00–12:15, 1002 ECE Building
Labs
All labs meet every Wednesday and Friday.
Section A: Spencer 9:00–9:50 1304 Siebel
Section B: Yipu 10:00–10:50 1304 Siebel
Section C: Charlie 11:00–11:50 1304 Siebel
Section D: Chao 12:00–12:50 1304 Siebel
Section E: Alex 1:00–1:50 1304 Siebel
Section F: Tana 1:00–1:50 1105 Siebel
Section G: Mark 2:00–2:50 1304 Siebel
Section H: Konstantinos  2:00–2:50 1105 Siebel
— There is no section I. —
Section J: Mark 3:00–3:50 1304 Siebel
Section K: Konstantinos  3:00–3:50 1105 Siebel
Office hours:
All in 3300G Siebel (the open area near 3304) or 214 Ceramics
Yipu Monday 11–12 3300G Siebel
Alex Monday 3–4 3300G Siebel
Charlie Monday 4–5 3300G Siebel
Jeff Wednesday 11–12 and 3–4 3300G Siebel
Alexandra Wednesday 1:30–2:30  3300G Siebel
Mark Thursday 1–2 3300G Siebel
Spencer Thursday 3–4 214 Ceramics
Konstantinos  Friday 12:30–1:30 3300G Siebel
Chao Friday 4–5 3300G Siebel
Tana Friday 5–6 214 Ceramics
Homework
Due Tuesdays at 8pm, uploaded to Gradescope
Homeworks are released at least one week before the due date.
Under normal circumstances, graded homeworks should be returned within two weeks of submission.
Quizzes
For review and self-study only; no deadlines and no effect on final course grade
Not this semester

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