CSE 374: Algorithms Worksheet 2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSE 374: Algorithms
Worksheet 2
[Full Marks 40]
Note: Worksheet problems are more like practice problems to hone your skills through better understanding the concepts. They are easier than homework problems. Solution to every problem should preferably be typed (or, very legibly written in hand on letter size pages). Plagiarism in any form will be strictly dealt with following departmental policy. You should try to solve by yourself as much as possible. You can take help of study materials and book resources and office hours.
1. Assume that each of the expressions below gives the running time T(n) of an algorithm on a problem of size n. Select the dominant term(s) in n and specify the Big-Oh complexity. [12]
2. Give approximations (Big-Oh) for the following quantities. Two has been done for you. [5*2 = 10]
a. N + 1 ~N
b. 1 + 1/N ~1
c. (1 + 1/N)(1 + 2N) =
d. 2N3 – 15N2 + N =
e. lg(2N)/lg(N)
f. lg(N2 + 1)/ lgN
g. N100 / 2N
3. The statements below show some features of “Big-Oh” notation for the functions f ≡ f(n) and g ≡ g(n). Determine whether each statement is TRUE or FALSE and correct the formula in the latter case. [10]
4. Sort 3, 1, 4, 1, 5, 4, 9, 2, 6, 7 using insertion sort. Show every step using the table. See first few steps done by me where * indicates a new element to be inserted. Grey cells are unsorted elements and green cells are sorted ones. Create cells as many as you need. [8]
|
Input |
3 |
1 |
4 |
1 |
5 |
4 |
9 |
2 |
6 |
7 |
|
i = 0 |
*3 |
1 |
4 |
1 |
5 |
4 |
9 |
2 |
6 |
7 |
|
i = 1 |
3 |
*1 |
4 |
1 |
5 |
4 |
9 |
2 |
6 |
7 |
|
Insert |
1 |
3 |
4 |
1 |
5 |
4 |
9 |
2 |
6 |
7 |
|
i = 3 |
1 |
3 |
*4 |
1 |
5 |
4 |
9 |
2 |
6 |
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2023-01-10