Student Name: …………………………………………………………………………………… Student Number: …………………………………………………………………………………
COMP ENG 2SI4
Data Structures, Algorithms and Discrete Mathematics
Day Class
Duration of Examination: 2.5 Hours
MCMASTER UNIVERSITY FINAL EXAMINATION SAMPLE Instructors: Dr. Ratnasingham Tharmarasa and Jianfeng Hu April 2020
This examination paper includes 9 pages and 8 questions. You are responsible for ensuring that your copy of the paper is complete. Bring any discrepancy to the attention of your instructor. The number in brackets at the start of each question is the number of marks the question is worth.
• Answer each question on a separate letter-size paper.
• All answers must be hand-written.
• Use the following naming convention for your files: StudentNumber QuestionNumber (e.g., 400654321 Q2).
– If you have answered on more than one page for a question, then the name of the second page should be StudentNumber QuestionNumber PageNumber (e.g., 400654321 Q2 p2).
• Write your name and student number on each page.
• Upload a scanned copy or clear photos of answer sheets to avenue by 3:30 pm on
April 25, 2020.
Academic integrity statement:
By submitting this work, I certify that the work represents solely my own independent efforts. I confirm that I am expected to exhibit honesty and use ethical behaviour in all aspects of the learning process. I confirm that it is my responsibility to understand what constitutes academic dishonesty under the Academic Integrity Policy.
n i = n(n+1) i=1 2
n ai=an+1−1, a̸=1 i=0 a−1
n i2 = n(n+1)(2n+1) i=1 6
1. Numbers from Student Number (2)
Fill in the following tables or update the spreadsheet included in the exam folder using the digits in your student number.
You can submit the updated spreadsheet or a scanned copy of the filled tables below. It is recommended to use the spreadsheet.
Example: If the student number is 400123456, D1 = 6, D3 = 4, hence #D1D2D3 = 654 and #D3D2D1 = 456.
Digits
D9
D8
D7
D6
D5
D4
D3
D2
D1
Your student number
Symbol
Number
#D1
#D5
#D3D2D1
#D5D4D3
#D6D4D2
#D1D3D5
You have to use the values from this table whenever you see a number start with “#” in any of the questions 2 to 8.
2. Stack and Queue
(a) (2) Suppose you push (#D1 + 20), (#D5 + 10), 9, 8 and () onto the stack. Then you pop four times. Which one is left on the stack?
#D1 and #D5 refer to numbers obtained from your student number.
(b) (5) Describe an implemention of a stack of integers using two queues. You are not required to write Java code. Clearly describe in words your algorithm and evaluate its running time. Less efficient solutions will be awarded a partial mark, depending on their efficiency.
3. Hashing
Consider a set of keys which are 3-digit integers of the form x1x2x3 where each of the xi ∈
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Consider a hash table of size M = 10 and the hash function h(x1x2x3) = (2 × x1 + x3) mod 10
(a) (3) Insert the following elements into a hash table of size 10:
110, #D3D2D1, #D5D4D3, #D6D4D2, 435, #D1D3D5
Resolve collisions using linear probing. For each insertion indicate the indices of all el- ements which are examined and indicate the final index where the insertion is performed. Show your work. (Note: the index of hash table starts from 0.)
If any of the numbers that you form with your student number is repetitive, increment by 20 until you find a number that is not already selected.
(Example: student number is 4001211111; #D3D2D1 = 111, #D5D4D3 = 111, #D6D4D2 = 211, #D1D3D5 = 111 the second number, #D5D4D3, 111 is already used, hence the second number is 131; the fourth number, #D1D3D5, 111 is also already inserted, 131
is also inserted, hence the fourth number is 151).
4. Heap and Heap Sorting
(a) (3) Consider the following min heap
30
70
210 800
340
50
190 150
390
Insert #D3D2D1 into this heap and draw the new heap obtained.
If the number #D3D2D1 that you form with your student number already exists on the heap or is equal to 000, increment by 2 until you find a number that is not on the heap. (Example: student number is 400113390; #D3D2D1 = 390, which is already on the heap; hence, use 392 (390 + 2) for #D3D2D1.)
5. Sorting
(a) (1) Pick 4 random numbers in the range of 10 to 99 and write the numbers in the picked sequence. Marks will only be given for proper random numbers (e.g., 11, 12, 13, 14 or 10, 20, 30, 40 are not acceptable random sequences).
(b) (2) Sort the 4 numbers picked in the question above in descending order using the in- sertion sort algorithm. Show the contents of the array after the first, second and third passes.
6. Graphs and Graph Theory
(a) (2) Write down all the possible paths from vertex a to c and their weights.
w1 = #D1 a
30
In the above, the weight w1 is equal to the number #D1 and w2 is equal to the number #D5.
b
w2 = #D5
c