15110 Spring 2012 [Touretzky/Kaynar]

Programming Assignment 7 - due Tuesday, October 16

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

For Part I of this assignment, you will create a Ruby source file containing a ruby function(s) implementing each of the problems described below. In implementing these functions, you may not use to_s, to_i or any built-in Ruby function that converts between numbers and strings. You may, however, use subscripting with [ ] to convert a character in a string to its ASCII value and use chr to convert an integer to the corresponding character with that ASCII value.

  1. [2 points] We saw how to convert non-negative decimal integers to binary integers in class. We can implement that conversion in Ruby by using the following algorithm that takes an integer \(n\) as input and returns a string of 1's and 0's holding the binary representation of \(n\).

    1. If \(n\) is zero return "0"
    2. Let s be an empty string.
    3. 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.
      3. Divide \(n\) by 2.
    4. Return s.

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

    Example:

    >> convert_to_bin(255)
    => "11111111"
    >> convert_to_bin(1024)
    => "10000000000"
    >> convert_to_bin(4)
    => "100"
    
  2. [2 points] The value of a binary number represented as a string s can be found by iterating over the indices of the string and, for each index i, updating value to so it reflects the value of the substring represented by s[0..i]. An example is shown in the table below:

    sis[i]value
    "10101"0"1"1
    "10101"1"0"2 = 2*1 + 0
    "10101"2"1"5 = 2*2 + 1
    "10101"3"0"10 = 2*5 + 0
    "10101"4"1"21 = 2*10 + 1

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

    Example:

    >> convert_to_int("0")
    => 0
    >> convert_to_int("1")
    => 1
    >> convert_to_int("101")
    => 5
    >> convert_to_int("0011101110")
    => 238
    

    Hint: Remember that if s is a string, s[0] is the ASCII value of the character at position 0 in s. If s is "Hello", then s[0] is not "H", it's 72, and s[0].chr is "H".

    Another hint: In the binary system, adding a digit \(k\) to the right of a given binary number \(n\) means multiplying \(n\) by 2 and adding \(k\) to the result. For example, the decimal value of the binary number 1112 is 7. This can be obtained from the binary number 112 by multiplying the value of the binary number 112 by 2 and adding 1 to the result.

  3. [3 points]

    1. Write a function convert_hex_to_bin(hex_string) (in convert_hex_to_bin.rb) 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. You can assume that the function is always called with a well-formed hexadecimal number.

      Hint: A hexadecimal number can be converted to a binary number by converting each hexadecimal digit in order. For example, the hexadecimal number 9AF can be converted by converting 9, A, and F to binary strings and concatenating them in the given order.

      Example:

      >> convert_hex_to_bin("4")
      => "0100"
      >> convert_hex_to_bin("D")
      => "1101"
      >> convert_hex_to_bin("4D")
      => "01001101"
      >> convert_hex_to_bin("2DA")
      => "001011011010"
      
    2. Write a function convert_hex_to_int(hex_string) (in convert_hex_to_int.rb) that converts a non-empty string 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 convert_to_int and convert_hex_to_bin functions that you defined above. You can assume that the function is always called with a well-formed hexadecimal number.

      Example:

      >> load "convert_to_int.rb"
      => true
      >> load "convert_hex_to_bin.rb"
      => true
      >> load "convert_hex_to_int.rb"
      => true
      >> convert_hex_to_int("0")
      => 0
      >> hex_hex_to_int("4")
      => 4
      >> convert_hex_to_int("D")
      => 13
      >> convert_hex_to_int("10")
      => 16
      >> convert_hex_to_int("2A7")
      => 679
      

Part II

(3pts) For part II of this assignment, you will work on a module in the Online Learning Initiative at CMU that will teach you about a new topic called cellular automata. This module will help you learn the basics about cellular automata before we cover this topic in class next week. The module is designed so we can focus in class on the parts of the topic that you find more difficult, which in turn will hopefully maximize your learning for this topic.

In order to get credit for this part, you must complete the module by the deadline for the programming part. We will not be grading you on how many questions you get right in the module. Instead, we will be grading you on whether you completed the module on time or not.

To access the Cellular Automata module:

  1. Go to this URL: https://oli.web.cmu.edu/ and click on the "Register" link in the upper right.

  2. Click on the "CMU users sign in here" link.
  3. Enter your course key cmu15110 into the box labeled "Register for a course" as shown at right.

  4. Follow the instructions on the My Courses page to get started on the Cellular Automata module.

  5. You don't have to do then entire module in one sitting; you can leave the web site and resume work on it later. But you must complete the module by the submission deadline for this assignment.

Submission

You should have a pa7 directory, containing:

  1. convert_to_bin.rb
  2. convert_to_int.rb
  3. convert_hex_to_bin.rb
  4. convert_hex_to_int.rb

Zip up your directory and upload it using the autolab system. (The autolab system will accept submissions beginning on Friday until the deadline Tuesday night.)