Practice Problems for Final 1 Consider the following undirected graph edges A B A F B E B G C F C G D F D G E F E G Is there an Euler path how do you know using Euler s theorems if there is one show one Is there an Euler circuit how do you know using Euler s theorems if there is one show one 2 Consider the following undirected graph edges A B A C A D B F C D C E D E E F Is there an Euler path how do you know using Euler s theorems if there is one show one Is there an Euler circuit how do you know using Euler s theorems if there is one show one 3 Consider the following undirected graph edges A B A E B C B D B F C D D E D F E F E G F G Is there an Euler path how do you know using Euler s theorems if there is one show one Is there an Euler circuit how do you know using Euler s theorems if there is one show one 4 Suppose that T1 N O f N and T2 N O f N For each of the following indicate if they are true or false a T1 N T2 N O f N circle T F b T1 N T2 N O 1 circle T F 5 Give a tight big Oh run time analysis in terms of N for each of the following code fragments a public static long A int N if N 1 return 1 return N N 1 A N 1 b sum 0 for int i 0 i N i for int j 0 j i j sum c sum 0 for int i 0 i N i for int j 0 j i i j for k 0 k j j k sum 6 Consider the following undirected graph edges A B A C B E C D C E D E Is there a Hamiltonian path if there is one show one if there is not one can you give an argument proving it Is there a Hamiltonian circuit if there is one show one if there is not one can you give an argument proving it 7 Consider the following undirected graph edges A B A D A E A F B C B D C F C G D E E G Is there a Hamiltonian path if there is one show one if there is not one can you give an argument proving it Is there a Hamiltonian circuit if there is one show one if there is not one can you give an argument proving it 8 Consider the following undirected graph edges A B A C B D B E C F C G E H Is there a Hamiltonian path if there is one show one if there is not one can you give an argument proving it Is there a Hamiltonian circuit if there is one show one if there is not one can you give an argument proving it 9 a For the following minimum binary heap drawn as a complete binary tree fill the items into the array below in the correct positions for the way a binary heap is normally represented with an array 4 11 6 13 21 8 23 27 14 29 33 12 19 array 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 b Using this array representation show the subscript calculations needed to find the children of the node with value 13 c Using this array representation show the subscript calculations needed to find the parent of the node with value 33 10 For the following items in the order given construct a minimum binary heap Use the O N algorithm we studied Show the steps in your work 6 3 29 21 7 2 19 24 8 4 61 16 9 11 a For the heap in the previous problem show the heap that results after doing a single removeMin operation Show the steps involved in rearranging the heap elements so that the new minimum ends up at the root b Do the same for the heap shown in problem 9 For good practice do 3 or 4 removeMin operations and re arrange the heap each time NOT APPLICABLE FALL 2015 12 Solve the recurrance equation analyzing the behavior of mergesort T N 2 T N 2 N T N something not using T N Show your steps For 13 16 the thing that gives you the most win is to think on how the sorts work not look up the answer in wikipaedia These are designed to make you study how the sorts manipulate the values being sorted 13 Is mergesort stable Give a good argument as to why or why not 14 Is selection sort stable Why or why not 14 Is insertion sort stable Why or why not 15 Is quicksort stable Why or why not 16 Is heapsort stable Why or why not 17 Consider this adjacency matrix representation for a graph with 0 used to represent no edge v1 v2 v3 v4 v5 v6 v1 1 0 0 0 1 1 v2 0 0 1 0 1 0 v3 1 1 0 1 0 0 v4 0 0 0 0 0 1 v5 1 0 0 1 0 0 v6 0 1 1 0 0 0 a Is this graph directed or undirected How can you tell b Would you call the arcs weighted or unweighted Discuss any nuances to your choice c Provide a drawing to represent the graph 18 Consider this graph represented as an adjacency matrix with 0 used to represent no edge v1 v2 v3 v4 v5 v1 0 0 0 0 0 v2 4 0 0 0 0 v3 0 5 0 2 0 v4 3 0 0 0 0 v5 3 0 1 0 0 a Provide a linked list representation of this graph b Is the graph acyclic If so give a topological sorting of the vertices in the graph if not identify a cycle c Determine the shortest paths from vertex v5 to all the other vertices in this graph d Determine the shortest paths from vertex v1 to all the other vertices in this graph 19 True or False If False give a counter example or tell why its false or change the wording to make it true a All directed graphs with fewer edges than vertices are acyclic b There is an O N 2 algorithm for finding Hamiltonian paths in undirected graphs c There is an O N 2 algorithm for finding Euler paths in undirected graphs d Clyde Kruskal s Uncle s algorithm for finding a minimum spanning tree in an undirected graph is O E V 2 e In a directed weighted graph that is a tree acyclic with every node having indegree of 1 or 0 the minimum spanning tree is the entire graph e A certain Duke student is working on a …
View Full Document