CONFIDENTIAL CD/FEB 2023/CSC645
UNIVERSITI TEKNOLOGI MARA
FINAL EXAMINATION
COURSE ALGORITHM ANALYSIS AND DESIGN
COURSE CODE CSC645
EXAMINATION FEBRUARY 2023
TIME 3 HOURS
INSTRUCTIONS TO CANDIDATES
1. This question paper consists of six (6) questions.
2. Answer ALL questions in the Answer Booklet. Start each answer on a new page.
3. Do not bring any material into the examination room unless permission is given by the
invigilator
4. Please check to make sure that this examination pack consists of:
) the Question Paper
) an Answer Booklet - provided by the Faculty
) a True/False Answer Sheet - provided by the Faculty
5. Answer ALL questions in English.
Decoy OP
DO NOT TURN THIS PAGE UNTiL YOU ARE TOLD TO DO SO
This examination paper consists of 6 printed pages
© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL
, Dynamic Programming (Richard Bellman)
Warshall
closure) O(n3))Stephen
Warshall algorithm (transitive
O(n3) (Robert floyd)
-
Floyd algorithm (all pair shortest
paths)
-
CONFIDENTIAL 2 CD/FEB 2023/CSC645
MST X
Greedy algorithm
a most
Semestiny
Shortest , First rule
PART A bena acycle Prim (MST)
understand hard to implement then Prim'inst)
Kruskal (MST) (easy to ,
different of numerical lable
Djikstra (Single source shortest path) (same as primnst , way computing
QUESTION 1
State whether the following statements are TRUE or FALSE.
1) Floyd algorithm is a Dynamic Programing algorithm for solving all pairs shortest path. T
based Warshall)
2) Warshali algorithm is based on Floyd algorithm. False (Floyd on
3) Knapsack problem cannot be solved by Dynamic Programming. False
4) Dynamic Programming is invented by William Rowan. False
5) Dijkstra's algorithm is similar to Prim's MST algorithm but a different way of computing
numerical labels. True
6) Huffman code is one of examples of Greedy design technique. True
7) FalseGreedy design technique constructs a solution to an optimization problem piece by piece
through a sequence of choices and picks the best solution from the pieces. True
8) Spanning tree of a connected graph G is a connected cyclic subgraph of G that includes
all of G's vertices. False (should be acyclic
9) A Hamiltonian circuit is named after the Irish mathematician Sir Richard Bellman. False sir William
Rowan
Hamiltonian
10) Exhaustive-search algorithms run in a realistic amount of time only on very small
instances. True (different time between small instance and large)
11) No universal method exists that would enable us to solve every recurrence relation.
True
12) Pseudo-code is a method of expressing an algorithm by a collection of connected
geometric shapes containing descriptions of algorithm's steps. False (should be flow hart
13) Flowchart is a mixture of a natural language-like constructs. False (should be pseudocode)
14) The basic operation for checking primality of a given integer n is multiplication. FakeCshould be
divide)
15) Basic operation is the operation that contributes most towards the running time of the
algorithm. true Time efficiency is analyzed
by determinin the number of repetition of
-
the basic operations as a function of input size.
16) Graph problem is the problem that can be represented via a collection of points called
vertices and their connectivity's called edges. True -
17) Numerical problem deals with geometric objects such as points, lines and polygons.
False -
should be graph
18) Big Oh relates to an lower bound on complexity.
False Brute Force
© Hak Cipta Universiti Teknologi MARA
Search CONFIDENTIAL
Exhaustive
Oh-upper
boundry William Hamiltonian)
Big Hamiltonian Circuit (Sir
Rowan
-
boundary cycle that passes through
Big Omega-lower of the graph
-
all the Vertices
exactly once-
Big Thefa-arabout
between two
, CONFIDENTIAL 3 CD/FEB 2023/CSC645
19) Big Omega relates to a upper bound on complexity.
False
20) Big Theta relates to a tight on complexity.
True (20 marks)
QUESTION 2
Let L be the list of non-negative integers and K is the search key. The goal is to find K in L. If
the K is found, the algorithm returns the index of L, otherwise, it returns - 1 .
Based on the following list: {6,9,0,1,2,5,0.8,3,7,6,4} and the K is 7.
a) Demonstrate the solution based on Brute Force design strategy.
(4 marks)
b) Demonstrate the solution based on Divide and Conquer design strategy.
(4 marks)
c) State how many comparisons done to find K by Brute Force algorithm and Divide and
Conquer algorithm?
(2 marks)
QUESTION 3
Find the big-0 time complexity of each of the following summation/pseudocodes.
a)
(3 marks)
b)
f o r i «- 0 t o n -- 1 do
for j 0 t o i - 1 do
p r .m t j
(3 marks)
© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL
, CONFIDENTIAL 4 CD/FEB 2023/CSC645
c)
function fun(n)
i f n <= 1
return
print n
fun(n/2)
fun(n/2)
(4 marks)
QUESTION 4
a) Given the following Master Theorem and recurrence relation.
If a <bd, T(n) e ®{nd)
d
If a = b«, T(n) e ©(n log n)
d
If a >b , T(n) e ©(n'°9ba)
T(n) = 4T(n/2) + n for n>1, T(1) = 0 for n = 1
i) State the value of a, b and d for the recurrence relation.
(3 marks)
ii) Find the time complexity of the recurrence relation by using the Master Theorem.
(2 marks)
iii) For the recurrence relation above, solve it by backward substitution method.
Note: Need to show the working steps.
(5 marks)
© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL
UNIVERSITI TEKNOLOGI MARA
FINAL EXAMINATION
COURSE ALGORITHM ANALYSIS AND DESIGN
COURSE CODE CSC645
EXAMINATION FEBRUARY 2023
TIME 3 HOURS
INSTRUCTIONS TO CANDIDATES
1. This question paper consists of six (6) questions.
2. Answer ALL questions in the Answer Booklet. Start each answer on a new page.
3. Do not bring any material into the examination room unless permission is given by the
invigilator
4. Please check to make sure that this examination pack consists of:
) the Question Paper
) an Answer Booklet - provided by the Faculty
) a True/False Answer Sheet - provided by the Faculty
5. Answer ALL questions in English.
Decoy OP
DO NOT TURN THIS PAGE UNTiL YOU ARE TOLD TO DO SO
This examination paper consists of 6 printed pages
© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL
, Dynamic Programming (Richard Bellman)
Warshall
closure) O(n3))Stephen
Warshall algorithm (transitive
O(n3) (Robert floyd)
-
Floyd algorithm (all pair shortest
paths)
-
CONFIDENTIAL 2 CD/FEB 2023/CSC645
MST X
Greedy algorithm
a most
Semestiny
Shortest , First rule
PART A bena acycle Prim (MST)
understand hard to implement then Prim'inst)
Kruskal (MST) (easy to ,
different of numerical lable
Djikstra (Single source shortest path) (same as primnst , way computing
QUESTION 1
State whether the following statements are TRUE or FALSE.
1) Floyd algorithm is a Dynamic Programing algorithm for solving all pairs shortest path. T
based Warshall)
2) Warshali algorithm is based on Floyd algorithm. False (Floyd on
3) Knapsack problem cannot be solved by Dynamic Programming. False
4) Dynamic Programming is invented by William Rowan. False
5) Dijkstra's algorithm is similar to Prim's MST algorithm but a different way of computing
numerical labels. True
6) Huffman code is one of examples of Greedy design technique. True
7) FalseGreedy design technique constructs a solution to an optimization problem piece by piece
through a sequence of choices and picks the best solution from the pieces. True
8) Spanning tree of a connected graph G is a connected cyclic subgraph of G that includes
all of G's vertices. False (should be acyclic
9) A Hamiltonian circuit is named after the Irish mathematician Sir Richard Bellman. False sir William
Rowan
Hamiltonian
10) Exhaustive-search algorithms run in a realistic amount of time only on very small
instances. True (different time between small instance and large)
11) No universal method exists that would enable us to solve every recurrence relation.
True
12) Pseudo-code is a method of expressing an algorithm by a collection of connected
geometric shapes containing descriptions of algorithm's steps. False (should be flow hart
13) Flowchart is a mixture of a natural language-like constructs. False (should be pseudocode)
14) The basic operation for checking primality of a given integer n is multiplication. FakeCshould be
divide)
15) Basic operation is the operation that contributes most towards the running time of the
algorithm. true Time efficiency is analyzed
by determinin the number of repetition of
-
the basic operations as a function of input size.
16) Graph problem is the problem that can be represented via a collection of points called
vertices and their connectivity's called edges. True -
17) Numerical problem deals with geometric objects such as points, lines and polygons.
False -
should be graph
18) Big Oh relates to an lower bound on complexity.
False Brute Force
© Hak Cipta Universiti Teknologi MARA
Search CONFIDENTIAL
Exhaustive
Oh-upper
boundry William Hamiltonian)
Big Hamiltonian Circuit (Sir
Rowan
-
boundary cycle that passes through
Big Omega-lower of the graph
-
all the Vertices
exactly once-
Big Thefa-arabout
between two
, CONFIDENTIAL 3 CD/FEB 2023/CSC645
19) Big Omega relates to a upper bound on complexity.
False
20) Big Theta relates to a tight on complexity.
True (20 marks)
QUESTION 2
Let L be the list of non-negative integers and K is the search key. The goal is to find K in L. If
the K is found, the algorithm returns the index of L, otherwise, it returns - 1 .
Based on the following list: {6,9,0,1,2,5,0.8,3,7,6,4} and the K is 7.
a) Demonstrate the solution based on Brute Force design strategy.
(4 marks)
b) Demonstrate the solution based on Divide and Conquer design strategy.
(4 marks)
c) State how many comparisons done to find K by Brute Force algorithm and Divide and
Conquer algorithm?
(2 marks)
QUESTION 3
Find the big-0 time complexity of each of the following summation/pseudocodes.
a)
(3 marks)
b)
f o r i «- 0 t o n -- 1 do
for j 0 t o i - 1 do
p r .m t j
(3 marks)
© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL
, CONFIDENTIAL 4 CD/FEB 2023/CSC645
c)
function fun(n)
i f n <= 1
return
print n
fun(n/2)
fun(n/2)
(4 marks)
QUESTION 4
a) Given the following Master Theorem and recurrence relation.
If a <bd, T(n) e ®{nd)
d
If a = b«, T(n) e ©(n log n)
d
If a >b , T(n) e ©(n'°9ba)
T(n) = 4T(n/2) + n for n>1, T(1) = 0 for n = 1
i) State the value of a, b and d for the recurrence relation.
(3 marks)
ii) Find the time complexity of the recurrence relation by using the Master Theorem.
(2 marks)
iii) For the recurrence relation above, solve it by backward substitution method.
Note: Need to show the working steps.
(5 marks)
© Hak Cipta Universiti Teknologi MARA CONFIDENTIAL
