COMSATS University Islamabad, Lahore Campus

□ Sessional-1 □ Sessional-II  Terminal Examination – SPRING 2020

Course Title: Design and Analysis of Algorithms Course Code: CSC301 Credit Hours: 3
Dr. Hasan Jamal, Ms. Asmara Safdar, BS Computer Science
Course Instructor/s: Programme: Name:
Ms. Zeenat Afzal BS Software Engineering
Semester: Batch: Section: Date: 17/08/2020
Time Allowed: 3 Hours Maximum Marks: 100
Student’s Name: Reg. No.

Question 1: [Marks: 15]

a. Pseudocode is dependent on language and machine. [TRUE/FALSE]

b. Quick sort algorithm is in-place. [TRUE/FALSE]
c. It is feasible to use Bucket sort to sort percentage marks of students in a class. [TRUE/FALSE]
d. Dijkstra’s algorithm is used to find the minimum spanning tree of a given graph. [TRUE/FALSE]
e. An algorithm giving different runtime on separate machines must be corrected. [TRUE/FALSE]
f. A problem must have a single algorithm. [TRUE/FALSE]
g. Best case running time of heap sort is same as its worst case. [TRUE/FALSE]
h. The statement “The running time of algorithm is at least O (n2)”, is meaningless. [TRUE/FALSE]
i. It is feasible to use Radix sort to sort a large list of ASCII codes. [TRUE/FALSE]

j. Two main measures for the efficiency of an k. Complexity of ExtractMin function in

algorithm are min-heap is
i. Processor and memory i. O (1)
ii. Complexity and capacity ii. O (n)
iii. Time and space iii. O (n log n)
iv. Data and space iv. None of the above

l. An in-place sorting algorithm is one that uses m. The operation of processing each
__________ arrays for storage. element in the list is known as:
i. Two dimensional i. Sorting
ii. More than one ii. Merging
iii. No Additional iii. Inserting
iv. None of the above iv. Traversal

n. In the Tower of Hanoi problem, to move a tower o. Given an unsorted list of 128 distinct
of 6 rings from one peg to another requires how numbers between 100 and 900. Which
many moves? of the following algorithm is the best
i. 63 choice to sort this list?
ii. 64 i. Insertion Sort
iii. 32 ii. Quick Sort
iv. 31 iii. Selection Sort
iv. Count Sort
Question 2: [Marks: 10]
Prove or disprove that n2 – 8n + 3  (n2)

Question 3: [Marks: 12 + 06 = 18]

a) Solve the following recurrence using the “Recursion Tree Method”
𝑛
𝑇(𝑛) = 4𝑇 ( ) + 𝑛2
3

b) Solve the following recurrence using the “Master Method”

𝑛
𝑇(𝑛) = 4𝑇 ( ) + lg 𝑛
2

Question 4: [Marks: 12]

Given a hash table of size 17 and a hash function H(k) = K mod 17, draw the contents of the hash
table if open addressing with quadratic probing is used to resolve collisions. What values will be in
the hash table after the following sequence of insertions? Show your work for partial credit.

6, 13, 17, 21, 28, 15, 33, 23, 32, 22, 3, 37

Question 5: [Marks: 05+02+01+02= 10]

Given the following undirected, weighted graph.

(a) Step through Dijkstra's algorithm to calculate the single-source shortest paths from vertex “S”
to every other vertex by filling in the table as done in class. Cross out old values and write in
new ones, from left to right, as the algorithm proceeds.

(b) Write down the order in which Dijkstra’s algorithm would mark each node as known.

(c) Write down the shortest (weighted) path from A to E and its length (weighted cost).

(d) Draw the minimum Spanning Tree of the graph.

Question 6: [Marks: 02+03 = 05]
Iron rods come is a standard size of 10 feet length. You require the following lengths of rods in feet.
What algorithm will you use to solve this problem and what are the minimum number of 10 feet iron
rods needed for this purpose. Show your working.

3, 6, 4, 1, 6, 4, 5, 4, 6, 4, 3

Question 7: [Marks: 07+03 = 10]

a) Find out the “Fixed Length” and “Variable Length” codes for the characters in the given table
below.

Characters H T I S R N E A
Frequency 6 28 17 39 12 11 60 28

b) Using the variable length code determined in part a), decode the following message.

1001011001000 01000 001110101110111011 0010010101111100 10111110111010

00100101001101010000 01110101110111011

Question 8: [Marks: 05+01+01+03 = 10]

Your friend Ali is coming home from Dubai and wants to pack his bag that gives him maximum
benefit. He has one bag with capacity W=11 and he wants to utilize that to carry maximum number
of items with overall best benefit in terms of value. He is having trouble filling the bag to maximize
benefit. He has called you for some provide him a quick solution to his problem. Following table
shows the list of 6 items (i) along with corresponding weights (wi) and values (bi). Help him out in
getting the maximum benefit out of it as you yourself want maximum value gifts from him.

Item # wi (weight of ith item) bi (value of ith item)

I1 4 6
I2 2 4
I3 3 5
I4 1 3
I5 6 9
I6 4 7

a) What is the maximum value/benefit (B) that can be achieved?

b) Item number/s that can be added in the bag to achieve the above max value/benefit (B)?
Question 9: [Marks: 10]

We have 3 assembly-lines in a car manufacturing factory each of which has 5 service stations. All
the costs are shown in the figure below. Find out the fastest way through the factory using the
“dynamic programming” approach.