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