Question 1
i. What are the basic features of a stack data structure, explain with the use of an example?
ii. What is the significance of the stacktop in a stack?
iii. Suppose that you want to develop a program that accepts a postfix expression and asks values for variables in the expression. Then you need to calculate the answer for the expression according to the given values.
For example,
The postfix expression is ab+c*
Value of a is 2
Value of b is 3
Value of c is 5
The result is 25
(a) Write the pseudo code algorithm for the above problem.
(b) Implement the algorithm in Java.
Question 2
i. Explain in your own words what an algorithm is giving an example.
ii. Describe different methods of developing algorithms with examples.
iii. With the use of an example describe what sort of problems are more suitable to solve in an algorithmic manner.
iv. Compare and contrast three widely used notations in algorithm analysis with respect to time.
v. Find the time complexities for the following loops. You should clearly analyze each step and give reasons for your answer.
(a)
sum = 0;
for( i = 0; i< n; i++)
for( j = 0; j < n * n; j++) sum++;
(b) sum = 0;
for( i = 0; i< n; i++)
for( j = 0; j < n * n; j++) sum++;
Question 3
i. Briefly describe the essential points to be satisfied in writing a recursive algorithm.
ii. Compare and contrast recursion vs iteration.
iii. Write a recursive pseudo code algorithm that returns the maximum among the first n
elements of an array.
iv. Write a recursive algorithm that prints all the permutations of the first n characters of a string. For example the call print ("ABC", 3) would print
ABC, ACB, BAC, BCA, CBA, CAB
v. Implement the algorithms written in part 3.3 and 3.4 in Java Language.
Question 4
i. Compare and contrast array structures with linked lists.
ii. Write a pseudo code algorithm to create a linked list with a header and insert five numbers to the list.
(a) Write a pseudo code algorithm to insert a new element between the 3rd and 4th elements.
(b) Write a pseudo code algorithm to delete an element in the middle of the linked list.
iii. Implement parts a andb in 4.4 using Java programming language.