Scribd
Upload
98 views4 pages

Assignment 2

This document is an assignment for a computer science course on algorithms. It contains 3 questions asking the student to demonstrate the optimal solution for the 0/1 knapsack problem using dynamic programming, analyze the running time of binary search, and design an algorithm to find the smallest element in an array that is first decreasing then increasing using a similar approach to binary search. The assignment is worth 5 marks total and asks the student to provide their name, class, registration number, and the marks obtained.

Uploaded by

Muhammad Mukarrum
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
98 views4 pages

Assignment 2

This document is an assignment for a computer science course on algorithms. It contains 3 questions asking the student to demonstrate the optimal solution for the 0/1 knapsack problem using dynamic programming, analyze the running time of binary search, and design an algorithm to find the smallest element in an array that is first decreasing then increasing using a similar approach to binary search. The assignment is worth 5 marks total and asks the student to provide their name, class, registration number, and the marks obtained.

Uploaded by

Muhammad Mukarrum
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Department of Computer Science CSC-321:Design and Analysis of Algorithm

Bahria University Semester 05 (Fall 2021)

ASSIGNMENT 02
Marks: 05

NAME: Muhammad Mukarrum


CLASS: 5 (A)
REG. NO: 02-134192-054
Marks Obtained: ______________________

QUESTION 01 (2 Mark)
Demonstrate the optimal solution for the 0/1 knapsack problem making use of dynamic
programming approach. Consider-
n=4
w = 5 kg
(w1, w2, w3, w4) = (2, 3, 4, 5)
(b1, b2, b3, b4) = (3, 4, 5, 6)

QUESTION 02 (1 Mark)
Use the substitution method to show that the recurrence

Has solution
T(n) = O ( n lg lg n )

1|Page
CS Department, BUKC 2 Semester 05 (Fall 2021)
CSC-321: DAA Assignment 02

QUESTION 03 (BINARY SEARCH) (2 Marks)


Binary search is a classical algorithm. Given an array A[1..n] sorted in ascending order, binary
search can find whether an element b is in the array A. The algorithm works as follows:
binary_search(A[1..n], b)
If n <= 2 then check whether b is in A by looking through all elements.
CS Department, BUKC 3 Semester 05 (Fall 2021)
CSC-321: DAA Assignment 02

Let k = n/2
Partition A into B, C where B contains A[1..k-1], and C contains A[k+1..n]
If A[k] == b then b is in array A
If A[k] > b then call binary_search(B, b)
If A[k] < b then call binary_search(C, b)
(a) Analyze the running time of the binary search algorithm.

(b) Using similar ideas, you are going to solve a related problem. In this problem you are given
an array A[1..n] that is first decreasing and then increasing. More precisely, there is a
CS Department, BUKC 4 Semester 05 (Fall 2021)
CSC-321: DAA Assignment 02

coordinate 1 ≤ p ≤ n such that for all i < p, A[i] > A[i + 1], and for all i ≥ p, A[i] < A[i + 1].
Your goal is to find the smallest element in this array. Please design an algorithm that has the
same asymptotic running time as binary search.

*************** End of Assignment 02 *************

You might also like