>>    




Homework Assignment

CS 121 (CS1)

Homework 5   Due Friday, February 21, 2014
  1. Function from specs [hc]

    1. spec -- Function specifications. A function specification is a structured description of the behavior of a function, in terms of arguments, return values, etc. For example, the mean function defined by
          def mean(num1, num2):
      	return (num1 + num2)/2
      
      satisfies the following specification:

      mean

      2 arguments: Numbers (integer or floating point)
      Return: A number, the average value of arg1 and arg2.
      This spec describes the function mean() unambiguously.
      • The number of arguments for that function are indicated, and their types are identified.

      • The return value is described in terms of the argument(s).

      • The spec uses arg1 and arg2 to refer to the individual arguments for that function.

      • The type of the return value is also indicated.

      A spec is often accompanied by one or more example calls, such as
          mean(5, 8) --> 6.5
      
      For another example of a spec, consider the function invite() defined by
          def invite(namelist):
              for name in namelist:
                  print("Hi,", name, "-- please come to my party!")
              return    
      
      This function prints output, but has no return value. Here is a spec:

      invite

      One argument: A list of strings, reprenting names
      State change:
      An invitation is printed for each name in arg1.
      Return: None
      Example call:
          invite(['Bob', 'Carol', 'Ted', 'Alice'])
          Hi, Bob -- please come to my party!
          Hi, Carol -- please come to my party!
          Hi, Ted -- please come to my party!
          Hi, Alice -- please come to my party!
      
      • A state change is an effect of a function other than a return value. Input and output (as in invite()) are examples of state changes.

      DO THIS: Write Python3 function definitions for each of the following specs. For each of these problems marked [HC],
      • Write out your function definition on a piece of paper as correctly as possible -- so correct, if possible, that someone else who didn't know Python3 could type it in exactly and produce a correct Python3 computation. If you are uncertain about anything as you write, look it up.

      • Then, enter your work in idle3, and verify that it runs correctly

      (Note: Writing out your work by hand precisely beforehand is the most direct way to master the details of Python3 programming. If there are no errors, your understanding of Python3 is confirmed. If there turns out to be an error in your code, that error indicates exactly what you still need to learn about Python3. Writing out by hand also prepares you for taking quizzes.)

      1. --
      2. drawSquare -- [HC]

        drawSquare

        2 arguments: A turtle and a number representing a length.
        State change:
        The turtle arg1 draws a square with side arg2, turning left for each new side.
        Return: none
        Example call
        import turtle
        win = turtle.Screen()
        sally = turtle.Turtle()
        
        drawSquare(sally, 100)
        

      3. drawColoredSquare -- [HC]

        drawColoredSquare

        3 arguments: A turtle, a number representing a length, and a list of four color names.
        State change:
        The turtle arg1 draws a square with side arg2, turning left for each new side, and drawing with each of the four colors in arg3 in order.
        Return: none
        Example call
            import turtle
            win = turtle.Screen()
            sally = turtle.Turtle()
            
            drawColoredSquare(sally, 100, ["red", "black", "blue", "green"])
        

        Hint:

        • Use a loop to process each color in order, much as the invite() function processes each name in order. Instead of printing an invitation for each name, this color loop will set a drawing color, draw one side of the desired square, then turn left to prepare for drawing the next side.

          Thus, there will be multiple Python3 turtle calls that are indented at the same level in this for loop, instead of the single print() call found in the definition of invite().


      4. areaCircle -- [HC] Area of a circle. In Mathematics, the area of a circle with radius r is .

        Use this formula to implement the following Python3 function.

        area

        One argument: A non-negative float value, representing the radius of a circle
        Return: A non-negative float value, the area of a circle of radius arg1
        Example call:
            import math
            area(3) --> 28.274333882308138
        
        Hint:
        • The value π is available as math.pi in the math library.


      5. moInterest -- [HC] Monthly interest. In Economics, the amount of monthly interest owed on a loan depends on the principal (or amount of money still owed on the loan) and the interest rate. The interest rate r is often expressed as a percentage per year. Thus, the formula for a monthly interest charge on a loan with current principal P is

        Use this formula to implement the following Python3 function.

        moInterest

        2 arguments: Non-negative float numbers, a principal amount (of money) and an interest rate (expressed in percent per year)
        Return: A non-negative float number, the amount of one month's interest on a loan with current principal arg1 at interest rate arg2. .
        Example:
            moInterest(10000, 6) --> 50.0
        


  2. _____
  3. Accumulators [hc]

    1. acc -- Programming with accumulators. Recall that a variable is a named location in main memory. For example, the assignment
          x = 7
      
      stores the value 7 in a location in main memory named x. We can visualize the results of this assignment in a diagram as follows:

      An accumulator is a variable that is used to build up an answer over time. For example, consider the following modified code for invite()

          def invite(namelist):
              count = 0
      	# invar: count holds the number of invitations printed so far
              for name in namelist:
                  print("Hi,", name, "-- please come to my party!")
                  count = count + 1
              return count
      
      Example call
          invite(['Bob', 'Carol', 'Ted', 'Alice']) --> 4
          Hi, Bob -- please come to my party!
          Hi, Carol -- please come to my party!
          Hi, Ted -- please come to my party!
          Hi, Alice -- please come to my party!
      
      Note: The comment which begins with # invar: count... is called an invariant assertion (or more simply, an invariant). It is intended for a human reader, not a Python3 processor (which ignores that comment). An invariant describes the state of a computation at the beginning and end of each iteration of a loop.

      This function definition prints the same four invitations as the original definition of invite(), but this definition returns 4 -- the number of invitations printed -- instead of returning no value. This new definition satisfies the following modified spec.

      invite   (modified)

      One argument: A list of strings, representing names
      State change:
      An invitation is printed for each name in arg1.
      Return: A non-negative integer, the number of invitations printed

      Here's a description of how this function uses a variable count to compute the desired return value.

      1. Just after the assignment count = 0, the memory location count holds the value 0:

      2. Just after the first invitation has been printed (for 'Bob'), count holds the value 1.

        Note: the expression

        count = count + 1
        would be nonsense if it were Mathematics, but in computing, it (a) computes the value of count+1, then (b) assigns that value to count. In terms of problem solving strategies, this is the expression that updates the accumulator.

      3. Just after the second invitation has been printed (for 'Carol', the accumulator variable count is updated to hold 2.

      4. After the third invitation has been printed, count holds 3. Notice how the invariant remains true at the beginning and end of each repetition: it always holds the number of invititations printed at those points in the computation.

      5. After printing the fourth invitation (for 'Alice'), count holds 4.

      Finally, when there are no more names to print, the for loop ends, and Python3 proceeds to execute the next statement after that loop (namely, the return statement). At the end of the loop, we know from the logic behind the invariant that count holds the number of invitations that were printed. That's the return value demanded by the spec, so we return the value count.

      DO THIS: Write Python3 function definitions for each of the following specs, using accumulator variables within those definitions to compute the desired return values. As before, write out precise and correct code for each of these [HC] problems on paper first, then test each on the computer. (It's ideal to write out an answer to one problem, then test that code using Python3, then write out an answer to the next problem, etc., so that any errors you catch on one problem can be avoided in the next.)


      1. --
      2. sum -- [HC] Adding vote totals. Many disciplines require operations on data. For example, a political scientist may need to tally vote totals for various regions from raw data per precinct or county; likewise, a historian may need to compute sums of the same kind, except for historical elections.

        Write a function addVotes satisfying the following spec.

        addVotes

        One argument: A list of non-negative integers, representing vote totals from local units.
        Return: A non-negative integer, the sum of the numbers in the list arg1
        Example call
            addVotes([729, 1183, 65, 1929, 505,4417]) --> 8828
        
        Notes:
        • Of course, the same function could presumably be used for adding the elements of any list of float or integer numbers, not just vote totals.

        • Include an invariant that fits this computation, and use a descriptive accumulator variable name (for example, avoid count).


      3. listMean -- [HC] Mean of survey results. Surveys are a widely used strategy for conducting research in the social sciences, Medicine, and other disciplines. Also, electronic ratings contributed by users are heavily used in web services businesses to convey aggregate user opinions about quality and value. One of the quickest and most useful statistics for assessing survey results is the mean score, whether assessing the prevalence of cancer in a certain population or deciding how many stars to display next to a movie or book.

        Write a function that computes the mean of a list of survey ratings.

        meanRating

        One argument: A list of non-negative integers, representing ratings in a survey.
        Return: A float number, the mean (average) value for that list arg1.
        Example call
            meanRating([4, 1, 3, 3, 2, 4, 5, 4, 5]) --> 3.4444444
        
        Notes:
        • You will need two accumulators in order to compute the mean: one to keep track of the count, and the other to accumulate the sum of ratings.

        • Include an invariant that describes both accumulators. For example, if your accumulator variables are named count and sum, your invariant might have the form "count holds ..., and sum holds .... You can create a two-line comment with # as the first character of each line.

        • Once again, your function will probably work with any list of numbers, whether integers, floats, negative, etc., so it could actually be applied to more than just survey results.


      4. concat -- [HC] Joining words back together. In linguistic analysis of a text being studied, a linguist or humanist might create a list of all the words in that text, perform some operation on those words, then reassemble the results back together. For example, a text whose words are tagged with their parts of speech (verb, noun, adjective, etc.) can be analyzed for language-usage patterns that might help distinguish one author or speaker from another, or one literary era from another.

        For example, the character Yoda from the Star Wars films has a distinctive speaking style that involves reorderings of words according to their parts of speech. Whereas an English speaker might say

            I was at the store, planning to buy a light saber.
        Yoda would say
            At the store, was I, to buy a light saber planning.  Hmmmmmm.
        according to the site
        http://www.yodaspeak.co.uk. The paper on which the site is based describes "Yodish" in terms of parts-of-speech analysis. Here is a version of the original English sentence including a simple form of part-of-speech tags:
            I:pronoun  was:verb  at:prep  the:article  store:noun,  
            planning:verb  to:prep  buy:verb  a:article  light:adj  saber:noun.

        But once the words in a list are tagged with parts of speech, how can we construct a single string that contains all those tagged words in order?

        DO THIS: Write a function to perform that reconstruction, satisfying the following spec.

        joinWords

        One argument: A list of strings, representing words tagged with their parts of speech.
        Return: A single string, consisting of all the tagged words in arg1 in order, each followed by a space character.
        Example call:
          joinWords(["I:pronoun", "was:verb", "at:prep", "the:article", "store:noun."])
                  --> "I:pronoun was:verb at:prep the:article store:noun. "
        
        Hints:
        • Use an accumulator that begins with an empty string "".

          Choose a descriptive name for your accumulator variable, and try writing an invariant for it sooner rather than later. These may be especially helpful for solving this problem.

        • For each new tagged word, append that word and a space to your accumulator. The + operator for strings will allow you to produce a single combined string from two other strings.

          +   (operator)

          2 arguments: Any two strings
          Return: A single string that consists of all characters in the string arg1 followed by the characters in arg2
          Example call:
              "hello" + "world"  -->  "helloworld"
          
          This string operator + has a different spec than the numerical addition operator +, which adds two numbers and returns the sum. The string + is called the concatenation operator.
        • To append a space to a string, you can use the concatenation operator + with a string " " .

        • As in the other examples, this function could be used to join together any list of strings, adding spaces at the end of each string. The strings don't have to be tagged words from a text.