UCAS_algorithm_course

UCAS CS091M4041H: Algorithm Design and Analysis – Fall 2024

Course information

• Instructor: Dongbo Bu

  • Email: dbu @ ict.ac.cn

  • Office: Room 844, ICT building, Beijing

  • Phone: 010-62600844

• TAs: Rui Wang, Jing Xu, Ning Xu, Hehuan Cao, Jianbo Zhou, Jiepeng Li, Tian Zhu, Shizhe Ding, Xiaoyang Hou, Xinru Zhang, Yihui Ren, Yue Yu, Zhiyuan Wang

  • Email: TAGC @ ict.ac.cn

  • Location: 424D, ICT building, Beijing

  • Office hours: 3:00-6:00, Wednesday

  • Thanks to the TAs who contributed to this course during the past years:

    • 2023: Tian Zhu, Shizhe Ding, Tiansu Gong, Xiaoyang Hou, Ruizhi Liu, Jingyan Sui, Xinru Zhang, Yihui Ren, Kun Wang, Jianquan Zhao, Yue Yu, Zhiyuan Wang
    • 2022: Milong Ren, Shizhe Ding, Tiansu Gong, Boyang Xia, Ruizhi Liu, Jingyan Sui, Xinru Zhang, Yihui Ren, Kun Wang, Jianquan Zhao, Xinglong Wang
    • 2021: Boyang Xia, Hui Wang, Jingyan Sui, Bin Huang, Xin Ku, Yu Wang, Ruizhi Liu, Shizhe Ding, Tiansu Gong, Liming Xu, Fangxiong Xiao
    • 2020: Zeshun tan, Hui Wang, Meijie Hou, Mingai Dang, Jingyan Sui, Fusong Ju, Bin Huang, Xin Ku, Yu Wang, Lupeng Kong, Ruizhi Liu, Shizhe Ding, Tiansu Gong
    • 2019: Junchuan Dong, Zeshun Tan, Hui Wang, Meijie Hou, Mingai Dang, Zhenxin Ding, Jingyan Sui, Fusong Ju, Bin Huang, Weiyi Pan
    • 2018: Jianwei Zhu, Lupeng Kong, Fusong Ju, Guozheng Wei, Qi Zhang, Bin Huang, Hui Wang, Zhenxin Ding, Weiyi Pan, Junchuan Dong, Xinyu Hua
    • 2017: Jianwei Zhu, Lupeng Kong, Xiaoran Cao, Jingwei Zhang, Fusong Ju, Guozheng Wei, Qi Zhang
    • 2016: Jianwei Zhu, Lepeng Kong, Feng Gao, Yanbo Li, Bing Wang, Xiaoran Cao, Jingwei Zhang
    • 2015: Yaojun Wang, Jianwei Zhu, Feng Gao, Yanbo Li, Bing Wang, Hai’e Gong, Fei Yang
    • 2014: Hai’e Gong, Fei Yang, Qing Xu, Chao Wang, Haicang Zhang, Chunlin Huang, Yaojun Wang, Renyu Zhang
    • 2013: Qing Xu, Chao Wang, Haicang Zhang, Chunlin Huang, Renyu Zhang, Yaojun Wang, Bin Ling
    • 2012: Dawei Chen, Chao Wang, Haicang Zhang, Chunlin Huang, Jin Li, Qin Huang, Lei Nie, Bin Ling
    • 2011: Chao Wang, Haicang Zhang, Mingfu Shao, Chunlin Huang, Jin Li, Qin Huang, Lei Nie
    • 2010: Mingfu Shao, Haicang Zhang, Chao Wang, Chunlin Huang
    • 2009: Chao Wang, Mingfu Shao
• Textbooks (recommended, not required):
  • T.H. Cormen, C.E. Leiserson, R. Rivest, and C. Stein, Introduction to algorithms (2nd ed.), MIT Press, 2001. Widely available.
  • J. Kleinberg and E. Tardos, Algorithm Design. Addison-Wesley, 2005.
  • R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge U. Press, 1995
