CS 325 – Homeworks #1 to 4 solution

Description

CS 325 – Homework #1

Problem 1. (4 points)
Order the following functions by growth rate: 𝑁, √𝑁, 𝑁
1.5
, 𝑁
2
, 𝑁𝑙𝑜𝑔𝑁, 𝑁𝑙𝑜𝑔𝑙𝑜𝑔𝑁,
𝑁𝑙𝑜𝑔2𝑁, 𝑁𝑙𝑜𝑔(𝑁
2)
, 37, 𝑁
2
log N, 𝑁
, 𝑁/2, 2
𝑁, 2
𝑁/2
3
. Indicate which functions grow at the same
rate.
Problem 2. (3 points)
Which function grows faster: 𝑁𝑙𝑜𝑔𝑁 or 𝑁
1+ɛ/√𝑙𝑜𝑔𝑁, ɛ>0? Show your work.
Problem 3. (3 points)
For each of the following six program fragments, give an analysis of the running time (Big-Oh
will do).
(1) sum = 0;
for( i = 0; i < n; ++i )
++sum;
(2) sum = 0;
for( i = 0; i < n; ++i )
for( j = 0; j < n; ++j )
++sum;
(3) sum = 0;
for( i = 0; i < n; ++i )
for( j = 0; j < n * n; ++j )
++sum;
(4) sum = 0;
for( i = 0; i < n; ++i )
for( j = 0; j < i; ++j )
++sum;
(5) sum = 0;
for( i = 0; i < n; ++i )
for( j = 0; j < i * i; ++j )
for( k = 0; k < j; ++k )
++sum;
(6) sum = 0;
for( i = 1; i < n; ++i )
for( j = 1; j < i * i; ++j )
if( j % i == 0 )
for( k = 0; k < j; ++k )
++sum;
Problem 4. (10 points)
Merge Sort and Insertion Sort Programs
Implement merge sort and insertion sort to sort an array/vector of integers. Name your programs
“mergesort” and “insertsort”, respectively. Both programs should read inputs from a file called
“data.txt” where the first value of each line is the number of integers that need to be sorted,
followed by the integers. The output will be written to files called “merge.out” and “insert.out”.
Example values for data.txt:
4 19 2 5 11
8 1 2 3 4 5 6 1 2
For the above example the output would be:
2 5 11 19
1 1 2 2 3 4 5 6
Problem 5. (10 points)
Merge Sort vs Insertion Sort Running time analysis
a) Modify code – Now that you have verified that your code runs correctly using the data.txt
input file, you can modify the code to collect running time data. Instead of reading arrays
from the file data.txt and sorting, you will now generate arrays of size n containing random
integer values from 0 to 10,000 to sort. Use the system clock to record the running times of
each algorithm for n = 5000, 10000, 15000, 20,000…. You may need to modify the values of
n if an algorithm runs too fast or too slow to collect the running time data. Output the array
size n and time to the terminal. Name these new programs “insertTime” and “mergeTime”.
b) Collect running times – Collect your timing data on the engineering server. You will need at
least seven values of t (time) greater than 0. If there is variability in the times between runs of
the same algorithm you may want to take the average time of several runs for each value of
n. Create a table of running times for each algorithm.
c) Plot data and fit a curve – For each algorithm plot the running time data you collected on an
individual graph with n on the x-axis and time on the y-axis. You may use Excel, Matlab, or
any other software. What type of curve best fits each data set? Give the equation of the
curves that best “fits” the data and draw that curves on the graphs.
d) Combine – Plot the data from both algorithms together on a combined graph. If the scales are
different you may want to use a log-log plot.
e) Comparison – Compare your experimental running times to the theoretical running times of
the algorithms? Remember, the experimental running times were the “average case” since the
input arrays contained random integers.
EXTRA CREDIT: A Tale of Two Algorithms: It was the best of times, it was the worst of
times …
Generate best case and worst case inputs for the two algorithms and repeat the analysis in parts
b) to e) above. To receive credit you must discuss how you generated your inputs and your
results.
Programs can be written in C, C++ or Python but all code must run on the
OSU engr servers. Submit a copy of all your code files and a README file
that explains how to compile and run your code in a ZIP file to TEACH. We
will only test execution with an input file named data.txt.

