*** Problem 1 *** ------------------- Write a program that inputs two lines, each with less than or equal to 80 characters. If the two lines are equivalent, the program is to output the message "These lines are equivalent." If they are not equivalent, the program is to output the message "These lines are not equivalent." In order to be equivalent, the lines must meet two criteria: (a) They must have the same number of characters, including trailing spaces. (b) They must have an equivalent sequence of characters. Upper and lower case versions of the same alpha character are considered to be equivalent. Other characters are equivalent only to themselves. Example: ------- line1: Utah will make the final four! line2: BYU will be lucky to win the first round. output: These lines are not equivalent. Example: ------- line1: Utah will make the final four! line2: Utah will make the FINAL FOUR! output: These lines are equivalent. *** Problem 2 *** ------------------- Write a program that inputs an integer N. If N is less than or equal to zero, the program is to end. If N is greater than zero, it is to output Pascal's triangle of depth N. Pascal's triangle of depth N is a sequence of N lists of integers. The first list consists only of the integer 1. The first and last integers in the other lists are 1's. The integers between the first and last are computed from the previous list; each one is the sum of the integer immediately above it and the one above and to the left. For example, if the previous list is 1 3 3 1 the current list would be 1 4 6 4 1 since 4 = 1+3, 6 = 3+3, and 4 = 3+1. Your program must output each list on a single line, and it must work for values of N as large as 20. At least one space must separate the integers in a list, but lists are not required to be lined up with one another. Example: ------- input: 7 output: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 *** Problem 3 *** ------------------- Mastermind is a game in which one player sets up a line of colored pegs, and the second player tries to figure out the color of those pegs. The technique used is as follows: (a) The second player guesses the color of all of the pegs. (b) The first player responds by giving Black and White tokens to his opponent, based upon the correctness of the guess. A Black token is given for each peg that has both the correct color and the correct position in the line. A White token is given for each peg that has the correct color, but is in the wrong position in the line. (c) The process is repeated until the guess receives the maximum number of Black tokens. Write a program that calculates the value of a guess in this game. Your program is first to input four characters that represent the actual sequence. It is then to input four characters that represent a guess. The output is to be the number of Black and White tokens awarded to the guess. Possible colors and the character used to represent them in the input to your program are as follows: R = Red, Y = Yellow, G = Green, B = Blue, O = Orange, T = Tan Example: ------- Correct: RRRR Guess: RYBB Output: Black: 1 White: 0 Example: ------- Correct: RYRY Guess: YRRY Output: Black: 2 White: 2 Example: ------- Correct: TOBY Guess: YBOT Output: Black: 0 White: 4 Example: ------- Correct: TOBY Guess: TOBY Output: Black: 4 White: 0 *** Problem 4 *** ------------------- Fax machines represent pictures as a series of dots (or pixels), each of which may be stored as a single bit. If the pixel is black, the the bit is 1; if the pixel is white, the bit is 0. In order to send the picture to another machine, these 1's and 0's are transmitted across the wire. In order to send information over a network as quickly as possible, it is important that it be represented using as few bits as possible. The process of reducing the number of bits required to represent the same amount of information is called "data compression." A common method of data compression is called "run length encoding" or RLE. This works particularly well for data that consists of mostly 0's with a few interspersed 1's, which is common for pictorial information. You are to write a program that implements the RLE data compression algorithm. Your program is to accept as input a line of 0's and 1's with no spaces between them. It is to compress that input data using the RLE algorithm and output the new line of 0's and 1's. The input line will be no longer than 50 characters. The RLE algorithm is as follows: (a) The input data is first translated into a sequence of integers that specify the number of 0's that precede each 1 in the line, as well as the number of 0's at the end of the line. For example, the input 0001000000001101000000000000001 produces the sequence 3 8 0 1 14 0 since there are three leading 0's followed by a 1, then eight 0's followed by a 1, then zero 0's followed by a 1, then one 0 followed by a 1, then fourteen 0's followed by a 1, then zero trailing 0's. (b) Each of these integers is then translated into a list of one or more numbers between 0 and 7. If the integer is less than 7, it is represented by itself. If the integer is 7 or greater, it is broken up into a group of 7's followed by an integer less than 7; the sum of the numbers in the group is the value of the integer. For example, the above sequence turns into 3 7,1 0 1 7,7,0 0 since 8 = 7+1 and 14 = 7+7+0. Note that the algorithm always converts an integer that is a multiple of 7 into some number of 7's followed by a 0. (c) Finally, each of the numbers in this list is converted to its 3-bit binary equivalent, which is the compressed data. For our example, the data that is actually transmitted would be 011 111 001 000 001 111 111 000 000 (3) (7) (1) (0) (1) (7) (7) (0) (0) (over) Example: ------- Input: 0001000000001101000000000000001 Output: 011111001000001111111000000 ******************************************************************************* Just in case you haven't learned about binary numbers, here is a conversion chart for the decimal numbers 0 through 7: 0 - 000 2 - 010 4 - 100 6 - 110 1 - 001 3 - 011 5 - 101 7 - 111 *** Problem 5 *** ------------------- Selecting the least expensive way to fly from one place to another can be a complex task. The problem is that air fares are not necessarily proportional to the distance flown or to the number of stops. The cost of a flight may depend more upon the amount of competition than any other factor. In order to find the best route, it is necessary to check many possible alternatives. You are to write a program that selects the least expensive route for an airplane trip. Input to the program will be a list of all available flights between pairs of cities, along with the cost of each. Output is to be the total cost and a description of the chosen route. The input will have the following format: NumberOfCities StartCity EndCity FromCity ToCity Cost FromCity ToCity Cost FromCity ToCity Cost . . 0 Cities are numbered from 1 to NumberOfCities, and NumberOfCities will not exceed 6. Only the listed flights are available. (Note that a flight from city A to city B does not imply that there is a flight from B to A. Also, the cost of a flight from A to B may not be the same as one from B to A.) Your program is to print out the least expensive route from StartCity to EndCity as well as the total cost. You may assume that a path exists from the start city to the end city. Example: ------- input: 5 1 3 1 2 20 1 3 100 1 5 10 2 3 20 4 3 10 5 1 10 5 4 10 0 output: The minimum cost is: 30 The least expensive route is: 1 5 4 3