一、課程說明 (Course Description)

There are many problems around us, and they need somefastandgoodmethods to be solved. For instance,

(i) Suppose that we have been very lazy the last few weeks,

and suddenly, we find that 10 homeworks A,B,C,D,E,..., J

will be due next week. The homeworks have different deadlines,

and some will be on Monday, some will be on Friday.

We have an estimation of how fast we can finish each homework.

Questions: Can we finish all of them?

If so, which one should we do first, which one next?

(ii) Suppose that our school has 100 landmarks (such as the library,

the EECS building, the main gate, etc), and you want to design

a system so that if a user enters any two landmarks (say, A and B),

your system can immediately suggest a shortest route from A to B.

Of course, you can find all the 100x100 routes by yourself, but

it would be better if you can write a computer program to do it

for you. Is there any efficient computer program for this problem?

To solve a particular problem, there are usually many different methods.

For instance, in Problem (i), we can try all possible arrangements of the

homeworks A,B,C,D,E, ... and see if they can all be finished in time.

However, we need to try 10! arrangements, and this would take a long time.

On the other hand, if we want to finish all the homeworks, it seems that

we should do the one whose deadline is nearest first, and then do the one

whose deadline is second nearest, and so on. There may be other methods

we can try. One question arises: Among all methods, is there one which

is always faster and better than the others?

In this course, we will look at a lot of fundamental problems that are solved

daily around us, and we will study their solutions (that is, the methods or

thealgorithms, and show how toanalyzethe performance of the

solutions. We will also introduce general techniques to help us design a good

algorithm when we face a new problem.

二、指定用書 (Text Book)

Introduction to algorithms, 2nd edition, the MIT press, 2001

by T. Cormen, C. E. Leiserson, and R. L. Rivest

三、參考書籍 (References)

1. Introduction to the Design and Analysis of Algorithms,

by R. C. T. Lee, R. C. Chang, S. S. Tseng, and Y. T. Tsai

更多參考書籍 (More References)

2. Algorithms in C++, (or Algorithms in Java), by R. Sedgewick

3. The Art of Computer Programming, by D. E. Knuth

四、教學方式 (Teaching Method)

Lectures and Tutorials (Lectures in English)

五、教學進度 (Syllabus)

I. Mathematical Foundations

1. Introduction

2. Growth of Functions

3. Summations

4. Recurrences

II. Sorting and Order Statistics

6. Heapsort

7. Quicksort

8. Sorting In Linear Time

9. Medians and Order Statistics

III. Data Structures: Self Study

IV. Advanced Design and Analysis Techniques

15. Dynamic Programming

16. Greedy Algorithms

17. Amortized Analysis

V. Advanced Data Structures

19. Binomial Heaps

20. Fibonacii Heaps

21. Data Structures for Disjoint Sets

VI. Graph Algorithms

22. Elementary Graph Algorithms

23. Minimum Spanning Trees

24. Single-Source Shortest Paths

25. All-Pairs Shortest Paths

26. Maximin Flow

VII. Selected Topics

28. Matrix Operations

32. String Matching

34. NP-Completeness

35. Approximation Algorithms

**. Branch-and-Bound

六、成績考核 (Evaluation)

5 Assignments: Best four * 37%

Remaining one * 3%

Midterm Quiz: 10%

Final Exam: 50%

-----------------------------------

Total 100%

Remark: You can discuss with your classmates and exchange

high level ideas in completing your homework.

However, youmustcomplete your homework

by yourself, using your own wordings.

If someone is caught copying the others or letting

the others to copy, we will adopt the following policy:

1. If caught for the first time,50%is multiplied

to the overall assignment scores.

E.g., If your scores in the assignments, quiz, and final

exam are originally 30/40, 6/10, and 35/50,

respectively. Then, the adjusted score will be:

15/40, 6/10, 35/50, so that in total, it becomes

56/100.

2. If caught for the second time,0%is multiplied

to the overall assignment scores.

E.g., If your scores in the assignments, quiz, and final

exam are originally 30/40, 6/10, and 35/50,

respectively. Then, the adjusted score will be:

0/40, 6/10, 35/50, so that in total, it becomes

41/100.

Our tutors are very nice and they will give you (reasonable) hints and

supports if you encounter difficulties in completing the assignment.

They are also very responsible in ensuring fairness, so that they will

try their best to catch students who are copying the others.

七、可連結之網頁位址 (Web links)

To be announced