Electrical Engineering
Welcome Biography Research Teaching Publications Awards
Lab Professional Activities Research Projects Links

 演算法 Algorithms

Spring 2013


Instructor: 顏嗣鈞
E-mail:  yen(_at_)cc.ee.ntu.edu.tw

Time:  9:10-12:00 AM, Monday

Place: Room BL-113

Office phone: (02) 3366 3700 ext 123

Office hours: by appointment

TA:  黃至敬;  E-mail:   r00943131@ntu.edu.tw



  • 作業或是程式成績有問題,請洽助教.          如要看期末考考卷,    請於7/3 (三)下午 6-7 PM 間來博理館525室, 或email 給我 (yen@cc.ee.ntu.edu.tw).

  • 作業-程式-期中考成績  ----  期末考成績(包括各題得分)

  • Final exam (Solutions)

  • Final exam  will be held on June  17 (Monday), 9:10 -- 12:10 AM.

  • 期末考範圍:  Greedy Algorithms (pp. 414-437); Amortized Analysis (451-471); Disjoint-sets (pp. 561-572); Graph Algorithms (pp. 589-620); Minimum Spanning Trees (pp. 624-636); Shortest Paths (pp. 643-668; 700-704); Maximum Flow (pp. 708-730); NP-completeness (pp. 1048-1110); Approximation Algorithms (pp. 1106-1116)

  • Homework #4: Due June 10, 2013

  • Programming Assignment #1  (input datadue: June 20 (strict)

  • 5/13日的演算法上課時間,改由 10:10 AM開始。

  • Homework #3  (Solutions): Due May 5, 2013

  • Midterm exam (Solutions) will be held on April  15 (Monday), 9:10 -- 12:10 AM.

  • 期中考範圍 (講義Units 0 - 4 的範圍)

  • 4月13日(六) 9:10 -- 12:10 於博理館112室補課

  • Sample midterm exams (2006, solutions) (2005, solutions) (2001, solutions)

  • Homework #2 (Solutions): Due April  8, 2013

  • 因老師出國四月一日的課暫停一次以後再補課

  • Homework #1 (Solutions): Due March 18, 2013

Class Notes: (感謝張耀文教授提供主要投影片內容)


This course provides a rigorous, undergraduate level introduction to the design and analysis of algorithms. Three things you will learn:

  • Design a good algorithm

  • Analyze (and verify) it

  • Lower bounds: know when to stop.


Topics to be covered will include:


  Section Topics Contents Slides  
1 per page 2 per page
    Introduction   0.pdf 0_2.pdf  
  I Algorithmic fundamentals mathematical foundations, growth of functions, recurrences, divide-and-conquer technique 1.pdf 1_2.pdf  
  II Sorting and order statistics sorting, finding the k-th element



  III Data structures binary search trees, red-black trees 3.pdf 3_2.pdf  
  IV Advanced design and analysis techniques dynamic programming 4.pdf 4_2.pdf  
greedy algorithms 5.pdf 5_2.pdf
amortized analysis 6.pdf 6_2.pdf
  V Advanced Data structures disjoint set union/find

(DS U/F  Supplementary)





  VI Graph algorithms graph representations, searching, spanning trees, shortest paths, network flow, matching 8.pdf 8_2.pdf  
  VII NP-completeness and approximation algorithms Intractability, polynomial-time reduction, NP-complete problems 9.pdf

More on NP-C

    Supplementary Materials Solving recurrence relations

Sorting Algorithm Demo


1,   2

    Other topics computational geometry, probabilistic algorithms,  on-line algorithms, ... as time permits      



















  • Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd Ed., McGraw Hill/The MIT Press, 2009.


  • Homework/Project: 20-30%

  • Midterm exam: 35-40%

  • Final exam:  35-40% 


With the exception of group assignments, the work (including homework assignments, projects  and tests) must be the result of your individual effort. This implies that one student should never have in his/her possession a copy of all or part of another student's homework. It is your responsibility to protect your work from unauthorized access. Academic dishonesty has no place in a university, in particular, in NTUEE. It wastes our time and yours, and it is unfair to the majority of students. Any form of cheating will automatically result in a failing grade in the course and will be reported to the university.