CS101 Algorithms and Data Structures Fall 2023 Homework 2
CS101 Algorithms and Data Structures
Fall 2023
Homework 2
Due date: 23:59, October 22, 2023
1. (12 points) Multiple Choices
Each question has one or more correct answer(s). Select all the correct answer(s). For each
question, you will get 0 points if you select one or more wrong answers, but you will get 1 point
if you select a non-empty subset of the correct answers.
Write your answers in the following table.
(a) (b) (c) (d) (e) (f )
-
(a) (2’) Which of the following scenarios are appropriate for using hash tables?
-
For each user login, the website should verify whether the username (a string)
exists.
-
While you are writing C++ codes, the IDE (for example, VS Code) is checking
whether all brackets match correctly.
-
The Domain Name System (DNS) translates domain names (like
www.shanghaitech.edu.cn) to IPv4 addresses (like 11.16.44.165).
-
A playlist where music files are played sequentially.
-
-
(b) (2’) We have a hash table of size M with a uniformly distributed hash function. n elements are stored into the hash table. Which of the following statements are true?
-
If n ≤ M, then the probability that there will be a hash collision is about Mn .
-
If collisions are resolved by chaining and the load factor is λ = 0.9, the average time complexity of a successful search (accessing an element which exists in the
hash table) is Θ(1).
-
If collisions are resolved by linear probing, when there are many erase operations,
lazy erasing is usually less time-consuming than actual erasing (attempting to
fill the empty bin by moving other elements).
-
If collisions are resolved by quadratic probing, when the hash table is fully filled
(n = M), you can reallocate a new space of size 2M and copy the M bins of the old space to the first M bins of the new space (like std::vector) in order to hold more elements.
-
-
(c) (2’) Consider a table of capacity 7 using open addressing with hash function k mod 7 and linear probing. After inserting 6 values into an empty hash table, the table is below. Which of the following choices give a possible order of the key insertion sequence?
Index 0 1 2 3 4 5 6 Keys 47 15 49 24 26 61
A. 26, 61, 47, 15, 24, B. 26, 24, 15, 61, 47, C. 24, 61, 26, 47, 15, D. 26, 61, 15, 49, 24,
(d) (2’) Which of the following A. n! = o(nn). √
B.(logn)2=ω( n).
49
49
49
47
statements is(are) NOT correct?
2
CS101 Algorithms and Data Structures Homework 2
Due date: 23:59, October 22, 2023
C. nlog(n2) = O(n2 log(n2)).
D. n+logn = Ω(n+loglogn).
-
(e) (2’) Consider the recurrence relation
(T(n−1)+3n
2 n=0Which of the following statements are true? A. T(n)=2n−1
B. T(n)=O(n) C. T(n)=Ω(3n) D. T(n)=Θ(n2)
-
(f) (2’) Your two magic algorithms run in
f(n) = n⌈√n⌉(1 + (−1)n) + 1g(n) = n⌊log n⌋
time, where n is the input size. Which of the following statements are true? A. f(n)=on2.
B. f(n)=ω(n).
C. f(n)+g(n)=Θn1.5.
D. f(n)+g(n)=ω(nlog(1.5n)).Here is the definition of Landau Symbols without using the limit:
f(n)=Θ(g(n)):∃c1,c2 ∈R+,0≤c1·g(n)≤f(n)≤c2·g(n)asn→∞. f(n) = O(g(n)) :∃c ∈ R+, 0 ≤ f(n) ≤ c · g(n) as n → ∞.
f(n) = Ω(g(n)) :∃c ∈ R+, 0 ≤ g(n) ≤ c · f(n) as n → ∞.f(n) = o(g(n)) :∀c ∈ R+, 0 ≤ f(n) < c · g(n) as n → ∞. f(n) = ω(g(n)) :∀c ∈ R+, 0 ≤ g(n) < c · f(n) as n → ∞.
T(n) =
n > 0
3
CS101 Algorithms and Data Structures Homework 2 Due date: 23:59, October 22, 2023
2. (11 points) Hash Table Insertions and Deletions
Consider an empty hash table of capacity 7 and with hash function h(k) = (3k + 6) mod 7. Collisions are resolved by quadratic probing with the probing function Hi(k) = (h(k) + i2) mod 7, paired with lazy erasing. We will give three kinds of instructions, which are among the set {Insert, Delete, Search}. For Insert/Delete instructions, you need to fill the hash table after each instruction. For Search instructions, write down probing sequence (index). Use ‘D’ to indicate that the bin has been marked as deleted.
(a) (1’) Insert 9
(b) (1’) Insert 17
Key Value
Index Key Value
0123456
0123456
0123456
0123456
0123456
(c) (1’) Insert 32
Key Value
Index
Index
(d) (1’) Insert 24
Key Value
Index
(e) (1’) Insert 18
Key Value
(f) (1’) Search 18
(g) (1’) Delete 32
Key Value
Index
Solution:
Index
0123456
4
CS101 Algorithms and Data Structures Homework 2 Due date: 23:59, October 22, 2023 (h) (1’) Insert 25
Index 0123456 Key Value
(i) (3’) Suppose that the collisions are resolved by linear probing.
i. Write down the content of the hash table after Insert 9, 17, 32, 24, 18.
Index 0123456 Key Value
ii. What is the load factor λ ?
Solution:
5
CS101 Algorithms and Data Structures Homework 2 Due date: 23:59, October 22, 2023
3. (4 points) Analysing the Time Complexity of a C++ Function
What is the time complexity of fun (in the form of Θ(f(n)), where n is the size of the vector a)?
void fun(std::vector<int> a) { int n = a.size(); for (int i = 1; i < n; i *= 2) { // do O(1) operations
for (int j = 0; j < n; j += i * 2) { // do O(1) operations |
for (int k = 0; k < i; ++k) { // do O(1) operations } } } |
|
} |
NOTE: Please clearly demonstrate your complexity analysis: you should give the complexity of the basic parts of an algorithm first, and then analyse the complexity of larger parts. The answer of the total complexity alone only accounts for 1pt.
Solution:
6
CS101 Algorithms and Data Structures Homework 2 Due date: 23:59, October 22, 2023
4. (6 points) Compare and Proof
For each pair of functions f(n) and g(n), give your answer whether f(n) = o(g(n)), f(n) = ω(g(n)) or f(n) = Θ(g(n)). Give a proof of your answers.
(a) (3’)
f(n) = log(n!) g(n) = log(nn)
Solution:
7
CS101 Algorithms and Data Structures Homework 2 (b) (3’)
f(n) = n1+ε, g(n) = n(log n)k,
Due date: 23:59, October 22, 2023
(ε ∈ R+) (k ∈ Z+)
Solution:
8
