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?


    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".