main

Assignment 1 – choose ONE exercise each from Chapters 2 and 3

Chapter 2: Exercises

  1. Write pseudocode instructions to carry out each of the following computational operations:
  • Determine the area of a triangle given values for the base b and the height h.
  • Compute the interest earned in 1 year given the starting account balance B and the annual interest rate / and assuming simple interest, that is, no compounding. Also determine the final balance at the end of the year.
  • Determine the flying time between two cities given the mileage M between them and the average speed of the airplane.
  1. Using only the sequential operations described in Section 2.2.2, write an algorithm that gets values for the starting account balance B, annual interest rate I, and annual service charge S. Your algorithm should output the amount of interest earned during the year and the final account balance at the end of the year. Assume that interest is compounded monthly and the service charge is deducted once, at the end of the year.
  2. Using only the sequential operations described in Section 2.2.2, write an algorithm that gets four numbers corresponding to scores received on three semester tests and a final examination. Your algorithm should compute and display the average of all four tests, weighting the final exam twice as heavily as a regular test.
  3. Write an algorithm that gets the price for item A plus the quantity purchased. The algorithm prints the total cost, including 6% sales tax.
  4. Write an if/then/else primitive to do each of the following operations:
  • a. Compute and display the value x / y if the value of y is not 0. if y does have the value 0, then display the message Unable to perform the division.
  • b. Compute the area and circumference of a circle given the radius r if the radius is greater than or equal to 1.0; otherwise, you should compute only the circumference.

  1. Modify the algorithm of Exercise 2 to include the annual service charge only if the starting account balance at the beginning of the year is less than $1,000. If it is greater than or equal to $1,000, then there is no annual service charge.

  2. Write an algorithm that uses the loop (1) to input 10 pairs of numbers, where each pair represents the score of a football game with the Computer State University (CSU) score listed first, and (2) for each pair of numbers, determine whether CSU won or lost. After reading in these 10 pairs of values, print out the won/lost/tie record of CSU. In addition, if this record is perfect 10-0, then print out the message Congratulations on your undefeated season.

  3. Modify the test-averaging algorithm of Exercise 3 so that it reads in 15 test scores rather than 4. There are 14 regular tests and a final examination, which counts twice as much as a regular test. Use a loop to input and sume the scores.

  4. Modify the sales computation algorithm of Exercise 4 so that after finishing the computation for one item, it starts on the computation for the next. This iterative process is repeated until the total cost exceeds $1,000.

  5. Write an algorithm that is given your electric meter readings (in kilowatt-hours) at the beginning and end of each month of the year. The algorithm determines your annual cost of electricity on the basis of a charge of 6 cents per kilowatt-hour for the first 1,000 kilowatt-hours of each month and 8 cents per kilowatt-hour beyond 1,000. After printing out your total annual charge, the algorithm also determines whether you used less than 500 kilowatt-hours for the entire year and, if so, prints out a message thank you for conserving electricity.

  6. Develop an algorithm to compute gross pay. The inputs of your algorithm are the hours worked per week and the hourly pay rate. The rule for determining gross pay is to pay the regular pay rate for all hours worked up to 40, time-and-a-half for all hours over 40 up to 54, and double time for all hours over 54. Compute and display the value for gross pay using this rule. After displaying one value, ask the user whether he or she wants to do another computation. Repeat the entire set of operations until the user says no.

  7. Develop a formal argument that “proves” that the sequential search algorithm shown in Figure 2.13 cannot have an infinite loop; that is, prove that it will always stop after a finite number of operations.

  8. Modify the sequential search algorithm of Figure 2.13 so that it works correctively even if the names in the directory are not unique, that is, if the desired name occurs more than once. Your modified algorithm should find every occurrence of NAME in the directory and print out the telephone number corresponding to every match. In addition, after all the numbers have been displayed, your algorithm should print out how many occurrences of NAME were located. For example, if NAME occurred three times, the output of the algorithm might look something like this:

    528-5638
