Homework 1 – Complexities and Correctness
BE205: Algorithms and Data Structures
MUST 2024 Fall ∗ Tuesday October 01 2024
1 Introduction and Review
There are several themes of this course:
• Analyzing the complexity of a given algorithm (or a snippet). • Proving the correctness or flaw of an algorithm.
• Design an algorithm for solving a given problem.
• Implement an algorithm using C++ (or C).
So, there are problems to be solved on these aspects.
∗The picture above the title, found at [1], shows some basic understanding of the big O notations.
1
2 How to submit the homework 2.1 Mathematical notations
Math notations are needed to write the answers to Problem 1. If you do not know how to edit math equations and notations using Word, Markdown, or Latex, you may use some easy-to-understand text form in a .txt file. For example, using ^ for superscript and _ for subscript, like:
• 2n+2 is described as 2^{n+2}.
• Σni=1i2 is described as Signma_{i=1}^{n}{i^2} • Θ(n2) is described as : \Theta(n^2)
• O(n log(n) is described as: O(n*log(n))
Pictures of clear hand writing can also be accepted.
2.2
• •
• •
2.3
1.
Submission method and deadline
Submit your homework files on Moodle through the portal of Assignment 1 (you can find it on the Moodle webpage of this course).
At most three students can form a group to do the homework together. Then, only one student should submit the files through the Moodle system.
You are welcome to do the homework again. I.e., a one-person group is surely fine.
The due time is about two weeks from the date of releasing the homeowork. The exact due time for this homework should refer to the setting of Assignment 1 on Moodle.
Files to be submitted
A report file hmk1_report. You can use the proper file format you can manage (.docx, .txt, .md, .pdf ...). This file should mention
• The full names of all the group members. Or you can say you did the homework alone.
• The tasks done by each member for this homework. This part is not needed if you did the homework alone.
• Anything meaningful that you want to document, like the difficulties and errors that you solved, some summary of the experience, etc. This part could help your future work.
• Answers to Problems 1, 2, 3.
2
2. A .zip file containing all the source code files for your programs of Problem 4. It is better to prepare two folders, one for the files of Problem 4.a, and the other for Problem 4.b. Then compress the two folders into the .zip file. Make sure your program files can compile. Do not include some project files of some IDE or executable files (.o, .exe. .obj. out). Just the source code files (.h, .c, .cpp, .txt) are fine.
Some specifics: about the files to be submitted.
• The answers to Problem 1 should clearly mention the snippet number, like:
Answer for snippet (1): ..
Answer for snippet (2): ...
3 Problems Problem 1
If you are sure, describe the upper bound of the complexity (running time relative to the problem size n) of the following code snippets using the Θ notation; otherwise, use the O notation. When log is used, the base should be 2.
(1) int sum = 0;
for (int i = 1; i < n; i *= 3)
++sum;
(2) int sum = 0;
for (int i = 0; i < n; ++i)
++sum;
for (int j = 0; j < n; ++j)
++sum;
(3) int sum = 0;
for (int i = 0; i < n; ++i)
for (int j = 1; j < n; j *= 2) ++sum;
(4) int sum = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) ++sum;
(5) int sum = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < i * i; ++j) 3
for (int k = 0; k < j; ++k) ++sum;
(6) int sum = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= 2n; ++j) { if (j % i == 2) {
for (int k = 0; k < j; ++k) { ++sum;
} }
} }
(7) int
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = n; k >= 1; k = k / 2 )
++sum;
(8) int sum = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n + 1; ++j)
for (int k = 0, c = 1; k < j; ++k, c = c * 2)
for (int l = 0; l < c; ++l) ++sum;
Problem 2
Prove the correctness of the exponentiation-computing algorithm presented by pseudocode as follows. It was discussed in our lectures.
Require: n ≥ 0 Ensure: y = xn
1: 2: 3: 4: 5: 6: 7: 8: 9:
10:
y ← 1
X ← x
N ← n whileN̸=0do
if N is even then X←X×X
N ← N2
else if N is odd then
y←y×X N ← N − 1
▷ A comment: don’t forget to update N
sum = 0;
4
8
9 10 11 12 13 14 15
} }
Hint: The correctness of this algorithm means that finally xn will always be the value y. One way is proving by induction some invariant of the loop, which means something is always true at each iteration of running the loop. The proof structure could like the following:
Lemma 1. An invariant: for each iteration, the statement . . . is true
Proof. Proof by induction:
Base case: In the first one, or several iterations the lemma is true, because . . .
Inductive step: Suppose in the previous k iterations, the statement is true, now we prove that for the k + 1th iteration it is also true. . . .
Theorem 1. Correctness of the exponentiation algorithm
Proof. Now based on the Lemma 1, the correctness of the algorithm should be true, because
....
Problem 3
The following algorithm is supposed to solve the Maximum Sum of Subsequence (MSS) problem. I t is mentioned in the textbook, described by a C++ program snippet. Prove the correctness of this algorithm.
// Linear-time maximum contiguous subsequence sum algorithm. Fig. 2.8 alg. 4
int maxSubSum4(const vector<int> &a) maxSum = 0, thisSum = 0;
(int j = 0; j < a.size(); ++j)
thisSum += a[j];
if (thisSum > maxSum) maxSum = thisSum; else if (thisSum < 0)
thisSum = 0; return maxSum;
1
2
3 4{
5 int
6 for
7{
Hint: The proof structure could similar to what are mentioned for Problem 2. An invari- ant can be proved. Based on it, the correctness must hold, because otherwise (proof by contradiction), something impossible will occur.
5
Problem 4
Problem 4.a
Given an array, sometimes we want to rotate its elements for some positions either to the right or left. For example. given an array with elements:
0, 11, 22, 33, 44, 55, 66, 77, 88, 99
if we rotate it to the right for 4 positions (shift is 4), then after doing so its elements will be print like:
66, 77, 88, 99, 0, 11, 22, 33, 44, 55
Or if we rotate it three positions to the left (shift is -3), its elements can be printed like:
33, 44, 55, 66, 77, 88, 99, 0, 11, 22
• There is an obvious way to "physically" rotate the elements in the array, just moving each element to its new position in the array after the rotation.
• Write a complete program where the a function with the following signature is imple- mented:
rotate(int * arrName, int arrLen, int shift)
• Do not use any library function for rotating or shifting an array.
• Test the function in a main function on an array with at least 10 elements. Test with at least 5 cases, for each case, use a different shift value (positive, 0, or negative, sometimes > 10 or < -11), and print the array before the rotation and after rotation.
• In this .cpp (or .c) file, besides the definition of the rotate function, describe as some comments about what is the time complexity of running this function.
Problem 4.b
We want to design some special array, call it Spin-and-Virtaul Array (SVArr), which has the following features: For the rotation task (make it ready to print its rotated elements), it can be done is a constant time (O(1)), instead of the "physical" way shown above. It is easy to know its size (the maximum number of elements can be stored in it). Out-of- boundary indexes are a not a problem. Increasing an index rotate to the right and touching the elements on the left end. Similarly, decreasing the index can rotate to the left and touch the elements on the right end. For example, given such an array arr with size 10:
**2; arr[9 + 1] == arr[0] **2; arr[7 + 5] == arr[2] **2; arr[−1] == arr[9] **2; arr[23] == arr[3]
6
**2; arr[−18] == arr[2]
It is a pain to move the elements of an array around, which are common operations in a sorting computation, specially, when an element has very large size. One idea is to have a change the "logical" indexes of the elements, instead of shuffling the of bit-sequences of array elements. For that purpose, a SV Array remembers two arrays:
• pArr, the "physical" array, the actual content of the data elements. This part does not change upon the actions like sorting or rotating.
• vArr, the "virtual-index" array, the logical indexes of the elements. This part will be updated by actions like sorting, or elements swapping.
For example, for an SVArr of 10 elements, initially, its two arrays are:
pArr 45 78 23 56 89 12 6**4 ** 55 vArr 0 1 2 3 4 5 6 7 8 9
After swapping 45 and 55, then the arrays changes to :
pArr 45 78 23 56 89 12 6**4 ** 55 vArr 9 1 2 3 4 5 6 7 1 0
After sorting the elements from small to large, the pArr does not change, while the vArr changes. Now, the two arrays become:
pArr 45 78 23 56 89 12 6**4 ** 55 vArr 5 2 7 0 9 3 6 1 4 8
Write a program to implement SVArr, with the following requirements:
• The style of ADT (abstract data type) should be expressed. So, SVArr should be a class, with public and private members. Some .h file and .cpp files should belong to the program.
• The main function test the following features of SVArr:
– An SVArr can be built based on a common array.
– Out-of-boundary indexes can be used; Print the value of these elements.
– Rotation can be done for positive and negative amount of shifting; Print the array before and after the shifting.
• The idea of O(1) time rotation should be implemented. Print the array after some rotation to see the effects.
• Show sorting on a SVArr, its virtual indexes changes while its physical array does not change.
7
• Do not use any library tools that have already implemented or covered the features of SVArr.
• The standard features of C++ classes should be used.
• If SVArr is implemented as a C++ template class, or some equivalent features sup- porting general types of elements, you deserve some bonus points. Otherwise, you can assume SVArr contains only integers.
• C programs are also accepted.
References
[1] Buket Senturk. Time complexity. https://medium.com/@buketsenturk/time-compl exity-202eb4f1db40, 2024. Accessed: 2024-10-01.
[2] Mark Allen Weiss. Data Structures and Algorithm Analysis in C++. Person, 4th edition, 2014. https://users.cs.fiu.edu/~weiss/.
A Helpful formulas
There are several formulas helpful to solve the Problem 1. 1+1+···+1=Σn 1=Θ(log(n))
(a+0d)+(a+1d)+(a+2d)+...+(a+(n−1)d) =
n
(a+(i−1)d) = na+d
i=1
(n − 1)n 2
2
12 ni=1i
n−1 1−rn a+ar+ar2+···+an−1 =ark =a1−r =Θ(rn−1)=Θ(rn)
= Θ(n )
k=0
n n(n+1)(2n+1)
12 + 22 + · · · + n2 = i2 = S = 6 = Θ(n3) i=1
Σni=1ik = Θ(nk+1) logk(n) = Θ(log2(n))
8
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
