Analysis of Algorithms
Analysis of Algorithms CS 483
Popular in Course
Popular in ComputerScienence
This 7 page Class Notes was uploaded by Leland Swift on Monday September 28, 2015. The Class Notes belongs to CS 483 at George Mason University taught by Staff in Fall. Since its upload, it has received 110 views. For similar materials see /class/215131/cs-483-george-mason-university in ComputerScienence at George Mason University.
Reviews for Analysis of Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/28/15
C8483 Final Exam Hints Version 2 1 D 00 10 Give a Huffman code for this string Write down both the tree and the actual binary encoding of the string ABAABAACAABAACACAACBAACBAACA compute frequencies for the individual symbols run the hu man tree algorithm to construct the optimal code write down the code for each symbol write down the encoding for the entire string 10 Suppose you have to nd a route in the network which has enough bandwith for the connection Your network has n nodes and bij is the bandwidth between nodes 2 and j The bandwidth of the connection depends on ie is the lowest bandwith link in the route a Suppose that you are given two nodes 2 andj and the needed bandwidth B How would you ef ciently nd a route from j to j which has bandwidth 2 B b Suppose that you want a route of maximum bandwidth from 2 to j How would you ef ciently nd such a route 7 o a Modify Dijkstra7s relaxation procedure The dv instead of representing the cost of the path from source to v7 will be representing the bandwidth connection found so far When deciding whether to relax the vertex when encountering the edge u7v with weight buy7 one has to check whether mindv7mindu7bu2 L B is above the desired bandwidth If yes then return the path 0 b Run the entire shortest path algorithm7 then you will end up with the maximal bandwidth 20 We are running one of these three algorithms on the graph below7 where the algorithm has already processed the bold face edges ignore the directions on the edges for Prim7s and Kruskal7s a Prim7s for the minimum spanning tree b Kruskal7s for the minimum spanning tree c Dijkstra7s shortest paths from s a Which edge would be added next in Prim7s algorithm b Which edge would be added next in Kruskal7s algorithm c Which vertex would be marked next in Dijkstra7s algorithm ie deleted from the top of the heap d Which nal edge would Dijkstra7s algorithm choose as part of the shortest path to this vertex ie which edge connects to this vertex as a part of the path of the 4 Cf shortest path from 5 this refers to vertex found in the previous step 0 CG added with Prim7s 0 FE Added with Kruskal7s o A marked with Dijkatra7s and last edge would be BA 5 You are given a computer network where some pairs are connected by a 2 way communication line You know which computers have links directly connecting them and you want to nd out for a speci c computer 00 its shortest route to every other computer 01 in the network The distance is de ned in tems of number of hops the message must travel There are 0 computers and L links Suggest an ef cient algorithm to nd the best route to all other computers in the network 0 Start BFS at the source computer Number of hops corresponds to the level in the BFS tree 10 What is the running time of Dijkstra7s algorithm when the priority queue is maintained as a a simple linear array b an ordinary binary heap c ls Dijkstra7s algorithm a greedy algorithm 7 DijkstraG w s for each vertex 1 EAdj u do Relaxuvw 1 Initialize single sourceGs 2 S lt O 3 Q lt o 4 while Q 7 o 5 do u lt EXtract MinQ 6 S lt S Uu 7 8 0 V2 7 since for each vertex7 in worst case the whole array has to be searched in order to nd minimum Relaxation is done in constant time 6 I o E log V see the book for explanation 0 Yes it is a greedy algorithm 0 The topological sort of an arbitrary directed graph GV E can be computed in linear time Only for acyclic graphs 0 Kruskal7s algorithm for minimum weight spanning trees is an example of dynamic programming algorithm false It is a greedy algorithm at each step 7safe7 edge with minimum weight is selected 0 Shortest path between two vertices is unique if all edge weights are distinct No Come up with an example It is the MWST which is unique if all edge weight are distint o A arbitrary graph with GV E with lVl 7 1 edges is a tree Yes as long as it is not disconnected and have cycles o If problem A reduces is polynomial time reducible to problem B and B is NP complete then A is NP complete False ls is the other way around If B reduced to A and B is NP complete then A is NP complete 0 Every problem in NP is NP complete False o If problem A reduces to problem B and B is in P then A is in P Yes The running time of A will be combination of reduction which can be done in polynomial time and the actual running time of B see slides note 10 Consider following matrix which corresponds to the initialized distance matrix of the all pairs shortest path algorithm 4 oo 0 4 0000000 2 0 oo 1 genoco a Draw the corresponding graph b Execute two iterations of Floyd Warshal algorithm What is the running time of the Floyd Warshal algorithm d In the following formula for updating costs which you can use what does k cor responds to 7 0 d mmd 1d 1 dig 0 Just run the algorithm 15 Extra credit problem Let 2 CNF SAT be a set of sati able boolean formulas in ONE with exactly 2 literals per clause Show that 2 CNF SAT E P Suggest an ef cient algorithm Hint Observe that x V y is equivalent to s a Reduce 2 CNF SAT to a problem in a directed graph that is ef ciently solvable Exam III Review Material 0 NPCompleteness 0 From Cormen chapter 3417343 0 Understand the formalism Formal lan ge notion Complexity class de nitions Reducability reduction functions 0 Understand basic set theory concepts Operators such as complement Kleene star concatenation union intersection etc The mathematical concept of closure ie what it means for a set to be closed under some operator etc Let A be a set and f be anoperation on set elements lfb fa E A gt b E A then we say that A is closed under f For example the set ofreal numbers is closed under arithmetic operators but is not closed under square root the square root of l is imaginary 0 Advanced problem solving methods 0 Dynamic Programming Backtracking Branch amp Bound Greedy algorithms 0 Dynamic Programming and Greed Algorithms from Cormen the rest is from class notes 0 Guest lecture slides available online from Course Schedule page Understand how the algorithms work be able to demonstrate them on a given problem Understand the advantages and disadvantages of the methods on various problems Good exercise Take example problems in lecture notes and explore how each method would be used to solve it What are the advantages and disadvantages to various approaches etc o Randomized Algorithms 0 Part from Cormen Chapter 5153 0 Additional material from class notes slides available online o Cormen section 54 contains some information relating indirectly to the coupon collectors problem section 542 Balls and bins Understand the differences between probabilistic analysis and randomized algorithms and how RAs can be used in design and analysis Understand how to use some of the analytical tools we discussed such as indicator variables Understand the basic difference between Las Vegas and Monte Carlo RAs 0 Understand the abstract problems we discussed Occupancy and Coupon collectors problems Wont be expected to know speci c distribution facts but you may be required to do some basic probability given those facts 65483 MidTerm Review Analysis of AlgoriThms General MoTivaTion ObjecTive of The course how To design and analyze algoriThms AlgoriThms recipes for solv ng problems They are realized by programs Programs sequences of insTrucTions One alTernaTive Take a program and counT The number of nsTrucTions This may be depend on mplemenTaTion We need some measure how To compare Them which would be ndependenT of mach ne deTails and iT would depend on The METHOD used To solve The problem In general given a program The number of nsTrucTions will depend oninpuT depends of The size of npuT number of inpuT elemenTs n depends on parTicuIar npuT Comparing algoriThmsprograms We wanT To compare algoriThms in The same class Trying To solve The same problems wiThouT worrying abouT deTails of speed of compuTer implemenTaTion Running Time gt Number of insTrucTions as a funcTion of inpuT size n AlgoriThm 1 Takes fn sTeps algoriThm 2 Takes gn sTeps we WanT To compare Them gt compare funcTions f g for large n Order of growTh of funcTions DefiniTions of classes of funcTions Upper bound lower bound TighT bound noT TighT upper lower bound Ofnfn 2fn AsympToTic Efficiency Measuring inpuT size WhaT is elemenTary operaTion DefiniTion of asympToTic noTaTions Basic Efficiency classes AsympToTic running Time of some elemenTary algoriThms sequenTial search binary search bruTe force algoriThms closesT pair convex hull eTc compuTing summaTions see appendix Techniques how To compare funcTions FOC I39Si polynomials are dominaTed by higher order Terms n3 n2 3n 013 To show iT from definiTion choose cand no such ThaT inequaliTies hold fn 3723 gn 3072 FOC I39Si exponenTial funcTions grow fasTer Then polynomials b lzmn oog n 0 Comparing funcTions using limiTs L39HospiTal rule zzmnsoom a M am 1 gn limnsmm 0 fn cum 2 gn sznsoom oo fn mm 3 gn WorsT case running Time LongesT running Time on any in LlT Regardless of The ianlT iT will Take af masfwn sTeps IT is The upper bound of The algoriThm on any ianlT Lower bound on The worsTcase running Time re is some ianlT ThaT The algoriThm will perform af easffn sTeps Worst case result on a particular array Best case result on a particular array If we ma e sTaTemenT abouT The algoriThm iT has To be for any inpuT Design and analysis of algorifhms Types of algoriThms ITeraTive lelTiple loops CompuTe exacT running time bounding summations Design and analysis of algorifhms Iferafive mulTiple loops ComleTe exacT running Time bounding slemaTions Recursive algoriThms parTiTion inTo smaller subproblems To esTablish The running Time we need To solve The recLlrrenT LlaTions Techniques for solving recurrences Expansion expand and comleTe or bound slemaTions 2 MasTer39s Theorem for divide and conquer problems Examples of recursive algoriThms Merge SorT Quick SorT Binary Search SelecTion Tower of Hanoi eTc number of biTs in n39s binary represenT BruTe force algorifhms SelecTion SorT worsT case running Time Bubble SorT worsT case running Time SequenTial Search STring MaTching ClosesT Pair Convex Hull problems ExhausTive Search knapsack Traveling salesman assignmenT problems Divide and Conquer strategy leads to recurrences of special form T ngt aw M Merge Sort Quick Sort Binary Search Matrix Multiplication Closest Pair and Convex Hull Master39s theorem Tn IT fn Exampes T0 7Tni2 4 quot2 Casel matrix multiplication alg lTn 2T rL2 wl Case 2 balanced Toi 47 n2 quot3 Case 3 made up 1 cost dominated by root 2 balanced 3 cost dominated by leaves Sorting algorithms Merge Sort Recursive algorithm splitsortmerge Master39s Theorem 6 7L lg n Heap Sort Combination of recursive and iterative G 77 lg 77 Quick Sort average time complexity Recursive algorithm partitionsplitsort e n lg 7L Worstcase partitioning for particular input 012 Bestcase partitioning for particular inputlower bound In general it is good to have an upper bound and lower bound on worsttime complexity as close as possible Decrease and Conquer Graph representations DF computed times vertices were first and last visited label edges as tree back forward es connected com onent BSF the same their efficiency queue Directed vs undirected graphs DAGs properties of DAGs no back edges Topological Sort reverse popping or source emova Generating Permutations minimal of operations Generating Subsets
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'