DTU Algorithms 02105+02326: Complexities Exercise Solutions

This document presents solutions to a mandatory exercise on complexities from the DTU Algorithms course (02105+02326). The exercise covers fundamental concepts in algorithm analysis, including determining the correctness of statements regarding asymptotic notation (Big O, Theta, Omega), arranging functions by asymptotic growth, and stating the asymptotic running time of algorithms in Theta notation. The assignment also includes a problem on frog lists, a specific data structure, requiring the student to draw the data structure for a given sequence and parameter, and to devise and analyze an efficient algorithm for searching within the frog list, considering the parameter and time complexity. The solutions are presented in a format suitable for Gradescope submission, with clear marking areas for each problem.

Mandatory Exercise: Complexities
The 02105+02326 DTU Algorithms Team
Admin Write your solutions to the exercises directly in the marked areas and submit using the Gradescope system. Your
final submission should be a single pdf-file identical to the template but with your information and solutions filled in the
designated areas. Do not change or modify the template in any way. To produce the file we recommend that you print out
the document, fill it in by hand, and scan it. Make sure that your handwriting and scan is of good quality and easily readable.
Alternatively, you may use a pdf-editor to fill in the template directly. Asymptotic bounds should be as tight as possible.
Unless otherwise specified, the base of all logarithms is 2 and logk n means (logn)k. Refer to the homepage for the
collaboration policy and scoring requirement for the exam.
1 Complexities
1.1 For each statement below mark whether or not it is correct:
Y
es No 1 n3 + n2 logn+17· n2 =Θ(n3)
4
1017 +(n3)2 +log2 n = O(n5)
42logn+!n+ n1/3 =Ω(n1/3)
2logn + 3n03/320 +log10 n =Θ(n)
(3log2 n+55log(n10)+8logn)·logn =Ω(log10 n)
1.2 Arrange the following functions in increasing order according to asymptotic growth. That is, if g(n) immediately follows f
(n) in your list, it must hold that f (n)= O(g(n)).
8!n log(2n) 7n3 1n 3log2 n n4/2
Solution: 3log2 n, log(2n), 7n3, n4/2, 8√𝑛 , 1n
1.3 State the asymptotic running time in Θ-notation of each of the following algorithms.

end for
return
1+ALG2(n−2) i = ⌊i/2 ⌋
for j = 1 to ⌊n/5 ⌋do end if end while c = c +1 end for
end for
Solution: Θ(n) Solution: Ω(g(n)) Solution: Ω(g(n))
1
2 Frog Lists Let S = s0,...,sn−1 be a sequence of monotonically increasing integers. A frog list for S with
parameter ∆,1≤∆≤n, is a data structure that consists of two singly-linked list L0 and L1. List L0 consists of
all elements of S. In the same order as S. List L1 consists of the elements si ,where i=0,∆,2∆,3∆,..., ⌊n−1∆⌋∆.
Each element in L1 stores both the integer value of the element and a pointer to the corresponding
element in L0.
2.1 Consider the sequence S = 1,2,3,4,5,6,7,8. Draw the frog list data structure for S with parameter ∆ = 3. Your drawing should
consist of the linked lists with pointers and values in each element.
2.2 The frog list search problem, is given a frog list for a sequence S with parameter ∆ and an integer x, to determine
if x is in S. Give an efficient algorithm for the frog list search problem with parameter ∆= ⌊!n ⌋. Analyse the time complexity
of your algorithm in the relevant parameters of the problem. Note: remember that "give an efficient algorithm" always
refers to a natural language description unless otherwise specified.
ALG1(n) c
= 0
for i = 1 to ⌊n/3 ⌋do
c = c +1
ALG2(n) if n ≤
1 then return
1 else
ALG3(n)
for j = 1 to n do i =
n while i ≥ 3 do
Solution:
L0 contains elements of and L1 contains elements with of L0 pointed to it after 3 deltas as shown below
L0: 1 -> 2 -> 3 ->4 ->5 ->6 ->7 -> 8
^ ^ ^
| | |
L1: 1 -------------------------------> 4 ---------------------------------> 7

Solution:
Create head pointer and store it into a temporary pointer variable known as ptr.
declare a local variable i and assign it to 0.
Traverse the list until the pointer ptr becomes null. Keep shifting pointer to its next and increasing i by +1.
Compare each element of the list S with the item x which is to be searched.
If the item matched with any node value then the location of that value, i will be returned from the function else NULL is
returned meaning x is not in S.
Step 1: IF HEAD == NULL
WRITE "ouch nothing here"
GO TO STEP 8
[END OF IF]
Step 2: Set ptr = HEAD
Step 3: Set i = 0
Step 4: Repeat step 5 to 7 while ptr! = NULL
Step 5: IF ptr→ data = x
return i
[END OF IF]
Step 6: i = i + 1
Step 7: ptr = ptr → next
Step 8: Exit
The complexity of this algorithm is O(N)