Analysis algorithm introduction Lecture# 1

Analysis algorithm introduction Lecture# 1

• 1.
  Lecture 2 Introduction 1 Analysis of Algorithms Spring 2008 Introduction Lec-1 Prepared by Dr. Zahoor Jan Department of Computer Science, University of Peshawar 11-02-08
• 2.
  Lecture 2 Introduction Yahoo group • Group name: Algo_UOP_Spring08 Group home • page: http://groups.yahoo.com/group/Algo_UOP_Spring08 • Group email: Algo_UOP_Spring08@yahoogroups.com 2 11-02-08
• 3.
  3 Analysis ofAlgo Steps involved in writing aa ccoommppuutteerr pprrooggrraamm:: • Problem formulation & specification • Design of solution • Implementation • Testing • Documentation • Evaluation of the solution 11-02-08
• 4.
  Problem formulation &&ssppeecciiffiiccaattiioonn • Half the battle is knowing what problem to solve. • Most problems have no simple precise specification. • Some problems are impossible to formulate. • Example: Gourmet recipe, World peace, Etc. 4 Analysis of Algo 11-02-08
• 5.
  How to formulate&& ssppeecciiffyy aa pprroobblleemm?? • Identify the problem parameters. • Expressing the problem by a formal model. • Looking for a solution for the model. • In the absence of a solution, discover about the model. 5 Analysis of Algo 11-02-08
• 6.
  How ttoo mmooddeellaanndd ssoollvvee aa pprroobblleemm?? • Using any branch of Mathematics or Science. • Identifying problems of numerical nature. • With a suitable model, attempt to find a solution in terms of that model • Simultaneous linear equations for electrical circuits. • Differential equations for predicting chemical reaction rates. 6 Analysis of Algo 11-02-08
• 7.
  7 Analysis ofAlgo AAllggoorriitthhmm • Finite sequence of instructions. • Each instruction having a clear meaning. • Each instruction requiring finite amount of effort. • Each instruction requiring finite time to complete. 11-02-08
• 8.
  AAllggoorriitthhmm • Finitesequence of instructions. An input should not take the program in an infinite loop • Each instruction having a clear meaning. Very subjective. What is clear to me, may not be clear to you. • Each instruction requiring finite amount of effort. Very subjective. Finite on a super computer or a P4? • Each instruction requiring finite time to complete. Very subjective. 1 min, 1 hr, 1 year or a lifetime? 8 Analysis of Algo 11-02-08
• 9.
  Algorithm Definition Afinite set of statements that guarantees an optimal solution in finite interval of time 9 Analysis of Algo 11-02-08
• 10.
  Using a mmooddeellttoo ssoollvvee aa ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm GIVEN: A complex intersection. OBJECTIVE: Traffic light with minimum phases. SOLUTION: • Identify permitted turns, going straight is a “turn”. • Make group of permitted turns. • Make the smallest possible number of groups. • Assign each phase of the traffic light to a group. 10 Analysis of Algo 11-02-08
• 11.
  Analysis of Algo Using a mmooddeell ttoo ssoollvvee aa ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm 11 A C B D E An intersection Charsadda Roads C and E are one way, others are two way. 11-02-08
• 12.
  Using a mmooddeellttoo ssoollvvee aa ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm There are 13 permitted turns. Some turns such as AB (from A to B) and AC can be carried out simultaneously. Other like AD and EB cross each other and can not be carried out simultaneously. The traffic light should permit AB and EC simultaneously, but should not allow AD and EB. 12 Analysis of Algo 11-02-08
• 13.
  Analysis of Algo Using a mmooddeell ttoo ssoollvvee aa ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm 13 A C B D E An intersection AB & AC AD & EB 11-02-08
• 14.
  Using a mmooddeellttoo ssoollvvee aa ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm SOLUTION: • We model the problem using a structure called graph G(V,E). • A graph consists of a set of points called vertices V, and lines connecting the points, called edges E. •Drawing a graph such that the vertices represent turns. • Edges between those turns that can NOT be performed simultaneously. 14 Analysis of Algo 11-02-08
• 15.
  Using a mmooddeellttoo ssoollvvee aa ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm 15 AD A C B D E An intersection BD AB AC BA BC DA DB DC EA EB EC ED Partial graph of incompatible turns Analysis of Algo 11-02-08
• 16.
  Analysis of Algo Using a mmooddeell ttoo ssoollvvee aa ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm 16 Partial table of incompatible turns 11-02-08
• 17.
  Using a mmooddeellttoo ssoollvvee aa ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm SOLUTION: The graph can aid in solving our problem. A coloring of a graph is an assignment of a color to each vertex of the graph, so that no two vertices connected by an edge have the same color. Our problem is of coloring the graph of incompatible turns using as few colors as possible. 17 Analysis of Algo 11-02-08
• 18.
  Using a mmooddeellttoo ssoollvvee aa ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm More on SOLUTION (Graph coloring): Graph coloring problem has been studied for decades. The theory of algorithms tells us a lot about it. Unfortunately this belongs to a class of problems called as NP-Complete problems. For such problems, all known solutions are basically “try all possibilities” In case of coloring, try all assignments of colors. 18 Analysis of Algo 11-02-08
• 19.
  Using a mmooddeellttoo ssoollvvee aa ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm Approaches to attempting NP-Complete problems: 1. If the problem is small, might attempt to find an optimal solution exhaustively. 2. Look for additional information about the problem. 3.Change the problem a little, and look for a good, but not necessarily optimal solution. An algorithm that quickly produces good but not necessarily optimal solutions is called a heuristic. 19 Analysis of Algo 11-02-08
• 20.
  20 Analysis ofAlgo 11-02-08
• 21.
  Using model tosolve complicated ttrraaffffiicc lliigghhtt pprroobblleemm A reasonable heuristic for graph coloring is the greedy “algorithm”. Try to color as many vertices as possible with the first color, and then as many uncolored vertices with the second color, and so on. The approach would be: 1. Select some uncolored vertex, and color with new color. 2. Scan the list of uncolored vertices. 3. For each uncolored vertex, determine whether it has an edge to any vertex already colored with the new color. 4. If there is no such edge, color the present vertices with the new color. 11-02-08 21
• 22.
  UUssiinngg mmooddeell ttoossoollvvee ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm This is called “greedy”, because it colors a vertex, whenever it can, without considering potential drawbacks. 22 1 5 3 4 22 1 5 3 4 2 Three colors used Two colors used ((ooppttiimmuumm)) 11-02-08
• 23.
  Analysis of Algo Using a mmooddeell ttoo ssoollvvee aa ccoommpplliiccaatteedd ttrraaffffiicc lliigghhtt pprroobblleemm Work SMART 23 not HARD  11-02-08