2017FA_EECS_336-0_SEC20 Design & Analysis of Algorithms

2017FA_EECS_336-0_SEC20 Design & Analysis of Algorithms

EECS 336: Introduction to Algorithms

[cover]

Required Text: Kleinberg and Tardos, Algorithm Design, 2005.
Discussion/Announcements: on Piazza.
Homework: on Mechanical TA. (Mechanical TA guidelines)

Lectures: Tuesday and Thursday 3:30-4:50pm in Tech LR3.
Instructor: Jason D. Hartline.
Office Hours: Thurs. 11-12pm; Ford 3-329.

Teaching Assistants: Yiding Feng, Isaac Lee, Zhiping Xiu
Lab Sections: Monday,

  • 10am, 11am, Tech M166.
  • 2pm, 3pm, Annenberg G32.

Office Hours: Mudd 2174

  • Zhiping: Wed. 10-11am.
  • Yiding: Wed. 11-12pm.
  • Isaac: Tues. 2-3pm.

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, 25% Peer review, 30% Midterms, 15% Final, 5% Participation.

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 submission in Mechanical TA.  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 Thursdays at midnight (or as noted).  Peer reviews are assigned on Thursdays at shortly after midnight and due Sunday at midnight.  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 automatically dropped.  See Homework Preparation Guidelines.

Tentative Schedule:

Week 1: beginning Sept. 18

Week 2: beginning Sept. 25

Week 3: beginning Oct. 2

Week 4: beginning Oct. 9

Week 5: beginning Oct. 16

Week 6: beginning Oct. 23

Week 7: beginning Oct. 30

Week 8: beginning Nov. 6

Week 9: beginning Nov. 13

Week 10: beginning Nov. 20

Week 11: beginning Nov. 27

Course Summary:

Date Details