Description
Short Answer Questions, Part 1
For each of the following algorithms, give:
a) the worst-case complexity
b) the average case complexity.of these algorithms
Give your answer in Big Oh notation.
If there is no difference in the worst case and the average case, then you may write
“Same” for part b), the average case
Each question is worth 2 points, 1 point each for a) and b) answers
1. Selection Sort of N items
2. Insertion Sort of N items
3. A sequence of M union-find operations on N disjoint sets.
Assume that the union operation is weighted quick union, and all operations
use path compression.
4. The total copying cost when using the doubling algorithm for a sequence of N
push operations. The initial size of stack is 1 element.
5. Quicksort, where the pivot is always 1st element, of N items
6. Merge sort of N items
7. Quickselect, where pivot is always 1st element, to find the median of N items
(assume N is an arbitrary odd number)
8. Quickselect, where pivot is always 1st element, to find the 4th smallest
element of N items (N ≥ 4).
9. Delete 1 element from a hash table that has N elements.
10. Find an item in a hash table that has N items.
Short Answer Questions, cont
Give the worst case performance (in Big Oh notation) for the following
algorithmic problems
Each question is worth 1pt each
11. A LSB radix sort over an alphabet of size A, for fixed-length strings of length
L. There are N such strings.
12. Build a binary heap from an array of size .
13. Find an item in a left-leaning red-black tree of size N.
14. The 1st find operation in sequence of Union/Find operations on disjoint
sets.
15. For a graph G = (V,E) with no negative edge weights, how long does Dijkstra’s
algorithm take to find the shortest path between distinguished vertices s and t?
16. Strassen’s algorithm to multiply 2 square matrices of size
NxN?
17. Given a sample string of length N, and a fixed pattern (NOT a regular
expression) of length M, what is the complexity of searching the sample string
for the pattern?
18. Given a sample string of length N, and a (fully parenthesized) regular
expression of length M, what is the complexity of searching the sample string
for the pattern?
19. Given a graph G = (V,E) with negative edge weights, but no negative cycles,
what is the best known asymptotic complexity for finding the shortest path
from 1 distinguished vertex s to all other vertices in the graph?
20. Given a graph G = (V,E), with weighted edges given by the function w(e)
for e ∈E, what is the complexity to find the minimum cost spanning tree for
G?
N
M N
“Long” Answer Questions
1. [4 pts] What is the complexity of the following program? (Big Oh notation is
sufficient). Assume that X[i][j] references the (i,j) component of matrix
X. Also, assume that N parameter describing the size of X as X[N,N],size of
v as v[N], and the size of b as b[N].
for i in range(N+1):
v[i] = 0
for j in range(i+1,N+1,2):
v[i] += A[i][j]*b[j]
Be sure to give your reasons for your complexity calculation.
2. [6 pts] Suppose someone you know implemented Kruskal’s algorithm for the
minimum spanning tree of a graph G = {V, E}. Unfortunately, your
acquaintance did not implement weighted union or path compression for the
union/find operations. What is the complexity of this variant of Kruskal?
3. [10 pts] Suppose you have an implementation of an A-heap. The A-heap is a
heap-like data structure that has complexity for the decrease-key
operation. All other operations of the data structure have the same complexity
as a traditional binary heap. What is the complexity of Dijkstra’s algorithm
using the A-heap data structure?
4. [6 pts] Using any method you like, find the Big Oh complexity of the
recurrence
5. [10 pts] You are given a complete, undirected graph with edge
weights. A complete graph is a graph s.t. for any 2 distinct vertices , there
is an edge . You construct a minimum cost spanning tree
(MST) for . Now suppose that 1 of the edges of the MST is deleted.
Give an efficient algorithm to construct a new MST from the old 1 without
using the deleted edge.
In addition to your algorithm, give the complexity of your algorithm.
O(1)
T(n) = 5T( n
4 ) +
n3
log2(n)
G = (V, E)
v1, v2
< v1, v2 > ∈ E
G
6. [4 pts] In Dijkstra’s algorithm, all distances are initialized to “infinity”.
Suppose, however, that you cannot represent infinity in your programming
language. What actual number could be used in place of “infinity”?
7. [10 pts] You have just won a shopping spree on a game show. You are allowed
to fill your shopping cart with everything the cart can hold. The cart has a
weight capacity of W. All of the items in the store are marked with both the
price and the weight. You are allowed to take multiple items.
7.1.[4 pts] Devise an efficient algorithm to maximize your profit subject to the
shopping cart constraints.
7.2.[2 pts] Apply your algorithm to this problem instance:
W = 20 lbs
Store items: item A: ($160, 7 lbs). item B: ($90, 3 lbs), item C:($15, 2 lbs)
7.3.[4 pt] For capacity W, and store item list of length N, give the complexity of
your algorithm in terms of both W and N.
8. [5 pts] You are given a list of meeting times as pairs of numbers. For
example:
#1 (7:30, 9) = from 7:30 AM to 9 AM
#2 (15, 16:30) = from 3 PM to 4;30 PM
#3. (8, 11) = from 8 AM to 11 AM
In the list, some meetings will overlap. For example meeting #1 and meeting
#3 overlap.
For this problem, you should find the most efficient possible algorithm to
merge all overlapping meetings.
Your output should be a list of new meeting times that do not overlap.
In the given example, your final output would be:
#1 (7:30, 11) = 7:30 AM to 11 AM, merge #1 & #3 above
#2 (15, 16:30). = 3 PM to 4:30 PM (nothing to merge)
Note that consecutive meetings should be merged. (2, 3) and (3, 4) should be
merged into (2,4)
Similarly, meetings that are subsumed should be merged into the inclusive
meeting. (1, 5) and (2, 4) should be merged into (1, 5).
The input to your merging algorithm will be an array of N pairs of starting and
ending times for meetings. Furthermore, meeting start and end times are
guaranteed to be on half hour boundaries, between 8:00 AM and 5:30. PM.
Finally, the times will be given in military time. 8:00 AM is 800; 5:30 PM is
1730.
In addition to showing your algorithm, analyze the complexity of your
algorithm in terms of N (the number of input pairs).
9. [5 pts] Write an algorithm that computes nonnegative integer powers of
arbitrary 3×3 matrices:
def pow3x3(M,n) = , where is an arbitrary 3 x 3 matrix.
10. [10 pts] A cycle in a directed graph. G = (V,E) is defined as a path <v1,v2,…
v1>, where the last vertex is the same as the first vertex.
Given a directed graph G=(V,E), determine if G has a directed cycle.
Hint: Use Depth First Search
Mn M