CS/ECE 374 A — Spring 2018
Instructor
Jeff Erickson (jeffe)
Assistants
Calvin Beideman
Ching-Hua Yu
Ian Ludden
Mingxi (Iris) Sun
Pooja Kulkarni
Rucha Kulkarni
Tana Wattanawaroon
Angad Garg
Ben Pankow
Caleb Ju
Dipro Ray
Fangwei Gao
Feng Hou
Hailey Malueg
Han Heul Jo
Peter Leung
Qilan Zhang
Shovik Guha
Zhekun Zhang


Announcements

February 2
All final-exam regrade requests have been processed, and all resulting grade changes have been submitted to the registrar.
January 22
Here is a revised list of letter grades, which reflects several changes due to final exam regrades and additional extra credit points. (Not all regrade requests have been processed, so even this list is not final.)

A+ A+ A+ A+ A+ A+ A+ A+ A+ A+ A+ A+ A+ A+ A+
A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A  A 
A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A– A–
B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+ B+
B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B  B 
B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B– B–
C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+
C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C  C 
C– C– C– C– C– C– C– C– C– C– C– C– C– C– C– C– C– C– C– C–
D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+ D+
D  D  D  D  D  D  D  D  D  D  D  D  D  D  D  D  D 
D– D– D– D– D– D– D– D– D– D– D– D– D– D– D–
F  F  F  F  F  F  F  F  F  F  F 
January 18
All solutions have been removed from the web site.

As a reminder: final-exam regrade requests can be submitted for one more week. Existing requests are still being processed; thanks for your patience.

Thanks everyone for a great semester!

January 1
For reference, here is the grade distribution for all three exams combined. These scores include only students who took both regular midterms and the regular final exam; all scores have been rounded down to the nearest ½ point. Estimated letter grade cutoffs are based on a mean (±stdev) of 110.00 (±26.00), determined by the students who took all three regular exams, excluding outliers at both ends of the curve as usual.

 A  161 157 157 156½ 156½ 156 154 154½ 153½ 153 152 152 152 151 150 149 149 149 148½ 148 148 145 145 144 144 144 144½ 143 142 141 141 140 140½ 140½ 140 139 139 138 138 138½ 138 138 137½ 137 136 136½ 136½
 B  136 135 134 134½ 134 133 133 132 132½ 132½ 132 131 131 131 130 130½ 130 130 129½ 128 128 128 127 127 127 127 126½ 126 126 125; 125 124 124 123 123 123 123½ 123½ 123½ 123 123 122 122 121 121 121 121 121 121 121 121 120½ 120½ 120½ 119 119 119 118 118 118½ 118½ 118 117 117½ 117 117 117 115 115 115½ 115 114½ 114½ 114 114 113 113 113½ 112 112 111 111 111½ 111 110 110½
 C  109 109 109 108 108½ 108 108 107 106½ 105 105 105 105 105½ 105½ 105 105 104½ 104½ 104½ 104 104 103 103 103 102 101½ 101 101 101 100½ 100 100 99 99 99 98 98½ 98 98 97 97½ 96 96 96 96 95½ 95½ 95 94 94 94½ 93 93½ 93 92 91 90 89 89 89½ 89 89 89 89 88 88½ 88 87½ 87½ 87 87 86 86½ 86½ 86 86 85 85 84 84
 D  83 81½ 81 80 80 79 78 78 78½ 77½ 77 76 75 75 75 73 73½ 73 73 71½ 71½ 70 69½ 69 68½ 68 68 67½ 66 66 63 63½ 63½ 62 62 61 59 58 58
 F  55 53 51 50 49 49 46 42 42½ 42 40

December 28
Course grades have been submitted.
  • Here is the list of all letter grades. I computed letter-grade cutoffs from the raw scores of students who took all three regular exams, using the my usual grading algorithm; the overall mean±stdev was 72.07%±11.82%. I then adjusted individual averages upward to account for extra credit, disparities between different exam versions, and the fact that this semester’s cohort of students was noticeably stronger on average than previous semesters‘.

    Some course grades may still increase due to final exam regrades. However, letter grade cutoffs are now frozen; regrading one student's final exam cannot affect another student's grade.

    The actual list of letter grades has been revised; see above.

  • Here is a scatterplot showing the (complete lack of) correlation of homework scores (horizontal) and exam averages (vertical). More than half the class had a homework average over 90%. One student earned an overall grade of D– despite having a 98% homework average; another earned an A– with only a 61% homework average.
