CS/ECE 374 A — Spring 2018
Instructor
Jeff Erickson (jeffe)
Assistants
Jacob Laurel
Phillip Shih
Sahand Mozaffari
Shalan Naqvi
Srihita Vatsavaya
Umang Mathur
Andre Gou Kevin Hong
Apoorva Dixit Linda Cai
Gaurav Pasari Rajgopal
He Qu Ruiqian Yao
Jeremy McMahan  Shivam Gupta
Jonathan Xu Thomas Yu


Announcements

April 26
We have finished grading Midterm 2. Graded exams have been released on Gradescope. Here is a statistical summary, showing problem averages for all three versions, and a complete list of scores for the ♠ version. Problems in the ♡ and ♢ versions are permuted to match roughly equivalent ♠ problems; in particular, the two starred problems were identical in all three versions. Letter-grade cutoffs for ♠ scores were computed only from ♠ scores, after excluding outliers above 90% and below 25%.

traversal Dijkstra div&conq dag DP product Total
1♠* 2♠ 3♠* 4♠ 5♠
Mean 8.36 3.58 3.30 6.63 6.61 28.47
Stdev 2.14 3.46 2.13 2.90 3.68 7.87
1♡* 5♡ 3♡* 2♡ 4♡
Mean 8.25 4.43 4.93 5.33 6.87 29.82
Stdev 1.90 2.59 3.07 3.06 3.32 7.19
1♢* 5♢ 4♢* 3♢ 2♢
Mean 8.88 5.53 4.07 6.59 6.07 31.13
Stdev 1.53 3.04 3.34 3.07 4.05 9.20

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

We will post cumulative score distributions for both midterms later today.

April 25
  • "Homework" 11 is "due" Tuesday, May 1, at 8pm. This homework is entirely optional, and it is unlikely to be graded before the final exam.
  • Homework 10 solutions are available.
