Challenge 04: kth smallest number

Problem overview

In this problem, you are given a list of integers, A = {a1, a2, ..., aN} and a number k. You are to find the kth smallest elements without sorting or doing k successive scans. More simply, no worse than O(n + k log n) time.

Inspiration

Note, this problem is based on a number of heap related interview questions, of which kth smallest number is the most popular.

Input / Output

You will be given a series of integers from standard input in the follow format:

N k
a_1 a_2 ... a_N

Each input array will consist of two lines:

  1. The first line consists of the N number of elements in the array and the desired the k

  2. The second line consists of the N elements in the array separated by spaces.

For each input array, output two elements: either Y or N if the array is a max heap (or not) and the kth smallest number.

For example, given the following input:

10 2
20 3916237 357920 3620601 7374819 7330761 30 6246457 6461594 266854

Your program should output the following:

N 30

Hints

  1. You want to think if turning a max heap into a min heap is any different than converting a vector into a heap
  2. Refer to Dr. Plank's notes on how to determine parent's and children of any arbitrary array entry in its corresponding heap representation

Rubric

We will grade your submission relative to the rubric below. 

+2    Code is well formatted, commented (inc. name, assignment, and overview), with reasonable variable names
+5    Solves kth smallest integer in O(n + k log n) time
+18   Test cases successfully solved (2 points each)

Testing your code prior to submission

To faciliate testing, you were previously asked to clone the course Github repository as follows: 

git clone https://github.com/semrich/ds302_19.git cs302

For this assignment, update this clone by using the following: 

git pull

We'll discuss this in class but note that your program must be named "solution.cpp" and compilable using make. To test your solution against ours, type: 

make test

Submission

To submit your solution, you must submit a single archive (.zip, .tar, .gz, etc.) on Canvas prior to the deadline.

Note: Although submission will be faciliated by Canvas, we will compile and test on EECS lab machines!

If you develop your solution elsewhere please make sure it works on the lab computers prior to the deadline