Computer Science And Engineering CSE 232 Lecture Notes - Lecture 4: Cheat Sheet, Merge Sort, Priority Queue
30 Apr 2018
School
Department
Professor
CSE 247 Data Structures
and Algorithms
Fall 2017
Given:
Nov. 6th, 2017
Exam 2
Start time: 6:30 PM
Due: 8:30 PM
This exam is closed-book, closed-notes except for the single 8.5x11in “crib sheet” mentioned in
class. No electronic devices or resources of any kind are allowed. Your work must be legible. Work that
is difficult to read will receive no credit.
You must sign the pledge below for your exam to be counted. Any cheating will cause the
student(s) involved to at the very least receive a 0 on the exam and incur academic integrity procedures.
Other action may also be taken.
Your work must be completed on these pages. There are blank pages at the end of the exam if
you need them. Remember not to spend too much time staying stuck on any one question: if you’re stuck,
move on and return to the question later.
You must fill in your identifying information correctly below. PLEASE PRINT.
Name:
Student ID (Print VERY clearly):
Problem
Number:
Possible
Points:
Received
Points
1
18
2
12
3
15
4
16
5
24
6
15
Total
100
Pledge: On my honor, I have neither given nor received any unauthorized aid on this exam.
Signed: _________________________________________________________________
(Be sure you filled in your information in the box above!)
1
Problem 1.
Consider the following recurrence that represents the simplified runtime of a k-way mergesort:
T(n) = kT(n/k) + kn for n > 1,
T(1) = k
for some constant integer k. Assume n is a power of k for simplicity.
a) Fill in all blank slots in the table below to tabulate work done at all levels of the recursion.
Recall that the root of a tree is at depth 0.
Note: Don’t forget to fill in the depth of the recursion tree at the base level.
tree (recursion)
depth
# nodes
at this depth
work per node
at this depth
total work
at this depth
0
1
1
2
i
_______
(base-case level)
b) Write a summation that expresses the total amount of work done over all levels.
_____________________________________
c) What is the closed-form solution of your summation?
Note: Don’t forget to specify the base of any logarithms used. An expression with an incorrect
log base will not receive full credit.
T(n) = _______________________
d) Based on your closed-form solution, what is the asymptotic time complexity of the recurrence
in simplest form?
T(n) = 𝚹 _______________________
2
Problem 2.
Lecture 7 presented radix sort as performed on integers; this problem explores radix sort
performed on strings.
a) Consider the following list of four-letter words (not that
kind, don’t worry):
PATH
PAST
FAST
CHIP
HOME
List the words in the order they would appear after two passes of radix sort done top-to-bottom
using lexicographic (i.e. alphabetical) ordering. Order the list least-to-greatest from top to
bottom:
___________ (lexicographically least)
___________
___________
___________
___________ (lexicographically greatest)
b) Give a list of five 4-character strings (they do not have to be real words) on which radix sort
would return an incorrect answer if done in most-significant- to least-significant-position order.
Assume the radix sort scans the list from top to bottom on each pass.
___________
___________
___________
___________
___________
c) If radix sort as presented in Lecture 7 were implemented on same-length strings of English
and Chinese characters, which implementation would be faster on a small input set of
100 strings in the worst case? Consider relevant constant factors.
________________________
Why? _____________________________________________________________________
3