April 18
Homework 9 solutions are available.
April 17
Homework 10 is due Tuesday, April 24, at 8pm. This is the last graded homework before the final exam.
April 15
We've added a list of useful NP-hard problems to the end of Homework 9. You are free to use any of these in any NP-hardness proof (except for the problem you are trying to prove NP-hard). We will provide a copy of this list on the final exam.
April 13
Solutions and tentative rubrics for all three versions of Midterm 2 are available:
April 10
Homework 9 is due Tuesday, April 7, at 8pm.
April 3
Homework 8 solutions are available.
April 2
Midterm 2 will be held next Monday, April 9, from 7pm to 9pm.
  • The exam covers all material covered in Homeworks 4–8: recursion, divide and conquer, backtracking, dynamic programming, graph modeling, graph traversal, depth-first search, topological sort, and shortest paths (single-source and all-pairs). There will be no questions about minimum-spanning trees, greedy algorithms, or material introduced before Midterm 1; however, you may need to apply material from prerequisite courses (for example: binary search trees or induction).
  • Please see the exam policies.
  • The exam will take place in the Lincoln Hall Theater.
  • The conflict exam will be offered on Tuesday, April 10. If you need to take the conflict exam, please register no later than Friday, April 6.
  • Lots of study materials are available:
    • A huge collection of study problems — Please read the advice on the first page.
    • Midterm 2 from previous semesters: Fall 2014 (ignore #2 and #4), Fall 2016, Fall 2017
      Except as noted, these exams cover roughly the same material as this semester's Midterm 2, but possibly with different emphasis.
    • Additional problems are avialable at the end of the relevant lecture notes.
    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. Very few if 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.
  • 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.
March 18
March 27
Welcome back!
Homework 8 is due Tuesday, April 3, at 8pm. This is the last homework before Midterm 2.
March 13
Midterm 1 grades are now available on Gradescope.
March 12
  • Homework 7 is due Tuesday after spring break, March 27, at 8pm.
  • We have finished grading Midterm 1. We will release the grades on Gradesope later today, after we finish some final sanity/consistency checks. Meanwhile, here are some preliminary statistics; some scores may still change slightly. All statistics and letter-grade cutoffs were computed after excluding outliers above 95% and below 25%. (Gradescope will report slightly higher averages, because it does not exclude these outliers.) The statistics also include both versions of the exam; score differences between the two versions were insignificant.

    Problem #1 #2 #3 #4 #5 Total
    Mean 7.39 6.24 6.62 5.97 7.24 33.46
    Stdev 2.11 3.35 2.65 2.67 2.57 8.88

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

    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 fairly common, and differences of up to two letter grades (in either direction) are still possible.

  • The campus has extended the official drop deadline to this Friday, March 16. Students are strongly encouraged to come talk with Jeff before dropping the class. I (Jeff) will be available this Thursday 2-4 and Friday 10-12 (in addition to my usual Thursday 4-5 and Friday 4:30-5:30 office hours) specifically for students who are thinking of dropping the class and/or are seriously concerned about their midterm performance.
March 8
  • Video walkthroughs of today's lab are available on the schedule page.
  • Today's sections will be in different rooms than usual, because of EOH.
    • All labs normally meeting in 1214 Siebel (sections AYA through AYH) will meet in 256 MEB.
    • Section AYJ (1pm) will meet in 1109 Siebel.
    • Section AYK (2pm) will meet in 1131 Siebel.
March 8
Homework 5 solutions are available.
March 6
Video walkthroughs of today's lab are available on the schedule page.
March 5
  • I (Jeff) will hold extra office hours this Thursday 5-6 and Friday 10-12 (in addition to my usual Thursday 4-5 and Friday 4:30-5:30 office hours) specifically for students who are seriously concerned about their midterm performance. Please see my post on Piazza for more information.
  • Homework 6 is due next Tuesday, March 13, at 8pm.
March 2
Video walkthroughs of today's lab are available on the schedule page.
February 28
February 26
Homework 5 is due next Tuesday, March 6, at 8pm.
February 21
Solutions and tentative rubrics for Midterm 1 are available:
February 20
Homework 4 is due next Tuesday, February 27, at 8pm.
February 15
Homework 3 solutions and Lab 5 solutions are available.
February 12
Midterm 1 will be held next Monday, February 19, 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.
  • Please see the exam policies.
  • Please go to the following rooms, according to when your registered lab section begins:
  • The conflict exam will be offered on Tuesday, February 20. If you need to take the conflict exam, please register no later than Friday, February 16.
  • Lots of study materials are available:
    • A huge collection of study problems — Please read the advice on the first page.
    • Midterm 1 from previous semesters: Fall 2014, Fall 2016, Fall 2017
      These cover roughly the same material as this semester's Midterm 1, but possibly with different emphasis.
    • Additional problems are avialable at the end of the lecture notes.
    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. Very few if 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.
  • 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.
February 7
Homework 2 solutions are available.
February 6
Homework 3 is due next Tuesday, February 13, at 8pm. This is the last homework before Midterm 1.
January 31
Homework 1 solutions are available.
January 29
Homework 2 is due next Tuesday, February 6, at 8pm.
January 24
Homework 0 solutions are available.
January 23
Homework 1 is due next Tuesday, January 30, at 8pm.
January 16
  • Homework 0 is due next Tuesday, January 23, at 8pm.
  • A LaTeX template for homework solutions is available.
  • Jeff will hold office hours immediately after class this week in the ECEB lobby. We are still working on the office hours schedule for the TAs and CAs.
January 10
  • 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 (formally: lecture section AL1 and lab sections AY*). Section B, taught by Mahesh Viswanathan, has a separate web site.
  • The class is full! There is no waiting list this semester.

Course calendar

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

Lectures
Tue Thu 11:00–12:15, 1002 ECE Building
Labs
All labs meet every Wednesday and Friday.
AYA: Sahand Mozaffari  9:00–9:50 1214 Siebel
AYB: Sahand Mozaffari 10:00–10:50 1214 Siebel
AYC: Umang Mathur 11:00–11:50 1214 Siebel
AYD: Srihita Vatsavaya 12:00–12:50 1214 Siebel
AYE: Srihita Vatsavaya 1:00–1:50 1214 Siebel
AYF: Phillip Shih 2:00–2:50 1214 Siebel
AYG: Shalan Naqvi 3:00–3:50 1214 Siebel
AYH: Shalan Naqvi 4:00–4:50 1214 Siebel
— There is no lab AYI. —
AYJ: Jacob Laurel 1:00–1:50 1302 Siebel
AYK: Jacob Laurel 2:00–2:50 1302 Siebel
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