Fundamentals of Algorithms (CS502)
Assignment # 01
Fall 2018
Total marks = 20
Deadline = 29/11/2018
Lectures Covered: This assignment covers Lecture # 1 to 11.
Objectives:
Objectives
of this assignment are:
of this assignment are:
·
To view the asymptotically equivalent functions.
To view the asymptotically equivalent functions.
·
To understand the concept of lower, upper and tight
Bounds.
To understand the concept of lower, upper and tight
Bounds.
·
To perform iteration method on recurrence relations.
To perform iteration method on recurrence relations.
Please read the following
instructions carefully before solving & submitting the assignment:
instructions carefully before solving & submitting the assignment:
1. The assignment will not be accepted
after due date.
after due date.
2.
Zero marks will be awarded if the assignment does not open or the
file is corrupt.
Zero marks will be awarded if the assignment does not open or the
file is corrupt.
3.
The assignment file must be an MS Word (.doc/.docx) file format;
Assignment will not be accepted in any other format.
The assignment file must be an MS Word (.doc/.docx) file format;
Assignment will not be accepted in any other format.
4. Zero marks will be awarded if assignment
is copied (from other student or copied from handouts or internet).
is copied (from other student or copied from handouts or internet).
5. Zero marks will be awarded if
Student ID is not mentioned in the assignment file.
Student ID is not mentioned in the assignment file.
Please do not post queries
related to assignment on MDB.
related to assignment on MDB.
Question # 1: 10 Marks
Compute Lower Bound and
Upper Bound of the following given
function by directly finding constants n0,
c1 and c2.
Upper Bound of the following given
function by directly finding constants n0,
c1 and c2.
Hint:
Question # 2: 10 Marks
Write
down the Recurrence Relation for
binary search tree; solve it using iterative method and give answer at the end
in asymptotic form.
down the Recurrence Relation for
binary search tree; solve it using iterative method and give answer at the end
in asymptotic form.
Note: need to show all possible steps.
Good
Luck
Luck
