EECS 336: Introduction to Algorithms (Fall 2015)
Lectures: Tuesday and Thursday 3:30-4:50 in Tech L211.
Instructor: Jason D. Hartline.
Office Hours: Tuesday, 2:00-2:50, or by appt.; Ford 3-329.
Teaching Assistant: Sam Taggart
Lab Sections: Monday and Tuesday, various times.
Office Hours: Wednesday, 10:30-12:00; Tech F281
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 randomized 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. 50% Homework, 15% Midterm, 25% Final, 10% Participation.
Homework Policy. Homeworks may be done in pairs by students in the same discussion section. Both students must contribute to the solution of all problems. Pairs should submit one typed copy of each problem to its corresponding assignment submission in Canvas. Both students will receive the same grade. Assignments must be typed - LaTeX is recommended. You may consult your text book and course notes when answering homework questions; you must not consult the Internet other than for help with LaTeX. (See LaTeX Hints.) Homeworks are assigned in class on Thursday and due the week after on Thursday at 11:59pm (or as noted). Late homework will be accepted until Sunday at 11:59pm and will be marked down by 25% of the grade received. See Homework Preparation Guidelines.
Week 1: beginning Sept. 21
- Course overview: computing Fibonacci numbers. (Chapter 1) [Lecture 1: Fibonacci Numbers]
- Review of runtime analysis, graphs, and basic graph algorithms. (Chapters 2 and 3) [Lecture 2: Philosophy, Tractability, Review]
Week 2: beginning Sept. 28
- Greedy algorithms: interval scheduling. (Chapter 4) [Lecture 3: Greedy and Interval Scheduling]
- Greedy algorithms: minimum spanning trees, matroids. (Chapter 4) [Lecture 4: Greedy and MSTs]
Week 3: beginning Oct. 5
- Greedy algorithms: greedy by value, matroids (Chapter 4, matroid-notes.pdf) [Lecture 5: Greedy, MSTs, Matroids]
- Dynamic Greedy: shortest paths, MSTs (Chapter 4) [Lecture 6: Dynamic Greedy, Shortest Paths, MSTs]
Week 4: beginning Oct. 12
- Divide and conquer: merge sort, recurrence relations, public key cryptography, repeated squaring (Chapter 5) [Lecture 7: Divide and Conquer]
- Divide and conquer: integer multiply, convolution, fast Fourier transform (Chapter 5) [Lecture 8: Fast Fourier Transforms]
Week 5: beginning Oct. 19
- Dynamic programming: memoization, weighted interval scheduling (Chapter 6) [Lecture 9: Dynamic Programming]
- Dynamic programming: integer knapsack, uniform pricing [Lecture 10: Finding subproblems] (cf. Chapter 6).
Week 6: beginning Oct. 26
- MIDTERM. [Review for Midterm]
- Dynamic Programming: Shortest Paths (with negative edge weights; Chapter 6) [Lecture 11: Shortest Paths, Revisited]
Week 7: beginning Nov. 2
- Reductions, Network flow, Bipartite Matching (Chapter 7) [Lecture 12: Reductions, Bipartite Matching, Network Flow]
- Network flow. (Chapter 7) [Lecture 13: Network Flow, Duality, Min Cut]
Week 8: beginning Nov. 9
- NP and intractability: NP, polynomial time reductions decision problems. (Chapter 8) [Lecture 14: P versus NP]
- NP and intractability: NP, 3-SAT, Hamiltonian Cycle (Chapter 8) [Lecture 15: NP, 3-SAT, Hamiltonian Cycle]
Week 9: beginning Nov. 16
- NP and intractability: Independent set (Chapter 8) [Lecture 16: INDEP-SET, CIRCUIT-SAT, 3-SAT]
- NP and intractability: NP, CIRCUIT-SAT, 3-SAT (Chapter 8) [Lecture 17: NP, CIRCUIT-SAT, 3-SAT]
Week 10: beginning Nov. 23
- Approximation algorithms: TSP, metric TSP, knapsack (Chapter 11) [Lecture 18: Approximation, Metric TSP, Knapsack]
Week 11: beginning Nov. 30
The syllabus page shows a table-oriented view of the course schedule, and the basics of course grading. You can add any other comments, notes, or thoughts you have about the course structure, course policies or anything else.
To add some comments, click the "Edit" link at the top.