Practice Problems for Final
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?
how do you know, using Euler's theorems?
if there is one, show one:
Is there an Euler circuit?
how do you know, using Euler's theorems?
if there is one, show one:
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?
how do you know, using Euler's theorems?
if there is one, show one:
Is there an Euler circuit?
how do you know, using Euler's theorems?
if there is one, show one:
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?
how do you know, using Euler's theorems?
if there is one, show one:
Is there an Euler circuit?
how do you know, using Euler's theorems?
if there is one, show one:
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
b) T1(N) - T2(N) = O(1) circle: T 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);
}
b) sum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < i; j++)
sum++;
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++;
6) Consider the following undirected graph
edges: (A,B) (A,C) (B,E) (C,D) (C,E) (D,E)
Is there a Hamiltonian path?
if there is one, show one:
if there is not one, can you give an argument proving it?
Is there a Hamiltonian circuit?
if there is one, show one:
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?
if there is one, show one:
if there is not one, can you give an argument proving it?
Is there a Hamiltonian circuit?
if there is one, show one:
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?
if there is one, show one:
if there is not one, can you give an argument proving it?
Is there a Hamiltonian circuit?
if there is one, show one:
if there is not one, can you give an argument proving it?
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
b) Using this array representation, show the subscript
calculations needed to find the children of the node
with value "13"
c) Using this array representation, show the subscript
calculations needed to find the parent of the node
with value "33"
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
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.
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.
//*** NOT APPLICABLE FALL 2015 **********************************************
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
//***************************************************************************
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.
14) Is selection sort stable? Why or why not?
14) Is insertion sort stable? Why or why not?
15) Is quicksort stable? Why or why not?
16) Is heapsort stable? Why or why not?
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?
b) Would you call the arcs weighted, or unweighted? Discuss any nuances
to your choice.
c) Provide a drawing to represent the graph
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
b) Is the graph acyclic? If so, give a topological sorting of the
vertices in the graph; if not, identify a cycle.
c) Determine the shortest paths from vertex v5 to all the other
vertices in this graph.
d) Determine the shortest paths from vertex v1 to all the other
vertices in this graph.
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.
b) There is an O(N^2) algorithm for finding Hamiltonian paths in
undirected graphs.
c) There is an O(N^2) algorithm for finding Euler paths in
undirected graphs.
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.
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.
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
b) you had only a small constant amount of extra memory to use
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.
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.
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.
c) Find a minimum spanning tree using Prim's algorithm.
d) By inspection, find a different spanning tree from your
minima.
23) What are the two properties that a binary heap (minimum heap)
must exhibit?