C OP 3 502C Programming Assignment # ...

Question

C
OP

3
502C

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 memor
y

leak detector files

in mimir.

Also,

submit a text file

yourl
ast
name.txt

explaining

the

bigO

run
-
time of your code.

Please include the fo
llowing 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 auth
orship 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 sub
mit

it by the

late submission deadline,

there will not be any pe
nalty.

After that t
he assignment submission will be

locked.

An assignment submitted by email will not be graded and

such emails

wil
l 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, t
he Median is the

"middle
"

of a

sorted

list of numbers
.

For example, for the following list of

sorted

number
: 10
,

11
, 13,

15,

16,

2
3, 26
, the median is

15

as we have

a total of

7 numbers

and after sorting 15 is

the

mid
dle

number on this list.

Ho
wever, if we hav
e even number of items,

we have two number
s in the

middle and in that case the median will be the average of those t
wo numbers.

In this assig
nment,

you will receive a
n

unordered

stream of

distinct

strings

where the strin
gs will contain on
ly

single word and

lower case letters
. T
he 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 bot
h of the middle

strings

in sorted order (based on the following

definition
)

as

part o
f the Med
ian.

I
n order to

compare strings,

you will use the following rule:

•

Given strings a and b, we say a < b="" if="" a="" has="" fewer="" characters="" than="">

•

If two strings a and b have the same length, we say a < b="" if="" a="" comes="" before="" b="" in="" alphabetical="">

Example:

Let
’
s say

the dat
a str
eam

are

orange,

apple,

app, mango
,

cherry
,

peach
,

melon
.

Afte
r

reading the first

item

“
orange
”

-
> th
e median is

“
orange
”

Afte
r

reading the

second

item

“
apple
”

-
> th
e median is

“
apple

orange
”

(according to our definition

as we have even

number of items and apple <>

Afte
r

reading the

third

item

“
app
”

-
> the median is

“
apple
”

Afte
r

reading the

fourth

item

“
mango
”

-
> the median is

“apple

mango
”

After reading the fifth item "
cherry
”

-
> th
e me
dian is

“
mango
”

After reading the

sixth

item "
peach
”

-
> th
e me
dian is

“mango

peach
”

After reading the

seventh

item "
melong
”

-
> th
e me
dian is

“
melon
”

Implementation restriction

and

important

hints
:

•

Note that you are getting one

string

at a time and then print

the median

immediately
.

•

Yo
u must im
plement a compareTo

function

that will receive two

strings and re
turn

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, t
he run
-
time complexity has t
o b
e 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 w
ill

resul
t 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 mi
ght be

no
w thinking

that how do we reall
y use heap in this

problem

and how can we

find median

without

sorting
! Here is the trick:

o

Y
ou can have two heap
s
,

one will

store smaller half o
f the numbers

(
left
h) and

the

other

one

(righth)

will store

bigger half of the data
. One of them will be mi
n heap and

th
e other will will be maxh
eap.

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.

P
rint

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 hea
p 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

dele
te an ite
m from on heap

and insert i
t in the another heap

(kind of

transferring
)

during th
is process

to b
alance

the heaps. Also, you need to insert the new string to an

appropriate

heap.

o

N
o
w,

you can

print the

new median from the

appropriate heap

and up
date 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 i
n

many cases

•

You have to use the h
eap code we have

seen in the class and need to modify it to

solve this

problem.

A

goo
d

idea

would

be

adding

another

parameter

to

the

percolate
Up

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 con
tain at le
ast th
e following heap related functions:

I
nsert
,

P
ercolate
up
,

R
emovemin
,

R
emovemax
,

initheap,

swap,

minimum, maximum.

•

D
uring 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 fu
ll 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
.

•

Ne
xt, 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

<>
,
00
1
)

that indiecates the number of

strings
.

The
n the

ne lines will contain n distinct strings where each string is a single word w
ith all lower case letter. The

maximum

length

of a string can be 50
.

The Output (to be printed

to

consol
e

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

app
le

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

•

R
un
-
time analysis
: 5 pts

•

Properly freeing memory leak: 8 pt
s

•

Implementing

both min heap and max heap

properly

with

proper

use of

strings and compareTo fuction

for this assignment scenario:

32 pts

•

I
nsert
,

P
ercolate
up
,

R
emovemin
,

R
emovemax
,

initheap,

swap,

minimum, maximum.

•

G
enerating proper

output

and passing all test cases (note that more test cases can be added while

grading. So, you should test your code

pro
perly

and consider generating your own test cases)
:

5
0

•

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 th
e code is not well indented and 5% for not commenting important blocks.

sampleout-3-cp1ya53z.txt samplein-3-25kz3omn.txt p5-sum-22-oj0mnrz0.pdf

C OP 3 502C 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:...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment