Introduction to Algorithms
The course is aimed for undergraduate students.
Goal
The aim of this course is to have a study
of efficient algorithms and data structures for computational problems. The idea is to cover a number of different methods
for construction of efficient algorithms through
studying efficient algorithms for a number of
basic computational problems.
Each problem will be described in details, and an algorithm
will be presented and analyzed if time permits. The plan is to cover the problems listed below.
The list is preliminary and might be changed depending
on the interest of the participants of the course. .
- Growth of functions and recurrences
- Heapsort, sorting in linear time, Medians.
- Randomized Quicksort. Universal Hash functions.
- Dynamic Programming, Greedy Algorithms, Amortized Analysis.
- Advanced Data Structures: B-Trees, Fibonacci Heaps,
Data Structure for Disjoint Sets.
- Graph Algorithms: Elementary Graph Algorithms, Minimum Spanning Trees,
Single-Source Shortest Paths, All-Pairs Shortest Paths, and Maximum
Flow.
- Fast multiplication using FFT.
-
Text Book: Cormen, Leiserson, Rivest and Stein,
``Introduction to Algorithms'', 3rd ed, 2009, MIT press.
- Related papers.
作業:
每一至二星期指定一作業。
成績計算:
成績計算以作業,考試成績加權合計(
手寫作業10%,隨堂小考+ 程式作業+上機考 30%, 期中考30%, 期末考 30% and Bonus.)
<sctsai@cs.nctu.edu.tw>