CS 325 – Homework #2

Problem 1.
Give the asymptotic upper bounds for T(n) in each of the following recurrences. Show your work
and explain how you solve each case.
Problem 1.a. (2 points)
• T(n) = b · T(n − 1) + 1 where b is a fixed positive integer greater than 1.
Problem 1.b. (2 points)
• T(n) = 3 · T(n/9) + n · log n
Problem 2. (6 points)
Solve Exercise 4.1-5 from the 3rd Ed. of the textbook.
Problem 3.
Consider the recurrence T(n) = 3 · T(n/2) + n.
Problem 3.a. (3 points)
• Use the recursion tree method to guess an asymptotic upper bound for T(n). Show your
work.
Problem 3.b. (3 points)
• Prove the correctness of your guess by induction. Assume that values of n are powers of 2.
Problem 4.
Consider the following pseudocode for a sorting algorithm, for 0 < α < 1 and n > 1.
badSort(A[0 · · · n − 1])
if (n = 2) and (A[0] > A[1])
swap A[0] and A[1]
else if (n > 2)
m = dα · ne
badSort(A[0 · · · m − 1])
badSort(A[n − m · · · n − 1])
badSort(A[0 · · · m − 1])
1
Problem 4.a. (3 points)
• Show that the divide and conquer approach of badSort fails to sort the input array if α ≤ 1/2.
Problem 4.b. (2 points)
• Does badSort work correctly if α = 3/4? If not, why? Explain how you fix it.
Problem 4.c. (2 points)
• State a recurrence (in terms of n and α) for the number of comparisons performed by badSort.
Problem 4.d. (2 points)
• Let α = 2/3, and solve the recurrence to determine the asymptotic time complexity of badSort.
Problem 5.
Problem 5.a. (3 points)
• Implementation: Implement badSort from Problem 4 to sort an array of integers. The value
of α should be an input parameter to your program. Implement the algorithm in C/C++.
Your program should be able to read inputs from a file called “data.txt”, where the first value
of each line is the number of integers that need to be sorted, followed by the integers. The
output will be written to a file called “bad.out”.
Problem 5.b. (3 points)
• Modify code: Modify the code to collect running time data. Call the new timing program
badSortTime. Instead of reading arrays from the file data.txt and sorting, you will now
generate arrays of size n containing random integer values from 0 to 10,000 to sort. Use
the system clock to record the running times of each algorithm for n = 5000, 10000, 15000,
20,000, . . . . for two values of α = 2/3 and α = 3/4. You may need to modify the values of
n if an algorithm runs too fast or too slow to collect the running time data. Provide a table
with the timing data.
Problem 5.c. (2 points)
• Plot data and fit a curve: Plot the running time data you collected for each value of
α ∈ {2/3, 3/4} on an individual graph with n on the x-axis and time on the y-axis. You
may use Excel, Matlab, R or any other software. How does your experimental running time
compare to the theoretical running time of the algorithm?
Problem 5.d. (2 points)
• Comparison: Looking at the plots in the previous step for α ∈ {2/3, 3/4}, which α provides
better performance?
Submit a copy of all your code files and a README file that explains how
to compile and run your code in a ZIP file to TEACH. We will only test
execution with an input file named data.txt.

CS 325 – Homework #3

