Course Code : MCS-031
Course Title : Design and Analysis of Algorithms
Assignment Number : MCA (3)/031/Assign/2014-15
Maximum Marks : 100
Weightage : 25%
Last Dates for Submission : 15th October, 2014 (For July 2014 Session)
15th April, 2015 (For January 2015 Session)
There are seven questions in this assignment, which carries 80 marks. Rest 20 marks are for viva-voce. Answer all the questions. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the MCA Programme Guide for the format of presentation
In response to the questions given in the assignment, illustrations and examples should be different from those given in the course material.
Q.1. a) Discuss briefly the five essential attributes of an algorithm. (3 marks) b) Write a recursive procedure for the product of first n natural (2 marks) numbers.
Then explain how your algorithm computes product of first 6 natural numbers.
- c) Arrange the following growth rates in increasing order: (2 marks)
O (n (log n)2), O ( (35)n ) , O (35n2 +11), O (1), O (n log n) d) In respect of understanding a problem for solving it using a (3 marks) computer, explain „analysing the problem‟ step.
Q.2. Suppose that instead of binary or decimal representation of (10 marks)
integers, we have a representation using 5 digits, viz. 0,1,2,3,4, along with 5‟s complement, representation of integers. For example, the integer 147 is represented as (01042)5 = (in decimal) + 1. 53 + 0. 52 + 4. 51 + 2. 30, where the leading zero indicates positive sign.
And the integer ( − 147 ) in 5’s complement is represented by 13403, the leading 1 indicates negative sign. The other digits, except the right-most, in the representation of ( − 147) are obtained by subtracting from 4 the corresponding digit in 147‟s representation, and then adding 1 (the representation of –147 is obtained as 13402 + 00001).
Write a program for the arithmetic (negation of an integer, addition, subtraction and multiplication of two integers) of integers using 5‟s complement representation. The program should include a procedure for calculating each of negation of an integer, addition, subtraction and multiplication of two integers. The integers will use 8 5-digit positions, in which the left-most position will be used for sign.
Using your program find the 5-digit representation of each of the decimal numbers/ expression: 345, − 297, 18 and
((345 − 297) * 18)
Q.3. a) Write a short note on each of the following: (4 marks) i) Best case analysis
- ii) amortized analysis
- b) Using one-by-one (i) insertion sort (ii)heap sort and (iii) (6 marks)
merge sort, sort the following sequence in increasing order and analyze (i.e., find number of comparisons and assignments in each of ) the algorithm:
84, 35, 47, 18, 82, 17, 56, 40, 12 ,67
Q.4. a) The following pseudo-code is given to compute ( ab )mod n, ( 5 marks) where a, b and n are positive integers. Trace the algorithm to compute 11362 mod 561
MODULAR-EXPONENTION (a, b, n)
Let (bk, bk − 1, … , b0) be binary representation of b, in which bk=1
- d ß a; d stores partial results of (ab) mod n
- for i ß ( k –1) downto 0
- do
- d ß (d . d) mod n
- if bi = 1
- d ß (d . a) mod n
- end-do
- return d.
Note: The above algorithm is a sort of implementation of the
ideas explained in Section 1.9 of Block2 of MCS- 031, and should be learned along with Section 1.9.
- b) Explain the essential idea of Dynamic Programming. How (5 marks) does Dynamic Programming differ from Divide and conquer approach for solving problems?
Q.5. a) For the graph given in Figure below, use (i) BFS (ii)DFS to (6 marks) visit various vertices. The vertex B is taken as the starting vertex and, if there are more than one vertices adjacent to a vertex, then the adjacent vertices are visited in lexicographic order.
- b) In context of graph search, explain the minimax principle. (4 marks)
Q.6. a) Is there a greedy algorithm for every interesting optimization (3 marks) problems? Justify your Claim.
- b) Apply each of (i) Prim‟s and (ii)Kruskal‟s algorithms one at a (7 marks) time to find minimal spanning tree for the following graph
Q7. Write note on each of the following: (20 marks)
- i) Unsolvability/ undecidability of a problem ii) Halting problem iii) Reduction of a problem for determining decidability iv) Rice theorem
- v) Post correspondence problem vi) NP-complete problem vii) K-colourability problem
viii) Independent set problem
. Assignments
Dear Student,
As per your last email you requested a solved assignment which is always available with us. We ensure you that the answer quality would be the best and you will get up to 90% to 100% marks in the assignments purchased from us. We have an expert on every subject working with us. The subject matter experts are highly qualified and deliver their best for you over and over again.
Please have a look at the price list mentioned below and send us a reply on this e-mail to let us know which assignment you want from us.
Type A- Rs._ per subject – This assignment is ready to use assignment for every student. (The content of this assignment is the same for every student. You may risk getting your marks deducted by the university due to plagiarism.)
Type B- Rs._ per subject - This assignment is personalized and customized just for you. The answers of this assignment would not be shared with any other student. The content of this assignment would be unique and we will delete it from our database after sending it to you exclusively. (This assignment would have 0% plagiarism)
Type C - Rs._ per Subject-Handwritten Assignment
If you want that your assignment should be written manually rather than being sent to you in a MS Word file or uploaded on the internet then we can do that for you. We will do your assignment manually and every answer would be created just for you. You only have to pay Rs._ per subject for handwritten assignments and we will make sure it gets to you on time every time. We can courier the assignment at your preferred address and you just have to receive it. This assignment will be delivered within a week’s time due to the fact that it needs more time to write down an answer than to type it. This assignment would also help you get around 90% to 100% marks because it would be done by our subject matter experts.
Please note that you have to pay us in advance. All payment should be made in INR. As soon as we receive your payment, we will send your Type A assignment within 10 minutes only. If you have opted for Type B, we will send the assignment within 5 hours of receiving your payment. If you have opted for Type C, we will send your assignment within 24 hours of receiving the payment. Type B and Type C assignment submission takes more time because we customize each and every word of the assignment just for you. So we request you to be patient.
Pay Online
Now you can also make the payment online by the below mentioned link. We accept payments through Credit Card, Debit Card and Net Banking too.
http://solvezone.in/bank-details/
Pay Offline
You can also pay us via NEFT / RTGS by visiting the nearest branch of your bank.
You can also deposit Cash by visiting the nearest branch of ICICI Bank.
Our process
After you have made the payment please email us your payment details with Assignment Name and Type Preference at solvezone@gmail.com. We will revert asap.
Note: For better response time, kindly use e-mail communication and avoid calling us. Our office timings are 9 AM to 6 PM.
University: IGNOU Year: 2015