1.    An algorithm is O(n2). It takes 20 sec for a given dataset. If twice as much data is used, then:

◯ A.          It will take 40 sec.

◯ B.          It will take 80 sec.

◯ C.         It will take 400 sec.

◯ D.         The time it will take depends on whether the new dataset is the same

case as the initial dataset; average, best or worst case.

◯ E.         None of the above.

2.    Which of the following sorting algorithms has a possible worst-case running time of O(n2) where n is the number of elements to be sorted?

◯ A.         Merge-sort.

◯ B.         Quick-sort.

◯ C.         Selection Sort.

◯ D.         A and C.

◯ E.          B and C.

3.    An important property of a doubly linked list compared to a singly linked list is the  ease of determining an item's predecessor. Which of the following operations can use this property of a doubly linked list to the greatest advantage when compared with a singly  linked list?   (Assume   that  the  lists   have   head  references  but  not  tail

rfeA(re)nces.)Accessing an item.

◯ B.         Adding an item at the front of the list.

◯ C.         Deleting an item.

◯ D.         Concatenating two lists.

◯ E.         Copying a list.

4.    Which of the following don’t affect the time complexity of bucket sort?

◯ A.         The algorithm implemented for sorting individual buckets.

◯ B.         The number of buckets used.

◯ C.         The values to be sorted.

◯ D.         None of the above.

◯ E.         All of the above.

5.    Which of the following data structures may be used to implement the Queue ADT such that it provides amortised constant running time for all operations?

◯ A.         An array.

◯ B.         A singly-linked list.

◯ C.         A doubly-linked list.

◯ D.         A circularly linked-list.

◯ E.         All of the above.

6.    Which of the following is the number of heaps with different key/node arrangements that all include the four keys 1, 2, 3 and 4?

◯ A.         2

◯ B.          3

◯ C.         4

◯ D.         5

◯ E.         None of the above.

7.    After inserting the keys 12, 25, 2, 32, 65 into a red-black tree, the resulting red-black tree will have __ black nodes (Note: Null leaf nodes are not included.)

◯ A.          1

◯ B.         2

◯ C.         3

◯ D.         4

◯ E.         None of the above.

8.    Which of the following statements is correct, for a graph with n vertices and m edges?

◯ A.         Topological sort can be applied to Directed Acyclic Graphs and can be

implemented using BFS.

◯ B.         Topological sort can be applied to Directed Acyclic Graphs and can be

implemented using DFS.

◯ C.         BFS can find the minimum number of edges between two vertices.

◯ D.         A and C.

◯ E.         All of the above.

9.    To find the shortest paths to all other locations in a network from a given point, which of the following algorithms are least applicable?

◯ A.          Dijkstra’s.

◯ B.          Floyd’s.

◯ C.         Prim’s

◯ D.         Kruskal’s

◯ E.          B and C.

10.   Which of the following is false about the string searching problem, where the pattern has m characters, and the test has n characters?

◯ A.         In many situations, the brute force string searching algorithm is sufficient.

◯ B.         It is easy to code an implementation of brute force searching.

◯ C.         The worst-case time complexity of brute force searching is O(m*n).

◯ D.         None of the above.

◯ E.         All of the above.

13.  Discuss the impact of choosing a pivot deterministically or randomly in quick sort. Hint: For “Deterministic”, discuss how “always picking the last element as pivot” will affect the worst-case time complexity.  (4 marks)

We would like to sort 7 items, where each item is a 4-digit decimal number.

a)   Briefly explain the maximum number of comparisons needed to sort these items with a radix sort. (2 marks)

b)  What would be the Big-Omega complexity to sort these items using an insertion sort? (2 Marks)

15.  Given a pointer to the last node (rightmost node in bottom layer) of a complete binary tree, describe how you would find its next adjacent node. That is, the next position where you could  insert  and  maintain  a  complete  binary  tree.   Explain  how  the  computational

complexity would differ between a linked list and an array-based representation. (6 marks)

16.  Draw the splay tree at each stage after the elements 1, 2, 3, and 4 are added to an

initially empty splay tree. (3 marks)

17.  There is a cycle in a linked list if there exists a node in the list that can be reached again by continuously following the next pointer. An example of a cycle in a linked list is shown below.

Design an efficient algorithm in pseudo code to detect if there is a cycle in a list of n nodes, using a Hash Table. Provide the space and time complexity of your algorithm.  (5 marks)

18.  Would it be possible to employ Breadth First Search to find topological sorting of vertices in a graph? If yes, write the algorithm in pseudo code, and explain it’s time complexity. If not, provide the reason. (5 marks)