EECS 336: Introduction to Algorithms

Required Text: Kleinberg and Tardos, Algorithm Design, 2005.
Discussion/Announcements: on Piazza.
Instructor Contact: send private message to Instructors on Piazza.
Homework: Logistics and Policies, Homework Guide, Peer Reviewing Guide, Canvas Issues.

Lectures: Tuesday and Thursday 2:00-3:20am in Annenberg G21.
Instructor: Jason D. Hartline.
Office Hours: TBA; Mudd 3015.

Teaching Assistants: Yingkai Li
Peer Mentors: Lily Barghi, Siyuan Chai, Alisa Liu
Lab Sections: Monday, 

• 11:00-11:50, Tech LG68
• 12:00-12:50, Tech LG68
• 1:00-1:50, Tech LG62
• 2:00-2:50, Tech LG62

Office Hours:

• Sunday, 4-6pm (Tech LG52)
• Tuesday, 8-10pm (Mudd 3534)
• Wednesday, 2-4pm (Mudd 3534)
• Thursday,  4-5pm (Mudd 3534)
• Friday, 2-4pm (Mudd 3534)

Overview. Algorithm design and analysis is fundamental to all areas of computer science and gives a rigorous framework for the study optimization. This course provides an introduction to algorithm design through a survey of the common algorithm design paradigms of greedy optimization, divide and conquer, dynamic programming, network flows, reductions, and approximation algorithms. Important themes that will be developed in the course include the algorithmic abstraction-design-analysis process and computational tractability (e.g., NP-completeness).

Prerequisites. EECS 212 (Mathematical Foundations of Computer Science) and EECS 214 (Data Structures and Data Management) which cover abstract data types such as stacks, queues, and binary search trees; and discrete mathematics such as recurrence relations, sets, and graphs.

Grading. 30% Homework, 15% Peer review, 10% Lab Sections; 30% Midterms, 15% Final.

Homework Policy. Homeworks are recommended to be done in groups of two; students must not work in groups greater than two.  Both students must contribute to the solution of all problems. Pairs should submit one typed copy of each problem to its corresponding assignment on Canvas (instructions).  Both students will receive the same grade for the submission.  Assignments must be typed and LaTeX is recommended (see LaTeX Hints). You may consult your text book and course notes when answering homework questions; you must not consult the Internet or other students except for getting ther than for help with LaTeX.   Homeworks are assigned and due on Friday at 8pm (or as noted).  Peer reviews are assigned on Friday at 9pm and due Sunday at 8pm.  Late homework and peer reviews will be not be accepted.  All homework problems and peer reviews will be equally weighted in your final grade with the exception of your lowest three of each which will be dropped.  See Homework Preparation Guidelines.

Notice: Uploading materials from this course to websites that sell such content to students is prohibited by Northwestern’s academic integrity policies, and may also put you at risk for violating copyright policies in Northwestern’s Student Conduct Code.

Tentative Schedule:

Lecture notes from a previous year are posted.  These will be updated with this years notes shortly before each lecture.

Week 1: beginning Sept 23:

• Course overview: computing Fibonacci numbers. (Chapter 1) [Lecture 1: Fibonacci Numbers]
• Philosophy of algorithms, review of runtime analysis. (Chapters 2 and 3) [Lecture 2: Philosophy, Tractability, Big-Oh]

Week 2: beginning Sept 30:

• Dynamic programming: memoization, weighted interval scheduling (Chapter 6) [Lecture 3: Dynamic Programming]
• Dynamic programming: integer knapsack, uniform pricing [Lecture 4: Finding Subproblems] (Chapter 6; Guide to Dynamic Programming (pdf)).

Week 3: beginning Oct 7:

• Dynamic Programming: Shortest Paths (with negative edge weights; Chapter 6) [Lecture 5: Shortest Paths]
• Dynamic Programming: interval pricing (Chapter 6) [Lecture 6: Interval Pricing]

Week 4: beginning Oct 14:

• Reductions, Network flow, Bipartite Matching (Chapter 7; Guide to Reductions) [Lecture 7: Reductions, Bipartite Matching, Network Flow] 
• Network flow. (Chapter 7) [Lecture 8: Network Flow, Duality, Min Cut]

Week 5: beginning Oct 21:

• Midterm: Dynamic Programming. [Sample Midterm 1]
• NP and intractability: NP, polynomial time reductions decision problems. (Chapter 8; Guide to Reductions) [Lecture 9: P versus NP]

Week 6: beginning Oct 28.

• NP and intractability: NP, 3-SAT,Independent Set (Chapter 8; Guide to Reductions) [Lecture 10: Independent Set, Hamiltonian Cycle, TSP, 3d-Matching]
• NP and intractability: Independent Set, Hamiltonian Cycle (Chapter 8) [Lecture 11: Deriving NP]

Week 7: beginning Nov 4.

• NP and intractability: NP, CIRCUIT-SAT, LE3-SAT (Chapter 8) [Lecture 12: Deriving NP (cont)]
• NP Review [Lecture 13: NP Review]

Week 8: beginning Nov 11:

• Greedy algorithms: interval scheduling (Chapter 4) [Lecture 14: Greedy, Interval Scheduling]
• Greedy algorithms:  minimum spanning trees, matroids. (Chapter 4, matroid-notes.pdf) [Lecture 14: Greedy, MSTs, Matroids]

Week 9: beginning Nov 18:

• Midterm: NP and intractability. [Sample Midterm 2]
• Approximation algorithms: TSP, metric TSP, knapsack (Chapter 11) [Lecture 15: Approximation, Metric TSP, Knapsack]

Week 10: beginning Nov 25:

• Approximation algorithms: Knapsack PTAS (Chapter 11) [Lecture 17: Pseudo-polynomial Time, Polynomial Time Approximation Schemes, Knapsack]
• Thanksgiving

Week 11: beginning Dec 2:

• Online algorithms: Ski-renter, Secretary (Chapter 11) [Lecture 18: Online Algorithms]
• Final: Cumulative.