課程大綱

課程資訊

課程名稱

演算法
ALGORITHMS

開課學期

97-2

授課對象

理學院數學系

授課教師

張鎮華

課號

MATH7708

課程識別碼

221 U4360

班次

學分

全/半年

半年

必/選修

選修

上課時間

星期二3,4(10:20~12:10)星期四1(8:10~9:00)

上課地點

舊數103舊數103

備註

總人數上限：30人

Ceiba 課程網頁

http://ceiba.ntu.edu.tw/972Algorithm

課程簡介影片

核心能力關聯

核心能力與課程規劃關聯圖

課程大綱

為確保您我的權利,請尊重智慧財產權及不得非法影印

課程概述

Subjects to be taught in this course include most important parts of the following topics:
(1) General introduction to the theory of algorithm.
(2) Sorting and ordered statistics.
(3) Data structures—stack, queue, linked list, tree, hash table, heap etc.
(4) Designs and analysis techniques of algorithms.
(5) Graph algorithms—DFS, BFS, minimum spanning tree, shortest path, maximum flow etc.
(6) NP-completeness and approximation algorithms.
(7) Lower bounds on numbers of arithmetic operations.
(8) Selected topics—Sorting networks, matrix operations, linear programming, fast Fourier transform, RAS public key cryptosystem, string matching, computational geometry etc.

課程目標

The study of algorithms is at the heart of the computer science. In recent years, a number of significant advances in the field of algorithms have been made. These advances have ranged from the development of faster algorithms to the startling discovery of certain natural problems for which all algorithms are inefficient. These results have kindled considerable interest in the study of algorithms, and the area of algorithm design and analysis has blossomed into a field of intense interest. The intent of this course is to teach fundamental results in this area, including the unifying principles and underlying concepts of algorithm design.

課程要求

預期每週課後學習時數

Office Hours

指定閱讀

參考書目

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to
Algorithms, Second Edition, 2002.

A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer
Algorithms, Addison-Wesley, Reading, Mass., 1976.

U. Manber, Introduction to Algorithms--A Creative Approach, Addison-Wesley,
Reading, Mass., 1989.

R. Sedgewick, Algorithms, Second Edition, Addison-Wesley, Reading, Mass.,
1988.

評量方式
(僅供參考)

No.	項目	百分比	說明
1.	Midterm Examination	35%	The midterm exmaintion is to be held on Week 9.
2.	Final Exmintaion	35%	The final exmination is to be held on Week 18.
3.	Homework	30%	Homework will be assigned every week.

課程進度

週次	日期	單元主題
第1週	2/17,2/19	General introduction to the theory of algorithm. (Up to Cormen Page 25; Page 48.)
第2週	2/24,2/26	General introduction to the theory of algorithm. (Up to Cormen Page 73; Skip Page 74--120.) Hepsort (Up to Cameron Page 137.)
第3週	3/03,3/05	Sorting and ordered statistics (Up to Cormen Page 170, Page 185.)
第4週	3/10,3/12	Sorting and ordered statistics. Data Structure (Cormen up to Page 207, Page 220, Sketch Hash Tables Pages 221-252.)
第5週	3/17,3/19	Data structures—stack, queue, linked list, tree, hash table, heap etc. (Up to Cormen Page 279, Page 301.)
第6週	3/24,3/26	Data Structure (Up to Cormen Page 318), Designs and analysis techniques of algorithms (Up to Cormen Page 369).
第7週	3/31	Designs and analysis techniques of algorithms (Up to Cormen Page 392).
第8週	4/07,4/09	Algorithm (Up to Cormen Page 404)
第9週	4/14,4/16	Midterm Exmination on 4/14 in the classes. (Up to Cormen Page 392.) Algorithm. (Up to Cormen Page 429.)
第10週	4/21,4/23	(Skip Chapters 18 to 20 in Cormen.) Chapter 21 Data structure for disjoint sets.
第11週	4/28,4/30	Graph algorithms—DFS, BFS, minimum spanning tree. (Cormen Page 527-560 and 561-579.)
第12週	5/05,5/07	Graph Algorithms. (Cormen Page 580-619 and 620-642.)
第13週	5/12,5/14	Graph Algorithms---Maximum Flow. (Cormen Page 643-669.)
第14週	5/19,5/21	NP-Completeness. (Cormen page 966--1021.)
第15週	5/26,5/28	Matrix operations.
第15週	5/26	Matrix operations. (Cormen Page 725--769.)
第16週	6/02,6/04	Numer-theoretic algorithms. (Cormen Page 849--905.)
第17週	6/09,6/11	Approximation algorithms. (Cormen Page 1022-1053.)
第18週	6/16,6/18	Computational geometry. (Final Exmination)
第18週	6/16	Final Exmination.