CS702 – Advanced Algorithms Analysis and Design
Assignment 3
Instructions to Solve Assignments
The purpose of the assignments is to give students hands on practice. It is expected that students will solve assignments themselves. The Following rules that will apply during the evaluation of the assignment.
Cheating from any source will result in zero marks in the assignment.
Any student found cheating in any two of the assignments submitted during the course will
be awarded “F” grade in the course.
No assignment after the due date will be accepted.
Fall 2019
Answer the following questions in your own words. Plagiarism will be checked for each question. Marks will be awarded on the basis of the answer and plagiarism report.
Question 1 (30 Marks)
Determine the cost and structure of an optimal binary search tree (OBST) for a set of n = 5 keys with the probabilities given below. You need to calculate the tables e[i, j], w[i, j] and root[i, j].
Fall 2019
i
0
1
2
3
4
5
pi
0.15
0.10
0.05
0.10
0.20
qi
0.05
0.05
0.05
0.10
0.05
0.10
Question 2
What is an optimal Huffman Code for the following set of frequencies? a:25 b:11 c:37 d:5 e:43 f:12 g:19 h:31
(20 Marks)
CS702 – Advanced Algorithms Analysis and Design
Assignment 1
Instructions to Solve Assignments
The purpose of the assignments is to give students hands on practice. It is expected that students will solve assignments themselves. The Following rules that will apply during the evaluation of the assignment.
Cheating from any source will result in zero marks in the assignment.
Any student found cheating in any two of the assignments submitted during the course will be awarded
“F” grade in the course.
No assignment after the due date will be accepted.
Answer the following questions in your own words. Plagiarism will be checked for each question. Marks will be awarded on the basis of the answer and plagiarism report.
Question No.1 (15 Marks)
Prove with the help of logical equivalence that the given proposition is a tautology. (p Λ q) v (~ p v ~( pq ))
Note: Show all the steps to get full marks
Question 2 (25 Marks)
Show by mathematical induction that any amount in cents ≥ n0 cents can be obtained using 8 cents and 9 cents coins only.
Note: First you will need to calculate n0.
Question No.3
Consider the recurrence
tn =n
(20) Marks
tn = 4tn-1 -11tn-2
Find general solution of the recurrence above.
-6tn-3
otherwise
ifn=0,1,2
CS702 – Advanced Algorithms Analysis and Design
Assignment 2
Instructions to Solve Assignments
The purpose of the assignments is to give students hands on practice. It is expected that students will solve assignments themselves. The Following rules that will apply during the evaluation of the assignment.
Cheating from any source will result in zero marks in the assignment.
Any student found cheating in any two of the assignments submitted during the course will
be awarded “F” grade in the course.
No assignment after the due date will be accepted.
Fall 2019
Answer the following questions in your own words. Plagiarism will be checked for each question. Marks will be awarded on the basis of the answer and plagiarism report.
Question 1
Prove that 2.n3 + 3.n + 10 O(n4)
Question 2
Use Brute Force Method to find an optimal solution for the 0-1 Knapsack problem.
(10 Marks) (20 Marks)
(20 Marks)
item weight value
1 4 40
2 10 60
3 20 100
4 10 20
Question 3
knapsack capacity W = 32
For the sequence of matrices, given below, compute the order of the product, A1.A2.A3.A4.A5, in such a way that minimizes the total number of scalar multiplications, using Dynamic Programming.
Order of A1 = Order of A2 = Order of A3 = Order of A4 = Order of A5 =
10x25 25x5 5x30 30x20 20x10
Fall 2019
CS702 Assignment 2 Solution and Discussion
CS702 - Advanced Algorithms Analysis and Design
2
Posts
1
Posters
454
Views
1
Watching
PAK VS BAN Live
File Sharing
