Algorithm Design and Analysis II

Syllabus

• Combinatorial problems and algorithms: dynamic programming, the knapsack problem, and approximation algorithms.
• Approximation methods for graph problems, including minimum 2-edge-connected spanning subgraphs.
• Graph algorithms: finding cut vertices, maximum-back orderings and their applications, and rigidity.
• Graph data structures and conversions between alternative graph representations.
• Random graphs: definitions, evolution processes, and simulation using random libraries.
• Algebraic algorithms: symbolic computation and generating functions.
• Geometric algorithms: convex hulls, bisecting lines, and Voronoi cells.
• Operations research: flow problems and integer programming.
• Data mining algorithms: the perceptron algorithm, k-means clustering, and the k-nearest-neighbour method.