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 9:30-10:50am in Annenberg G21.
Instructor: Jason D. Hartline.
Office Hours: Wed. 1-2pm; Mudd 3015.

Teaching Assistants: Paula Kayongo, Michalis Mamakos
Peer Mentors: Siyuan Chai, Richard Huang
Lab Sections: Monday, 

• 10:00-10:50, Tech L168
• 11:00-11:50, Tech L168
• 1:00-1:50, Tech M120

Office Hours: Mudd 3532

• Monday 2-4pm (Richard, Timothy)
• Tuesday 4-6pm (Richard, Siyuan)
• Wednesday 3-4pm (Michalis)
• Friday Siyuan 2-3pm (Siyuan)

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 Wednesday at midnight (or as noted).  Peer reviews are assigned on Thursday morning and due Friday at 5pm.  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.

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 April 1:

• 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 April 8:

• 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 April 15:

• 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 April 22:

• 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 April 29:

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

Week 6: beginning May 6.

• 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 May 13.

• NP and intractability: NP, CIRCUIT-SAT, LE3-SAT (Chapter 8) [Lecture 12: Deriving NP (cont)]
• Greedy algorithms: interval scheduling (Chapter 4) [Lecture 13: Greedy, Interval Scheduling]

Week 8: beginning May 20:

• Greedy algorithms:  minimum spanning trees, matroids. (Chapter 4, matroid-notes.pdf) [Lecture 14: Greedy, MSTs, Matroids]
• Approximation algorithms: TSP, metric TSP, knapsack (Chapter 11) [Lecture 15: Approximation, Metric TSP, Knapsack]

Week 9: beginning May 27:

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

Week 10: beginning June 3:

• Approximation algorithms: Knapsack PTAS (Chapter 11) [Lecture 17: Pseudo-polynomial Time, Polynomial Time Approximation Schemes, Knapsack]
• Online algorithms: Ski-renter, Secretary (Chapter 11) [Lecture 18: Online Algorithms]

Week 11: beginning June 10:

• Final: Cumulative, Thursday, 12pm-2pm.