The course will introduce principles and meaning of algorithms analysis; apply asymptotic methods to analyzing time complexities in worst and average case; compare the asymptotic behaviors of functions obtained by elementary composition of polynomials, exponentials, and logarithmic functions in order to understand the meanings of asymptotic analysis. Describe the relative merits of worst-, average-, and best-case analysis. The course will also introduce basic means of analyzing algorithms, including those of analyzing iterative and recursion algorithms.

The course will introduce important algorithmic design paradigms, including the divide-and-conquer paradigm, the greedy paradigm, the dynamic-programming paradigm, the acktracking paradigm and branch and bouding paradigm. While describing these methods, we will explain when an algorithmic design situation calls for them, and the principles of these methods will be given, we also analyze the time complexity of the designed algorithms. We also discuss the correctness of the designed algorithms and the problems of implementation of the designed algorithms, such as select data structures, hardness of implementation. A lot of examples will be presented in the course to illustrate the above abstract concepts and methods, which come from typical applications.

The course will briefly introduce more deep issues in algorithms analysis, i.e. well known NP-complete problems, including the definition of class NP, NP-hardness and NP-complete problems and their proof. The approximate methods for solving some NP-complete problem will be introduced.

The course introduces students to the running time analysis and basic paradigms for design of computer algorithms. Upon completion of this course, students will be able to understand worst-case, best-case and average-case time complexities of a algorithm and learn some methods of analyzing asymptotic time complexities of algorithms, and able to apply basic methods of algorithm design to designing algorithms, and evaluate “goodness and badness” of designed algorithms. In terms of studying this course, students will obtain a right understanding and ideas of designing algorithms.

• Dynamic Programming( lecture)
Readings(M-Must read, O-Optional read):


subsection	handout
what is the DP?	(M) Eddy, S.R., What is dynamic programming? Nature Biotechnology, 2004. 22(7): p. 909-910. download (M) Dynamic programming in mathematical optimization from http://en.wikipedia.org/ download
0/1 Knapsack problem	(M)Acosta, A., & Almeida, F. (2013). Skeletal based programming for dynamic programming on MultiGPU systems. The Journal of Supercomputing. doi:10.1007/s11227-013-0895-x download (M) Pisinger, D., Where are the hard knapsack problems? Computers & Operations Research, 2005. 32(9): p. 2271-2284. download (O) Poirriez, V., Yanev, N., and Andonov, R., A hybrid algorithm for the unbounded knapsack problem. Discrete Optimization, 2009. 6(1): p. 110-124. download
Matrix Multiplication Chains	(O) Hu, T.C. and Shing, M.T., Computation of matrix chain products: Part I, Part II, in CS-TR-81-875. 1981.download
All Pairs Shortest Path	(M) Seidel, R. On the all-pairs-shortest-path problem. in Proceedings of the twenty-fourth annual ACM symposium on Theory of computing. 1992. download
Longest Common Subsequences	(M) Iliopoulos, C.S. and Rahman, M.S. A New Efficient Algorithm for Computing the Longest Common Subsequence. in 3rd international conference on Algorithmic Aspects in Information and Management. 2007. download

• Backtracking( lecture)
Readings(M-Must read, O-Optional read):


subsection	handout
Introduction	(M) Rolfe, T.J. and Paul W. Purdom, J., An Alternative Problem for Backtracking and Bounding ACM SIGCSE Bulletin, 2004. 34(4): p. 83-84. download (O) Lynce, I. and Marques-Silva, J.P., An overview of backtrack search satisfiability algorithms. Annals of Mathematics and Artificial Intelligence, 2003. 37(3): p. 307-326. download

• Branch and Bound( lecture)
• NP-Complete Problems (lecture)

subsection	handout
Introduction	(M) Woeginger, G. (2003). Exact algorithms for NP-hard problems: A survey. Combinatorial Optimization—Eureka, You Shrink! Springer-Verlag. Retrieved April 12, 2011, from http://www.springerlink.com/index/Q7QTNCJDNL72E4W2.pdf. download (O) Agrawal, M., Kayal, N., & Saxena, N. (2004). PRIMES is in P. Annals of Mathematics, 160(2), 781-793. doi: 10.4007/annals.2004.160.781. download

• Summary (lecture)

2014-4-24: Assignment 1
Due date : 2014-4-29

2014-5-8: Assignment 2
Due date : 2014-5-21

2014-5-8: Handout 1
Due date : 2014-5-29