CS 4311 Design and Analysis of Algorithms (Spring 2009)

 

 

General Information

 

Lecturer:

Wing-Kai Hon

韓永楷

 

wkhon @ cs.nthu.edu.tw / EECS 741

 

Consultation hour:  9—10am, Monday

 

Tutors:

Frank

邱聖元

 

bigbite @ gmail.com  /  綜二734

 

Consultation hour:  2—3pm, Thursday

 

 

Wisely

古宗翰

 

wiselyku @ gmail.com / 綜二717

 

Consultation hour:  9—10am, Friday

 

 

Foga

劉富翃

 

g9662587 @ oz.nthu.edu.tw / 綜二734

 

Consultation hour:  2—3pm, Monday

 

 

Jenny

劉向瑄

 

g9662647 @ oz.nthu.edu.tw / 綜二734

 

Consultation hour:  2—3pm, Wednesday

 

 

Announcement

 

Final Exam

Time:    Jun 23, 1010—1240

Scope:  Notes 17—24, 26, 27

            Homework 6, 7

 

Jun 21:

Solns for HW 6 [pdf] and 7 [pdf] posted

 

Jun 21:

Tutorial on NP-Complete [pdf] posted

 

 

Meeting Times:

Tue 1010—1200, Thu 1110—1200

 

 


 

 Course Materials

 

Lecture

Topics

Files

References

Notes by Prof BF Wang

[link]

0

Overview

[pdf]

1

Getting Started

[pdf]

2

Growth of Function

[pdf]

3

Recurrences

[pdf]

4

Heapsort

[pdf]

5

Quicksort 

[pdf]

**

Probability and Expectation

[pdf]

6

Sorting in Linear Time

[pdf]

7

Lower Bound on Comparison Sorts

[pdf]

8

Order Statistics

[pdf]

9

Dynamic Programming I    (Assembly Line,  Memoization)

[pdf]

10

Dynamic Programming II   (Matrix Chain Multiplication)

[pdf]

11

Dynamic Programming III  (Optimal BST)

[pdf]

12

Dynamic Programming IV  (Longest Common Subsequence)

[pdf]

13

Greedy Algorithm

[pdf]

14

Amortized Analysis I    (Aggregate Method)

[pdf]

15

Amortized Analysis II   (Accounting Method, Potential Method)

[pdf]

16

Amortized Analysis III  (Dynamic Table)

[pdf]

17

Binomial Heap

[pdf]

18

Fibonacci Heap I    (Insertion, Union, Extract-Min)

[pdf]

19

Fibonacci Heap II   (Decrease-Key, Delete, Max-Deg)

[pdf]

20

Disjoint Sets I   (Linked List)

[pdf]

21

Disjoint Sets II  (Union by Size, Union by Rank, Path Compression)

[pdf]

22

Graph Algorithms I   (BFS)

[pdf]

23

Graph Algorithms II  (DFS)

[pdf]

24

Graph Algorithms III (Topological Sort)

[pdf]

25

Graph Algorithms IV (Strongly Connected Components)

[pdf]

26

Minimum Spanning Trees

[pdf]

27

Single-Source Shortest Paths

[pdf]

 

Tutorial

Topics

Files

1

Classwork for Lecture 2

[pdf]

2

Writing Good Answers, Homework 1 Hints

[pdf]

3

Homework 1 Solution, Homework 2 Hints

[hw1sol] [hw2hints]

4

Random Selection

[pdf]

5

Catalan Number

[pdf]

6

Homework 4 Hints

[pdf]

7

Hirschberg’s Trick for LCS Problem

[pdf]

8

Ackermann Function

[pdf]

9

KMP Algorithm, Suffix Trees and Suffix Arrays

[kmp] [suffix-tree]

10

Theory of Computation

[pdf]

 

Assignment

Topics

Related Files

1

Basics (Searching and Sorting)

[pdf] [solution]

2

Basics (Searching and Sorting)

[pdf] [solution]

3

Sorting and Order Statistics

[pdf] [solution]

4

Dynamic Programming

[pdf] [solution]

5

Greedy Algorithm, Amortized Analysis

[pdf] [solution]

6

Advanced Data Structures

[pdf] [solution]

7

Graph Algorithms

[pdf] [solution]

 


 

 Teaching Plan

 

1

Basics

Growth of Function, Solving Recurrences

2

Sorting & Order Statistics

Heapsort, Quicksort, Bucketsort, Finding Median

3

Basic Data Structures

Red-Black Tree, Interval Tree, Hash Tables

4

Advanced Design & Analysis

Dynamic Program, Greedy Algorithm, Amortization

5

Advanced Data Structures

Binomial Heap, Fibonacci Heap, Union-Find

6

Graph Algorithms

Topological Sort, MST, Shortest Path, Max Flow

7

Selected Topics

String Matching, NP-complete, Approx Algo

 


Last updated: 21 June 2009