December 21
  • Solutions to the final exam are available.
  • Solutions to the conflict final exam are available.
  • The final exam has been graded. All graded exams are now available on Gradescope.
  • Regrade requests for the final exam can be submitted on Gradescope until January 24, 2020, the first Friday of the Spring 2020 semester. I (Jeff) reserve the right to ignore regrade requests whose positive outcome would not affect anyone's final course grade, and I am unlikely to start answering regrade requests until at least January 1.

  • The following statistics and rough letter-grade cutoffs for the final exam were computed after excluding outliers above 95% and below 25%. (Gradescope reports slightly higher averages, in part because it does not exclude these outliers.) These statistics include only the regular version of the final exam. Raw grades listed below have been rounded down to the nearest ¼ point.

    Problem #1 #2 #3 #4 #5 #6 Total
    Mean 13.65 6.94 6.26 6.77 6.89 3.38 43.89
    Stdev 3.24 2.51 3.66 2.61 2.71 2.66 11.71

     A  66 65½ 64¾ 64½ 64¼ 64 63½ 63½ 62½ 62¼ 62¼ 62¼ 62 62 61¾ 61¾ 61¾ 61½ 61½ 61¼ 61 60¾ 60¼ 60¼ 60¼ 59¾ 59¾ 59¾ 59¾ 59½ 59½ 59½ 59½ 59½ 59¼ 59¼ 59¼ 59 59 58½ 58¼ 58¼ 58¼ 58 58 57¾ 57¾ 57½ 57¼ 57¼ 57¼ 57 57 56½ 56½ 56¼ 56¼ 56¼ 55½
     B  55¼ 55¼ 55¼ 55 54¾ 54½ 54½ 54½ 54½ 54¼ 54¼ 54¼ 54 54 53¾ 53¾ 53¾ 53½ 53½ 53½ 53¼ 53¼ 53¼ 53 53 52¾ 52¾ 52½ 52½ 52½ 52¼ 52¼ 52¼ 52 52 51½ 51½ 51¼ 51¼ 51 51 51 50½ 50½ 50½ 50¼ 50¼ 50¼ 50¼ 50 50 49¾ 49¾ 49¼ 49¼ 48¾ 48¾ 48¾ 48¾ 48½ 48 48 47½ 47½ 47¼ 47¼ 47 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
     C  43¾ 43¾ 43¾ 43½ 43½ 43½ 43½ 43¼ 43¼ 43¼ 43 43 43 42¾ 42½ 42½ 42½ 42¼ 42¼ 42¼ 42 42 41¾ 41¾ 41¾ 41½ 41½ 41½ 41 41 41 41 40¾ 40½ 40½ 40½ 40¼ 40¼ 40¼ 40 40 39¾ 39½ 39½ 39¼ 39¼ 39 38¾ 38½ 38½ 38½ 38½ 38¼ 38¼ 38 37¾ 37¾ 37¼ 36¾ 36½ 36¼ 36¼ 36¼ 36¼ 35½ 35¼ 34¾ 34¾ 34¾ 34½ 34¼ 33¾ 33¾ 33½ 33¼ 33¼ 33 33 32¾ 32½
     D  32¼ 32¼ 32 32 32 31¾ 31½ 31½ 31½ 31 31 30¾ 30¼ 30¼ 30¼ 30 29¼ 28½ 28 28 27¾ 27¾ 27½ 27 27 26¾ 26 25 25 25 24¾ 24½ 24½ 24¼ 24¼ 23¾ 23½ 23 22½ 22¼ 22¼ 22¼ 21½ 21 20½
     F  20¼ 20 20 19¾ 19¾ 19¼ 19 19 18½ 18¼ 16¼ 15¼ 12¾ 12 7¼

    Please keep in mind that these letter grades are very crude predictions of your course grade, based on only 30% of your overall coursework.

December 9
"Homework 11" solutions are available.
December 7
The final exam will be held Friday Dcemeber 13, from 8am to 11am
  • The exam covers all material covered in Homeworks 0 through 10, plus some undecidability. Following previous semesters (see link below), the exam will consist of a large True/False section (worth 20 points) and five open-ended questions (worth 10 points each). Undecidability questions will appear only in the True/False section.
  • Please go to the following rooms, according to the time when your registered lab section meets:
    • 12:00, 1:00, or 2:00 — 1013 ECEB or 1015 ECEB
    • Everyone else — 1002 ECEB
  • The conflict final exam will be offered Monday, December 16, 8am-11am. If you need to take the conflict exam for any reason, please fill out the registration form at least 48 hours before the regular exam.
  • Please read and understand the exam policies. In particular, you are allowed to bring two double-sided hanD–written cheat sheets. We will ask you to submit your cheat sheets with your answer booklets, so please scan them before the exam if you want to keep a copy.
  • Lots of study materials are available:
  • Jeff will continue to hold extra office hours Monday 2–5 for people who are concerned about their performance on Midterm 2. (Please, no fianl-exam study questions.) All regularly scheduled office hours will continue through Thursday afternoon. Watch Piazza and the Google calendar at the bottom of this page for additional office-hour announcements.
  • Tuesday's "lecture" will be an overview of the class and a review session; Jeff will walk (quickly) through one of the previous semester's final exams.
