More Final Exam Practice Problems 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 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 b all directed acyclic graphs DAG are trees NOT APPLICABLE FALL 2015 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