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? yes how do you know, using Euler's theorems? exactly two nodes have odd degree, so the EP starts at one and ends at the other if there is one, show one: B A F C G D F E G B E Is there an Euler circuit? no how do you know, using Euler's theorems? EC only when all nodes have even degree if there is one, show one: N/A 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? no how do you know, using Euler's theorems? EP only when there are 0 or 2 nodes with odd degree, this graph has 4 nodes with odd degree if there is one, show one: N/A Is there an Euler circuit? no how do you know, using Euler's theorems? if no EP, then no EC if there is one, show one: N/A 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? yes how do you know, using Euler's theorems? all node are even degree so there is EP (and EC) if there is one, show one: E G F E A B C D B F D E Is there an Euler circuit? yes how do you know, using Euler's theorems? all node are even degree so there is an EC if there is one, show one: answer from (a) or another: A B C D B F G E F D E A 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 T b) T1(N) - T2(N) = O(1) circle: T F 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); } O(N) b) sum = 0; for (int i = 0; i < N; i++) for (int j = 0; j < i; j++) sum++; O(N^2) 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++; O(N^7) 6) Consider the following undirected graph edges: (A,B) (A,C) (B,E) (C,D) (C,E) (D,E) Is there a Hamiltonian path? yes if there is one, show one: D C A B E if there is not one, can you give an argument proving it? Is there a Hamiltonian circuit? yes if there is one, show one: A B E D C A 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? yes if there is one, show one: A B D E G C F if there is not one, can you give an argument proving it? Is there a Hamiltonian circuit? yes if there is one, show one: A B D E G C F A 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? no if there is one, show one: N/A if there is not one, can you give an argument proving it? the graph is a tree so you must backtrack to visit all nodes Is there a Hamiltonian circuit? no if there is one, show one: N/A if there is not one, can you give an argument proving it? since there is no HP, there is also no HC 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 _______________________________________________________________ | | | | | | | | | | | | | | | | | | | 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" 13 is at subscript 4 the children of 13 are at 2*4=8, and 2*4+1=9 c) Using this array representation, show the subscript calculations needed to find the parent of the node with value "33" 33 is at subscript 11 the parent of 33 is at floor(11/2) = 5 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 too long to draw in an editor. the O(N) procedure say first put all elements in an array in the order they arrive (the order above). Then bubble the elements starting with the next to last row. The final heap loops like this (array rep) element 2 3 6 8 4 9 19 24 21 7 61 16 29 subscript 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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. element 3 4 6 8 7 9 19 24 21 29 61 16 subscript 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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. _______________________________________________________________ | | | | | | | | | | | | | | | | | | | 6| 11| 8| 13| 21| 12| 23| 27| 14| 29| 33| 19| | | | array: |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 _______________________________________________________________ | | | | | | | | | | | | | | | | | | | 8| 11| 12| 13| 21| 19| 23| 27| 14| 29| 33| | | | | array: |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 _______________________________________________________________ | | | | | | | | | | | | | | | | | | | 11| 13| 12| 14| 21| 19| 23| 27| 33| 29| | | | | | array: |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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 from the text 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. yes it can be if you always pick from the left list first when merging items with the same value 14) Is selection sort stable? Why or why not? not necessarily but it can be made stable with linked lists 14) Is insertion sort stable? Why or why not? yes 15) Is quicksort stable? Why or why not? no, when efficiently sorting inplace you swap elements from one end of the array to another 16) Is heapsort stable? Why or why not? no, there are data sequences that cause two equal elements to come out of the heap in reverse of the order they went in. When a delMin operation is done, heap elements get rearranged and the order of equal elements can get altered during this movement. 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? directed, because the matrix is not symmetric b) Would you call the arcs weighted, or unweighted? Discuss any nuances to your choice. I would call them unweighted, with the "1" simply being used to mean "an arc is there". Same thing could be done with boolean T (and F where there is a 0). However, it could be a weighted graph with a weight on 1 on all arcs. c) Provide a drawing to represent the graph can't draw here 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 can't draw here b) Is the graph acyclic? If so, give a topological sorting of the vertices in the graph; if not, identify a cycle. acyclic topo sort: v5 v3 v2 v4 v1 c) Determine the shortest paths from vertex v5 to all the other vertices in this graph. v1: 3, v5 -> v1 v2: 6, v5 -> v3 -> v2 v3: 1, v5 -> v3 v4: 3, v5 -> v3 -> v4 d) Determine the shortest paths from vertex v1 to all the other vertices in this graph. no paths 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. false is you allow disconnected graphs true if connected graphs b) There is an O(N^2) algorithm for finding Hamiltonian paths in undirected graphs. false? actually, we don't know if its true or false we have not proved there are none (would make the answer false) we have not found one (would make the answer true) c) There is an O(N^2) algorithm for finding Euler paths in undirected graphs. true, since there is also one that is linear in size of graph and since O(N) is a bound, so is O(N^2) (not a tight bound) 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. true 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. no he wont... why not? well he either is creating sorting into buckets (which we already know about) or he is trying to create something that does not exist (a sort that uses only compares and runs in less that O(N log N) time) 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 merge sort... stable, fast, no bad cases b) you had only a small constant amount of extra memory to use quick sort... fast and uses little extra memory however it is not stable 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. using less memory is good even if you have lots of extra however, quick sort if not stable so if you have extra memory you get stable. Also, quicksort has worst case O(N^2) so if you can use mergesort, you get worst case O(N log N). 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. most anything works... all the spanning trees have |V|-1 edges 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. edges are looked at (A,C,2)(A,G,2)(A,E,2)(F,G,1)(D,G,2)(D,B,2) c) Find a minimum spanning tree using Prim's algorithm. pick any node, find smallest arc from it keep picking smallest arc from nodes selected (A,C,2)(A,G,2)(A,E,2)(F,G,1)(D,G,2)(D,B,2) d) By inspection, find a different spanning tree from your minima. (A,C,2)(C,F,6)(C,E,4)(B,F,5)(B,D,2)(B,G,4) 23) What are the two properties that a binary heap (minimum heap) must exhibit? a) heap structure property: a binary heap is a complete binary tree, filled left to right b) heap order property: on any path from a leaf back to the root (or equivalently, from root to a leaf) the elements are in order; for a min heap, the elements are in non-decreasing order from root to leaf.