DESIGN AND ANALYSIS OF ALGORITHM: DESIGN AND ANALYSIS OF ALGORITHM By: Er.Bhupinder kaur (Asst.Professor CSE)
Topics to be covered: Topics to be covered Introduction Performance analysis of algorithm Elementary data structure Backtracking Branch-And-Bound Dynamic Programming
Introduction to Algorithm: Introduction to Algorithm An algorithm is a finite set of instructions that takes set of values as input and produces set of values as output. A sequence of computational steps that transform the input into the output. A tool for solving a well - specified computational problem. Any special method of solving a certain kind of problem
Characteristics of algorithm: Characteristics of algorithm Input : Zero or more quantities are externally supplied. Output : At least one quantity is produced. Definiteness : Each instruction is clear and unambiguous. Finitenes s: Algorithm must terminate after a finite number of steps. Effectiveness : Each step must be sufficiently basic ie.it must be carried out by a person using paper and pencil. Each step must be not only definite but also be feasible.
Importance of Analyze Algorithm: Importance of Analyze Algorithm Need to recognize limitations of various algorithms for solving a problem Need to understand relationship between problem size and running time Need to learn how to analyze an algorithm's running time without coding it Need to learn techniques for writing more efficient code Need to recognize bottlenecks in code as well as which parts of code are easiest to optimize
Performance analysis of algorithm : Performance analysis of algorithm Algorithm analysis : a process of determining the amount of time, resource, etc. required when executing an algorithm. Space complexity : It is the amount of memory it needs to run to completion. Time complexity : It is the amount of time it needs to run to completion.
Asymptotic Notations: Asymptotic Notations It enables us to make meaningful statements about the time and space complexities of an algorithm. O-notation (Big Oh) Θ -notation (Big Omega) Ω -notation (Big Theta)
ASYMPTOTIC NOTATIONS O-notation (Big Oh): ASYMPTOTIC NOTATIONS O-notation (Big Oh) f(N) = O(g(N)) There are positive constants c and n 0 such that f(N) c g(N) when N n 0 The growth rate of f(N) is less than or equal to the growth rate of g(N) g(N) is an upper bound on f(N)
ASYMPTOTIC NOTATIONS Θ-notation (Big Theta): ASYMPTOTIC NOTATIONS Θ -notation (Big Theta) Asymptotic tight bound Θ (g(n)) represents a set of functions such that: Θ (g(n)) = {f(n): there exist positive constants c 1 , c 2 , and n 0 such that 0 ≤ c 1 g(n) ≤ f(n) ≤ c 2 g(n) for all n≥ n 0 }
ASYMPTOTIC NOTATIONS Ω-notation (Big Omega): ASYMPTOTIC NOTATIONS Ω -notation (Big Omega) f(N) = (g(N)) There are positive constants c and n 0 such that f(N) c g(N) when N n 0 The growth rate of f(N) is greater than or equal to the growth rate of g(N).
Elementary Data Structures: Elementary Data Structures Stack : It is an ordered list in which all insertions and deletions are made at one end called top . It refers to as L ast I n F irst O ut (LIFO). Queue: The first element that is inserted into the queue is the first one to be removed. It refers to as F irst I n F irst O ut (FIFO). Linked List: A singly linked list is a concrete data structure consisting of a sequence of nodes.
Contd..: Contd.. Trees : It is an abstract model of a hierarchical structure. It consists of nodes with a parent-child relation. Binary Trees : It is a finite set of nodes that is either empty or consists of root called left and right subtrees. Example: arithmetic expression tree for the expression (2 ( a - 1) + (3 b)) + - 2 a 1 3 b
Backtracking: Backtracking Backtracking is a methodical way of trying out various sequences of decisions, until you find one that “works”. start ? ? dead end dead end ? ? dead end dead end ? success! dead end
Terminology of Backtracking: Terminology of Backtracking A tree is composed of nodes There are three kinds of nodes: The (one) root node Internal nodes Leaf nodes Backtracking can be thought of as searching a tree for a particular “goal” leaf node
The backtracking algorithm: The backtracking algorithm Backtracking is really quite simple--we “explore” each node, as follows: To “explore” node N: 1. If N is a goal node, return “success” 2. If N is a leaf node, return “failure” 3. For each child C of N, 3.1. Explore C 3.1.1. If C was successful, return “success” 4. Return “failure”
Example: Eight Queen Problem: Example: Eight Queen Problem Place 8 queens in a chessboard so that no two queens are in the same row, column, or diagonal. A solution Not a solution
Solution to problem: Solution to problem Each recursive call attempts to place a queen in a specific column A loop is used, since there are 8 squares in the column For a given call, the state of the board from previous placements is known (i.e. where are the other queens?).
Contd..: Contd.. Current step backtracking : If a placement within the column does not lead to a solution, the queen is removed and moved "down" the column Previous step backtracking : When all rows in a column have been tried, the call terminates and backtracks to the previous call (in the previous column)
Contd..: Contd.. Pruning : If a queen cannot be placed into column i, do not even try to place one onto column i+1 – rather, backtrack to column i-1 and move the queen that had been placed there Using this approach we can reduce the number of potential solutions even more.
Backtracking in 8-Queen problem: Backtracking in 8-Queen problem Backtracking prunes entire sub trees if their root node is not a viable solution The algorithm will “backtrack” up the tree to search for other possible solutions
Efficiency of Backtracking: Efficiency of Backtracking This given a significant advantage over an exhaustive search of the tree for the average problem Worst case: Algorithm tries every path, traversing the entire search space as in an exhaustive search
Branch-And-Bound: Branch-And-Bound The branch-and-bound design strategy is very similar to backtracking in that a state space tree is used to solve a problem. The differences are that the branch-and-bound method 1) does not limit us to any particular way of traversing the tree, and 2) is used only for optimization problems. A branch-and-bound algorithm computes a number (bound) at a node to determine whether the node is promising.
Contd..: Contd.. Besides using the bound to determine whether a node is promising, we can compare the bounds of promising nodes and visit the children of the one with the best bound. This approach is called best-first search with branch-and-bound pruning. The implementation of this approach is a modification of the breadth-first search with branch-and-bound pruning.
Example: The assignment problem: Example: The assignment problem We want to assign n people to n jobs so that the total cost of the assignment is as small as possible (lower bound)
Example: The assignment problem: Example: The assignment problem Select one element in each row of the cost matrix C so that: no two selected elements are in the same column; and the sum is minimized For example: Job 1 Job 2 Job 3 Job 4 Person a 9 2 7 8 Person b 6 4 3 7 Person c 5 8 1 8 Person d 7 6 9 4 Lower bound : Any solution to this problem will have total cost of at least : sum of the smallest element in each row = 10
Assignment problem: lower bounds: Assignment problem: lower bounds
State-space levels 0, 1, 2: State-space levels 0, 1, 2
Complete state-space: Complete state-space
Dynamic Programming: Dynamic Programming It is an algorithm design method that can be used when the solution to a problem can be viewed as a sequence of decisions. Dynamic programming solves optimization problems by combining solutions to sub problems “Programming” refers to a tabular method with a series of choices, not “coding”
Contd..: Contd.. A set of choices must be made to arrive at an optimal solution Recall the divide-and-conquer approach Partition the problem into independent sub problems Solve the sub problems recursively Combine solutions of sub problems
Sequence of Dynamic programming: Sequence of Dynamic programming A dynamic programming approach consists of a sequence of 4 steps Characterize the structure of an optimal solution Recursively define the value of an optimal solution Compute the value of an optimal solution in a bottom-up fashion Construct an optimal solution from computed information
PowerPoint Presentation: THANK YOU