EECS 477: Introduction to Algorithms
Fall 2002
Syllabus
Chapter and section numbers below refer to Brassard and Bratley text.
- Introduction: notation and basics, proofs,
mathematical induction : two lectures, Ch.1
- Elementary algorithmics, problems vs instances,
computational models : two lectures, Ch.2
- Asymptotic notation : two lectures, Ch.3
- Analysis of control structures, barometer, average-case: one
lecture, Ch.4.1-4.4
- Recursion, solving recurrencies, master theorem: two
lectures, Ch.4.7, (and Cormen et
al. 4.3)
- Data structures, graphs, heaps, union-find: two
lectures, Ch.5
- Greedy algorithms, MST, graph traversal, knapsack: two
lectures, Ch.6.1-6.5, parts of Ch.9
- Midterm on Thursday, October 24th
- Divide and conquer, linear time median: one
lecture, Ch.7
- Dynamic programming, making change, knapsack, Floyd's
algorithm, traveling salesman: two lectures, Ch.8
- Graphs and games, branch and bound: two lectures
- Linear programming, FFT: one lecture, handout
- Computational complexity, lower bounds,
information theoretic, adversary arguments: one lecture
- Decision problems, reduction, complexity classes, P and NP, SAT,
SAT3, SAT2, HAM vs Eulerian paths: two lectures,
Ch.12
- Heuristic and approximate algorithms, metric TSP,
approximate knapsack: one
lecture, Ch.13
- Final exam tentatively on Tuesday, December 17th
Basic information
Course Material
- Required text: ``Fundamentals of Algorithms'' by
Brassard and Brately, Prentice Hall 1996
- Recommended additional text: ``Introduction to Algorithms'' by
Cormen, Leiserson, Rivest (and Stein -- 2nd ed.), all editions are ok.
Prerequisites
Students must have taken EECS 203 (Discrete Structures)
and EECS 380(281) (Algorithms and Data Structures),
or equivalents. Programming experience in C or C++ is required.
Some assignments in this class may require the understanding of C++/STL,
but not necessarily designing large programs in C++.
If you only know Pascal or Java (or some other language), talk to Prof. Guskov.
Grading
Final grades will be based on the total points earned on the projects and
exams. Grading will be on the curve.
Factors such as class participation may be used to adjust your final
grade, especially if it falls on a borderline.
The tentative point breakdown is as follows:
- Homework: 25%
- One project: 25%
- One midterm: 25%
- Final: 25%
PLASE SEE COURSE WEBPAGE FOR MORE INFORMATION
Copyright © 2002 Igor Guskov