922-7874
488-2020

  9. Use the Find Largest algorithm of Figure 2.14 to help you develop an algorithm to find the median value in a list containing N unique numbers. The median of N numbers is defined as the value in the list in which approximately half the values are larger than it and half the values are smaller than it. For example, consider the following list of seven number:

    25, 50, 83, 44, 91, 20, 55

    The median value is 50 because three values (20, 26, 44) are smaller and three values (55, 83, and 91) are larger. if N is an even value, then the number of values larger than the median will be one greater than the number of values smaller than the median.

  10. With regard to the Find Largest algorithm of Figure 2.14, if the numbers in our list were not unique and therefore the largest number could occur more than once, would the algorithm find the first occurrence? The last occurrence? Every occurrence? Explain precisely how this algorithm would behave when presented with this new condition.

  11. On the sixth line of the Find Largest algorithm of Figure 2.14, there is an instruction that reads, while(i<=n) do. Explain exactly what would happen if we changed that instruction to read as follows:

    • a. while(i>=n) do
    • b. while(i<n) do
    • c. while(i==n) do

  12. On the seventh line of the Find Largest algorithm of Figure 2.14, there is an instruction that reads if A > largest so far then .... Explain exactly what would happen if we changed that instruction to rea as follows:

    • a. if A >= largest so far then...
    • b. if A < largest so far then...

    Looking back at your answers in Exercises 16 and 17, what do they say about the importance of using the correct relational operations (<,==,>,>=,<=,!=) when writing out either an iterative or conditional algorithmic primitive?

  13. Refer to the pattern-matching algorithm in Figure 2.16.

  • a. What is the output of the algorithm as it currently stands if our text is We must band together and handle adversity and we search for and?
  • b. How could we modify the algorithm so that it finds only the complete word and rather than the occurrence of the character sequance a, n and d that is contained within another word, such as band?
  1. Refer to the pattern-matching algorithm in Figure 2.16. Explain how the algorithm would behave if we accidentally ommitted the statement on Line 16 that says Increment k by 1.
  2. Design an algorithm that is given a positive integer N and determines whether N is a prime number, that is, not evenly divisible by any value other than 1 and itself. The output of your algorithm is either the message not prime along with a factor of N, or the message ‘prime’.
  3. Write an algorithm that generates a Caesar cipher - a secret message in which each letter is replaced by the one that is k letters ahead of it in the alphabet, in a circular fashion. For example, if k = 5, then the letter a would be replaced by the letter f, and the letter x would be replaced by the letter c. (We’ll talk more about the Caesar cipher and other encryption algorithms in Chapter 8.) The input to your algorithm is the text to be encoded, ending with the special symbol $, and the value k. (You may assume that, except for the special ending character, the text contains only the 26 letters a...z.) The output of your algorithm is the encoded text.
  4. Design and implement an algorithm that is given as input an integer value `k

    = 0and a list ofknumbersN1,N2,…,Nk. Your algorithm should reverse the order of the numbers in the list. That is, if the original list contained: N1 = 5, N2 = 13, N3 = 8, N4 = 27, N5 = 10 (k = 5)then when your algorithm has completed, the values stored in the list will be:N1 = 10, N2 = 27, N3 = 8, N4 = 13, N5 = 5`.

  5. Design and implement an algorithm that gets as input a list of k integer values N1, N2,...,Nk as well as a special value SUM. Your algorithm must locate a pair of values in the list N that sum to the value SUM. For example, if your list of values is 3, 8, 13, 2, 17, 18, 10 and the value of SUM is 20, then your algorithm would output either the two values (2, 18) or (3, 17). If your algorithm cannot find any pair of values that sum to the value.SUM, then it should print out the message Sorry, there is no such pair of values.
  6. Instead of reading in an entire list N1, N2, ... all at once, some algorithms (depending on the task to be done) can read in only one element at a time and process that single element completely before inputting the next one. This can be a useful technique when the list is very big (e.g., billions of elements) and there might not be enough memory in the computer to store it in its entirety. Wire an algorithm that reads in a sequence of values V >= 0, one at a time, and computes the average of all the numbers. You should stop the computation when you input a value of V = -1. Do not include this negative value in your computations; it is not a piece of data but only a marker to identify the end of the list.
  7. Write an algorithm to read in a sequence of values V >= 0, one at a time, and determine if the list contains at least one adjacent pair of values that are identical. The end of the entire list is marked by the special value V = -1. For example, if you were given the following input: 14, 3, 7, 7, 9, 1, 804, 22, -1. the output of your algorithm should be a Yes because there is at least one pair of adjacent numbers that are equal (the 7s). However, given the following input: 14, 3, 7, 77, 9, 1, 804, 22, -1 the output of your algorithm should be a No because there are no adjacent pairs that are equal. You may assume in your solution that there are at least two numbers in the list.
  8. Modify the algorithm that you developed in Exercise 25 so that if there is a pair of identical adjacent values, your algorithm also outputs, in addition to the phrase Yes, the value of the identical numbers. So, given the first list of numbers shown in Exercise 25, the output of your algorithm would be something like Yes, the numbers 7 and 7 are adjacent to each other in the list.

Chapter 3: Exercises

  1. Use the binary search algorithm to decide whether 35 is in the following list: 3, 6, 7, 9, 12, 14, 18, 21, 22, 31, 43

    def search(target, items)
  return false if items.empty?

  mid = items.size / 2
  return true if items[mid] == target
  return items[mid] > target ? items[0..mid] : items[mid+1..-1]
end

    The comparisons are: