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 cleaver new algorithm for sorting a list of N numbers; his dissertation says that it runs in O(N) time worst case on a single CPU computer; he will successfully defend this dissertation and receive the PhD degree. 20) If you were given one million 32 bit integers and told to sort them as efficiently as possible (yes, we know bubble sort is not the way to go) what algorithm would you pick if a) you could use any amount of extra memory in sorting b) you had only a small constant amount of extra memory to use c) Why not use the same one for both situations? To answer this consider the best, worst, and average time complexity of the methods you chose. 21) a) Write axioms for the behavior of a data structure we shall call a unique queue, or UQUE. In a UQUE, we add elements to the queue at the back, and we remove them from the front like a plain queue. However, we do not allow two or more elements in the queue to have the same value. We do this during the add operation. If I do, say, add(Q,5) and 5 is already in Q, then nothing is added, and the queue remains the same length as before the add. If 5 is not in Q, then the length of Q grows by 1 and 5 is now at the back of the queue. Let the operations be new, add, peek, rest, length, in, empty. add puts an item on the tail of the queue peek returns the head item rest produces a queue that is whats left when the head item is taken off length tells how many items are in the queue in tells is a particular item is in the queue, or not empty tells if a queue has zero items in it, or not b) Consider implementing this UQUE with some of the data structures we have studied. Is there a way to implement it so that the add operation takes time better than O(N) worst case (for a UQUE of length N)? 22) a) For each of the graphs in problems 1, 2, 3, and 6, 7, 8 find a minimum spanning tree. Consider them to have all edge weights of 1. For (b) and (c) Consider this graph (the number in each edge is the weight): (A,C,2) (A,E,3) (A,G,2) (B,D,2) (B,F,5) (B,G,4) (C,E,4) (C,F,6) (D,G,2) (F,G,1) b) Find a minimum spanning tree using Kruskal's algorithm. c) Find a minimum spanning tree using Prim's algorithm. d) By inspection, find a different spanning tree from your minima. 23) What are the two properties that a binary heap (minimum heap) must exhibit?