Instructor:Jeff Erickson (jeffe@illinois.edu), 3304 Siebel Center- Office hours: Mon 10-11 and Thu 11-12, in the open area outside 3303 Siebel Center

Administrative assistant: Elaine Wilson, 3229 Siebel Center

Teaching assistant:Alina Ene (ene1@uiuc.edu)- Office hours: Tue 2-3 and Thu 2-3, in the open area outside 3303 Siebel Center

Course information:

Administrivia:Audience, prerequisites, reading material, etc.- Stuff you already (should) know
Course policies:Homework • Grading • Academic integrity- Grades (on Compass)
- Jeff's old lecture notes, homeworks, and exams
- Algorithm march with ninjas

Schedule and lecture notes

## Announcements

January 11:All solutions have been removed from the course web site.

December 20:

- All final exams have been graded; grades should be available on Compass. Here is the score distribution:
Mean±stdev = 38.79±9.25

A+: 61½ 58

A: 52 51.8 51½ 50 50 50 48¾ 48½ 48½ 48½ 47¾ 47½ 47½ 47¼

A-: 45½ 44½ 44½ 44½ 44¼ 44 43½ 40 39¼ 38¾ 38¾

B+: 38½ 37½ 37½ 35¾ 35½ 35½ 35½ 35 34 34 33¼ 32¾

B: 29½ 29½ 29 28¾ 28¼ 28 28

B-: 26 25¾ 25¾ 24¾ 23 21¾

F: 18½All course grades have been submitted.You should be able to retrieve your course grade online from the registrar within a day or two.

- Thanks for a great semester! Have a safe and restful winter break.

December 17:

- Solutions for the final exam are available.

December 14:

- We have finished grading all homework problems (including regrades). Please email Alina if you are missing grades in Compass, or some of your grades have been incorrectly recorded in Compass.

- Alina is holding office hours today at 2pm.

December 13:

- The
final examwill be held Tuesday, December 14, from 7pm to 10pm, in112 Chemistry Annex. The exam will cover everything covered in lecture before Thanksgiving break (no network simplex or approximation by LP rounding), with slightly more emphasis on flows, cuts, and linear programming.You may bring

two(8½"×11") sheets of paper with anything written, printed, photocopied, on both sides. No other papers, books, or electronic devices can be used. We will provide a list of NP-hard problems.If you need to take a conflict exam, you should have already made arrangements with Jeff.

November 30:

- Homework 4 has been graded. You can pick up your homework during office hours.

November 29:

- Homework 5 solutions are available.
- Homework 6 is "due" Wednesday, December 8, but not really. This is practice only, in preparation for the final exam.

November 15:

- Homework 5 problem 5 has been revised to remove some typos (indicated in red in the new version).
- Midterm 2 solutions have been revised to include alternate solutions to problems 2 and 5(a).

November 12:

- Grades for Midterm 2 are now posted on Compass. Here are statistics and very rough letter-grade equivalents:

- Mean±stdev = 29.11±8.12
- 12½ ≤ B- ≤ 18 ≤ B ≤ 23½ ≤ B+ ≤ 29 ≤ A- ≤ 34½ ≤ A ≤ 40 ≤ A+
Here are statistics and rough letter-grade equivalents for both midterms, dropping the 2 lowest problems. Because they account for only 40% of your overall coursework, these are

VERYrough predictors of your final course grade.

- Mean±stdev = 55.95±8.55 (excluding top and bottom outliers)
- 39 ≤ B- ≤ 44 ≤ B ≤ 50 ≤ B+ ≤ 56 ≤ A- ≤ 62 ≤ A ≤ 73 ≤ A+
I've already sent email to all students I think are in any danger of failing. If you are concerned about your grade, please talk to me after class this afternoon. The paper drop deadline is this afternoon at 5pm; I will be in my office after 2:30 to sign forms for students who want to drop the course.

November 8:

- Homework 5 is due Friday, November 19 (just before Thanksgiving break).

November 4:

November 3:

- Homework 4 solutions are available. Rubrics will be added soon.

