Teacher Assistant：

TA Class: Mon. 16:50~17:50 (E6-204)

Syllabus:

- Introduction of Algorithms (Al-Khwarizmi-1)(Al-Khwarizmi-2)(AlgIntro.zip)

- From Algorithms to Programs (Homework1)(programs)(How
to
submit a homework)

- The complexity of algorithms and the lower bounds of problems

(SortAna.zip)(Alg02.zip)(Homework2 is contained in Alg02.zip)(Quiz041004)(Answer041004) - The theory of NP-Completeness (NPC.zip) (Notice! Homework excludes Ex3.2 this week (Oct.6))

(NPC2.zip)(Special Sets in Graphs)(Recipe, cook and carp.zip)(Turing Machine.zip)

- The greedy method (Greedy.zip)(Greedy2.zip) (Notice!
Midterm Project: Write a Java Program to implement Kruskal's algorithm,
Prim's algorithm or Dijkstra's algorithm or all of them. Due date: Nov.
15 midnight.)

(Exercise 1: To prove the correctness of Prim's algorithm)

(Exercise 2: To prove the correctness of the Greedy Knapsack algorithm)

- Dynamic programming (DynamicP.zip)(DynamicP2.zip)

Homework: Exercise 8.1 in Lee's book (p 447) (Hand in hard a hard copy before the class on Nov. 3rd.)

- Midterm Examination (including all materials above) (close-book, held at 10:00AM~11:50AM on Nov. 10)(Question Sheet)
- The divide-and-conquer strategy (Divide-Conquer.zip)(Divide-Conquer2.zip)(Divide-Conquer3.zip)

(Voronoi/Delaunay Applet)(Voronoi.ppt)

- The prune-and-search strategy (Selection.ppt)

Homework: Write a Java program to implemet the prune-and-search selection algorithm (Due day: Dec 12 midnight)

(PruneAndSearch.zip)

- The branch-and-bound strategy (TreeSearch.ppt)(BranchAndBound.ppt)

Homework: Exercises 6.3 and 6.4 in Lee's book (p 346) (Hand in hard a hard copy before the class on Dec. 27.)

- Approximation algorithms (ApproximationAlgorithms.zip)(TheSetCoveringProb.ppt)

- Homework: Show that APPROX_VERTEX_COVER has ratio bound of 2. (Hand in hard a hard copy before the class on Jan. 5.)
- Homework: Consider each of following words as a set of letters: {arid, dash, drain, heard, lost, nose, shun, slate, snare, thread}. Show which set cover (for covering all appearing letters) GREEDY-SET-COVER produces when ties are broken in favor of the word that appears first in the disctionary. (Hand in hard a hard copy before the class on Jan. 5.)
- Bonous Homework: Show that GREEDY-SET-COVER has ratio bound of ln |X|+1. (Hand
in hard a hard copy
before the class on Jan. 10.)

- Final Examination (including all materials above taught after Midterm Exam.) (close-book, held at 10:00AM~11:50AM on Jan. 12)
- Hash Table (JavaDS09.ppt) (Distributed Hash Table)

Bonous Program: Design a Java Applet for a hash table using the multiple hasing mechanism. (Due Jan. 14.)

- Distributed algorithms (DistributedAlgorithms.zip)(PDCAT04.ppt)(MUREX.ppt)

Homework: Design a distributed algorithm for leader election on rings. The algorithm must be better than that introduced in the class. (Due day: Dec. 6 midnight)

- Textbook 1: 物件導向資料結構—使用Java語言, 江振瑞 著, 松崗圖書公司, 2003
- Textbook 2: Introduction to the Design and Analysis of Algorithms, R.C.T. Lee et. al., Flag Corp.
- Textbook 3: Introduction to Algorithms, Cormen et. al., MIT Press (開發代理)

- Reference 1: 中文Java程式設計, 江振瑞 著, 儒林出版社

- Reference 2: Algorithms, R. Johnsonbaugh and M. Schaefer, Prentice Hall, 2004 (新月代理)

**Midterm 35%****Final 40%****Homework, Quiz and Inclass 25% (Notice! 10%~15% for TA)**