.: Overview
This course is about algorithms both sequential and
parallel. We will explore how to design an algorithm, how to
prove that it is correct, how to measure its performance, how to
improve its performance. Both the theoretical and practical aspects are
studied in this course.
.: Objective
This is one of the foundation courses for any computer-related majors. After completing this course, students should have a basic practical understanding of the following:
1. How to evaluate algorithms based on their characteristics.
2. How to prove the correctness of an algorithm
3. How to design a correct algorithm
4. How to improve the performance of an algorithm
.: Approach
Students are required to read through the textbooks before attending each class. Throughout the course, theoretical exercises and programming exercises will be systematically analyzed and discussed. Additional assignments will be given to expand the knowledge beyond the textbooks.
.: Reference
The main textbook for this course is
We occasionally refer the following references for additional materials.
- (JE) Jon Kleinberg and Éva Tardos, Algorithm Design, Addison-Wesley, 2006 (ISBN 0-321-37291-3)
- (RM) Richard Johnsonbaugh and Marcus Schaefer, Algorithms, Prentice Hall, 2004 (ISBN 0-13-122853-6)
.: Course Outline
The following schedule is tentative only; it may change depending on the circumstances.
| Week | Topics | Book Section |
|---|---|---|
| 1 | Introduction | SP: Ch 1 - 2 RM: Ch 1 |
| 2 | Mathematics for Algorithms | SP: Ch 3 - 5 RM: Ch 2 |
| 3 | Data Structure: Linear |
SP: Ch 6 RM: Ch 3 |
| 4 | Data Structure: Non-linear | SP: Ch 7 RM: Ch 3 |
| 5 | Divide and Conquer | SP: Ch 8 RM: Ch 5 |
| 6 | Searching | SP: Ch 11 RM: Ch 4 |
| 7 | Sorting and Selection | RM: Ch 6 |
| 8 | Midterm | - |
| 9 | Greedy Algorithm | SP: Ch 10 RM: Ch 7 |
| 10 | Dynamic Programming | SP: Ch 9 RM: Ch 8 |
| 11 | Randomization | SP: Ch 12 |
| 12 | P and NP | SP: Ch 13 RM: Ch 10 - 11 |
| 13 | Parallel and Distributed Algorithm | - |
| 14 | Concurrency | - |
| 15 | Sequential and Parallel | - |
| 17 | Final Exam | - |
Note that the above schedule is tentative by nature; it may change at the instructor's discretion.
.: Evaluation
The course evaluation will be divided equally between examinations
and assignments. The distribution of each half is shown below.
| Items | Weight |
|---|---|
| Individual Assignments | 15% |
| Group Assignments | 15% |
| Discussion | 15% |
| Game Participation | 15% |
| Midterm Exam | 20% |
| Final Exam | 20% |
Please make sure that you have carefully read and understand the academic policy.
Note that the above description is only tentative; it may change at the instructor's discretion.