University of Chinese Academy of Sciences

Course Code: B63009H

Course Name: Design and Analysis of Algorithm

Credits: 2.0

Level: Undergraduate

Pre-requisite: Programming language, Data structure

Lecture Time:40 hours

Instructors:Dongbo Bu, Jialin Zhang

Course Description

This course introduces preparatory knowledge in algorithm design and analysis including abstraction, modeling and algorithm estimation. The course intends to develop students' ability of solving practical problems with this course content. This course is designed for undergraduates with major in Computer Science and Engineering, Applied Mathematics and plays as fundamental course for other courses related with algorithm theory.

Topics and Schedule

1. Introduction (2hrs)

1.1.Insight and Analysis

1.2.Modeling

1.3.Algorithm: Design and Estimation

1. Divide and Conquer (4hrs)

2.1.Reduction

2.2.Tree Decomposition

2.3.Example: GCD(Greatest Common Divisor) Problem

1. Dynamic Programming (6hrs)

3.1.Sub-problem: Definition and Sub-structure

3.2.Advanced Dynamic Programming

3.3.Examples

         3.3.1 Matrix chain multiplication

         3.3.2 String alignment

         3.3.3 Shortest path

3.3.4 Interval Scheduling

1. Greedy Algorithm (4hrs)

4.1.From Dynamic Programming to Greedy Algorithm

4.2.Bellman-Ford, Dijkstra Algorithm

4.3.Fibonacci Heap

1. Linear Programming and Duality (4hrs)
   1. Modeling, Simplex algorithm
   2. Lagrangian Duality
2. Network Flow (4hrs)
3. Modeling
4. Ford-Fulkerson algorithm
5. Push-Relabel algorithm
   1. Reduction and NP-Completeness (4hrs)
      1. Turing machine
      2. Polynomial reduction
      3. NP-Complete problem
6. Search (4hrs)

8.1.Intelligent Search Technology

8.2. Branch and bound

8.3. Local search, Metropolis, Simulated annealing

1. Approximation Algorithm (4hrs)

9.1. Introduction of Approximation algorithm

9.2. Makespan Problem, LP-Round Technology

1. Random Algorithm (4hrs)

10.1. Introduction of Random algorithm

10.2.LP+random rounding, etc

Grading

No regular weekly homework will be given in this course, but several design work during the course require students to submit their solutions to specific problems with knowledge they learn from this course and will count 30% of the total. At the end of the semester, there will be a final examination, which will count for 70%. The full score of this course is 100.

Textbook

J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley, 2005 ISBN：9787302143352

References