Algorithms
Fall 2001
Syllabus
Instructor: Hsu-Chun Yen
Class: Monday 2:10--5:00 PM
Office: EE 540
Phone: 23635251 - 540
E-mail: yen@cc.ee.ntu.edu.tw
Office Hours: By appointment
Check the grades of your homeworks, midterm, and final exams.
Make-up lecture: 9:10 -- 12:00 AM,
Saturday, Jan. 5, 2002, Room 225.
Midterm Exam: Monday, Nov. 19, 2001,
2:10 -- 4:10 PM, Room EE106.
midterm exam;
solution;
Final Exam: Monday, January 14, 2002,
2:10 -- 3:50 PM, Room EE106.
final exam;
solution;
Term Project: (Due: January 24, 2002;
absolute deadline)
(References:
Graph Drawing ;
VLSI Placement )
Homework: #1 (due: Nov. 12, 2001); solution (.pdf)
Homework: #2 (due: Dec. 10, 2001); solution (.doc)
Homework: #3 (due: Jan. 5, 2002); solution (.doc)
Should you have any questions regarding the grading of your homeworks,
please contact the TA (Mr. Lin) at `b85029@pchome.com.tw'
Class Notes:
Prerequisites:
Familiarity in C, C++, or PASCAL.
Required Textbook:
Introduction to Algorithms, by
T. Cormen, C. Leiserson, and R. Rivest, McGraw-Hill.
Topics:
- Preliminaries.
Recurrence relations. Order Notation.
- Algorithm design & analysis techniques.
Greedy. Divide-and-conquer. Dynamic programming.
Amortized analysis.
- Graph algorithms.
Depth first search. Breadth first search. Minimum spanning
trees. Shortest paths.
- NP-completeness.
Models of computation.
Cook's theorem.
Proving NP-completeness.
Coping with NP-completeness.
- Approximation algorithms.
Bin packing.
Traveling salesman problem. Vertex cover.
- Parallel algorithms.
PRAM model. Parallel algorithm design.
- String matching.
- Computational Geometry.
Intersection and point location problems.
Convex hulls.
- Network Optimization Problems.
The maximum flow problem and the max-flow/min-cut theorem.
The Ford-Fulkerson algorithm.
- As time permits, topics from
Distributed algorithms
(Mutual exclusion, Leader election, Termination detection,
Global snapshot)
On-line algorithms (Competitive analysis,
List update problem, K-server problem),
and Probabilistic algorithms.
Course Requirements:
There will be homework assignments, one midterm exam, a final exam, and
programming projects.
The weightings within the semester grade will be:
Homework & Prog. Project: 25%
Midterm exam: 35%
Final exam: 40%
Homework:
Only homework turned in by the due date is guaranteed
to be graded. Any special circumstances that cause difficulty in
meeting the deadlines should be brought to the attention of the
instructor in advance.
Cheating:
With the exception of group assignments, the work (including
homework, programming assignments, tests) must be the result of your
individual effort. This implies that one student should never have in his/her possession
a copy of all or part of another student's homework.
It is your responsibility to protect your work from unauthorized access.
Academic dishonesty has no place in a university, in particular, in NTUEE.
It wastes our time and yours, and it is unfair to the majority of students.
Any form of cheating will automatically result in a failing grade in
the course and will be reported to the Dean's office.
Announcements:
Visit http://www.ee.ntu.edu.tw/~yen/courses/algorithm01.html
regularly for announcements (including homework assignments,
homework solutions, exame dates, and more) of this class!!!