01) There are a number of ways to organize a collection of integers if the problem we wish to solve is to remove the minimum item in the collection each time we access it. One way is to build a priority queue and use the "removeMin" operation. Another way is to keep a simple linked list and search for the smallest item and remove it when needed. What is the break even size (number of items) that makes a priority queue cheaper to use than the simple linked list? you can analyze this as average or as worst case avg: list takes 1/2N to do a find pque takes log N to do a remove min what is N where log N = 1/2N? 2 log N = N N/(log N) = 2 N = 4 worst case: list takes N for a find pque takes log N to do a removeMin log N = N N/log N = 1 there isnt one basically dont use the list 02) Draw a graph (>=7 nodes) that has one spanning tree... which is therefore its minimum spanning tree. 03) Draw a graph (>=7 nodes) that has more than one minimum spanning tree. 04) Draw a graph (>=7 nodes) that has more than one spanning tree, but only one minimum spanning tree. 05) Draw the complete graph with 6 nodes. 06) a) Draw a graph that is planar. b) Draw a graph that is NOT planar. 07) True or False (if false, give an example) a) all acyclic undirected graphs are trees true b) all directed acyclic graphs (DAG) are trees false 08) We learned that the Halting Problem is undecideable (no program can be written to solve the problem). The problem was defined this way: given ANY program P and any input I for that program, does the P halt when executed using I as input? What if we restrict the problem to any program P without loops (either explicit, like "while" or made with "goto" jumps)? Is the Halting Problem unsolvable on programs without loops? If yes, can you think of an algorithm that would answer the problem? If no, can you give an argument supporting your claim? What about detecting if a program has loops? Can we write a program that will examine a program P and an input I and decide if P has no loops? 09) Given the following graph, a) give the order the nodes are visited when you use a depth-first search starting at node A. b) give the order the nodes are visited when you use a depth-first search starting at node F. c) give the order the nodes are visited when you use a breadth-first search starting at node A. d) give the order the nodes are visited when you use a breadth-first search starting at node F. this is an adjacency matrix, and it is symmetric so it represents an undirected graph. You may wish to draw the graph to solve the problem but you can also work it straight off the matrix A B C D E F G H I A x x x B x x x x x C x x x D x x x x E x x x x F x x x x x G x x H x x x I x 10) For each of the following problems, describe an algorithm to solve the problem and give its worst case time (use asymptotic notation). Make sure to cleary indentify what you use as the size of the problem. a) given a collection of integers, find all the subsets with elements that sum to greater than the average of the elements b) given a string of characters (and a dictionary), show all the rearragements of the characters that are "real words".