DESIGN OF INFORMATION STRUCTURES
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
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
[email protected] 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]