December 4
  • Homework 10 solutions are available.
  • Jeff will hold extra office hours this Friday, December 8, 10-12 and 1-3, specifically for people who are concerned about their performance on Midterm 2, in addition to his regular 3-4 office hours.
December 3
Midterm 2 has been graded; all graded exams are now available on Gradescope.

The following statistics and letter-grade cutoffs were computed after excluding outliers above 95% and below 25%. (Gradescope reports slightly higher averages, in part because it does not exclude these outliers.) These statistics include only the regular version of the exam. Raw grades listed below have been rounded down to the nearest ¼ point.

Problem #1 #2 #3 #4 #5 Total
Mean 8.17 5.91 6.52 7.21 4.24 32.06
Stdev 2.13 3.69 3.79 2.92 3.36 8.77

 A  50 50 50 50 50 49½ 49 49 49 49 48½ 48 48 48 48 48 48 47 47 47 47 47 46½ 46½ 46½ 46 46 46 46 46 46 46 46 45 45 45 45 45 44½ 44½ 44 44 43½ 43 43 43 43 43 42 42 42 42 42 42 41½ 41½ 41 41 40½ 40½ 40½ 40½ 40½
 B  40 40 40 40 40 40 40 40 40 40 40 39½ 39½ 39½ 39½ 39½ 39½ 39½ 39 39 39 39 39 39 38½ 38½ 38½ 38¼ 38 38 38 38 38 38 38 38 38 37¾ 37½ 37½ 37 37 37 37 36¾ 36½ 36½ 36½ 36 35½ 35½ 35½ 35¼ 35 35 35 35 35 35 35 35 35 34½ 34½ 34½ 34½ 34½ 34½ 34½ 34 34 34 34 34 33 33 33 33 32½ 32½ 32½ 32½ 32½ 32½ 32¼
 C  32 32 32 32 32 31½ 31½ 31½ 31½ 31½ 31¼ 31¼ 31 31 31 31 31 31 31 31 31 31 31 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 27¼ 26½ 26½ 26½ 26½ 26½ 26½ 26½ 26½ 26¼ 26 26 25½ 25½ 25½ 25½ 25½ 25½ 25¼ 25 25 24¾ 24½ 24½ 24½ 24½ 24½ 24 24 23½ 23½ 23½ 23½ 23½
 D  23 23 23 22½ 22 22 22 22 22 21½ 21½ 21 21 21 21 20½ 20 19½ 19½ 19 19 18 18 17½ 17½ 17½ 17½ 16½ 16½ 16½ 16 16 15½ 15½ 15 15 15 15 15 15 14¾
 F  14½ 14 13½ 13½ 10½ 10½ 10½ 10 8½ 7½ 7½ 7 6½ 6 5

Here is the grade distribution for both midterms combined. The raw totals include only students who took both regular midterms, and they have all been rounded down to the nearest ½ point. Letter grade cutoffs are based on a mean (±stdev) of 62.55 (±16.36), determined by the students who took both regular midterms, excluding outliers at both ends of the curve as usual.

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

Please keep in mind that these letter grades are still very rough predictions of your final course grade, based on only 40% of your overall coursework. Past experience suggests that most students‘ final course grades will be within one letter grade of these estimates, but differences of up to a full letter grade (in either direction) are fairly common.

Finally, here is a scatterplot of Midterm 1 scores versus Midterm 2 scores, normalized to lettergrade boundaries. This data includes only students who took both regular midterms, including outliers.

December 2
  • Homework 11 is available. These are practice problems only, not for submission. We will release solutons next Monday.
  • The final exam is next Friday, December 13, from 8am to 11am. We will most more information about the final exam shortly.
  • We are tentatively planning to offer a conflict final exam either later on December 13, or on the following Monday, December 16; however, the actual date and time will depend on when students who need the conflict exam are available. If you need to take the conflict final exam, please fill out the registration form no later than this Friday, December 6.
November 20
  • Homework 9 solutions are available.
  • Rather than introduce a new difficult topic right before Thanksgiving break, we are making a few changes to the rest of this week's schedule:
    • Thursday's "lecture" will be a review session for NP-hardness.
    • Friday's lab will be more practice with NP-hardness proofs.
    • We have removed Problem 3 from Homework 10.
    • We will start discussing undecidability after the break.
