CS 211
Data Structures

Stonehill College                          CS 211

barmove.gif (33725 bytes)
Assignment 4
Due Oct23, 2007

1. prog4a.cpp


In a  priority queue a priority is associated with each data item so that when an item is removed from the queue the item with the highest priority is removed. (If two items have equal priority, they can be stored in either order.)

For example, suppose q is a priority queue which stores names.  Each name comes with a priority. The highest priority is 1.  Now consider the following operations:

q.insert("Dopey",3);

q,insert("Sleepy",1);

q.insert("Doc", 2);

q.insert("Happy",1);

q.insert("Grumpy",3);    

q.insert("Sneezy",4);    

q.insert("Bashful",3);

cout<<q.remove()<<" ";

cout<<q.remove()<<" ";

cout<<q.remove()<<" ";

cout<<q.remove()<<" ";

cout<<q.remove()<<" ";

cout<<q.remove()<<" ";

cout<<q.remove()<<" ";      

The output might be:
Happy Sleepy Doc Bashful Grumpy Dopey Sneezy

It could also be

Sleepy Happy Doc Dopey Grumpy Bashful Sneezy

since items with equal priority are considered equal in THIS definition of a priority queue.
Priority queues are often used in computer systems.  For example, in a multi-user envirnment, a priorit queue might be set up for the printer-- most important jobs get highest priority.

The Basic operations on a priority queue are:

1. bool empty()

2. void clear()

3. void insert(const T & x,int p)  -- where x is data and p is a priority

4. T remove()  -- returns item with hoighest priority

5. int size()


There are several ways to implement a priority queue .  (For now) we will look at two possible not-so-efficient implementations.  Later, we will study a more efficient implementation.  

But for now: 

1.The priority queue might be implemented as an ordered linked list.  That is items are ordered   by priority (1,2,3...). 

2. The priority can be stored as a  list of (standard) queues.  There would be one ordinary queue for each priority. 

Your assignment is to implement a class PriorityQueue using both implementations.
(You might try inheritance for the first implementation -- but remenber only 4 operations
are allowed. ( How might you "disallow" some of the other list operations?)

To demonstrate your class consider the following senerio:

Jobs entering a  computer system each have an ID number and a priority. (Highest priority is 1.)
As jobs arrive, they are kept placed in a priority queue.  Write a program which presents the user
with a menu.  The items on the menu are:

I : insert into the queue  

R : remove item from queue and prints its ID and priority

E : prints "Empty" or "Not Empty"

S : prints the size of the queue

C : clears the queue

Q : quit

You should write two programs : one using each implementation. Call the programs
Prog4A.cpp and Prog4B.cpp.

 

Here's a picture for part 2.   Note the artistic skill and talent.

priorityq.JPG (190520 bytes)

 

2. prog4b.cpp

For this problem, here is an obvious data structure.   Think about the problem. Think about the appropriate data structure. Work the examples by hand. Devise an algorithm.......then think about coding.

Here is a markup language similar to HTML. Let’s call it JHTML (J for junior).

This markup language is used to encode messages, however. In other words, we are looking at a form of encription.

A string in JHTML is a sequence of characters with embedded markup tags. Each tag is a string of the form "<tag>sub-string</tag>"; if the sub-string between the tag delimiters is nested to include other tags, then it is a complex tag. The twenty-nine different characters that are allowed in a JHTML string (aside from the tags) are: <SPACE>, 'A' - 'Z', <COMMA> (','), and <PERIOD> ('.'). Note that tags use lower case characters, and '<', '>', and '/'. These characters will never be part of the final encoded representation of the JHTML string.

 

Each tag performs an action on its sub-string as shown in the following table:

 

Tag Action
<+>...</+> Set each character c between the tags to be successor(c)
<->...</-> Set each character c between the tags to be predecessor(c)
<s>...</s> Sort the characters between the tags in ascending order
<r>...</r> Reverse the sequence of characters between the tags

 

 

The functions predecessor (c) and successor (c) are defined below for the valid characters in KJML. For example, the successor of <COMMA> (',') is ('.').

 

Function

<SPACE>

'A'

'B'

'C'

...

'X'

'Y'

'Z'

','

'.'
predecessor '.' <SPACE> 'A' 'B' ... 'W' 'X' 'Y' 'Z' ','
successor 'A' 'B' 'C' 'D' ... 'Y' 'Z' ',' '.' <SPACE>

The coded representation of a simple tag is the sequence of characters resulting from processing its action on its sub-string. A Complex Tag must first have all of its nested tags recursively replaced with their coded representation before the tag processes its actions. When given the 2nd sample input, for example, your program should first replace "<->IS A</->" with the coded representation "HR. " then it can compute the outer tag "<r>THIS HR. TEST</r>", resulting in the final output as shown below.

Input

 

The input will consist of a valid JHTML string of n (n <= 200) characters.

Output

 

Your program should output on a single line the encoded representation of that string

Sample Input Sample Output
<+>TESTING</+> UFTUJOH
<r>THIS <->IS A</-> TEST</r> TSET .RH SIHT
<+>ALL FOR ONE,<+> AND ONE FOR<r>ALL</r></+></+> BMMAGPSAPOF.BCPFBQPGBHQTNNC
<r>MASSA<s>CHUSETT</s><+>S</+></r> TUTTSHECASSAM

This problem was given  in a recent programming contest.

3. prog4c.cpp

The four color theorem states that any map in a plane can be colored using at most four colors so that regions with a common border (other than a single point) do not share the same color.

The  four color problem ( that a map can be colored using just 4 colors) can be traced back to 1852.  However, the theorem was not proven until 1976.  You can read about the four color theorem and its history at

http://www.math.gatech.edu/~thomas/FC/fourcolor.html

The problem at hand is to color the map of the US ( as represented by its adjacency matrix) using just four colors, say red, green, yellow, and blue, just like the map on the above website, although not necessarily the same color assignments:


You should use a recursive backtracking algorithm.

Here is a  table showing which state borders another.  For example, if there are  just four states A,B,C,D :

The table or matrix would be:

  A B C D
A 0 1 0 1
B 1 0 1 0
C 0 1 0 1
D 1 0 1 0

This matrix can be interpreted as  "A borders on B and D  ( look for the 1's);  B borders on A and C;  C borders on B and D; D borders on A and C."

This array is called the Adjacency Matrix for the map.

 

Your output should be similar to

Maine    red
New Hampshire    green
Vermont    blue

The order of the states is not important.