CSC 8301-Design And Analysis Of Algorithms Lecture 4

2/8/17CSC 8301- Design and Analysis of AlgorithmsLecture 4Brute Force, Exhaustive Search,Graph Traversal AlgorithmsBrute-Force ApproachBrute force is a straightforward approach to solving aproblem, usually directly based on the problem’sstatement and definitions of the concepts involved.Example 1: Computing an (a 0, n is a positive integer)Example 2: Searching for a given value in a list1

2/8/17Brute-Force Algorithm for SortingSelection Sort Scan the array to find its smallest element and swap itwith the first element. Then, starting with the second element, scanthe elements to the right of it to find the smallest among them andswap it with the second element. Generally, on pass i (0 i n-2),find the smallest element in A[i.n-1] and swap it with A[i]:A[0] . . . A[i-1] A[i], . . . , A[min], . . ., A[n-1]in their final positionsExample: 7 8 2 3 5Analysis of Selection Sort Basic operation Summation for C(n)2

2/8/17 Summation for C(n)C(n) S0 i n-1 Si 1 j n-1 1Closest-Pair ProblemThe closest-pair problem is to find the two closest points in a set of npoints in the Cartesian plane (with the distance between two pointsmeasured by the standard Euclidean distance formula).Brute-force algorithm for the closest-pair problemCompute the distance between every pair of distinct pointsand return the indexes of the points for which the distance isthe smallest.3

2/8/17Closest-Pair Brute Force Algorithm (cont.) Time efficiency: Noteworthy improvement:General Notes on Brute-Force ApproachStrengths:q wide applicabilityq simplicityq yields reasonable algorithms for some important problems(e.g., sorting, searching, matrix multiplication)Weaknesses:q yields efficient algorithms very rarelyq some brute-force algorithms are unacceptably slowq not as constructive as some other design techniquesNote: Brute force can be a legitimate alternative in view of thehuman time vs. computer time costs4

2/8/17Exhaustive searchExhaustive search is a brute force approach to solving a problem thatinvolves searching for an element with a special property, usuallyamong combinatorial objects such permutations, combinations, orsubsets of a set.Method:– systematically construct all potential solutions to the problem(often using standard algorithms for generating combinatorialobjects such as those in Sec. 4.3)– evaluate solutions one by one, disqualifying infeasible onesand, for optimization problems, keeping track of the bestsolution found so far– when search ends, return the (best) solution foundExample 1: Traveling salesman problem (TSP)Given n cities with known distances between each pair, find theshortest tour that passes through all the cities exactly once beforereturning to the starting city.Alternatively: Find shortest Hamiltonian circuit in a weightedconnected graph.Example:2a5b348c7d5

2/8/17TSP by exhaustive searchToura b c d aa b d c aa c b d aa c d b aa d b c aa d c b aCost2 3 7 5 172 4 7 8 218 3 4 5 208 7 4 2 215 4 3 8 205 7 3 2 17Fewer tours?Efficiency:Example 2: Knapsack ProblemGiven n items withweights: w1 w2 wnvalues:v1 v2 vnand a knapsack of capacity W,find most valuable subset of the items that fit into the knapsackExample: Knapsack capacity W 16item weightvalue12 2025 30310 5045 106

2/8/17Knapsack by exhaustive searchSubset Total 1,2,3,4}22Total value 20 30Efficiency: 50 10 50 70 30 80 40 60not feasible 60not feasiblenot feasiblenot feasibleComments on Exhaustive SearchqqqTypically, exhaustive search algorithms run in a realistic amount oftime only on very small instancesFor some problems, there are much better alternatives– shortest paths– minimum spanning tree– assignment problemIn many cases, exhaustive search (or variation) is the only knownway to solve problem exactly for all its possible instances– TSP– knapsack problem7

2/8/17Graph TraversalMany problems require processing all graph vertices (and edges) insystematic fashion, which can be considered “exhaustive search”algorithmsGraph traversal algorithms:– Depth-first search (DFS)– Breadth-first search (BFS)Depth-First Search (DFS)qVisits graph’s vertices by always moving away from last visitedvertex to unvisited one, backtracks if no adjacent unvisited vertex isavailable.Source: t searchq“Redraws” graph in tree-like fashion (with tree edges and backedges for undirected graph)8

2/8/17Depth-First Search (DFS)qUses a stack– a vertex is pushed onto the stack first time is reached– a vertex is popped off the stack when it becomes a dead end, i.e.,when there is no adjacent unvisited vertexabcdefghExample: DFS traversal of undirected graphqAssumption: ties broken alphabeticallyabcdiefghjDFS traversal stack:DFS forest:9

2/8/17Pseudocode of DFS19Notes on DFSqDFS can be implemented with graphs represented as:– adjacency matrices: Θ( V 2)– adjacency lists: Θ( V E )qYields two distinct ordering of vertices:– order in which vertices are first encountered (pushed onto stack)– order in which vertices become dead-ends (popped off stack)qApplications:– checking connectivity, finding connected components– checking acyclicity– searching state-space of problems for solution (AI)10

2/8/17Breadth-first search (BFS)qVisits graph vertices by moving across to all the neighbors of lastvisited vertexSource: rst searchq“Redraws” graph in tree-like fashion (with tree edges and crossedges for undirected graph)Pseudocode of BFS2211

2/8/17Example of BFS traversal of undirected graphqqInstead of a stack, BFS uses a queueAssumption: neighbors visited in alphabetical orderabcdiefghjBFS traversal queue:BFS forest:Notes on BFSqqqBFS has same efficiency as DFS and can be implemented withgraphs represented as:– adjacency matrices: Θ( V 2)– adjacency lists: Θ( V E )Yields single ordering of vertices (order added/deleted from queueis the same)Applications: same as DFS, but can also find paths from a vertex toall other vertices with the smallest number of edges12

2/8/17HomeworkExercises 3.1: 4, 5, 8, 11Exercises 3.4: 1, 5, 6Exercises 3.5: 1, 2, 4, 6Reading:q Sec. 3.1, 3.4 and 3.5Next: Decrease-and-conquer (Chapter 4)13

CSC 8301-Design and Analysis of Algorithms Lecture 4 Brute Force, Exhaustive Search, Graph Traversal Algorithms Brute-Force Approach Brute forceis a straightforward approach to solving a problem, usually directly based on the problem’s statement and definitions of the concepts involved. E