Introduction to Algorithms Massachusetts Institute of Technology Professors Erik Demaine Piotr Indyk and Manolis Kellis April 13 2011 6 006 Spring 2011 Quiz 2 Solutions Quiz 2 Solutions Problem 1 True or false 24 points 8 parts For each of the following questions circle either T True or F False Explain your choice Your explanation is worth more than your choice of true or false a T F Instead of using counting sort to sort digits in the radix sort algorithm we can use any valid sorting algorithm and radix sort will still sort correctly Solution False Need stable sort b T F The depth of a breadth first search tree on an undirected graph G V E from an arbitrary vertex v V is the diameter of the graph G The diameter d of a graph is the smallest d such that every pair of vertices s and t have s t d Solution False An arbitrary vertex could lay closer to the center of the graph hence the BFS depth will be underestimating the diameter For example in graph G V E a v b a v v b a BFS from v will have depth 1 but the graph has diameter 2 6 006 Quiz 2 Solutions Name c T F Every directed acyclic graph has exactly one topological ordering Solution False Some priority constraints may be unspecified and multiple orderings may be possible for a given DAG For example a graph G V E a b c a b a c has valid topological orderings a b c or a c b As another example G V E a b has valid topological orderings a b or b c d T F Given a graph G V E with positive edge weights the Bellman Ford algorithm and Dijkstra s algorithm can produce different shortest path trees despite always producing the same shortest path weights Solution True Both algorithms are guaranteed to produce the same shortestpath weight but if there are multiple shortest paths Dijkstra s will choose the shortest path according to the greedy strategy and Bellman Ford will choose the shortest path depending on the order of relaxations and the two shortest path trees may be different 2 6 006 Quiz 2 Solutions Name e T F Dijkstra s algorithm may not terminate if the graph contains negative weight edges Solution False It always terminates after E relaxations and V E priority queue operations but may produce incorrect results f T F Consider a weighted directed graph G V E w and let X be a shortest s t path for s t V If we double the weight of every edge in the graph setting w0 e 2w e for each e E then X will still be a shortest s t path in V E w0 Solution True Any linear transformation of all weights maintains all relative path lengths and thus shortest paths will continue to be shortest paths and more generally all paths will have the same relative ordering One simple way of thinking about this is unit conversions between kilometers and miles 3 6 006 Quiz 2 Solutions Name g T F If a depth first search on a directed graph G V E produces exactly one back edge then it is possible to choose an edge e E such that the graph G0 V E e is acyclic Solution True Removing the back edge will result in a graph with no back edges and thus a graph with no cycles as every graph with at least one cycle has at least one back edge Notice that a graph can have two cycles but a single back edge thus removing some edge that disrupts that cycle is insufficient you have to remove specifically the back edge For example in graph G V E a b c a b b c a c c a there are two cycles a b c a and a c a but only one back edge c a Removing edge b c disrupts one of the cycles that gave rise to the back edge a b c a but another cycle remains a c a h T F If a directed graph G is cyclic but can be made acyclic by removing one edge then a depth first search in G will encounter exactly one back edge Solution False You can have multiple back edges yet it can be possible to remove one edge that destroys all cycles For example in graph G V E a b c a b b c b a c a there are two cycles a b a and a b c a and a DFS from a in G returns two back edges b a and c a but a single removal of edge a b can disrupt both cycles making the resulting graph acyclic 4 6 006 Quiz 2 Solutions Name Problem 2 Short answer 24 points 6 parts a What is the running time of R ADIX S ORT on an array of n integers in the range 0 1 n5 1 when using base 10 representation What is the running time when using a base n representation Solution Using base 10 each integer has d log n5 5 log n digits Each C OUNTING S ORT call takes n 10 n time so the running time of R ADIX S ORT is nd n log n Using base n each integer has d logn n5 5 digits so the running time of R ADIX S ORT is 5n n 2 points were awarded for correct answers on each part A point was deducted if no attempt to simplify running times were made e g if running time for base 10 representation was left as log10 n5 n 10 Common mistakes included substituting n5 as the base instead of 10 or n This led to n5 and n6 runtimes b What is the running time of depth first search as a function of V and E if the input graph is represented by an adjacency matrix instead of an adjacency list Solution DFS visits each vertex once and as it visits each vertex we need to find all of its neighbors to figure out where to search next Finding all its neighbors in an adjacency matrix requires O V time so overall the running time will be O V 2 2 points were docked for answers that didn t give the tightest runtime bound for example O V 2 E While technically correct it was a key point to realize that DFS using an adjacency matrix doesn t depend on the number of edges in the graph 5 6 006 Quiz 2 Solutions Name 6 c Consider the directed graph where vertices are reachable tic tac toe board positions and edges represent valid moves What are the in degree and out degree of the following vertex It is O s turn X O O X X Solution There were three possible vertices that could have pointed into this board position O O X X X X O O X O O X And there are four possible vertices …
View Full Document
Unlocking...