香港城市大学：Introduction to Real-Time Systems（Design and Analysis of Algorithms）

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

Soviet rail Network. 1955 量a 荡 的面 减 的画 出A Reference: On the history of the transportation and maximum flow prob/ Alexander Schrijver in Math Programming, 91: 3, 2002 Find a shortest path from station a to station B -need serious thinking to get a correct algorithm 2021/26 CS4335 Design and Analysis of

2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 6 Find a shortest path from station A to station B. -need serious thinking to get a correct algorithm. A B

A Real-Time Drivers Direction System Given an electronic map(stored on a computer ), the position of your car(provided by GPs), and the destination the system can tell you the way to go to the destination Tell you tern left or right 40 meters before according to the shortest path If you did not follow the direction, re-calculate the shortest path USS 400 each 2021/26 CS4335 Design and Analysis of

2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 7 A Real-Time Driver’s Direction System Given an electronic map (stored on a computer), the position of your car (provided by GPS), and the destination, the system can tell you the way to go to the destination. Tell you tern left or right 40 meters before according to the shortest path. If you did not follow the direction, re-calculate the shortest path. US$ 400 each

Dijkstras Algorithm: (Recall) Dijkstra's algorithm assumes that w(e) 20 for each e in the graph maintain a set s of vertices such that Every vertex v ES, d/v/=8(s, v), i.e., the shortest-path from s to v has been found (Intial values: S-=empty, d[s=0 and d[v=ac) (a) select the vertex uev-S such that d/u=min d/x/x Ev-S/ Set S-=sufu (b) for each node v adjacent to u do relax(u, v, w) Repeat step(a)and (b )until S=v 2021/26 CS4335 Design and Analysis of

2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 8 Dijkstra’s Algorithm: (Recall) Dijkstra’s algorithm assumes that w(e)0 for each e in the graph. maintain a set S of vertices such that Every vertex v S, d[v]=(s, v), i.e., the shortest-path from s to v has been found. (Intial values: S=empty, d[s]=0 and d[v]=) (a) select the vertex uV-S such that d[u]=min {d[x]|x V-S}. Set S=S{u} (b) for each node v adjacent to u do RELAX(u, v, w). Repeat step (a) and (b) until S=V

Descriptions of algorithms Flow chart Pseudo-code Programs Natural languages The purpose: Allow a well-trained programmer to write a program to solve the computational problem Any body who can talk about algorithm MUst have basic programming skills Also cs3334: Data structures 2021/26 CS4335 Design and Analysis of

2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 9 Descriptions of Algorithms Flow chart Pseudo-code Programs Natural languages The purpose: Allow a well-trained programmer to write a program to solve the computational problem. Any body who can talk about algorithm MUST have basic programming skills Also CS3334: Data structures

What We cover 1. Some classic algorithms in various domains Graph algorithms Euler path, shortest path, minimum spanning trees, maximum flow, Hamilton Cycle, traveling salesman String Algorithms Exact string matching, Approximate string matching, Applications in web searching engines Scheduling problems Computational Geometry 2. Techniques for designing efficient algorithms divide-and-conquer approach, greedy approach, ynamic programming 2021/26 CS4335 Design and Analysis of

2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 10 What We Cover: 1. Some classic algorithms in various domains Graph algorithms • Euler path, shortest path, minimum spanning trees, maximum flow, Hamilton Cycle, traveling salesman, String Algorithms • Exact string matching, Approximate string matching, Applications in web searching engines Scheduling problems Computational Geometry 2. Techniques for designing efficient algorithms divide-and-conquer approach, greedy approach, dynamic programming