Assessment

Final Examination

Instructions

Answer all the questions that follow below.

1. Briefly describe:
   1. three different applications of a stack. (9 marks)
   2. the hashing technique. (8 marks)
   3. the binary search algorithm. (8 marks)
2. Differentiate between:
   1. PUSH and POP as used in a stack. (8 marks)
   2. a stack and a Queue? (8 marks)
3. Explain the following:
   1. the types operations of an array. (9 marks)
   2. three properties of an algorithm. (6 marks)
4. How do you insert a new item in a binary search tree? (14 marks)

Feedback

1. • Any three among the following applications of stack are as follows:
     • Function calls.
     • Reversal of a string.
     • Checking validity of an expression containing nested parenthesis.
     • Conversion of infix expression to postfix.
   • In general, in all searching techniques, search time is dependent on the number of items. Hashing is a technique where search time is independent of the number of items or elements. In this technique a hash function is used to generate an address from a key. The hash function takes a key as input and returns the hash value of that key which is used as an address index in the array.
   • Binary search algorithm always chooses the middle of the remaining search space, discarding one half or the other, again depending on the comparison between the key value found at the estimated position and the key value sought. The remaining search space is reduced to the part before or after the estimated position.
2. 1. - Pushing and popping refers to the way data is stored into and retrieved from a stack.
      • PUSH – Data being pushed/ added to the stack.
      • POP – Data being retrieved from the stack, particularly the topmost data.
   2. Stack – Represents the collection of elements in Last In First Out order.

      Operations includes testing null stack, finding the top element in the stack, removal of topmost element and adding elements on the top of the stack.

      Queue – Represents the collection of elements in First In First Out order. Operations include testing null queue, finding the next element, removal of elements and inserting the elements from the queue.

      Insertion of elements is at the end of the queue.

      Deletion of elements is from the beginning of the queue.

3. 1. Arrays are used for storing the data until the application expires in the main memory of the computer system. So that, the elements can be accessed at any time. The operations are:

      Any 3 operations

      • Adding elements
      • Sorting elements
      • Searching elements
      • Re-arranging the elements
      • Performing matrix operations
      • Pre-fix and post-fix operations
   2. Properties of an algorithm:

      Any 3 properties

      • Should be written in simple English
      • Should be unambiguous, precise and lucid
      • Should provide the correct solutions
      • Should have an end point
      • The output statements should follow input, process instructions
      • The initial statements should be of input statements
      • Should have finite number of steps
      • Every statement should be definitive

4. Assuming that the data to be inserted is a unique value (that is, not an existing entry in the tree), check first if the tree is empty. If it’s empty, just insert the new item in the root node. If it’s not empty, refer to the new item’s key. If it’s smaller than the root’s key, insert it into the root’s left subtree, otherwise, insert it into the root’s right subtree.