• Other reading material:
  • Christos H. Papadimitriou, Kenneth Steiglitz, Kenneth Steiglitz. Combinatorial Optimization: Algorithms And Complexity. Courier Dover Publications, 1998
  • Ding-Zhu Du, Ker-I Ko, Xiaodong Hu. Design and analysis of approximation algorithms. Springer, 2012
  • Daming Zhu, Shaohan Ma. Algorithm design and analysis. High Education Press, 2009.
  • Udi Manber, Introduction to Algorithms: A Creative Approach.
  • M. Mitzenmacher and E. Upfal, Probability and Computer. Cambridge U. Press, 2005.
  • M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York, 1979.

• Prerequisites:

  We will assume knowledge of:

  • Basic data structures such as lists, trees, heaps, sorting and searching;
  • Basic discrete mathematics such as proofs by mathematical induction;
  • Computability and programming experience.

Topics:

We will cover the following topics if time permits:

• Problem hardness, NP-completeness;
• Algorithm analysis techniques, including worst-case and average-case, amortized, randomization, and competitive;
• Basic algorithm techniques, including greedy, iteration, divide-and-conquer, dynamic programming, network flow, linear programming;
• Algorithm techniques for hard problems, including approximation algorithms, local search, primal-dual algorithms, linear programming;
• Randomized algorithms: basic techniques from discrete probability, and applications to optimization.
• Specific problems from computational biology and Bioinformatics (if time permits).

Grading policies

5 assignments and final examination.

Weekly Schedule

The week number is an active link – each week has its own page that includes required reading, recommended reading, assignment (if any), teaching assistants, etc. Topics for weeks beyond the current and next are always tentative.

---

• Week 1, 2, 3: Introduction to algorithm and basic design techniques

  • Topic 1: Algorithm design in the era of AI Slides: AI-aided algorithm design

  • Topic 2: Introduction to algorithm: some representative problems

    Slides: Lec1.pdf

  • Topic 3: Divide-and-conquer technique, and the combination with randomization; FFT; Matrix multiplication；Blum’s algorithm for Selection problem and the improvement by G. Zeng

    Slides: Lec5.pdf, Lec5-FFT.pdf, demo merge (by K. Wayne), demo of QuickSort partition (by Y. Danial Liang)

  • Reading material:

    • Chapter 1 of Algorithm design
    • Chapter 17 of Introduction to Algorithms
    • Lecture 8, 9 of The Design and Analysis of Algorithms
    • Faster sorting algorithms discovered using deep reinforcement learning (by Daniel J. Mankowitz, et al, 2023)
    • Discovering faster matrix multiplication algorithms with reinforcement learning (by Alhussein Fawzi, et al, 2022)
    • An optimal algorithm for matrix multiplication (by Changjun Jiang and Zhehui Wu, 1988)
    • On the solution of linear recurrence equations (by Mohamad Akra and Louay Bazzi, 1998)
    • Two papers on the selection problem (by BFPRT, and FR)
    • College Admissions and the Stability of Marriage (by Gale and Shapley, 1962)
    • STABLE ALLOCATIONS AND THE PRACTICE OF MARKET DESIGN (compiled by the Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences, 2012)
    • Stable matching: Theory, evidence, and practical design (INFORMATION FOR THE PUBLIC, The Nobel prize in economic sciences, 2012)
    • Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithms Repository (by Steven S. Skiena, 1999)
    • An Effective Heuristic Algorithm for the Traveling-Salesman Problem (by S. Lin and B. W. Kernighan, 1971)
    • Gene coexpression measures in large heterogeneous samples using count statistics (by Y. Wang, M. S. Waterman, and H. Huang, 2014)
    • Duality applied to the complexity of matrix multiplications and other bilinear forms (by J. Hopcroft, and J. Musinski, 1973)
    • The Coppersmith-Winograd matrix multiplication algorithm (by M. Anderson and S. Barman, 2009)
    • Some techniques for solving recurrences (by George S. Lueker, 1980)
    • Karatsuba algorithm vs. grade-school method: experimental results (picture)
    • Karatsuba algorithm vs. grade-school method: experimental results (a summary)
    • Fast Division of Large Integers — A comparison of Algorithms (by Karl Hasselstrom, 2003)
    • Quicksort (by C. A. R. Hoare, 1962)
    • Time bounds for selection (by Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald Rivest, and Robert E. Tarjan, 1973)
    • Expected time bounds for selection (by Robert W. Floyd, Ronald L. Rivest, 1973)
    • Ph. D. thesis of Michael Ian Shamos (Section 6.2: Closest-Point Problems)
    • Finding and counting given length cycles (by Noga Alon, Raphael Yuster, and Uri Zwick, 1994)
    • Closest Pair Data Structure: Applications (by David Eppstein)
    • Dynamic Euclidean Minimum Spanning Trees and Extrema of Binary Functions (by David Eppstein, 1995)
    • Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs (by David Eppstein, 1998)
    • Fourier analysis (by Cleve Moler)
    • A general method for solving divide-and-conquer recurrences (by J. L. Bentley, D. Haken, J. B. Saxe, 1980)
    • The complexity of computations (by A. A. Karatsuba, 1995)
    • Sorting and selection on dynamic data (by Aris Anagnostopoulos, et al, 2011)
    • Gaussian elimination is not optimal (by V. Strassen, 1969)
    • Matrix multiplication via arithmetic progressions (by Don Coppersmith, Shmuel Winograd, 1990)