November 19
Homework 10 is due Tuesday after break, December 3, at 8pm. HW10 is the last graded homework before the final exam. This brings us to 33 assigned homework problems; only your top 24 scores will count toward your final course grade.
November 14
Homework 8 solutions have been available for a while, but I forgot to add the link here.
November 13
November 12
Homework 9 is due next Tuesday, November 19, at 8pm.
November 10
Scribbles and video from today's Midterm 2 review session are available.
November 9
Jeff will hold another midterm review session this Sunday, November 10, from 2pm to 4pm, in 1404 Siebel, not the usual ECEB lecture hall. Please bring questions! (The review session will be recorded for those who can't attend.)
November 2
Midterm 2 will be held next Monday, November 11, from 7pm to 9pm.
  • The exam covers all material covered in Homeworks 4 through 8: Recursion, divide and conquer, backtracking, dynamic programming, graphs, traversal/connectivity/reachability, topological sort, strong components, and shortest paths. No questions on minimum spanning trees.
  • Please read and understand the exam policies.
  • Please go to the following rooms, according to the time when your registered lab section meets. (The times are jumbled to distribute everyone into unqueal room sizes.)
    • 9:00 or 11:00 — 213 Gregory Hall
    • 10:00, 4:00, or 5:00 — 180 Bevier Hall
    • 12:00, 1:00, 2:00, or 3:00 — 100 Noyes Lab
  • The conflict exam will be offered on Tuesday, November 12, either 10-12 or 11-1. (Tuesday's lecture will be recorded.)
    • If you need to take the conflict exam, please fill out the registration form no later than Friday, November 8.
    • If you need to take the conflict but you have additional conflicts both immediately before and immediately after the 374 lecture on November 11, please fill out the registration form no later than Wednesday, November 6.
  • Lots of study materials are available: These should give you a good indication of the types of questions that we will ask on the exam, but they should also convince you that there are infinitely many reasonable questions of each type. It is unlikely that any of these exact problems will appear on the exam. We will not distribute solutions for these problems. In past semesters, students collaborated on a shared Google Doc with solutions. (However, not all those solutions were correct.)
  • There is no lecture this Thursday, and there are no labs this Friday; instead, we will hold optional review sessions at the regular lecture and lab times. Please bring questions. In particular, please feel free to ask questions from the list of study problems.
  • Jeff is trying to arrange an additional review session on Saturday. Stay tuned for details.
October 30
Homework 7 solutions are available.
October 29
Homework 8 is due next Tuesday, November 5, at 8pm. This is the last homework before Midterm 2.
October 27
Homework 6 solutions have been updated to include a significantly faster algorithm for problem 1.
October 23
Homework 6 solutions are available. (Problem 3 is the one that can be solved using a greedy algorithm.)
October 21
October 17
Midterm 1 has been graded; all graded exams are now available on Gradescope.

The following statistics and letter-grade cutoffs were computed after excluding outliers above 95% and below 25%. (Gradescope reports slightly higher averages, in part because it does not exclude these outliers.) These statistics include only the regular version of the exam. Raw grades listed below have rounded down to the nearest ¼ point.

Problem #1 #2 #3 #4 #5 Total
Mean 6.69 4.92 6.45 5.84 5.10 28.90
Stdev 2.13 2.69 2.33 1.93 3.31 8.08

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

Please keep in mind that these letter grades are extremely rough predictions of your final course grade, based on only 20% of your overall coursework. Past experience suggests that most students‘ final course grades will be within one letter grade of these estimates, but differences of up to a full letter grade (in either direction) are quite common, and there are a few differences of two letter grades or more (in either directions) every semester.

Students are strongly encouraged to come talk with Jeff before dropping the class. Jeff will be available Thursday 1-4 and Friday 9-12 and 1-5, specifically for students who are thinking of dropping the class and/or are seriously concerned about their midterm performance.

October 16
Homework 5 solutions are available.
October 14
Homework 6 is due next Tuesday, October 22, at 8pm.
October 9
Homework 4 solutions are available.
October 8
Homework 5 is due next Tuesday, October 15, at 8pm.
October 1
September 29
Scribbles and video from yesterday's review session are available.
September 25
Homework 3 solutions are available.
September 23
Jeff will offer an additional optional midterm review session this Saturday from 1pm to 3pm in ECEB 1002. We will walk through a complete sample midterm during Thursday's review session. Please bring your own questions to the review sessions on Friday and Saturday.
September 21
Midterm 1 will be held next Monday, September 30, from 7pm to 9pm.
  • The exam covers all material covered in Homeworks 0, 1, 2, and 3: Induction, regular languages, regular expressions, DFAs, NFAs, product and subset constructions, fooling sets, regular language transformations, and context-free grammars. No questions on Turing machines; no questions on Han and Wood's algorithm.
  • Please read and understand the exam policies.
  • Please go to the following rooms, according to the time when your registered lab section meets:
    • 9:00, 10:00, or 11:00 — 314 Altgeld
    • 12:00, 1:00, or 2:00 — 100 MSEB
    • 3:00, 4:00, or 5:00 — 100 Gregory Hall
  • The conflict exam will be offered on Tuesday, October 1, either 10-12 or 11-1. (Tuesday's lecture will be recorded, and it's motly review anyway.)
    • If you need to take the conflict exam, please fill out the registration form no later than Friday, September 27.
    • If you need to take the conflict but you have additional conflicts both immediately before and immediately after the 374 lecture on October 1, please fill out the registration form no later than Wednesday, September 25.
  • Lots of study materials are available: These should give you a good indication of the types of questions that we will ask on the exam, but they should also convince you that there are infinitely many reasonable questions of each type. It is unlikely that any of these exact problems will appear on the exam. We will not distribute solutions for these problems. In past semesters, students collaborated on a shared Google Doc with solutions. (However, not all those solutions were correct.)
  • There is no lecture this Thursday, and there are no labs this Friday; instead, we will hold optional review sessions at the regular lecture and lab times. Please bring questions. In particular, please feel free to ask questions from the list of study problems.
September 18
Homework 2 solutions are available.
September 16
Homework 3 is due next Tuesday, September 24, at 8pm. This is the last homework before Midterm 1.
September 11
Homework 1 solutions are available.
September 10
  • Homework 2 is due next Tuesday, September 17, at 8pm.
  • Jeff is out of town for a conference all next week (Sep 15–21), but class will still meet as usual. Chandra Chekuri will give Tuesday's lecture (Sep 17), and Ian Ludden will given Thursday's lecture (Sep 19).
September 5
Homework 0 solutions are available. (Sorry, I should have posted these Wednesday morning.)
September 2
Homework 1 is due next Tuesday, September 10, at 8pm.

Starting with this homework, groups of up to three people can submit joint solutions for each problem. Each problem should be submitted by exactly one person, and the beginning of the homework should clearly state the Gradescope names and email addresses of each group member. In addition, whoever submits the homework must tell Gradescope who their other group members are.

August 28
As expected, the class is now full.
August 26
  • Homework 0 (tex source) is due next Tuesday, September 3, at 8pm.
  • A LaTeX homework solution template is available.
  • All homework in this class will be submitted on Gradescope; please enroll yourself using the code MKNYRY. You are welcome to enroll on Gradescope using any name and email address you like; however, if you decide not to register with your real name and university email address:
    • Please consistently use your Gradescope name on all submitted work for the entire semester, including group homeworks submitted by other people.
    • Please register your Gradescope identity so that we can give you credit for your work.
  • Jeff will hold office hours in the ECEB lobby immediately after this week's lectures. We are still working out permanent times and location for office hours; watch the course calendar and Piazza for more information.
August 12
  • Welcome! We're working hard to get everything set up here before the semester begins. Meanwhile, you may notice several broken links or pages that refer to previous courses.
  • There are two independent sections of CS/ECE 374 this semester. This is the web site for Section A. Section B, taught by Nikita Borisov, has a separate web site.
  • Registration is currently restricted, and will open to all students on August 26. Experience strongly suggests that the class will reach capacity very quickly. There is no waiting list. Registration will close permanently after the September 9 self-service add deadline.
  • Do not try to change lab sections through Self-Service. You may find yourself locked out of the course, because another student took the slot that you "temporarily" vacated. Instead, ask one of the advisors in the CS or ECE academic office to make the switch for you.

Course calendar

All office hours are in the open area outside 3304 Siebel, unless specified otherwise.

Lectures
Tuesdays and Thursdays and 11:00–12:15 in 1002 ECE Building
Labs
Wednesdays and Fridays in 1105 Siebel. Yes, the section labels are out of order.
ADA: Ian 9:00–9:50
ADB: Tana 10:00–10:50
ADC: Rucha 11:00–11:50
ADD: Ching-Hua 12:00–12:50
ADF: Pooja 1:00–2:00
ADH: Calvin 2:00–2:50
ADK: Calvin 3:00–3:50
ADE: Iris 4:00–4:50
ADG: Ian 5:00–5:50
Office hours:
See the Google calendar above.
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 10 days of submission.

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