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

     

Announcements:

  • 作業或是程式成績有問題,請洽助教.          如要看期末考考卷,    請於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 data)  due: 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.

•
1.
2.
3.

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

2.pdf

2_2.pdf

 　
　 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)

 7.pdf

7A.pdf

 7_2.pdf

7A_2.pdf

 　
　 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

 9_2.pdf 　
　 　 Supplementary Materials Solving recurrence relations

Sorting Algorithm Demo

 RR.pdf

1,   2

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

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

Textbook:

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

Grading:  

  • Homework/Project: 20-30%

  • Midterm exam: 35-40%

  • Final exam:  35-40% 

　

CHEATING:
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.

　

.