---

• Week 3, 4, 5: More on basic algorithm design techniques

  • Topic 1: Dynamic programming technique

    Slides: Lec6.pdf, Lec6-HMM.pdf, Lec6-RNA.ppt

  • Topic 2: Advanced dynamic programming

    Slides: Lec6.pdf, Lec6-NNTSP-Feidiao2018.pptx (by Feidiao Yang)

  • Reading material:

    • Chapter 2, 15, 16, 7, 33.4 of Introduction to Algorithms
    • Chapter 5, 4, 6 of Algorithm design
    • On Efficient Computation of Matrix Chain Products (by S. S. Godbole, 1973)
    • An O(n log n) algorithm for computation of matrix chain products (by T. C. Hu and M. T. Shing, 1981)
    • A general method applicable to the search for similarities in the amino acid sequence of two proteins (by Saul B. Needleman, Christian D. Wunsch, 1970)
    • Identification of Common Molecular Subsequences (by T.F.SMITH and M. S. WATERMAN, 1981)
    • The statistical distribution of nucleic acid similarities (by T.F.SMITH, M. S. WATERMAN, and C. Burks, 1985)
    • Esitmating statistical significance of sequence similarities (by M. S. WATERMAN, 1994)
    • Implementation of the Smith-Waterman Algorithm on a Reconfigurable Supercomputing Platform (White paper by ALTERA, 2007)
    • A linear space algorithm for computing maximal common subsequences (by D. S. Hirschberg, 1975)
    • Rapid similarity searches of nucleic acid and protein data bank (by W. J. Wilbur and D. J. Lipman, 1983)
    • Fast optimal alignment (by James W. Ficket, 1984)
    • A short note on dynamic programming in a band optimal alignment (by Jean-Francois Gilbrat, 2018)
    • Basic Local Alignment Search Tool (by S. Altschul, et al. 1990)
    • P-value calculation (by J. Zhang, 2007)
    • PAM matrix for BLAST algorithm (by C. Alexander, 2002)
    • On a routing problem (by Richard Bellman, 1958)
    • All pair shorest path
    • Advanced dynamic programing
    • Richard Bellman on the birth of dynamic programming (by Stuart Dreyfus, 2002)
    • Algorithms for Knapsack problem (Ph. D. thesis of David Pisinger, 1995)
    • Computing Partitions with Applications to the Knapsack problem (by E. Horowitz and S. Sahni, 1974)
    • The rise and fall of Knapsack cryptosystems (by A. M. Olyzko, 1994)
    • A dynamic programming approach to sequencing problems (by Michael Held and Richard M. Karp, 1962)
    • Knapsack problems (by Hans Kellerer, Ulrich Pferschy, and David Pisinger, 2003)
    • Publick-key cryptosystem (by Charles Clancy)

---

