### Design and analysis of algorithms

Course Code: B63009H

Course Name: Design and Analysis of Algorithm

Credits: 2.0

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.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