COP 3502C Programming Assignment#5
Topics covered: Binary Heap-Priority Queue
Please check Webcourses/Mimir for the Due Date
Read all the pages before starting to write your code
Introduction: For this assignment you have to write a c program that will utilize the merge sort, insertion sort,
and binary search algorithm.
What should you submit?
Write all the code in a single main.c file and submit the main.c file and memory leak detector files in mimir.
Also, submit a text file yourlastname.txt explaining the bigO run-time of your code.
Please include the following lines in the beginning of your code to declare that the code was written by you:
/* COP 3502C Programming Assignment 5
This program is written by: Your Full Name */
Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Assignment
rules mentioned in syllabus, are also applied in this submission. The TA and Instructor can call any students
for explaining any part of the code in order to better assess your authorship and for further clarification if
needed.
Caution!!!
Sharing this assignment description (fully or partly) as well as your code (fully or partly) to
anyone/anywhere is a violation of the policy. I may report such incidence to office of student conduct and
an investigation can easily trace the student who shared/posted it. Also, getting a part of code from anywhere
will be considered as cheating.
Deadline: See the deadline in Webcourses. If you can submit it by the deadline you will get 5% extra. If you can submit
it by the late submission deadline, there will not be any penalty. After that the assignment submission will be
locked. An assignment submitted by email will not be graded and such emails will not be replied according to
the course policy.
Additional notes: The TAs and course instructor can call any students to explain their code for grading.
Problem: The Median
In general, the Median is the "middle" of a sorted list of numbers. For example, for the following list of sorted
number: 10, 11, 13, 15, 16, 23, 26, the median is 15 as we have a total of 7 numbers and after sorting 15 is
the middle number on this list. However, if we have even number of items, we have two numbers in the
middle and in that case the median will be the average of those two numbers.
In this assignment, you will receive an unordered stream of distinct strings where the strings will contain only
single word and lower case letters. The maximum number of characters of a string can be 50. As soon as you
receive a string, you need to print the median of the strings you have received so far. If you have even number
of strings, you should print both of the middle strings in sorted order (based on the following definition) as
part of the Median.
In order to compare strings, you will use the following rule:
• Given strings a and b, we say a
• If two strings a and b have the same length, we say a
Example:
Let’s say the data stream are orange, apple, app, mango, cherry, peach, melon.
After reading the first item “orange” -> the median is “orange”
After reading the second item “apple” -> the median is “apple orange” (according to our definition as we have even
number of items and apple
After reading the third item “app” -> the median is “apple”
After reading the fourth item “mango” -> the median is “apple mango”
After reading the fifth item "cherry” -> the median is “mango”
After reading the sixth item "peach” -> the median is “mango peach”
After reading the seventh item "melong” -> the median is “melon”
Implementation restriction and important hints:
• Note that you are getting one string at a time and then print the median immediately.
• You must implement a compareTo function that will receive two strings and return a positive
number if the first string is greater than second string based on the specified rule. Otherwise,
it should return a negative number if the first string second string.
• If there are a total of n strings, the run-time complexity has to be O(n log n) [this O(n log n)
restriction does not include how you will take the input.]
• Using insertion sorting technique during this process could be a good idea, however, it will
result in O(n^2). So, you are not allowed to use any sorting algorithm in your code.
• You must use priority queue (heap) to solve this problem.
• Important hints: You might be now thinking that how do we really use heap in this problem
and how can we find median without sorting! Here is the trick:
o You can have two heaps, one will store smaller half of the numbers (lefth) and the
other one (righth) will store bigger half of the data. One of them will be min heap and
the other will will be maxheap. Please think a bit which one will be minheap and which
one will be max heap. o First string is a special case and it is a median without any comparison. Print this, and
add it to the heap for the smaller number. Keep track this as a current median.
o Create three cases: one for if the size of left heap is greater, another for if the size of
the right heap is greater, and finally one for if both heaps have same size.
o As soon as you receive a string, depending on the size of the left and right heap, and
the new string and the current median, you might need to delete an item from on heap
and insert it in the another heap (kind of transferring) during this process to balance
the heaps. Also, you need to insert the new string to an appropriate heap.
o Now, you can print the new median from the appropriate heap and update the current
median. In case of even items, you can update the current median with the smallest
one among them for further processing.
o Consider adding a peek function for lookup the root of a heap. This can be useful in
many cases
• You have to use the heap code we have seen in the class and need to modify it to solve this
problem. A good idea would be adding another parameter to the percolateUp and
percolateDown function to decide whether the operation is for a minheap or maxheap. Also,
remove all unnecessary functions that are not relevant to this.
• Your code should contain at least the following heap related functions: Insert, Percolateup,
Removemin, Removemax, initheap, swap, minimum, maximum.
• During this process, string operations could create additional challenges. Make sure to do
proper dynamic memory allocatin, strcpy, etc.
• You must use the memory leak detector and In order to get full credit, you need to free all the
memory.
• The code will be tested in mimir platform like previous assignments.
• The output must have to match with the sample output format. Do not add additional space, extra
characters or words with the output as we will use diff command to check whether your result
matches with our result.
• Next, you must have to write a well structure code. There will be a deduction of 10% points if the
code is not well indented and 5% for not commenting important blocks.
The Input (to be read from in.txt file) - Your Program Will Be Later Tested on Multiple Files
The first line of the input contains 1 integer n ( 0 n ,001) that indiecates the number of strings. Then the
ne lines will contain n distinct strings where each string is a single word with all lower case letter. The
maximum length of a string can be 50.
The Output (to be printed to console as well as to out.txt file)
There should be n lines of output. The ith line line of the output should contain the median at that moment
based on the ith input.
Sample Input data in in.txt file (Note: Query points in blue for clarity.)
7
orange
apple
app
mango
cherry
peach
melon
Sample Output (out.txt as well as in standard console output)
orange
apple orange
apple
apple mango
mango
mango peach
melon
Steps to check your output AUTOMATICALLY in Mimir or repl.it:
You can run the following commands to check whether your output is exactly matching with the sample output
or not.
Step1: Copy the sample output into sample_out.txt file and move it to the server
Step2: compiler and run your code using typical gcc and other commands. Your code shou ld produce out.txt
file.
Step3: Run the following command to compare your out.txt file with the sample output file
$diff -i out.txt sample_out.txt
The command will not produce any output if the files contain exactly same data. Otherwise, it will tell you the
lines with mismatches.
Rubric (Suject to change):
• A code not compiling or creating seg fault without producing any result can get zero. There may or
may not be any partial credit. But at least they will not get more than 50% even if it is a small reason.
Because, we cannot test those code at all against our test cases to see whether it produces the correct
result or not.
• Missing any one of the restriction can result in 50% penalty.
• There is no grade for just writing the required functions. However, there will be 20% penalty for not
writing and using CompareTo() function
• Reading the input properly: 5 pts • Run-time analysis: 5 pts
• Properly freeing memory leak: 8 pts
• Implementing both min heap and max heap properly with proper use of strings and compareTo fuction
for this assignment scenario: 32 pts
• Insert, Percolateup, Removemin, Removemax, initheap, swap, minimum, maximum.
• Generating proper output and passing all test cases (note that more test cases can be added while
grading. So, you should test your code properly and consider generating your own test cases): 50
• There will be various types of simple to complex test files within the assignment criteria
• There is no point for well structured, commented and well indented code. There will be a deduction
of 10% points if the code is not well indented and 5% for not commenting important blocks.