THE UNIVERSITY OF WARWICK
LEVEL 4 Open Book Assessment [2 hours]
Department of Computer Science
CS126 DESIGN OF INFORMATION STRUCTURES
Instructions
1. Read all instructions carefully and read through the entire paper at least once before you
start writing.
2. There are EIGHT questions: four in part A and four in part B.
You should attempt SIX questions: ALL four in part A and TWO in part B.
Indicate clearly which six questions you have attempted. You should not submit answers
to more than the required number of questions.
3. All questions will carry the same number of marks unless otherwise stated.
4. You should handwrite your answers either with paper and pen or using an electronic device
with a stylus (unless you have special arrangements for exams which allow the use of a
computer). Start each question on a new page and clearly mark each page with the page
number, your student id and the question number. Handwritten notes must be scanned or
photographed and all individual solutions should (if you possibly can) be collated into a
single PDF with pages in the correct order. You must upload two files to the AEP: your
PDF of solutions and a completed cover sheet. You must click FINISH ASSESSMENT
to complete the submission process. After you have done so you will not be able to upload
anything further.
5. Please ensure that all your handwritten answers are written legibly, preferably in dark blue
or black ink. If you use a pencil ensure that it is not too faint to be captured by a scan or
photograph.
6. Please check the legibility of your final submission before uploading. It is your responsi-
bility to ensure that your work can be read.
7. You are allowed to access module materials, notes, resources, references and the internet
during the assessment.
1
8. You should not try to communicate with any other candidate during the assessment pe-
riod or seek assistance from anyone else in completing your answers. The Computer Sci-
ence Department expects the conduct of all students taking this assessment to conform
to the stated requirements. Measures will be in operation to check for possible miscon-
duct. These will include the use of similarity detection tools and the right to require live
interviews with selected students following the assessment.
9. By starting this assessment you are declaring yourself fit to undertake it. You are expected
to make a reasonable attempt at the assessment by answering the questions in the paper.
Please note that:
– You must have completed and uploaded your assessment before the 24 hour assessment win-
dow closes.
– You have an additional 45 minutes beyond the stated duration of this assessment to allow for
downloading and uploading the assessment, your files and technical delays.
– For further details you should refer to the AEP documentation.
Use the AEP to seek advice immediately if during the assessment period:
• you cannot access the online assessment;
• you believe you have been given access to the wrong online assessment;
Please note that technical support is only available between 9AM and 5PM (BST).
Invigilator support will be also be available (via the AEP) between 9AM and 5PM (BST).
Notify Dcs.exams@warwick.ac.uk as soon as possible if you cannot complete your assessment
because:
• you lose your internet connection;
• your device fails;
• you become unwell and are unable to continue;
• you are affected by circumstances beyond your control (e.g. fire alarm).
Please note that this is for notification purposes, it is not a help line.
Your assessment starts below.
2
Section A Answer ALL questions
1. (a) Determine whether each of the following statements is true or false, justifying your
answer in each case.
i. 0.02n2 + 1000n is O(n) [2]
ii. 4n−2 is Θ(22n) [2]
iii. log2(n) is Ω(log2(n7)) [2]
(b) The numbers of operations performed by algorithms A and B on an input of size n
are 200n and 5n2, respectively. Find the smallest n0 such that algorithm B is slower
than algorithmA for all n ≥ n0, assuming that every operation takes exactly the same
amount of time. [3]
(c) If the following sentence is true then prove it, otherwise give a counterexample:
If f(n) is O(g(n)) and p(n) is Ω(q(n)) then f(n) · q(n) is O(g(n) · p(n)).
[4]
2. (a) Suppose that an initially empty stack S has performed a total of 16 push operations,
3 isEmpty operations, and 7 pop operations 3 of which returned null. What is the
current size of S? [4]
(b) What sequence of values is returned during the following sequence of stack opera-
tions, if executed on an initially empty stack? [4]
push(K), push(C), push(W ), pop(), push(I), push(R), push(A), pop(),
pop(), push(W ), pop(), pop(), pop()
(c) Suppose that you have a stack S that contains n elements and a queue Q that is
initially empty. You are also given an element x and you must correctly answer
whether x occurs in stack S or not. However, once you are done, the original contents
of the stack S must have been restored, all elements in it in the same order as at the
beginning.
Describe an algorithm for achieving the task described above that does not use any
data structures other than the stack S and the queue Q. [5]
3
3. (a) Briefly describe the Priority Queue Sort algorithm. [4]
(b) Illustrate the Selection Sort algorithm on the input sequence [2, 5, 1, 7, 4, 3, 6]. [4]
(c) For what specific implementation of the Priority Queue abstract data type does the
Priority Queue Sort algorithm yield the Selection Sort algorithm?
What is the worst-case asymptotic running time of the Selection Sort algorithm? Are
there inputs for which Selection Sort runs asymptotically faster than this worst-case
bound? If yes, describe them; if not, explain why. [5]
4. (a) Draw the binary tree representation of the following arithmetic expression: [5]
((g + ((a− d) ∗ h)) + d) + ((f/c) + b)
(b) Draw the binary tree whose array-based representation is [4]
H,K, T,N,D,N, U,D,O,A, L .
(c) Give the sequence of letters that is obtained by the postorder traversal of the tree from
part (b). [4]
4
Section B Answer TWO questions
5. (a) Draw a binary search tree with 7 nodes and whose height is 4. [4]
(b) What is the smallest height of a binary search tree with 13 nodes? Give an example
of such a binary search tree. [5]
(c) What is the largest number of nodes in a binary search tree of height 3? Give an
example of such a binary search tree. [4]
(d) Give a sequence of insertion operations that, when performed on an initially empty
binary search tree, will disprove the following statement: [6]
For every node in a binary search tree, the heights of its left and right sub-
trees differ by at most 1.
(e) Give an example that disproves the following statement: [5]
The order in which a fixed set of entries is insterted into a binary search tree
does not matter—the same tree results each time.
6. (a) We say that an undirected graph is complete if it contains an edge between every
pair of distinct vertices. Describe the shape of the breadth-first search tree of any
complete graph. [6]
(b) Let V be the set of vertices in an undirected graph and let m be the number of edges
in the graph.
Prove that
∑
v∈V deg(v) = 2m, where deg(v) is the number of edges that are incident
on the vertex v. [6]
(c) Given an n-element array R, algorithm A performs O(n − i) operations for each
element R[i] of the array. What is the worst-case running time of algorithm A? [6]
(d) Suppose that an n × n array A contains only 0’s and 1’s. Moreover, assume that in
every row of A and in every column of A, all the 0’s come before the 1’s.
Assuming that A is already in memory, describe an algorithm that counts the number
of 0’s in array A in time O(n). [6]
5
7. (a) Draw the undirected graph represented by the following adjacency list data structure.
vertex adjacent vertices
1 (2, 7, 8)
2 (1, 3, 8)
3 (2, 8)
4 (5, 6, 7)
5 (4, 6, 7)
6 (4, 5, 7)
7 (1, 4, 5, 6)
8 (1, 2, 3)
[4]
(b) Give the sequence of vertices of the graph from part (a) visited by the breadth-first
search started at vertex 3. [5]
(c) Draw the depth-first search tree of the graph from part (a) that is rooted at vertex 8.
[5]
(d) Suppose that a graph has 4,000 (four thousand) vertices and 10,000 (ten thousand)
edges, and it is important to use as little space as possible.
What data structure should you use for representing this graph: the adjacency list
structure or the adjacency matrix structure? Explain why. [5]
(e) Suppose that a graph has 4,000 (four thousand) vertices and 7,000,000 (seven million)
edges, and it is important to use as little space as possible.
What data structure should you use for representing this graph: the adjacency list
structure or the adjacency matrix structure? Explain why. [5]
6
8. (a) Draw all the heaps with four elements whose keys are 1, 3, 6, and 7. [5]
(b) Draw the heaps that are obtained after each step of the following sequence of opera-
tions on an initially empty heap:
insert(5), insert(3), insert(7), insert(4), removeMin(), insert(2), insert(1),
removeMin()
Mention all the upheap and downheap operations that need to performed. [7]
(c) In a large population of people, we want to identify the few who have been infected
by a novel virus so that they can be isolated to prevent further spread. Blood tests for
the presence of the virus exist but are scarce and very costly, so we want to use as few
tests as possible. A viable mechanism to achieve it is to mix small blood samples of
many patients for testing purposes: the test result will come out positive if and only
if at least one of the patients whose blood sample was included is infected. A blood
sample of each person can be used in many tests.
Suppose that there is exactly one person who has been infected by the virus and we
want to find them in a population of n people. Design an algorithm that helps a testing
lab decide the blood samples of which groups of people to mix for testing purposes
in order to identify the infected person using O(log n) tests. [6]
(d) In the virus testing scenario from the previous question, assume that in a population
of n people, there are d who have been infected by the virus.
Design an algorithm that helps a testing lab decide the blood samples of which groups
of people to mix for testing purposes in order to identify all the d infected people
using O(d · log n) tests. [6]
7















































































































































































学霸联盟