• Week 5, 6, 7: Still more on basic algorithm design techniques

  • Topic 1: Greedy technique

    Slides: Lec7.pdf, demo of Dijkstra’s algorithm, demo of Interval Scheduling algorithm (by Kevin Wayne), Lec7-Heap.pdf, Lec7-UnionFind.pdf, FibonacciHeaps.pdf (by Kevin Wayne), BinomialHeaps.pdf (by Kevin Wayne), FibonacciHeaps.pdf (by Kevin Wayne), DemoBinaryHeap.pdf (by Kevin Wayne), DemoHeapify.pdf (by Kevin Wayne)

  • Topic 2: Basic algorithm analysis techniques, worst-case, average-case, and amortized analysis

    Slides: Lec2.pdf, demo of TableInsert (by C. Leiserson)

  • Reading material:

    • Chapter 2, 15, 16, 7, 33.4 of Introduction to Algorithms of Algorithm design,
    • Chapter 4, 5, 6 of Introduction to Algorithms,
    • a note by Sleator
    • A note on two problems in connexion with graphs (by E. W. Dijkstra, 1959)
    • Algorithm 97: Shortest path (by Robert W. Floyd, 1962)
    • Top-down analysis of path compression (by Raimund Seidel and Micha Sharir, 2005)
    • Set merging algorithms (by Hopcroft J. E., Ullman J. D., 1973)
    • Efficiency of equivalence algorithms (by M. Fischer, 1972)
    • Efficiency of a good but not linear set union algorithm (by R. Tarjan, 1975)
    • Worst-case analysis of set union algoritms (by R. Tarjan, 1984)
    • A theorem on Boolean matrics (by Stephen Warshall, 1962)
    • Efficient algorithms for shortest paths in sparse networks (by Donald B. Johnson, 1977)
    • Disjoint paths in networks (by J. W. Suurballe, 1974)
    • An interview with Edsger W. Dijkstra (Conducted by Philip L. Frana 2001)
    • On the shortest spanning subtree of a graph and the traveling salesman problem (by Joseph B. Kruskal Jr., 1955)
    • Shortest Connection Networks and Some Generalizations (by Robert. C. Prim, 1957)
    • A Mathematical Theory of Communication (by C. E. Shannon, 1948)
    • An interview with Claude Shannon (Conducted by Robert Price, 1982)
    • An interview with Robert M. Fano (Conducted by Arthur L. Norberg, 1989)
    • A Method for the Construction of Minimum-Redundancy Codes (by DAVID A. HUFFMAN, 1952)
    • Profile: David A. Huffman Encoding the “Neatness” of Ones and Zeroes (by Gary Stix, 1991)
    • Binary Essence: Various aspects of data compression
    • Algorithm 245, TreeSort 3 (by Robert M. Floyd, 1964)
    • Discovery of Huffman Codes (by Inna Pivkina, 2010)
    • Binomial Heap Script (by Sotirios Stergiopoulos, 2001)
    • Fibonacci Heap Animation (by Jason Huang Hu and Wei Wang, 2003)
    • What is a matroid? (by James Oxley, 2003)
    • On the abstract properties of linear dependence (by Hassler Whitney, 1935)
    • Non-separable and planar graphs (by Hassler Whitney, 1932)
    • Matroids and greedy algorithms(by Jack Edmonds, 1971)
    • A Data Structure for Manipulating Priority Queues (by Jean Vuillemin, 1978)
    • Fibonacci heaps and their uses in improved network optimization algorithms (by M. Fredman and R. Tarjan, 1987)
    • Robert Tarjan — the art of the algorihtms (by Jamie Beckett, 2004)
    • Amortized Analysis Explained (by Rebecca Fiebrink)

---

