CS 211
Data Structures

Stonehill College                       CS 211


Assignment 6
DUE LAST DAY OF CLASS

1.prog6a

To solve the following problem you MUST make
a simple graph class.  

Question of Hierarchy ( from a recent programming contest)

King John is bored. To cheer up, he decides to sponsor a festival for all the nobles in the land. As you know, the importance of a noble is directly proportional to the size of his estate. At the festival, the nobles will be introduced in order of importance. Unfortunately, there is not enough time to sponsor a full survey of all estates in the kingdom, and the King is forced to use ancient lists as his guide. These lists compare the relative size of pairs of estates (whether one estate is greater or smaller than another). He does not wish to offend any noble so he seeks to determine a unique order of nobles from least important (the one with the smallest estate) to the most important (the one with the largest estate). If there is no such ordering, King John must know immediately. There are a total of twenty-six nobles, and since each of their names starts with a different letter, the King’s list simply contains orderings of the form E₁ ORDER E₂.

The input will consist of a positive integer n (n = 20) followed by n lines each of which contains 5 characters. Each line is of the form "E₁ ORDER E₂" where E₁ and E₂ are single letters from 'A' - 'Z' and ORDER is either '<' (when E₁ is smaller than E₂) or '>' (if the opposite is true). You can assume that each ordering is valid (i.e., no estate appears twice in the same ordering and ORDER is either '<' or '>') and that there are no contradictions in the set of orderings. The input should come from cin.

The ordering of estates (with no spaces) should appear on a single line in order from smallest to highest. If multiple linear orderings are possible, your program should output on a single line the words "NO ORDER".

2. prog6b

Write a program to play the following game:

 The initial  board is an N x N  grid of  random integers in the range 1..N² .  One position is designated as the initial current position.  Two players alternate in turns.  At each turn a player must select a grid element in the current row or column.  The value of the selected position is added to the player’s score, and that position becomes the current position  and cannot be selected again.  Players alternate until all grid elements in the current row and column are already selected, at which point the game ends and the player with the highest score wins.

Notes:

• You may assume the  maximum board size is 10 x 10 and the starting position is [0,0].  Your program should prompt the player for the actual board size, N.
  

• You should fill the board with random integers in the range 1..N², Duplicates are allowed.
  

• Your program should be  an interactive game between a human player and the computer. Of course, the computer should play intelligently.
  

•  Prompt the user for the depth of the gametree game tree
  

• Assume that the computer is player Max. 
  

• You have to develop your own evaluation function. There is not necessarily one best function.  But obviously, some functions are better than others.   You should include with your code a description of you evaluation function.  Explain why you chose your particular function. This should be a rather long comment
  

• The human player should have the option of going first or second.
  

• At each turn your program should print out the current board configuration. When the computer takes a turn, inform the opponent of the chosen move.  
  

• Use the recursive algorithm that we looked at in class