Midterm 2will be held this evening from 7pm to 830pm, inEducation Building, room 2. (That's roughly one blocksounthof David Kinley Hall; please give yourself extra time to get there.) The exam will cover the following topics:You may bring one (8½"×11") sheet of paper with anything written, printed, photocopied, on both sides; however, you may not bring a microscope. No other papers, books, or electronic devices can be used. We will provide a list of NP-hard problems.

- Material covered on Midterm 1 (but this won't be the main focus)
- Greedy algorithms
- Approximation algorithms
- Randomized algorithms and data structures (including treaps, skip lists, hashing, and amplification)

There will be no lecture this afternoon.However, Jeff will be in the usual lecture room at the usual time to answer any questions.

November 2:

- Homework 3 has been graded. You can pick up your homework during office hours.

November 1:

- Jeff will have office hours from 11:30 to 12:30 today instead of 10-11. He will also hold office hours tomorrow afternoon from 2 to 3. Sorry for the last minute notice!

October 26:

- Problem 4(c) in Homework 4 has been revised; the probability of choosing
ushould be w(v)/(w(u)+w(v)).- The Homework 3 solutions have been revised to fix an off-by-one error in problem 3 ("else if deg(z) > n-5" should be "else if deg(z) > n-6") and to add some more details in problem 1.

October 23:

- Homework 3 solutions are available.

October 20:

- Homework 2 has been graded. You can pick up your homework during office hours.

October 19:

- Homework 4 is due Monday, November 1.

October 7:

- Midterm 1 has been graded; all grades have been posted on Compass. Here is the grade distribution (for all five problems), along with rough letter-grade equivalents. Red and green grades are outliers, which were removed before computing letter-grade cutoffs.
Sum of all five scores:Mean (±stdev) = 32.15 (±6.71)

A+ 49 47 46 4645 45A 41.5 40.5 39.5 39.5 38 37.5 A- 36.5 36 36 35.5 35 34.5 34 34 34 33.5 33 33 33 33 32.5 B+ 32 32 31 31 31 30 29.78 29.5 29.5 29 28.75 28.5 28.25 B 27 27 26.5 26.5 26 26 25.25 25 24 24 23.5 B- 23 22.25 21.5 19.5 F 14.75 12

- Means(±stdev) for each problem: 8.11 (±2.79), 2.87 (±2.43), 7.98 (±2.97), 8.26 (±2.56), 4.09 (±3.29)
- Median for each problem: 10, 3, 9, 9, 3
- "I don't know"s for each problem: 2, 10, 2, 3, 17

October 1:

- Solutions for Midterm 1 are available. We expect to have the exams graded by the end of next week.

- Homework 3 is due Monday, October 18.

September 28:

- Homework 2 solutions are available.

September 27:

Midterm 1will be held this Wednesday, September 29, from 7pm to 830pm, inDavid Kinley Hall, rooms 119 and 123. The exam will cover the following topics:You may bring one (8½"×11") sheet of paper with anything written, printed, photocopied, on both sides; however, you may not bring a microscope. No other papers, books, or electronic devices can be used. We will provide a list of NP-hard problems.

- Prerequisites (induction, recurrences, basic data structures)
- NP-hardness
- Divide and conquer
- Backtracking
- Dynamic programming (but
notthe advanced tricks)

There will be no lecture Wednesday afternoon.However, Jeff will be in the usual lecture room at the usual time to answer any questions.

September 26:

- Homework 1 has been graded. You can pick up your homework during office hours.

September 15:

- Homework 1 solutions are available.

September 13:

- Homework 2 is due Monday, September 27.

- And don't forget: Homework 1 is due today at 5pm. Submit your homework in the drop boxes in the basement of Siebel.

September 5:

- Homework 0 solutions have been revised; the original solution to problem 5(c) was incorrect.
Everybody now gets full credit for problem 5(c); your actual scores on problem 5(c) will be awarded as extra credit.Also, two students will be awarded extra credit for reporting the bug. And yes, this is the standard response to finding a bug in the homework solutions.

September 3:

- Homework 0 solutions are available.

September 1:

- Homework 1 is due next
~~Friday, September 10~~Monday, September 13.

August 25:

- A revision of Homework 0 is available, which addresses two issues:

- Removed a parity issue in Problem 3 that maked the problem more difficult.
We will accept solutions to either version of the problem.- Revised problem 5 to clarify the experiment: Prof. Jay is running a while loop.
- A new version of the LaTeX source is available; the previous version was missing two files.

August 25:

- Welcome!

The class is full,but if you are still interested in taking it this semester, don't panic!

- Homework 0 is due
in classnext Wednesday, September 1.

- Please read the course policies on homework, grading, and especially academic integrity. I apologize in advance for their length.
- LaTeX source for the homework (and for fake solutions) is available.
- You may find Jeff's notes on induction and solving recurrences useful.