Virtual University of Pakistan Study forum !
Fundamentals of Algorithms (CS502)
Assignment # 01
Total marks = 20
Deadline = 10/05/18
Lectures Covered: This assignment covers Lecture # 1 to 7.
Objectives of this assignment are:
Please read the following instructions carefully before solving & submitting the assignment:
For any query about the assignment, contact only at CS502@vu.edu.pk
Please do not post queries related to assignment on MDB.
Question # 1: 10 Marks
For the following code segment, provide line-by-line analysis and construct function T(n) that give the runtime of this code as a function of "n". Also determine the big-O for this code segment. [Marks: 5+3+2]
Code segment Cost
i = 1
j = 1
k = 1
while (i <= n)
i = i + 1
while (j < n)
a = 2 + g
j = j + 1
if (k <= n)
a = 2
a = 3
Question # 2: 5 Marks
Which of the following two functions is faster?
Question # 3: 5 Marks
In the context of 2D Maxima problem, Brute Force algorithm runs in Θ(n2) time and Plane-Sweep algorithm runs in Θ(nlog2n) time. For n = 500,000, if Plane-Sweep takes 1 second, how much time (in hours) Brute Force algorithm will take? Calculate and show all the steps.
Note: Base of log is 2 (e.g. log210 = 3.321928095)