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? yes
how do you know, using Euler's theorems? exactly two nodes have
odd degree, so the EP starts at one and ends at the other
if there is one, show one: B A F C G D F E G B E
Is there an Euler circuit? no
how do you know, using Euler's theorems? EC only when all nodes have
even degree
if there is one, show one: N/A
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? no
how do you know, using Euler's theorems? EP only when there
are 0 or 2 nodes with odd degree, this graph has 4 nodes
with odd degree
if there is one, show one: N/A
Is there an Euler circuit? no
how do you know, using Euler's theorems? if no EP, then no EC
if there is one, show one: N/A
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? yes
how do you know, using Euler's theorems? all node are even degree
so there is EP (and EC)
if there is one, show one: E G F E A B C D B F D E
Is there an Euler circuit? yes
how do you know, using Euler's theorems? all node are even degree
so there is an EC
if there is one, show one: answer from (a)
or another: A B C D B F G E F D E A
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
T
b) T1(N) - T2(N) = O(1) circle: T F
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);
}
O(N)
b) sum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < i; j++)
sum++;
O(N^2)
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++;
O(N^7)
6) Consider the following undirected graph
edges: (A,B) (A,C) (B,E) (C,D) (C,E) (D,E)
Is there a Hamiltonian path? yes
if there is one, show one: D C A B E
if there is not one, can you give an argument proving it?
Is there a Hamiltonian circuit? yes
if there is one, show one: A B E D C A
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? yes
if there is one, show one: A B D E G C F
if there is not one, can you give an argument proving it?
Is there a Hamiltonian circuit? yes
if there is one, show one: A B D E G C F A
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? no
if there is one, show one: N/A
if there is not one, can you give an argument proving it?
the graph is a tree so you must backtrack to visit all nodes
Is there a Hamiltonian circuit? no
if there is one, show one: N/A
if there is not one, can you give an argument proving it?
since there is no HP, there is also no HC
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
_______________________________________________________________
| | | | | | | | | | | | | | | | |
| | 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"
13 is at subscript 4
the children of 13 are at 2*4=8, and 2*4+1=9
c) Using this array representation, show the subscript
calculations needed to find the parent of the node
with value "33"
33 is at subscript 11
the parent of 33 is at floor(11/2) = 5
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
too long to draw in an editor.
the O(N) procedure say first put all elements in an array in the
order they arrive (the order above). Then bubble the elements
starting with the next to last row.
The final heap loops like this (array rep)
element 2 3 6 8 4 9 19 24 21 7 61 16 29
subscript 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
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.
element 3 4 6 8 7 9 19 24 21 29 61 16
subscript 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
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.
_______________________________________________________________
| | | | | | | | | | | | | | | | |
| | 6| 11| 8| 13| 21| 12| 23| 27| 14| 29| 33| 19| | | |
array: |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
_______________________________________________________________
| | | | | | | | | | | | | | | | |
| | 8| 11| 12| 13| 21| 19| 23| 27| 14| 29| 33| | | | |
array: |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
_______________________________________________________________
| | | | | | | | | | | | | | | | |
| | 11| 13| 12| 14| 21| 19| 23| 27| 33| 29| | | | | |
array: |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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
from the text
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.
yes it can be if you always pick from the left list first when
merging items with the same value
14) Is selection sort stable? Why or why not?
not necessarily
but it can be made stable with linked lists
14) Is insertion sort stable? Why or why not?
yes
15) Is quicksort stable? Why or why not?
no, when efficiently sorting inplace you swap elements
from one end of the array to another
16) Is heapsort stable? Why or why not?
yes, if you make sure to select from the left list first when
merging equal keys
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?
directed, because the matrix is not symmetric
b) Would you call the arcs weighted, or unweighted? Discuss any nuances
to your choice.
I would call them unweighted, with the "1" simply being used to
mean "an arc is there". Same thing could be done with boolean T
(and F where there is a 0). However, it could be a weighted graph
with a weight on 1 on all arcs.
c) Provide a drawing to represent the graph
can't draw here
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
can't draw here
b) Is the graph acyclic? If so, give a topological sorting of the
vertices in the graph; if not, identify a cycle.
acyclic
topo sort: v5 v3 v2 v4 v1
c) Determine the shortest paths from vertex v5 to all the other
vertices in this graph.
v1: 3, v5 -> v1
v2: 6, v5 -> v3 -> v2
v3: 1, v5 -> v3
v4: 3, v5 -> v3 -> v4
d) Determine the shortest paths from vertex v1 to all the other
vertices in this graph.
no paths
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.
false is you allow disconnected graphs
true if connected graphs
b) There is an O(N^2) algorithm for finding Hamiltonian paths in
undirected graphs.
false?
actually, we don't know if its true or false
we have not proved there are none (would make the answer false)
we have not found one (would make the answer true)
c) There is an O(N^2) algorithm for finding Euler paths in
undirected graphs.
true, since there is also one that is linear in size of graph
and since O(N) is a bound, so is O(N^2) (not a tight bound)
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.
true
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.
no he wont... why not?
well he either is creating sorting into buckets (which we already
know about)
or he is trying to create something that does not exist (a sort
that uses only compares and runs in less that O(N log N) time)
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
merge sort... stable, fast, no bad cases
b) you had only a small constant amount of extra memory to use
quick sort... fast and uses little extra memory
however it is not stable
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.
using less memory is good even if you have lots of extra
however, quick sort if not stable so if you have extra
memory you get stable.
Also, quicksort has worst case O(N^2) so if you can use
mergesort, you get worst case O(N log N).
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.
most anything works... all the spanning trees have |V|-1 edges
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.
edges are looked at
(A,C,2)(A,G,2)(A,E,2)(F,G,1)(D,G,2)(D,B,2)
c) Find a minimum spanning tree using Prim's algorithm.
pick any node, find smallest arc from it
keep picking smallest arc from nodes selected
(A,C,2)(A,G,2)(A,E,2)(F,G,1)(D,G,2)(D,B,2)
d) By inspection, find a different spanning tree from your minima.
(A,C,2)(C,F,6)(C,E,4)(B,F,5)(B,D,2)(B,G,4)
23) What are the two properties that a binary heap (minimum heap)
must exhibit?
a) heap structure property: a binary heap is a complete binary
tree, filled left to right
b) heap order property: on any path from a leaf back to the root
(or equivalently, from root to a leaf) the elements are in
order; for a min heap, the elements are in non-decreasing
order from root to leaf.