Lecturer：jrjiang@csie.ncu.edu.tw (江振瑞)
Teacher Assistant：alg@sonslab.csie.ncu.edu.tw
Assistant Page: http://sonslab.csie.ncu.edu.tw/course/alg/module.php?name=news.php
Time: Mon. 16:00~16:50, Wed. 10:00~11:50
Place: Mon. E6-204, Wed. E6-209
TA Class: Mon. 16:50~17:50 (E6-204)
Download: Jeep2 (Java Editor for Chinese Programmer Ver. 2)
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)
  

   
Textbooks:

• 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 Books:

• Reference 1: 中文Java程式設計, 江振瑞  著, 儒林出版社
  
• Reference 2: Algorithms, R. Johnsonbaugh and M. Schaefer, Prentice Hall, 2004 (新月代理)

Scoring：

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