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.

Lectures: Tuesday and Thursday 9:30-10:50am. Tech Institute Lecture Room 4
Instructor: Jason D. Hartline.
Office Hours: Monday, 1pm, gather.town.

Teaching Assistants: Yifan Wu, Chenhao Zhang
Peer Mentors: Brando Socarras, Nathan White.

Office Hours: gather.town.

• Sunday, 1-2pm.
• Monday, Tuesday, Wednesday; 1-2pm, 4-5pm.

Lab Session: 

• Friday 1:00-2:50pm, Annenberg Hall G32
• Friday 3:00-4:50pm. Technological Institute LG52
• Saturday 10:00-11:50am, gather.town

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. 25% Homework, 15% Peer review, 10% Exercises, 15% Labs, 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 help with LaTeX.   Homeworks are assigned and due on Wednesday at 8pm (or as noted).  Peer reviews are assigned on Wednesday at 9pm and due Friday 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.  Using such materials when preparing graded coursework is an academic integrity violation per the policy on Internet sources.

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 Jan 3 :

• 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 Jan 10:

• 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 Jan 17:

• Dynamic Programming: Shortest Paths (with negative edge weights; Chapter 6) [Lecture 5: Shortest Paths]
• Additional Reading: Interval Pricing [Lecture 6: Interval Pricing]
• Reductions, Network flow, Bipartite Matching (Chapter 7; Guide to Reductions) [Lecture 7: Reductions, Bipartite Matching, Network Flow] 

Week 4: beginning Jan 24:

• Network flow. (Chapter 7) [Lecture 8: Network Flow, Duality, Min Cut]
• NP and intractability: NP, polynomial time reductions decision problems. (Chapter 8; Guide to Reductions) [Lecture 9: Reductions for Decision Problems] [Slides 9]

Week 5: beginning Jan 31:

• Midterm: Dynamic Programming. [Sample Midterm 1]
• NP and intractability: NP, 3-SAT,Independent Set (Chapter 8; Guide to Reductions) [Lecture 10: Independent Set, Hamiltonian Cycle, TSP, 3d-Matching] [Slides 10]

Week 6: beginning Feb 7:

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

Week 7: beginning Feb 14

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

Week 8: beginning Feb 21:

• NP Review. [NP Review]
• Midterm: NP and intractability. [Sample Midterm 2]

Week 9: beginning Feb 28:

• Approximation algorithms: TSP, metric TSP, knapsack (Chapter 11) [Lecture 16: Approximation, Metric TSP, Knapsack] [Slides 16]
• Approximation algorithms: Knapsack PTAS (Chapter 11) [Lecture 16: Pseudo-polynomial Time, Polynomial Time Approximation Schemes, Knapsack] [Slides 17]

Week 10: beginning Mar 7:

• Online algorithms: Ski-renter, Secretary (Chapter 11) [Lecture 18: Online Algorithms] [Slides 18]
• Review [Lecture 19: Final Review]

Week 11: Final Exam, Friday, Mar 18, 12-2pm. [Sample Final (not full length)]