Description
algorithms
Unformatted Attachment Preview
Northeastern University
CS5800 Algorithms, Spring 2024
Instructor: Hyonho Lee
Assignment 4
(Total Marks: 50 pts)
Due Date: March 11, 2024, 6pm
Name:
Student Number:
Collaborators:
I,
, read and understood Northeastern University’s Academic Integrity Policy (https://osccr.sites.northeastern.edu/academic-integrity-policy/).
1. (15 pts) You are given a list of sorted lists of integers. Write an algorithm that returns
the sorted list consisting of all numbers in the list of sorted lists. That is, implement a function,
sort(A), where A is a list of non-empty sorted lists in non-decreasing order.
For example, sort([[2, 3, 3, 4], [1, 5], [1, 2, 4]]) should return [1, 1, 2, 2, 3, 3, 4, 5]. Your
algorithm should run in O(n log p), where n is the total number of elements in all lists and p is the
number of lists. (So, you should NOT sort all elements. That would result in Θ(n log n).)
You may use Python built-in heapq module.
def sort(A):
## Write Your Code Here ###
sort([[1]]) # returns [1]
sort([[2], [1]]) # returns [1, 2]
sort([[2, 3, 3, 4], [1, 5], [1, 2, 4]]) # returns [1, 1, 2, 2, 3, 3, 4, 4, 5]
sort([[10, 100], [1, 1, 1], [1, 1000]]) # returns [1, 1, 1, 1, 10, 100, 1000]
1
2. (15 pts) You are given a list of sorted lists of integers. Write an algorithm that returns kth
largest element in all of the lists. That is, implement a function, k largest(A, k), where A is a
list of non-empty sorted lists in non-decreasing order and k is an integer. Assume that k is less
than or equal to the sum of sizes of given lists. k largest returns kth largest element among all
elements in given lists.
For example, if A is [[2, 3, 3, 4], [1, 5], [1, 2, 4]] and k is 4, k largest should return 3 since 3 is
the 4th largest element among [2, 3, 3, 4, 1, 5, 1, 2, 4]. Your algorithm should run in O(p + k log p),
where p is the number of lists. (So, you should NOT sort all elements. That would result in
Θ(n log n), where n is the total number of element in all lists.)
You may use Python built-in heapq module.
def k_largest(A, k):
## Write Your Code Here ###
k_largest([[1]], 1) # returns 1
k_largest([[2], [1]], 2) # returns 1
k_largest([[2, 3, 3, 4], [1, 5], [1, 2, 4]], 4) # returns 3
k_largest([[10, 100], [1, 1, 1], [1, 1000]], 7) # returns 1
3. (20 pts) You are given a binary search tree. Write an algorithm that gives kth largest element
in the binary search tree. That is, implement a function, k largest bst(root, k), where root is
the root node of a binary search tree and k is an integer. Assume that k is less than or equal to
the size of the binary search tree. k largest bst returns kth largest element in the binary search
tree rooted at root.
For example, if the below binary search tree is given along with k = 4, then k largest bst
should return 65.
Do not modify the below class, Node. Note that, unlike in the class, below Node does not have
a parent pointer. Your algorithm should work without a parent pointer.
class Node:
def __init__(self, key: int):
self.left = None
self.right = None
self.value = key
def k_largest_bst(root: Node, k: int):
## Write Your Code Here ###
2
Practice Exercises
(The following questions will not be graded. Do not submit solutions. But similar questions
may appear in the exams.)
Exercise 6.1-4
Exercise 6.1-7 (6.1-6 for 3rd Ed.)
Exercise 6.2-1
Exercise 6.2-6 (6.2-5 for 3rd Ed.)
Exercise 6.3-1
Exercise 6.4-1
Problem 6-2 (d-ray heap)
Problem 6-3 (Young tableaus)
Exercise 12.2-5
Exercise 12.2-7
Exercise 12.3-3
3
Purchase answer to see full
attachment
