Due Thursday July 12 at 6 p.m.
Your code will be graded on both its correctness and its elegence. So please take the time to try to come up with short and easy to understand solutions. Please read the programming guides on the Assignments page.
Please consult the directory ~hsc/classes/270/examples on CDF. Some of the examples may prove useful in solving these problems.
This problem is an introduction to abstract data types. For this problem, you will create a the data type queue which will hold integers.
The queue is to support the following functions:
Each queue function takes an error_flag as an argument which is set if there is an error. For example, the queue is full or the queue is empty.
You are to write a routine which accepts use input and manipulates the queue. Call this program use_queue.c. The acceptable user inputs are "insert" followed by a value, "remove", and "peek". The response to "insert" is either "Ok" or "Queue is full." The response to "peek" and "remove" is either a value or "Queue is empty."
Here is a sample execution:
eddie% use_queue insert 4 Ok. insert 5 Ok. peek 4 remove 4 remove 5 remove Queue is empty.
First implement the queue as a circular array of size 10. This is simply an array which you treat as if it were a ring. Thus, if the last element added to the queue goes into array[n-1], then the next element added will go into array[0]. Thus is probably easiest if you maintain three values, head, tail, and empty. head will store the index of the first element of the queue, tail will store the next free index (the index immediately after the last element of the queue), and empty will indicate whether the queue is empty. tail = head only if the queue is empty or full. If tail = head as a result of incrementing head (because we removed an element), then empty should be set to true. If tail = head from incrementing tail (because we added a new element), then empty should be false. Call this implementation queue_array.c.
Next, you are to implement the queue as a linked list. Call this implementation queue_ll.c.
Submit the following files electronically: use_queue.c, queue.h, queue_array.c, queue_ll.c.
Let us define the game of pick-up sticks between two players as follows. There is a pile of N sticks and the players take turns removing sticks from the pile. The player to take the last stick wins the game.
Obviously, if the players could take any number of sticks, the game is boring. Therefore, the number of sticks that a player may take in a single turn will be restricted by a set of legal moves. To make the game challenging, the set and value of the legal moves may change from game to game. For example, if the set of legal moves is {1, 4}, then at each turn, a player may take either 1 stick or 4 sticks.
Many such games have the property that one of the players has a guaranteed win. For example, if the player moving first has a guaranteed win, then no matter how well the second player plays, the second player can not win unless the first player makes a mistake.
For this problem, you are to input the parameters of the game and determine which player, if any, has a guaranteed win. If the player moving first has the guaranteed win, you should output "The player going first has a guaranteed win." followed by a second line which indicates what the first move of the player should be: "The first player should take n sticks."
If the player moving second has the guaranteed win, you should print, "The player going second has a guaranteed win." If neiter player has a guaranteed win, print "No player has a guaranteed win".
The input is a sequence of integers. The first integer is the number of sticks, the second integer is the number of legal moves, and then following is a list of the legal moves. The following sample input if for the game with 8 sticks, 2 possible moves and the moves are 1 or 4 (a player may take 1 or 4 sticks).
Sample Input
8 2 1 4
Sample Output
The player going first has a guaranteed win. The first player should take 1 sticks.
You may add prompts to the input if you wish, but it is not required.
Electronically submit the program in a file called sticks.c.
The program will read in a database of flight info. The program will then receive a travel request from the user consisting of the departure city, the arrival city, the earliest desired departure time, and the latest desired arrival time. The program will find the cheapest flight and output the itinerary.
Here is a program, flights.c , that finds the cheapest nonstop flight. You are to modify it so that it will find the cheapest fare if the traveller may change planes.
If a passenger is going to change planes, you must leave at least one hour between when the first plane arrives and the second one departs. Also, assume that all travel occurs on the same day.
Sample execution:
eddie% flights flight_data_small Welcome the the travel agent Legal cities are: TOR MON HAL QUE Enter the departure city or 'quit' >>> HAL Enter the arrival city >>> QUE Enter the earliest departure time [0 - 23] >>> 12 Enter the latest arrival time [1 - 24] >>> 18 Leg 1: Flight #667: Departs HAL at 17:00, Arrives QUE at 18:00 Cost: $400.00 Enter the departure city or 'quit' >>> TOR Enter the arrival city >>> HAL Enter the earliest departure time [0 - 23] >>> 6 Enter the latest arrival time [1 - 24] >>> 15 Leg 1: Flight #334: Departs TOR at 8:00, Arrives QUE at 11:00 Leg 2: Flight #445: Departs QUE at 12:00, Arrives HAL at 13:00 Cost: $500.00 Enter the departure city or 'quit' >>> quit
Here are two flight databases: flight_data_small, flight_data_large.
This problem will only be graded on correctness.
A note on extra credit: Extra credit is worth no points. Instead, it will be taken into account when calculating your final grade. Please be certain that you first complete the other problems on this assignment before working on the extra credit.