到訪人數:

Instructor Prof. Gwo-Boa Horng
Lectures Time: Tues. 9:10 - 12:00;
Place: Room 802
Textbook

Introduction to algorithms; Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

 

  Date    Lecture Notes Homework Reference
9/11

Lecture 01:

  * Introduction

      -- insertion sort

      -- merge sort

      -- asymptotic notation

   
9/18 No Class (颱風放假)     
9/25

Lecture 02:

  * Recurrences

  * master theorem

  * elementary data structures

  * binary search trees 

HW#1:

 *1.1-3

 *1.2-2

 *1.3-4

 *2-4(a)~(f)

 *4.4-3

 
10/2

Lecture 03:

  * Read-black trees

  * augmenting data structures

      -- interval trees

  * dynamic programming

      -- matrix chain multiplication

      -- strassen's algorithm

      -- elements of dynamic programming  

HW#2:

 *4-7

 *11-1

 *13.1-1

 *14.1-2

 
10/9

Lecture 04:

  * dynamic programming (cont.)

      -- longest common subsequence

      -- optimal polygon triangulation

  * Greedy algorithms 

      -- activity selection problem

      -- elements of greedy strategy

HW#3:

 *15.3-3

 *31.2-5

 *31.2-6

 *16.3-5

 
10/16

Lecture 05:

  * Greedy algorithms (cont.)

      -- matroid

      -- unit task scheduling

  * Amortized analysis

      -- stack, binary counter 

HW#4:

 *Prove that M' is a matroid. 

 *17.1-1

 *17.2-1

 *17.4-5

 *17-1

 
10/23

Lecture 06: 

  * Amortized analysis (cont.)

      -- aggregate method

      -- accounting method

      -- potential method

      -- dynamic table

  * Heaps

      -- binary heaps 

HW#5:

  *18.1-3

  *18.2-2

  *18.3-3

  * 7.1-1

 
10/30

Lecture 07:

  * binary heaps (cont.)

  * binomial heaps 

HW#6:

  * 7.3-3

  * 7-2(a)~(c)

  * 20.2-3

  * 20.2-7

 
11/6

Lecture 08:  

  * Fibonacci heaps

     -- basic idea

     -- potential function

     -- consolidating

     -- cut and cascading cut

     -- bounding the max degree  

HW#7:

  * 21.2-1

  * 21.2-3  

  * 21.4-1

  * 21-1

 
11/13 期中考    
11/20

  * Data structures for disjoint sets

      -- disjoint-set operations and applications

      -- linked-list representation

        weighted-union heuristic

      -- rooted tree representation

        weighted-union heuristic

        path compaction heuristic

        analysis            

HW#8:

  * 22.1-3

  * 22.2-4

  * 22.3-3

  * 22-1

 
11/27

  * Graphs and representations of graphs

      -- adjacency-list

      -- adjacency-matrix

  * Elementary graph algorithms

      -- breadth-first search

      -- depth-first search

      -- topological sort

  * Minimum Spanning trees 

      -- generic-MST

      -- Kruskal's algorithm

      -- Prim's algorithm

HW#9:

  * 5-2(a)

  * 23.1-6

  * 23-1

  * 24.2-3

 
12/4

  * Single-source shortest paths

      -- Shortest paths and relaxation

      -- Dijkstra's algorithm

      -- Bellman-Ford algorithm

      -- SSSP in DAG 

HW#10:

  * 25.2-2

  * 25.2-4

  * 25.3-6

  * 25.4-4

  * 25-1

 
12/11

  * All-pair shortest paths

      -- matrix multiplication

      -- Floyd-Warshall algorithm

      -- Johnson's algorithm

      -- general framework

  * Introduction to NP-completeness 

HW#11

  * 26.1-7

  * 26.1-9

  * 26.2-6

  * 26.3-3

  * 26-1

 
12/18

  NP-Completeness

      -- Problems, encodings, language

      -- Polynomial-time solvable, complexity class P

      -- Polynomial-time verification, complexity class NP

      -- NP-completeness and reducibility

      -- NP-completeness proofs

   SAT

        3-CNF-SAT

        CLIQUE

        VERTEX-COVER

      -- NP-completeness problems

HW#11

  * 36.2-7

  * 36.4-3

  * 36.5-6

  * 36-1 (a), (b)

 
12/25

  Approximation algorithms

      -- Performance bounds

      -- Approximation-Vertex-Cover

      -- Approximation-TSP-Tour

      -- General TSP 

   
1/1 開國紀念日    
1/8 期末考