Problem 1. (4 points)
What does dynamic programming have in common with divide-and-conquer? What is a principal
difference between them?
Problem 2. (6 points)
Shortest path counting: A chess rook can move horizontally or vertically to any square in the
same row or the same column of a chessboard. Find the number of shortest paths by which a
rook can move from one corner of a chessboard to the diagonally opposite corner. The length of
a path is measured by the number of squares it passes through, including the first and the last
squares. Solve the problem:
a) by a dynamic programming algorithm.
b) by using elementary combinatorics.
Problem 3. (6 points)
Maximum square submatrix: Given an m×n Boolean matrix B, find its largest square submatrix
whose elements are all zeros. Design a dynamic programming algorithm and indicate its time
efficiency. (The algorithm may be useful for, say, finding the largest free square area on a
computer screen or for selecting a construction site.)
Problem 4. (14 points)
Consider the following instance of the knapsack problem with capacity W = 6
Item Weight Value
1 3 $25
2 2 $20
3 1 $15
4 4 $40
5 5 $50
a) Apply the bottom-up dynamic programming algorithm to that instance.
b) How many different optimal subsets does the instance of part (a) have?
c) In general, how can we use the table generated by the dynamic programming algorithm to tell
whether there is more than one optimal subset for the knapsack problem’s instance?
d) Implement the bottom-up dynamic programming algorithm for the knapsack problem. The
program should read inputs from a file called “data.txt”, and the output will be written to screen,
indicating the optimal subset(s).
e) For the bottom-up dynamic programming algorithm, prove that its time efficiency is in
Θ(nW), its space efficiency is in Θ(nW) and the time needed to find the composition of an
optimal subset from a filled dynamic programming table is in O(n).
EXTRA CREDIT (4 points)
Implement an algorithm that finds the composition of an optimal subset from the table generated
by the bottom-up dynamic programming algorithm for the knapsack problem.
Programs can be written in C, C++ or Python, but all code must run on the
OSU engr servers. Submit to TEACH a copy of all your code files and a
README file that explains how to compile and run your code in a ZIP file.
We will only test execution with an input file named data.txt.

CS 325 – Homework #4

Problem 1.
Write a concrete example of the knapsack problem where you specify a set of at least 5 objects,
their dollar values (i.e., benefits) and their weights, as well as the weight of the knapsack, denoted
W. Now, consider the greedy approach of sorting items based on decreasing benefit/weight ratios
and picking items from the beginning of the list. In the context of your example, show that
Problem 1.a. (2 points)
• The greedy approach works for fractional knapsack.
Problem 1.b. (2 points)
• The greedy approach may fail for 0-1 knapsack.
Problem 2.
Consider the following symbols with their corresponding frequencies:
A : 1, B : 1, C : 2, D : 3, E : 5, F : 8, G : 13, H : 21
Problem 2.a. (3 points)
• Construct the Huffman coding of these symbols along with its optimal coding tree.
Problem 2.b. (3 points)
• Use your coding tree to decode 0001001000010000000001001
Problem 3.
Consider the problem of making change for n cents using the fewest number of coins. Assume that
each coin’s value is an integer.
Problem 3.a. (4 points)
• Suppose that the available coins are in the denominations that are powers of c, i.e., the
denominations are c
0
, c1
, · · · , ck
for some integers c > 1 and k ≥ 1. Show that the greedy
algorithm of picking the largest denomation first always yields an optimal solution. You are
expected to reason about why this approach gives an optimal solution. (Hint: Show that for
each denomination c
i
, the optimal solution must have less than c coins.)
Problem 3.b. (4 points)
• Design an O(nk) time algorithm that makes change for any set of k different coin denominations, assuming that one of the coins is a penny.
1
Problem 4. (7 points)
Implementation: Implement the make change algorithm you designed in the previous problem.
Your program should read a text file “data.txt” where each line in “data.txt” contains three values
c, k and n. Please make sure you take your input in the specified order c, k and n. For example, a
line in “data.txt” may look like the following:
3 4 38
where c = 3, k = 4, n = 38. That is, the set of denominations is {3
0
, 3
1
, 3
2
, 3
3
, 3
4} = {1, 3, 9, 27, 81},
and we would like to make change for n = 38. The file “data.txt” may include multiple lines like
above.
The output will be written to a file called “change.txt”, where the output corresponding to each
input line contains a few lines. Each line has two numbers, where the first number denotes a denomination and the second number represents the cardinality of that denomination in the solution.
For example, for the above input line ‘3 4 38’, the optimal solution is the multiset {27, 9, 1, 1}, and
the output in the file “change.txt” is as follows:
27 1
9 1
1 2
which means the solution contains 1 coin of denomination 27, one coin of 9 and two coins of
denomination 1. You can use a delimiter line to separate the outputs generated for different input
lines.
Problem 5. (3 points)
Extra credit: Can you generalize the results you found in the construction of Problem 2 (i.e., the
Huffman coding tree )? Write a statement/theorem that captures your generalization.
Submit a copy of all your code files and a README file that explains how
to compile and run your code in a ZIP file to TEACH. We will only test
execution with an input file named data.txt.