Description
1 Written Questions
Question 1: Priority Queues (15 points)
Simulating Priority Queue Using a Stack
Write a function push with priority(stack, priority, element) that pushes elements onto a
stack based on a given priority. Lower priority elements should always appear closer to the top.
Your Answer:
d e f p u s h w i t h p r i o r i t y ( s t ac k , p r i o r i t y , elemen t ) :
# Temporary s t a c k t o h old el em e n t s u n t i l the r i g h t p o s i t i o n i s found
temp s t ac k = [ ]
# 1 ) Move el em e n t s t o temp s t ac k w hil e m ai n t ai ni n g p r i o r i t y o r d e r
# 2 ) I n s e r t the new elemen t with i t s p r i o r i t y
# 3 ) Move the el em e n t s back from temp s t ac k t o s t a c k t o m ain t ain
t h e i r o r d e r
# Example u s a ge
s t a c k = [ ]
p u s h w i t h p r i o r i t y ( s t ac k , 3 , ”A” )
p u s h w i t h p r i o r i t y ( s t ac k , 1 , ”B” )
p u s h w i t h p r i o r i t y ( s t ac k , 2 , ”C” )
p r i n t ( s t a c k ) # Output : [ ( 3 , ’A ’ ) , ( 2 , ’C ’ ) , ( 1 , ’B ’ ) ]
Question 2: Binary Search Tree Operations (20 points)
In this question, you will perform several operations on a Binary Search Tree (BST).
a) (10 points) Draw the binary search tree after inserting the following 12 elements into an empty BST
in the given order
[50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 65, 90]
b) (5 points) Insert Element: After constructing the BST with the above elements, draw the updated
tree after inserting the element 17 into the tree.
c) (5 points) Delete Element: Draw the binary search tree after deleting the element 70 from the tree
and describe how the tree restructures itself.
Question 3: Sorting (20 points)
Task 1: [10 points]
Demonstrate the quick-sort algorithm step by step, using the last element of the current subarray
as the pivot. Given the array:
[8, −3, 7, −1, 10, 2, −5]
Complete the following table by showing the left partition (L), right partition (G), and the pivot at
each step. Perform quicksort recursively on the subarrays and show each intermediate result.
Solution Template:
Step Pivot Left Partition Right Partition
Initial Array – – –
1
2
3
…
Final Array – – –
Table 1: Solution Template
Notes for Students:
• Use the solution template above to format your answers.
• Use the last element of the current subarray as the pivot for each step.
Task 2: [2 points]
Complete the missing line in the following code fragment to correctly implement merge-sort’s merge
function.
d e f merge ( S1 , S2 , S ) :
i = j = 0
w hil e i + j < l e n ( S ) :
i f j == l e n ( S2 ) o r ( i < l e n ( S1 ) and S1 [ i ] < S2 [ j ] ) :
S [ i+j ] = S1 [ i ] # copy i t h elemen t o f S1 a s nex t item o f
S
i += 1
e l s e :
# Mi s sin g l i n e
j += 1
Task 3: [8 points]
You are given a function that performs quick sort using extra storage to partition the array. Your task
is to fill in the missing lines in the code to complete the quick sort implementation.
Code:
d e f q u i c k s o r t e x t r a s t o r a g e ( S , a , b ) :
i f a >= b :
r e t u r n
pi v o t = S [ b ] # Choose the pi v o t
# C re a te new a r r a y s f o r the p a r t i t i o n s
l e f t p a r t i t i o n = [ ]
r i g h t p a r t i t i o n = [ ]
f o r i i n r an ge ( a , b ) : # I t e r a t e onl y u n t i l b ( e x cl u d e pi v o t )
i f S [ i ] < pi v o t :
l e f t p a r t i t i o n . append ( S [ i ] )
e l s e :
r i g h t p a r t i t i o n . append ( S [ i ] )
# S o r t l e f t p a r t i t i o n
q u i c k s o r t e x t r a s t o r a g e ( l e f t p a r t i t i o n , 0 , l e n ( l e f t p a r t i t i o n ) − 1 )
# S o r t r i g h t p a r t i t i o n
q u i c k s o r t e x t r a s t o r a g e ( r i g h t p a r t i t i o n , 0 , l e n ( r i g h t p a r t i t i o n ) −
1 )
# Mi s si n g l i n e s h e r e t o c o r r e c t l y merge the p a r t i t i o n s and pi v o t back
i n t o the o r i g i n a l a r r a y
Hint:
After the recursive calls to the left and right partitions, think about how you can reconstruct the
original array using the sorted left partition, the pivot, and the sorted right partition. The original
array must be updated with these sorted parts.
2 Coding Questions
Question 1: Analyzing Character Frequencies (35 points)
Implement a Python function analyze character frequencies(text) that takes a string text as
input and does the following:
Count the frequency of each character in the text and store the character-frequency pairs in a dictionary.
The function should process the text as follows:
• Convert the text to lowercase.
• Consider only alphanumeric characters (letters and digits).
• Ignore whitespace and punctuation characters.
• Store the character-frequency pairs in a dictionary where the keys are the characters and the
values are their respective frequencies.
Return a list of the characters sorted in descending order based on their frequencies. If multiple characters have the same frequency, sort them in alphabetical order.
Instructions:
• Implement the analyze character frequencies(text) function according to the given requirements.
• You can assume that the input text contains only alphanumeric characters, whitespace, and
punctuation characters.
• The function should handle case-insensitivity when counting character frequencies.
• If the input text is an empty string or contains only whitespace and punctuation characters, the
function should return an empty list.
Input:
Knack for knick-knacks, the keen kangaroo quickly kicked the kooky koala into the knapsack
by the kayak on the kooky creek.
Output:
[’k’, ’a’, ’e’, ’o’, ’n’, ’c’, ’t’, ’h’, ’y’, ’i’, ’r’, ’l’, ’s’, ’b’, ’d’, ’f’, ’g’, ’p’, ’q’, ’u’]
Marking Rubric: This question will be marked out of 35 for correctness (pass test cases):
• 35/35: Pass all 5 of the test cases
• 21/35: Pass any 2 (or more) of the test cases
• 7/35: Pass any of the test cases
3 Submission Instructions (10 points)
Please follow these submission instructions carefully. Correctly submitting all files is worth 10 points.
In these files, you must replace ccid with your own ccid. Your ccid is the first part of your UAlberta
email (ccid@ualberta.ca). Do not zip any of these files. Please submit the following files to eclass:
• ccid writtenQuestions.pdf : Your answers to all written questions should be in this one pdf
file.
• ccid solutionQuestion1.py : Edit the provided file for question 1. After your solution passes
all test cases (which you must test using the driver), rename the file to include your ccid, that
is, ccid solutionQuestion1.py and submit it to eclass.