• Week 8, 9: Linear programming

  • Topic 1: Linear programming and simplex algorithm

    Slides: Lec8.pdf, Lec8-Secretary-Problem.pdf, Lec8.pdf, Lec8-Genome-Rearrange-Problem.pdf, an example of cycling in simplex algorithm (given by E. M. L. Beale, 1955), the DIET problem (in.math format)

  • Topic 2: Klee-Minty cube and smoothed complexity

    Slides: an example of Klee-Minty cube, a script to generate Klee-Minty cube (with noise), a script to generate Klee-Minty cube (without noise)

  • Reading material:

    • Chapter 29 of Introduction to Algorithms, Combinatorial optimization: algorithm and complexity
    • An interview with George B. Dantzig: the farther of linear programming (Conducted by Watts, Griffis and McOuat, 1986)
    • Mathematical Methods of Organizing and Planning Production (by L. Kantorovich, 1939)
    • The First Algorithm for Linear Programming: An Analysis of Kantorovich’s Method (by C. van de Panne and F. Rahnama, 1985)
    • CONCEPTS OF OPTIMALITY AND THEIR USES (Nobel memorial lecture, by T. Koopmans, 1975)
    • Mathematics in Economics: Achievements, Difficulties, Perspectives (Nobel memorial lecture, by L. Kantorovich, 1975)
    • The diet problem (by George B. Dantzig, 1990)
    • A primal-dual algorithm (by George B. Dantzig, L. R. Ford, D. R. Fulkerson 1956)
    • The cost of subsistence (by George Stigler, 1945)
    • Linear programming (by George B. Dantzig, 2002)
    • Linear programming and extensions PART I (by George B. Dantzig, 1963)
    • Linear programming and extensions PART II (by George B. Dantzig, 1963)
    • Ellipsoid Method (by Steffen Rebennack, 2008)
    • Lecture notes on the ellipsoid algorithm (by Michel Goemans, 2009)
    • The Ellipsoid Method: A Surve
    • Primal-Dual methods for linear programming (by Philip E. GILL, Walter MURRAY, Dulce B. PONCELEON and Michael A. SAUNDERS, 1994)
    • Interior point methods and linear programming (by Robert Robere, 2012)
    • ON PROJECTED NEWTON BARRIER METHODS FOR LINEAR PROGRAMMING AND AN EQUIVALENCE TO KARMARKAR’S PROJECTIVE METHOD (by Philip E. Gill, Walter MURRAY, Michael A. SAUNDERS, J.A. TOMLIN, Margaret H. WRIGHT, 1986)
    • A new polynomial-time algorithm for linear programming (by N. Karmarkar, 1984)
    • C++ implementation of Khachiya algorithm for the minimum enclosing (or covering) ellipsoid (by Bojan Nikolic)
    • In memoriam: Leonid Khachiyan
    • Klee-Minty example (by H. Greenberg)
    • Simplex examples
    • Smoothed complexity (by D. Spielman and S. Teng)
    • Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time (by D. Spielman and S. Teng, 2001)
    • GLPK (GNU Linear Programming Kit
    • A new polynomial-time algorithm for linear programming (by N. Karmarkar, 1984)
    • The interior-point revolution in optimization: history, recent developments, and lasting consequences (by Margaret H. Wright, 2004)
    • Why a pure primal Newton barrier step may be infeasible? (by Margaret H. Wright, 1995)
    • Numerical Optimization (by Nocedal, Jorge, Wright, S., 2006)
    • Solving Inequalities and Proving Farkas’s Lemma Made Easy (by David Avis and Bohdan Kaluzny)

---

• Week 10, 11: Linear programming and duality
  • Topic 1: Lagrangian duality, Lagrange multiplier method and KKT conditions

  • Topic 2: Interior point algorithm, transform a quadratic linear programing into two-step dynamic programing

    Slides: Lec9.pdf, a gnuplot script to illustrate Lagrangian dual, Lec9-DIET.math, Lec9-DIET-Dual.math, Lec9-DIET-b1-2001.math, Lec9-DIET-b2-56.math, Lec9-DIET-b3-801.math

  • Reading material:
    • Chapter 29 of Introduction to Algorithms
    • Combinatorial optimization: algorithm and complexity
    • On the theory of games of strategy (by John von Neumann, 1928)
    • Non-Cooperative Games (by John Nash, 1951)
    • Zero-sum Two-person Games (by T. E. S. Raghavan, 1994)
    • KKT Examples (by Stanley B. Gershwin)
    • KKT conditions and applications (by Michel Baes)
    • Duality and KKT conditions (by S. Cui)
    • Lagrangian Multipliers Revisited (by Morten Slater, 1950)
    • The Lagrangian Relaxation Method for Solving Integer Programming Problems (by Marshall Fisher, 2004)
    • Lagrange relaxation and KKT conditions ()
    • Applied integer programming — modelling and solution

---

• Week 12, 13: Network flow algorithm

  • Topic: 1 Network flow and its applications

    Slides: Lec10.pdf, Applications of network flow

  • Topic: 2 Ford-Fulkerson algorithm, Scaling technique, Edmonds-Karp algorithm, Dinic’s algorithm, push-relabel algorithm and recent progress

    Slides: demo of Ford-Fulkerson algorithm, irrational capacities might lead to endless iterations, multiple optimal solutions, demo of Edmonds-Karp algorithm , demo of Dinic’s algorithm

  • Reading material:

    • Chapter 26 of Algorithm design,
    • Chapter 7 of Algorithm design, Combinatorial optimization: algorithm and complexity
    • Network-flow research history (by A. Schrijver)
    • Maximal flow through a network (by L. R. Ford Jr. and D. R. Fulkerson, 1956)
    • Efficient Maximum Flow Algorithms (by Andrew V. Goldberg, and Robert Tarjan, 2014)
    • The exact time bound for a maximum flow algorithm applied to a set of representative problems (by A. Karzanov, 1973)
    • Determining the maximal flow in a network by the method of preflows (by A. Karzanov, 1974)
    • Determinining the maximal flow in a network by the method of preflows (by A. Karzanov, 1974)
    • Algorithm for solution of a problem of maximum flow in a network with power estimation (by E. A. Dinic, 1970)
    • Finding minimum-cost flows by double scaling (by R. A. Ahuja, A. V. Goldberg, J. B. Orlin, and R. E. Tarjan, 1992)
    • Dinitz’ Algorithm: The Original Version and Even’s Version (by Yefim Dinitz, 2006)
    • Finding disjoint paths in networks (by D. Sidhu, R. Nair, and S. Abdallsh, 1991)
    • Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems (by Jack Edmonds and Richard M. Karp, 1972)
    • Network Flow Algorithms (Andrew V.Goldberg, Eva Tardos and Robert E. Tarjan, 1990)
    • Maximum Matching and a Polyhedron With O,1-Vertices1 Jack Edmonds (by Jack Edmonds, 1964)
    • Paths, Trees and Flowers
    • Paths, Trees and Flowers (by Jack Edmonds, 1965)
    • Faster scaling algorithms for general graph matching problems (by H. N. Gabow, R. Tarjan, 1991)
    • A Scaling Algorithm for Maximum Weight Matching in Bipartite Graphs (by Ran Duan, Hsin-Hao Su, 2012)
    • Efficient Algorithms for Finding Maximal Matching in Graphs (by Zvi Galil, 1983)
    • Linear-Time Approximation for Maximum Weight Matching(by Ran Duan, Seth Pettie, 2014)
    • Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality (by Mohsen Bayati, Devavrat Shah, and Mayank Sharma, 2008)
    • A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems (by Morton Klein, 1967)
    • Max flows in O(nm) time, or better (by James Orlin, 2012)
    • Trees: A Mathematical Tool for All Seasons, including History of algorithms to find minimum cost spanning trees (by Joe Malkevitch)
    • 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, Springer, 2010 (Edited by M. Juenger, T. M. Kiebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey)
    • Finding minimum-cost circulations by successive approximation ( by Andrew V. Goldberg, Robert E. Tarjan, 1987)
    • What energy functions can be minimized via graph cuts (by Vladimir Kolmogorov, Ramin Zabih, 2004)
    • Polyhedral Combinatorics and Combinatorial Optimization (by Alexander Schrijver)
    • Two theorems in graph theory (by Clauder Berge, 1957)
    • An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs (by J. Hopcroft, and R. Karp, 1973)
    • On representatives of subsets (by P. Hall, 1935)
    • A Primal Method for the Assignment and Transportation Problems (by M. L. Balinski and R. E. Gomory, 1964)
    • The Hungarian Method for the Assignment Problem (by H. W. Kuhn, 1955)
    • Variants of The Hungarian Method for Assignment Problems (by H. W. Kuhn, 1956)
    • On the history of combinatorial optimization (by Alexander Schrijver, 2005)
    • Jen¨o Egerv´ary: from the origins of the Hungarian algorithm to satellite communication (by Silvano Martello, 2009)
    • On combinatorial properties of matrices (by Jeo Egervary, 1931, Translated by H. Kuhn)
    • Solutions of games by differential equations (by G. W. Brown, von Neumann, In: H. W. Kuhn and A. W. Tucker, Eds., Contributions to the Theory of Games I, Princeton University Press, Princeton, 1950)
    • A certain zero-sum two-person game equivalent to the optimal assignment problem (by von Neumann, In: H. W. Kuhn and A. W. Tucker, Eds., Contributions to the Theory of Games I, Princeton University Press, Princeton, 1950)
    • Algorithms for the assignment and transportation problems (by James Munkres, 1957)
    • A bibliography of graph matching (by Seth Pettie)
    • Differential gene expression analysis using coexpression and RNA-Seq data (by Tao Jiang et al. 2013)

---

• Week 14, 15, 16: Problem intrinsic property: Hardness

  • Topic 1: Computability and Turing machine

    Slides: demo of Turing machine (by Zhen Ji), demo of Turing machine (by Andrew Hodges), Turing machine (by Kevin Wayne), Computability (by Kevin Wayne)

  • Topic 2: Problem hardness and polynomial-time reduction

    Slides: Lec3.pdf

  • Topic 3: NP-Hard problems: packing problem, covering problem, sequencing problem, partitioning, coloring, SAT, numbering problems, etc.

    Slides: Lec4.pdf, 2SAT is in P ((by D. Moshko)

  • Reading material:

    • Computer and intractability
    • Chapter 34 of Introduction to Algorithms,
    • Chapter 8 of Algorithm design
    • Reducibility among combinatorial problems (by R. M. Karp, 1972)
    • Molecular Computation of Solutions to Combinatorial Problems (by Leonard M. Adleman, 1994)
    • Computing with DNA (by Leonard M. Adleman, 1998)
    • Computer in a testtube (by Hendrik Jan Hoogeboom, 2010)
    • How to apply de Bruijn graphs to genome assemly (by Phillip E. C. Compeau, Pavel A. Pevzner, and Glenn Tesler, 2011)
    • The complexity of theorem-proving procedures (by Stephen A. Cook, 1971)
    • The P versus NP problem (by Stephen Cook)
    • A compendium of NP optimization problems (Edited by Pierluigi Crescenzi, Viggo Kann, M. Halldorsson, M. Karpinski, and G. Woeinger)

---

• Week 17, 18, 19: Solving hard problems: approximation, randomization, special cases and heuristics

  • Topic 1: Approximation algorithm: a brief introduction

    Slides: Lec11.pdf, Parametric pruning algorithm for k-center problem (by P. Potikas), Lec11-SetCover-Primal.math, Lec11-SetCover-Dual.math, Lec11-MakeSpan.math

  • Topic 2: Randomized algorithm: a brief introduction

    Slides: Lec12.pdf, Hashing (by Kevin Wayne)

  • Topic 3: Extending limits of tractability

    Slides: Lec13.pdf

  • Topic 3: Heuristics, including lcoal search and simulated annealing

    Slides: Local Search (by K. Wayne)

  • Reading material:

    • Chapter 10, 11, 13 of Algorithm design,
    • Chapter 35 of Introduction to Algorithms,
    • Combinatorial optimization: algorithm and complexity
    • Randomized Algorithm (by R. Motwani and P. Raghavan)
    • Approximation algorithm (by V. Vazirani)
    • Branch and bound algorithms — priciples and examples (by Jens Clausen, 1999)
    • Parameterized complexity and approximation algorithms (by Daniel Marx, 2005)
    • CS266 – Parameterized Algorithms and Complexity (by Ryan Williams, 2013)
    • Invitation to parameterized algorithms (by Rolf Niedermeier, 2002)
    • Randomized algorithms (by P. Raghavan)
    • Global Min-cuts in RNC, and other ramifications of a simple min-cut algorithm (by David R. Karger, 1992)
    • TreePack: rapid side-chain prediction using tree-decomposition
    • Rapid side-chain prediction via tree decomposition (by Jinbo Xu, 2005)
    • Protein Threading using PROSPECT: Design and Evaluation (by Ying Xu and Dong Xu, 2000)

---

• Week 20, 21, 22: Some interesting problems and algorithms

  • Topic 1: Cache paging problem: FF, LRU, and randomized algo

    Slides: Lec16.pdf

  • Topic 2: String matching problem: DFA, KMP method, randomized finger-print, and Karp-Rabin algorithm

    Slides: Lec17.pdf

  • Topic 3: Closest string and substring problems: random rounding and random sampling

    Slides: Lec18.pdf

  • Topic 4: Bi-Clustering problem: random rounding, a new random sampling idea

    Slides: Lec19.pdf

  • Topic 5: MaxCut problem: Hardness, Local search algorithm, randomization algorithm, derandomization, and SDP approach;

    Slides: Lec20.pdf

  • Reading material:

    • Lectures by D. P. Williamson
    • Semidefinite programming (by LIEVEN VANDENBERGHEt AND STEPHEN BOYD, 1996)
    • Introduction to semidefinite programmin (by R. Freund)

---

The course is supported by Loongson CPU

In memory of my student, Prof. Yu Lin, who is an excellent computer scientist and has great contribution to this course

This site is open source. Improve this page.