15110 SUMMER SESSION TWO - 2014

Programming Assignment 7 - due Wednesday, July 23 at 9:00AM

Note: You are responsible for protecting your solutions to these problems from being seen by other students either physically (e.g., by looking over your shoulder) or electronically. (More information can be found in the instructions for Programming Assignment 2.)

Part I

You will create a Python source file containing a Python function(s) implementing each of the problems described below. In implementing these functions, you may not use and built-in data conversion functions that convert between numbers and strings directly. You may, however, use subscripting with [ ] to access a character of a string, and the functions ord (to convert from a character to its ASCII value) and chr (to convert from an ASCII value to the corresponding character).

  1. [2 points] A positive integer \(n\) can be converted to a string of 1's and 0's holding that numbers binary represntation using the following algorithm:

    1. Let s be an empty string.
    2. While \(n > 0\) do the following:
      1. Let ch be "0" if \(n\) is even and "1" if \(n\) is odd.
      2. Add ch to the beginning of s. (Use the + concatenation operator.)
      3. Divide \(n\) by 2.
    3. Return s.

    Write a function int_to_bin_string(n) (in int_to_bin_string.py) which takes a non-negative integer n and returns the a string of 1's and 0's

    Note: You will have to figure out how to adjust the algorithm to deal with the case where parameter n = 0.

    Example:

    >python3 -i int_to_bin_string.py
    >>> int_to_bin_string(127)
    '1111111'
    >>> int_to_bin_string(4)
    '100'
    >>> int_to_bin_string(3)
    '11'
    >>> int_to_bin_string(0)
    '0'
    
  2. [2 points] The value of a number represented with a binary string s can be found by iterating over the indices of the string and, for each index i, updating value to be the value of the binary number represented by s[0:i+1]. An example is shown in the table below:

    sis[i]value
    "11001"0"1"1
    "11001"1"1"3
    "11001"2"0"6
    "11001"3"0"12
    "11001"4"1"25

    Write a function bin_string_to_int(s) (in bin_string_to_int.py) that takes a non-empty string of 1's and 0's and converts it into the corresponding integer value.

    Example:

    >python3 -i bin_string_to_int.py
    >>> bin_string_to_int("0")
    0
    >>> bin_string_to_int("1")
    1
    >>> bin_string_to_int("101")
    5
    >>> bin_string_to_int("0011101110")
    238
    
    HINT: For each character in the string (from left to right), if it is a "1", double the current value and add 1. If it is a "0", just double the current value.
  3. [3 points]

    1. Write a function hex_string_to_bin_string(hex_string) (in hex_string_to_bin_string.py) that converts a non-empty string containing the hexadecimal representation of a number (using the characters "0"-"9" and "A"-"F" as digits) into a string containing that number's binary representation.

      Example:

      > python3 -i hex_string_to_bin_string.py
      >>> hex_string_to_bin_string("2")
      '0010'
      >>> hex_string_to_bin_string("A")
      '1010'
      >>> hex_string_to_bin_string("2A")
      '00101010'
      >>> hex_string_to_bin_string("2AC")
      '001010101100'
      
    2. Write a function hex_string_to_int(s) (in hex_string_to_int.py) that converts a non-empty string s containing the hexadecimal representation of a number and converts it into the corresponding integer value. This function should be implemented by making calls to the bin_string_to_int and hex_string_to_bin_string functions that you defined above. Include copies of these functions in the hex_string_to_int.py file so you can load all of these functions together in python3.

      Example:

      > python3 -i hex_string_to_int.py
      >>> hex_string_to_int("0")
      0
      >>> hex_string_to_int("4")
      4
      >>> hex_string_to_int("D")
      13
      >>> hex_string_to_int("2A7")
      679
      
  4. [3 points] All functions for this part should be in a file called characters.py.

    For this problem you will convert letters between upper and lower case. This is easy to do, because in the ASCII encoding, the code for each lower-case letter is obtained by adding 32 to the code for the corresponding upper-case letter. But you can't do arithmetic with characters in Python. Instead, you must get the character's code using the ord function, do the arithmetic, and convert the result back to a character using the chr function.

    Example:

    >>> ord('A')
    65
    >>> ord('a')
    97
    >>> ord('Z')
    90
    >>> ord('z')
    122
    >>> chr(65)
    'A'
    >>> chr(97)
    'a'
    >>> chr(90)
    'Z'
    >>> chr(122)
    'z'
    

    You are not allowed to use any built-in functions that convert between upper and lower case, or any that indicate whether a character is upper or lower case. Instead, use the character codes and numeric operations.

    1. Write a function to_upper(c) that takes a character stored in the parameter c and returns the upper-case version of this character. If the character is not a lower-case letter, just return it unchanged.

      Example:

      >>> to_upper('a')
      'A'
      >>> to_upper('m')
      'M'
      >>> to_upper('M')
      'M'
      >>> to_upper('*')
      '*'
      

    2. Write a function to_lower(c) that takes a character stored in the parameter c and returns the lower-case version of this character. If the character is not an upper-case letter, just return it unchanged.

      Example:

      >>> to_lower('A')
      'a'
      >>> to_lower('M')
      'm'
      >>> to_lower('m')
      'm'
      >>> to_lower('*')
      '*'
      

    3. [HARDER] Write a function called capitalize(s). The parameter is a string s and the function returns another string that is the same as s except that all words are capitalized. To capitalize a word means to convert its first letter to upper case and all the other letters to lower case. A word is any sequence of letters (not including spaces). You may assume that the string s contains only letters and spaces. You must use the functions to_upper and to_lower that you already defined.

      Example:

      >>> capitalize("the quick brown fox")
      'The Quick Brown Fox'
      >>> s = "PYTHON IS A SNAKE"
      >>> capitalize(s)
      'Python Is A Snake'
      >>> s
      'PYTHON IS A SNAKE'
      >>> capitalize("  abc   ")
      '  Abc   '
      >>> capitalize("abc")
      'Abc'
      

      HINT:

      Loop over each character of the string s. If it can be the start of a word, make it upper case. Otherwise, make the character lower case (this will not affect spaces). The big question is: how do you know when you're at the start of a word?

Submission

You should have a pa7 directory, containing:

  1. int_to_bin_string.py
  2. bin_string_to_int.py
  3. hex_string_to_bin_string.py
  4. hex_string_to_int.py
  5. characters.py

Zip up your directory and upload it using the autolab system.