COMP20003 Algorithms and Data Structures
Spring 2015 Name:
Midterm Student ID
17/9/2015
Time Limit: 45 Minutes
This paper has three questions. Answer all questions on the test paper on the printed side
only. You may use the facing page for your own notes if you wish, but it will not be marked
unless you clearly indicate this as your wish.
There are extra blank pages at the end of the paper.
Marks are shown out of 10, and this paper counts for 10% of your final grade. You are
permitted to use pencil.
This exam contains 14 pages (including this cover page) and 8 questions.
Please do not open this test until instructed to do so.
Grade Table (for teacher use only)
Question Points Score
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 3
Total: 10
COMP20003 Algorithms and Data Structures Midterm - Page 2 of 14
Computational Complexity (2 marks)
1. (1 point) Given the following functions f(n) and g(n), is f in O(g(n)) or is f in Θ(g(n)),
or both? If true, specify a constant c and point n0, if false, briefly specify why.
(a) (1/3 points) f(n) = 2n, g(n) = 22n.
(b) (1/3 points) f(n) = n!, g(n) = 2n.
(c) (1/3 points) f(n) =
∑n
i=1 i
k, g(n) = nk.
2. (1 point) Consider f(n) = 1 + c+ c2 + . . .+ cn where c is a positive real number, and a
function g(n) which satisfies f(n) ∈ Θ(g(n)):
(a) (1/3 points) if c < 1, then g(n) =?.
(b) (1/3 points) if c = 1, then g(n) =?.
COMP20003 Algorithms and Data Structures Midterm - Page 3 of 14
(c) (1/3 points) if c > 1, then g(n) =?.
COMP20003 Algorithms and Data Structures Midterm - Page 4 of 14
Searching and Sorting (5 marks)
Briefly and clearly answer each of the following questions.
3. (1 point) This question is about arrays/lists and selection/insertion sort.
(a) (1/2 points) Given m lookup/search operations over n items, is there any efficiency
difference between using an unsorted linked list or an unsorted array? Under which
circumstances would sorted list or array be more efficient? Answer in terms of the
parameters m and n.
(b) (1/2 points) Which method runs fastest for an array with all keys identical, selec-
tion sort or insertion sort?
COMP20003 Algorithms and Data Structures Midterm - Page 5 of 14
4. (1 point) Which rotation do you need to get an AVL tree? Draw the resulting AVL tree
COMP20003 Algorithms and Data Structures Midterm - Page 6 of 14
5. (1 point) Given a BST, explain how can you free all the nodes from memory.
6. (1 point) Insert the integers {10, 5, 4, 14, 4, 25, 23, 12, 41} in a hash table of size B using
linear probing and the hash function h(x) = x%B, where B = 10
COMP20003 Algorithms and Data Structures Midterm - Page 7 of 14
7. (1 point) Given the sequence of integers { 15, 7, 3, 8, 4, 10, 2}, sort them using mergesort.
Show the changes at every step, specify the worst case performance. Justify your answers.
COMP20003 Algorithms and Data Structures Midterm - Page 8 of 14
C Code (3 marks)
8. (3 points) On the next page, you are given a partially written C program that reads in
strings from stdin. The program first allocates memory to B, a pointer to a pointer to
char, that can be used like an array.
Fill in code in the three places indicated in the program, to:
ˆ Store each string in B using space efficiently.
ˆ Sort the strings by increasing Alphanumeric order using selection sort.
ˆ Free all the memory that has been used by the program, before it terminates.
Note that the number of strings is not known at the start of the program. You can
assume a maximum string length of size MAXSTRING.
You are to fill in C code to accomplish this task, as indicated.
To sort, you can use strcmp,
1 i n t strcmp ( const char * str1 , const char * str2 ) ;
which returns 0 if strings are equal, returns < 0 if ptr1 has lower value than ptr2, and
> 0 viceversa.
1 #inc lude
2 #inc lude
3 #inc lude
4 #de f i n e MAXSTRING 200
5 #de f i n e NUMBER 10
6 #de f i n e OK 0
7
8 i n t main (argc , argv)
9 {
10 char ** B ;
11 char line [MAXSTRING ] ;
12 i n t i ,j ,strings ,arraysize ;
13
14 i f ( (B = ( char **)malloc(NUMBER * s i z e o f ( char *) ) ) == NULL)
15 {
16 printf( ”mal loc e r r o r \n” ) ; fflush(stdout) ;
17 exit (1 ) ;
18 }
19
20 strings=0;
21 arraysize=NUMBER ;
COMP20003 Algorithms and Data Structures Midterm - Page 9 of 14
22
23 /**
24 * f g e t s reads cha ra c t e r s from stream and s t o r e s them
25 * as a C s t r i n g in to s t r u n t i l (MAXSTRING−1) cha ra c t e r s
26 * have been read or e i t h e r a newl ine or the end−of− f i l e
27 * (EOF) i s reached , whichever happens f i r s t .
28 */
29 whi le ( (fgets(line ,MAXSTRING ,stdin) ) !=NULL)
30 {
31 /**
32 * ADD CODE HERE
33 * s t o r e each s t r i ng , e f f i c i e n t l y , in the array B,
34 * count the s t r i n g s
35 */
COMP20003 Algorithms and Data Structures Midterm - Page 10 of 14
1 }
2
3 /**
4 * ADD CODE HERE
5 * Sor t ing B us ing S e l e c t i o n Sort . Remember that s e l e c t i o n s o r t
6 * r epea t ed ly f i n d s the sma l l e s t element in the unsorted part o f
7 * the array and swaps i t with the f i r s t element in the unsorted
8 * part o f the array .
9 */
COMP20003 Algorithms and Data Structures Midterm - Page 11 of 14
1
2 /**
3 * ADD CODE HERE
4 * now f r e e a l l the space you have
5 * acqu i red with mal loc ( )
6 */
1 re turn (OK) ;
2 }