Virtual University of Pakistan Study forum !
Fundamentals of Algorithms (CS502)
Assignment # 01
Spring 2018
Total marks = 20
Deadline = 10/05/18
Lectures Covered: This assignment covers Lecture # 1 to 7.
Objectives:
Objectives of this assignment are:
Instructions:
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
else
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 Θ(n^{2}) time and Plane-Sweep algorithm runs in Θ(nlog_{2}n) 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. log_{2}10 = 3.321928095)
Good Luck
Tags:
Replies are closed for this discussion.
Ideal Solution...!!!
jazakALLAH Khair for sharing
jazakALLAH Khair for sharing
Started by ★·.·★ Ќąɲώąℓ ★·.·★.
Last reply by + caмe4ѕтυdιeѕ May 9.
4 Replies
1 Like
Started by + caмe4ѕтυdιeѕ.
Last reply by Ali Raza Feb 20.
4 Replies
0 Likes
© 2018 Created by Muhammad Anwar Tahseen. Powered by
© Copyright Created by Muhammad Anwar Tahseen | Designed By VU HELP Team