CS 432 Harvard University Analysis of Algorithms Questions

CS395 Assignment 252 Points
1. Consider the following two digraphs:
a. [Points: 3] Solve the topological sorting problem for these digraphs applying the DFSbased algorithm.
b. [Points: 3] Solve the topological sorting problem for these digraphs applying the sourceremoval algorithm.
2. [Points: 5] For n = 1, 2, 3, 4, and 5, draw all the binary trees with n nodes that satisfy the balance
requirement of AVL trees.
3. [Points: 5] Consider the list [6, 5, 4, 3, 2, 1]. Construct an AVL tree by inserting the elements of
this list successively, starting with the empty tree.
4. [Points: 5] Fill in the following table with the average-case and worst-case efficiency classes for
the five implementations of the ADT dictionary:
5. [10 Points] Review your weekly assignments for Insertion Sort, QuickSort and Selection Sort, as
well as the program you used to compare their running time.
a) [3 Points] What is the big theta complexity of each of the algorithms?
b) [7 Points] Explain the results you got for their running time in terms of the relative complexity of
the algorithms. (Include a copy of the results of running your code)
6. [5 Points] Implement Horspool’s algorithm, the Boyer-Moore algorithm, and the brute-force
algorithm of Section 3.2 (using C/C++).
a. [1 Points] Give an example of input text where the brute-force method would be
noticeably slower than the other two algorithms.
b. [4 Points] All three algorithms will give the same final result, but the shifts each time the
needle is moved will be different. Give an example of an input text where the shifts
from the Boyer-Moore would be different from the shifts for the Horspool. Show the
shifts for each. Why are they different?
Chapter 8 ——————————————————–2) [6 Points] Knapsack problem:
a) [Points: 5] Apply the bottom-up dynamic programming algorithm to the following instance of
the knapsack problem: (Your answer will be in the form of a table similar to the one shown in
Figure 8.5 of the textbook on page 294.)
b) [Points: 1] How many different optimal subsets does the instance of part (a) have?
3) [Points: 5] Apply Warshall’s algorithm to find the transitive closure of the digraph defined by the
following adjacency matrix. Your answer should show the work in the same way as in Figure 8.13 on
page 307 of the textbook.
4)
[Points: 5] Solve the all-pairs shortest-path problem for the digraph with the following weight
matrix using Floyd’s algorithm. Your answer should show the work in the same way as in Figure 8.16
on page 311 of the textbook.
(1)
(a)
– The popping off order: c,f,g,b,c,a,d
– Reversing the stack contents, the topologically
sorted list is as follows: d,a,c,b,g,f,e
– The topologically sorted list:
!”!!””
d
a
c
b
g
f
e
#
(b)
– The popping off order: e, g, d, c, b, a, f
– The topologically sorted list:
$$$
f
a
b
c
d
g
e
(2) For n = 1, 2, 3, 4, and 5, draw all the binary trees with n nodes that satisfy the balance
requirement of AVL trees.
n = 1
n = 2
n = 4
n = 5
n = 3
(3)
The elements to be inserted: 6, 5, 4, 3, 2, 1
1
Insertion of elements:
5
Insert 6:
0
6
1
0
4
6
0
1
6
2
3
5
2
0
5
4
1
2
0
6
3
6
0
1
1
2
5
5
0
0
0
0
4
0
0
2
5
0
4
6
3
0
6
4
2
5
0
1
6
3
1
0
2
4
0
1
1
3
1
0
5
2
0
1
0
4
0
6
(4) Fill in the following table with the average-case and worst-case efficiency classes for the five
implementations of the ADT dictionary:
O(n)
O(n)
O(log(n)) O(log
(n))
O(n)
O(n) O(n)
O(n)
O(n)
O(n) O(n)
O(n)
O(log(n)) O(n)
O(log(n)) O(log(n))
O(log(n))
O(n)
O(log(n)) O(log
(n))
O(log(n))
O(n) O(log
(n))
O(log
(n))
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
(6)
//C++ program
#include
#define MAX 500
# define NO_OF_CHARS 25
using namespace std;
int t[MAX];
void shiftTable(string pattern)
{
int i,j,m;
m=pattern.length();
for(i=0;i