Algorithm

jdwang@asia.edu.tw, Room:5317, ext:1847

Text Book

• Introduction to Algorithms, 2nd Edition
  • Thomas H. Cormen et al.ISBN: 0-262-03293-7,MIT Press

Reference Book

• Java 資料結構與演算法, 廖榮貴等 文魁資訊,書號：D5016, ISBN 986-125-520-6
• Data Structures, Algorithms, & Applications in Java
  • Sartaj Sahni,http://www.cise.ufl.edu/~sahni/dsaaj/webpage/java_versions.html

• Introduction to the Design and Analysis of Algorithms (International Edition)
  • Anany Levitin,Pearson, Addison Wesley,ISBN: 0-321-21076-X,ftp://ftp.aw.com/cseng/authors/levitin/

Outline ppt

Grading

• 期中考(35%)(2007.4.26, Room: 5001, 3:10pm~4:30pm)
• 平時成績(30%)
  • FTP: 210.70.82.226, login:algorithm, algorithmXXX,
    1. 建立一個個別目錄, (學號﹍姓名)
       • 上傳
  • (15%)作業(1) (Date: 2007.4.12)
    • Sorting Algorithms (Java codes, Chpater 6, Java 資料結構與演算法,)
      • Bubble Sort,  Exchange Sort,  Selection Sort ,Insertion Sort, Radix Sort, Shell Sort, Quick Sort, Merge Sort,
      • Extra: Counting Sort, Heap Sort
      • Comparison
        • Time Complexity
          • Average,
          • Worst,
        • Stability, In Place, Comments
        • (Excel 作圖)
          • (Modified by 張自勤 ) NewCode
          • Running Time vs N (the number of items for sorting, e.g. N=2^10,2^11, 2^12,..., 2^20)
          • Running Time vs Memory Size(RAM)(e.g. 256M,512M, 1G, 2G)
          • Running Time vs the value of Max key
          • Running Time (Average case、worst case and best case)
      • 心得
  • (15%)作業(2) (Date:  2007.5.31)
    • Search Algorithm Comparison (Java codes, Chpater 5, Java 資料結構與演算法 )
      • Linear Search, Binary Search, Interpolation Search, Hashing Search, Fibonacci Search
      • Time Complexity,
      • 心得
    • 說明下列方法的特性。適用於這類型方法的問題有哪些(至少舉出3個例子)？與相對的Time Complexity.
      • Dynamic Programming
        • e.g. Assembly-line scheduling problem. Time Complexity: ?O(n).
        • Matrix-Chain Multiplication
        • Longest common subsequence
      • Greedy Algorithm
        • Activity-Selection problem
        • Huffman Code
        • ...
      • Graph Problems
        • Searching Graph
          • Breadth-first Search (BFS)
          • Depth-first Search (DFS)
        • Topological Sort
        • Minimum Spanning Trees
          • Kruskal 's algorithm
          • Prim's algorithm
        • Single-Source Shortest Paths
          • The Bellman-Ford algorithm (negative weight)
          • via Topological sort
          • Dijkstra's algorithm (nonnegative weight)
        • All-Pairs Shortest Paths
          • Floyd-Warshall algorithm
• 期末考(35%)
  • Date: 2007.6.21(週四), Time: 3:10pm~4:40pm
  • place: Room 5001