lOMoARcPSD|53991452
CSE373, MAT373: Mock Final Exam 1 Solutions - Spring
2021
Analysis Of Algorithms (Stony Brook University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by kuchy kuchy ()
, lOMoARcPSD|53991452
CSE373, MAT373: Analysis of Algorithms, Spring 2021 Date: May 11, 2021
Mock Final Exam 1 (Solutions)
( 5:30 PM – 8:00 PM : 150 Minutes )
• This exam will account for 45% of your overall grade.
• There are six (6) questions, worth 250 points in total. Please answer all of them.
• This is a closed book, closed notes exam. No cheat sheets are allowed.
• You are allowed to use scratch papers for your calculations.
• You are not allowed to use your own calculator. A scientific calculator will be available inside
the Respondus Lockdown Browser.
Good Luck!
Question Parts Points
1. Mergesort – 2.5 × 8 = 20
2. Heap Operations (a)–(h) 5 × 8 = 40
3. Dijkstra’s SSSP (a)–(l) 5 + 5 × 10 + 10 = 65
4. Kruskal’s MST (a)–(j) 5 × 10 = 50
5. Longest Common Subsequence (a)–(c) 20 + 10 + 10 = 40
6. Complexities (a)–(g) 7 × 5 = 35
Total 250
Downloaded by kuchy kuchy ()
, lOMoARcPSD|53991452
Question 1. [ 20 Points ] Mergesort. Recall that the mergesort algorithm we saw in the class
(before midterm) works by splitting the given sequence at the midpoint, recursively sorting the two
parts, and then merging the two sorted parts into a single sorted sequence.
This task asks you to fill out the following figure in order to show how the splitting and merging
steps work for the given input sequence.
You do not need to draw the figure in your answer. You simply need to write down the contents of
the cells after each split/merge step. Here is an example.
Suppose the contents of the four blocks in step 6 are as follows.
Then you write the following line for step 6 in your answer.
6. [a1 , a2 , a3 , a4 ] [b1 , b2 , b3 , b4 ] [c1 , c2 , c3 , c4 ] [d1 , d2 , d3 , d4 ]
Your answer must include a separate line for each of the 8 steps.
1
Downloaded by kuchy kuchy ()
CSE373, MAT373: Mock Final Exam 1 Solutions - Spring
2021
Analysis Of Algorithms (Stony Brook University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by kuchy kuchy ()
, lOMoARcPSD|53991452
CSE373, MAT373: Analysis of Algorithms, Spring 2021 Date: May 11, 2021
Mock Final Exam 1 (Solutions)
( 5:30 PM – 8:00 PM : 150 Minutes )
• This exam will account for 45% of your overall grade.
• There are six (6) questions, worth 250 points in total. Please answer all of them.
• This is a closed book, closed notes exam. No cheat sheets are allowed.
• You are allowed to use scratch papers for your calculations.
• You are not allowed to use your own calculator. A scientific calculator will be available inside
the Respondus Lockdown Browser.
Good Luck!
Question Parts Points
1. Mergesort – 2.5 × 8 = 20
2. Heap Operations (a)–(h) 5 × 8 = 40
3. Dijkstra’s SSSP (a)–(l) 5 + 5 × 10 + 10 = 65
4. Kruskal’s MST (a)–(j) 5 × 10 = 50
5. Longest Common Subsequence (a)–(c) 20 + 10 + 10 = 40
6. Complexities (a)–(g) 7 × 5 = 35
Total 250
Downloaded by kuchy kuchy ()
, lOMoARcPSD|53991452
Question 1. [ 20 Points ] Mergesort. Recall that the mergesort algorithm we saw in the class
(before midterm) works by splitting the given sequence at the midpoint, recursively sorting the two
parts, and then merging the two sorted parts into a single sorted sequence.
This task asks you to fill out the following figure in order to show how the splitting and merging
steps work for the given input sequence.
You do not need to draw the figure in your answer. You simply need to write down the contents of
the cells after each split/merge step. Here is an example.
Suppose the contents of the four blocks in step 6 are as follows.
Then you write the following line for step 6 in your answer.
6. [a1 , a2 , a3 , a4 ] [b1 , b2 , b3 , b4 ] [c1 , c2 , c3 , c4 ] [d1 , d2 , d3 , d4 ]
Your answer must include a separate line for each of the 8 steps.
1
Downloaded by kuchy kuchy ()
