演算法

The study of algorithms is at the heart of computer science. This course focuses on fundamental results in this area, including the unifying principles and underlying concepts of algorithm design and analysis. We expect everyone to be comfortable reading, even writing, proofs. Several programming assignments will be given to embody the ideas. Moreover, we hope that everyone can learn general problem-solving techniques. Intended audience: 1. who are interested in computer science 2. who are computing something 3. who are learning problem-solving techniques

1. Data structures 2. Discrete mathematics 3. Computer programming in C 4. Computer programming in C++ *Two out of above four courses*

無備註

Lecture notes and related information will be released on the e3 course website.

1. Homework assignments 10% 2. Projects (two mini-projects: 20% + term project: 20%) 3. Two in-class tests (Midterm: 25% + Final: 25%)

• Basics of algorithm analysis

  Asymptotic order of growth, case study on stable matching

• Introduction

  Stable matching and some representative problems

• Graphs

  Connectivity, traversal, bipartiteness testing, topological sorting

• Greedy algorithms

  Interval scheduling, shortest paths, minimum spanning tree, (Huffman codes)

• Divide and conquer

  Mergesort, recurrence relations, counting inversions, finding the closest pair of points, (convolutions & FFT)

• Dynamic programming

  Weighted interval scheduling, memoization/iteration, segented least squares, subset sums & Knapsacks, RNA secondary structure, sequence alignment, shortest paths

• Network flow

  Maximum-flow and min-cut, bipartite matching, airline scheduling

• NP and computational intractability

  Polynomial-time reductions, satisfiability, NP, NP-completeness, graph coloring

• Amortized analysis

  Aggregate method, accounting method, potential method

• Linear Programming

  Duality, simplex method

• PSPACE

  Optional

• Approximation algorithms

  Optional

• Local search

  Optional

• Randomized algorithms

  Optional

• Algorithms that run forever

  Optional

Required text: J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2006. (J. Kleinberg, 20 Best Brains under 40, Discover Magazine, 2008) Reference books: S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw-Hill, 2007. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Third Edition, McGraw Hill/The MIT Press, 2009.

地點

ED540

時間

12:00--12:30, Mondays (made by appointment)

聯絡方式

huiru.jiang@gmail.com