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 uV-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