Scribd
Upload
3 views

SCS B213_B

This document outlines the supplementary examination for the Bachelor of Science in Computer Science for the course SCS B213, focusing on design and analysis of algorithms. It includes various questions covering topics such as graph algorithms, dynamic programming, greedy algorithms, and data structures like B-Trees and Splay trees. The exam consists of multiple questions with specific marks allocated to each, requiring students to demonstrate their understanding of algorithm concepts and problem-solving techniques.

Uploaded by

Afrikan Noel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views

SCS B213_B

This document outlines the supplementary examination for the Bachelor of Science in Computer Science for the course SCS B213, focusing on design and analysis of algorithms. It includes various questions covering topics such as graph algorithms, dynamic programming, greedy algorithms, and data structures like B-Trees and Splay trees. The exam consists of multiple questions with specific marks allocated to each, requiring students to demonstrate their understanding of algorithm concepts and problem-solving techniques.

Uploaded by

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

UNIVERSITY SUPPLEMENTARY EXAMINATIONS 2019/2020 ACADEMIC

YEAR

YEAR 2 SEMESTER 2 SUPPLEMENTARY EXAMINATION FOR BACHELOR


OF SCIENCE IN COMPUTER SCIENCE

COURSE CODE/TITLE SCS B213 DESIGN AND ANALYSIS OF ALGORITHMS


END OF SEMESTER: 1 DURATION: 2 HOURs

DAY/TIME: APRIL DATE:

INSTRUCTIONS: Aswer Question ONE and any TWO questions.

QUESTION 1(30 Marks)

a. Explain the following concepts in relation to graph algorithms:

i. Path
ii. Loop
iii. Degree
iv. Neighborhood
v. Dag
vi. Connected component (6 Marks)

b. Explain the three main asymptotic methods used to represent the rate of growth of running
time of an algorithms. (6 marks)

c. Differentiate between following concepts :

i. Dynamic Programming and Greedy algorithm


ii. 0-1 knapsack problem and fractional knapsack problem
iii. NP-Complete class and NP-hard class (6 Marks)

d. Insert 60, 30, 10, 20, 50, 40, 70, 80, 15, 90, 100 into a B-Tree (6 Marks)

f. Solve the following Knapsack Problem using Dynamic Method. Given that six items where:

Weight W = 10

Item 1 2 3 4 5 6
Weight (w) 4 2 3 1 6 4

Value (v) 6 4 5 3 9 7 (6 Marks)

QUESTION 2(20 Marks)

a. List any three pillars of greedy algorithms (3 Mark)

b. Explain any two collision resolution strategies for hashing. (6 Marks)

c. Write down and explain the procedure for tackling the 8 - queens problem using a
backtracking approach. (5 Marks)

d. Compute the LCS-LENGTH on the sequence given X=(A ,B ,C ,B ,D ,A ,B) and Y = ( B, D,


C, A, B, A). (6 Marks)

QUESTION 3(20 Marks)

a. List any two features of an algorithm (2 Marks)

b. After a depth-first search in a graph, the edges of the graph are classified into 4 categories.
Briefly describe the four categories of edges (4 Marks)

c. Create min heap for following data:

56 23 18 89 46 77 88 36 74 63 14 (6 Marks)

f. Consider the weighted graph below apply Floyd-Warshall algorithm to find shorted path.
Compute matrix D of shortest path weights and then construct the predecessor matrix ∏ from
matrix D.

(8 Marks)
QUESTION 4(20 Marks)

a. Using examples explain briefly the following operations of Splay tree:

i. Zig-Zag
ii. Zag-Zag
iii. Zag-Zig
iv. Zig-Zig (4 Marks)

b. Compare and constrast Bell-Ford and Dijkstra algorithms for single source path (4 Marks)
c. Explain the following methods of solving recurrence
i. Substitution method
ii. Iteration method
iii. Tree method (6 Marks)
d. Construct Huffman Tree for the following data set f:5 e:9 c:12 b:13 d:16 a:45 where alphabets
represent the data and numbers represent their corresponding frequencies. (6 Marks)

You might also like