CS4335: Design and analysis of Algorithms Who we are. Instructors Shuai Cheng ll, y6634, 3442 9412, shuaicli(@cityu. edu Lusheng Wang. b6422, 3442 9820 lwang(@cs. cityu. edu Dept. of Computer Science Coursewebsitewww.cs.cityu.eduhk/shuaicli/cs4335 2021/26 CS4335 Design and Analysis of
2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 1 CS4335: Design and Analysis of Algorithms Who we are: Instructors: Shuai Cheng LI, Y6634, 3442 9412, shuaicli@cityu.edu. Lusheng WANG, B6422, 3442 9820, lwang@cs.cityu.edu Dept. of Computer Science Course web site: www.cs.cityu.edu.hk/~shuaicli/cs4335
Text book J. Kleinberg and e Tardos, Algorithm design, Addison-Wesley 2005 We will add more material in the handout References T.H. Cormen. C. E LeisersonR.L. rivest. Introduction to Algorithms. The mit press http://theory.ics.mit.edu/clr/ R Sedgewick, Algorithms in C++, Addison-Wesley, 2002 A Levitin, Introduction to the design and analysis of algorithms, Addison-Wesley, 2003 M.R. Garry and D.S. Johnson. Computers and intractability. a guide to the theory of NP-completeness, W.H. Freeman and company, 1979 2021/26 CS4335 Design and Analysis of
2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 2 Text Book: • J. Kleinberg and E. Tardos, Algorithm design, Addison-Wesley, 2005. • We will add more material in the handout. References: • T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, The MIT Press. http://theory.lcs.mit.edu/~clr/ • R. Sedgewick, Algorithms in C++, Addison-Wesley, 2002. • A. Levitin, Introduction to the design and analysis of algorithms, Addison-Wesley, 2003. • M.R. Garry and D. S. Johnson, Computers and intractability, a guide to the theory of NP-completeness, W.H. Freeman and company, 1979
Pearson International Edition in Ed ary Copy Educat Algorithm Design. Jon Kleinberg Eva Tardos 2021/26 CS4335 Design and Analysis of
2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 3
Algorithms Step-by-step procedure for calculation Any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output a sequence of computational steps that transform the input into output a sequence of computational steps for solving a well-specified computational problem 2021/26 CS4335 Design and Analysis of
2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 4 Algorithms Step-by-step procedure for calculation. Any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. A sequence of computational steps that transform the input into output. A sequence of computational steps for solving a well-specified computational problem
Example of well-specified problem: Sorting Input: a sequence of numbers l,100,8,25,11,9,2,1,200 Output: a sorted(increasing order or decreasing order)sequence of numbers 1,2,8,9,11,25,100,200 Another example Create web page that contains a list of papers using HTML -everybody can do it Not need to design computational steps Page 5 2021/26 CS4335 Design and Analysis of
2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 5 Example of well-specified problem: Sorting Input: a sequence of numbers 1, 100, 8, 25, 11, 9, 2, 1, 200. Output: a sorted (increasing order or decreasing order) sequence of numbers 1, 2, 8, 9, 11, 25, 100, 200. Another example: Create web page that contains a list of papers using HTML. -everybody can do it. Not need to design computational steps