Applied Data Structure & Algorithms

UNIVERSITY OF MAURITIUS

FACULTY OF ENGINEERING

SECOND SEMESTER EXAMINATIONS MAY 2010

PROGRAMME MODULE NAME DATE BSc (Hons) Information Systems Applied Data Structures and Algorithms Monday 10 May 2010 TIME NO. OF QUESTIONS SET 13:30 – 15:30 hrs 5 MODULE CODE DURATION NO. OF QUESTIONS TO BE ATTEMPTED CSE 1246(1) 2 Hours 4

INSTRUCTIONS TO CANDIDATES Answer Any Four (4) questions. All questions carry equal marks.

APPLIED DATA STRUCTURES AND ALGORITHMS – CSE 1246(1)

Answer any four (4) questions. All questions carry equal marks. Question 1 – [Total 25 marks] (a) State which data structure you would use to implement a program to: (i) (ii) (iii) Keep track of customers to be serviced at the bank. Keep records of students such that the details pertaining to a particular student can be easily retrieved by using the student ID. Store a list of student names and their CPA to be sorted in ascending order of CPA, given that the number of students is known and will not change. Keep track of the books kept in a box, given that if you want to remove a particular book, you need to first of all remove all the books kept on top of it. Keep records of all complaints made by the students concerning the services offered on campus, given that duplicate complaints are discarded. [5 * 2 marks]

(iv)

(v)

(b)

Predict the output of the following Java program:

public static void main(String[] args) { SortedSet mySet = new TreeSet(); mySet.add('a'); mySet.add('c'); mySet.add('b'); mySet.add('a'); Iterator it = mySet.iterator(); while(it.hasNext()){ System.out.print(it.next() + " "); } } // end main

[3 marks] (c) Given the following complexities for two sorting algorithms, sortingAlgo1 and sortingAlgo2, which one would you select to sort a large number of elements in a random order, based on their running time performance? Justify your answer. sortingAlgo1:Best-case: O(n log (n)) Average-case: O(n2) Worst-case: O(n ln(n)) sortingAlgo2:Best-case: O(n log (n))...