Design and analysis of algorithms Seminar

Course Code: B63010H

Course Name: Design and Analysis of AlgorithmSeminar

Credits: 1.0

Level: Undergraduate

Pre-requisite: Programming language, Data structure

Lecture Time:20 hours

Instructors: Dongbo Bu, Jialin Zhang

Course Description

This seminar is subordinate course of design and analysis of algorithm. All students are automatically added with this course. With discussion and demonstration on several practical problems and comparison among several algorithms, this course intends to develop and enhance students’ ability of designing and realizing algorithm.

Topics and Schedule

  1. Dynamic Programming (4hrs)

1.1.String alignment

1.2.Hirshburg Algorithm

  1. Linear Programming and Duality (4hrs)
    1. Simplex algorithm
    2. Integer linear programming on classic problems
  2. Network Flow (4hrs)
  3. Ford-Fulkerson algorithm
  4. Dinitz algorithm
    1. NP-Completeness (4hrs)
      1. NP-Complete problem
      2. Local search algorithm on Traveling salesman problem(TSP)
  5. Backtracking algorithm (4hrs)

5.1. Branch and Bound MethodApproximation Algorithm (4hrs)

Grading

Several project works counts total point of this course, and the final grade of this course weights 30% in the grade of design and analysis of algorithm.

Textbook

References