2017-08-24

2017-08-24

Lecture 01

2017-08-29

Lecture 02

Example problem (sorting) and example algorithms (insertion sort, merge sort). Asymptotic notations. Summations.

[notes-asymptotics.pdf]

[notes-summations.pdf]

[notes-asymptotics.pdf]

[notes-summations.pdf]

2017-08-31

Homework 1

Note: Access to the solutions document is password protected. The username is the three-digit number for this course. The password is the same as the username.

[hw01.pdf]

[hw01-sol.pdf]

[hw01.pdf]

[hw01-sol.pdf]

2017-08-31

Lecture 03

Summations. Bounding by individual terms. Bounding by adding or removing terms. Telescoping sums. Bounding by integrals.

2017-09-05

Quiz 1

Covering material from HW1. CLRS chapters 1, 2, 3, and Appendix A.

Average score: 31.6/40.0

Quiz papers may be collected from the instructor during office hours.

[quiz01-sol.pdf]

2017-09-14

Quiz 2

Covering material from HW2. CLRS Sections 4.3 and 4.4.

Average score: 34.5/40.0

[quiz02-sol.pdf]

2017-09-14

Lecture 07

More on the master theorem.

2017-09-26

Quiz 3

Covering material from HW3. CLRS Section 4.5 and Chapter 6.

Average score: 37.3/40.0

[quiz03-sol.pdf]

2017-09-26

Lecture 10

September 26 will have Quiz 3 only. No additional lecture after the quiz.

2017-09-28

Lecture 11

No class meeting in WMBB 409. Instead, please use the lecture time to watch this recorded lecture on lower bounds, in preparation for HW4 and Quiz 4.

[lect-lowerbounds.mp4]

[notes-lowerbounds.pdf]

[lect-lowerbounds.mp4]

[notes-lowerbounds.pdf]

2017-10-03

Lecture 12

Medians and order statistics. Quickselect. Linear time deterministic selection.

[notes-selection.pdf]

[notes-selection.pdf]

2017-10-05

Lecture 13

More on linear time deterministic selection.

2017-10-16

Midpoint

Last day to drop without WF

2017-10-17

Lecture 16

Treaps.

2017-10-19

Fall break

(no class)

2017-11-02

Lecture 20

Potential method for amortized analysis.

2017-11-09

Lecture 22

Fibonacci heaps: Operations and analysis.

2017-11-14

Lecture 23

Fibonacci heaps: Degree bound. Disjoint sets via linked lists. Disjoint set forests.

[notes-disjoint-sets.pdf]

[notes-disjoint-sets.pdf]

2017-11-16

Lecture 24

Disjoint sets: Path compression and union-by-rank.

2017-11-21

Lecture 25

Basic graph algorithms. Minimum spanning trees: Definitions, basics, Kruskal's algorithm.

[notes-disjoint-sets.pdf]

[notes-mst.pdf]

[notes-disjoint-sets.pdf]

[notes-mst.pdf]

2017-11-23

Thanksgiving

(no class)

2017-11-28

Lecture 26

Minimum spanning trees: Prim's algorithm. Shortest paths.

2017-11-30

Lecture 27

More on shortest paths. Negative weights.

2017-12-07

Lecture 29

NP-complete problems. End of course evaluations.

2017-12-10

Reference Sheet

The final exam will include a crowd-sourced one-page reference sheet filled with information that you, as a class, recommended.
~~To add information to the reference sheet, use this link to edit the current draft, by 11:59pm on December 10. Though I reserve the right to revise the final version, the intent is to include any information you suggest that (a) fits reasonably within the one-page format without resorting to tiny fonts, (b) is factually correct, and (c) is of general reference value, rather than a recapitulation of solutions to specific types of problems. The finalized sheet will be made available before the exam, so you will know what to expect.~~

When the deadline for edits to the reference sheet passed, the document extended well beyond the one-page limit and contained some LaTeX compile errors. I've cleaned up the parts that I could (page 1) and let the rest (page 2) stand pretty much as is. The version linked here (both pages) is the one that will be available for the final exam.

[reference-sheet.pdf]