[Home | Assignments | Links | Grades | CIS 313]

CIS 323 - Assignment 4

Binary min-heap and simple cryptography

Due Thursday, March 4, 2010

Description

You can write your code in any programming language for this assignment.

The goal of this assignment is to get familiar with using heaps as priority queues and use them to make a hidden message system as described below.

Problem description

You and your friend want to develop a simple method for exchanging hidden messages to each other. You decide to embed your message within a bunch of other random words and using a key k that only the two of you know, your method will extract the hidden message from the list of random words.

The method you decide on works as follows:

Each word in the wordlist gets a unique number attached, greater than or equal to zero.
The length of the message is known. Let's call it w
The entire number of words in the list is unknown but you decide that the last line of the list should always be -1
To find each word in the message, extract k words with the smallest number. The (k+1)th word is a word in the hidden message
Repeat step 4, w times

Task

According to the above description, you should:

Implement a heap with priority queue operations. The heap should have a fixed initial size and grow when it is needed.
Find the hidden messages in my input files, given the above description
Besides reading input from an input file through standard input (like usual), your program should be able to take a key k as an argument to the program.
You should conform to the input/output specification given further down.

You can find heap and priority queue implementation in chapter 6 of the book.

Input/Output

The input will be formatted in the following way:

A non-negative integer w, on its own line, representing the number of words in the hidden message.
An unspecified number of lines, each with a number x and a name s, separated by a whitespace
The input-file is terminated by a -1

Notice that there is no information on the secret key. That is the whole point of having a cryptographic system. Only the sender and the recipient should be able to know the system.

You may assume that no duplicate numbers will be inserted.

Here is an example:

Input:

35 dwarves

9 I

21 Grumpy

48 Sneezy

11 Bashful

19 hide

32 Happy

44 Doc

28 amongst

4 Sleepy

-1

Output

If I run the above data, located in the file hiddenMessageFile, with the key 1, it will look something like:
./myProgram 1 < hiddenMessageFile
This command should produce the following output

hide

amongst

dwarves

You should conform exactly to the input and output specification, as I will be using massive test cases and checking your output against the correct output. Just like last time.

Testcases

You can find test inputs here. There are two testcases with supplied correct output. There is also a zip-file, containing five messages with unknown keys. In the file hints, I have written a short hint for the key of each of the five files. You have to submit the hidden message for each of the five files as part of your assignment. See the section below on what to turn in.

Finding the hidden message

For each input file, I will give a hint to what the key is for that file. You will have to figure out the key by yourself though.

What to turn in

Your implementation of the Min-Priority-Queue that can take a key as an argument and produce the correct output, as specified above.
The hidden message for each of the testcases I provide. This will be part of your grade!

Submission

No further submission possible.