Posted: August 27th, 2015

algorithm and data structure/PE424001 Algorithm and Data Structure

algorithm and data structure/PE424001 Algorithm and Data Structure

Assignment 2
(25% of the module score)
Q1. (10 Marks) Answer the following questions using Figure 1
Figure 1 A directed graph
a) Construct the corresponding adjacency matrix of Figure 1 (2 Marks)
b) What is the main disadvantage of using matrix to form the graph relationship? (1 Mark)
c) Execute Dijkstra’s algorithm on the graph of Figure 1 starting at vertex A. It is noted that each vertex MUST be visited at least once. (3 Marks)
d) What is the shortest path from A to F. Show the route. (1 Marks)
Figure 2 An undirected graph
e) An undirected version is shown in Figure 2. Use Depth-First search traverse the graph (from node A) and illustrate the steps using proper data structure. (3 Marks)
Q2. (9 Marks) Given the following data sequence.
[35, 20, 38, 16, 31, 40, 10, 22, 34]
a) Draw the binary search tree formed by entering the data in the order from 20 to 50 one by one and assign a balancing factor in each node. (4 Marks)
b) Using the tree above, give the preorder scan of the nodes. (1 Marks)
c) Using the tree above, give the inorder scan the nodes. (1 Marks)
d) Using the tree above, give the postorder scan the nodes. (1 Marks)
e) Reform the tree into AVL tree and put the balancing factor in each node. (2 Marks)
Q3. (6 Marks) Huffman code is one of the Greedy approach to compress data string. Given the following simple frequency
49 e’s 11 b’s 8 c’s 12 d’s
a) Draw a Huffman tree and label the binary number (try to make your tree as balance as possible) (2 Mark)
b) Write down the final codeword of each symbol (2 Marks)
c) Consider the following code fragment
Cost
Times
i = 1;
C1
T1
sum = 0;
C2
T2
While (I <= n) {
C3
T3
i = i +1 ;
C4
T4
sum = sum + i;
C5
T5
}
Complete T1 to T5 and write down the total cost formula. (2 Marks)
iii) Submission
– DEADLINE: 22:00:00 31st August, 2015
– Submission method:
1. Zip up all the files and name the zip file to “[Last name]_[First name].zip”. (E.g. Chan_Peter.zip)
2. Send the zip file to [email protected]
3. Enter “ADS Assignment 2 Submission – [Last name] [First name]” in the subject.
4. Marks will be deducted if you don’t follow the submission method.
Marks will be deducted on late submission.
iv) Marking Scheme
This assignment contributes 25% of the final grade of PE424001
The full mark for this assignment is 25 marks, which break down into:
– Question 1 contributes 10 marks.
– Question 2 contributes 9 marks.
– Question 3 contributes 6 marks.
– End –
1 week
Your marks x 90%
2 weeks
Your marks x 80%
More than 2 weeks
Your marks x 0%