CS 4, Summer 2006: HW 5, due Friday, August 11

Instructions

The first part of this homework involves writing JavaScript, along with some HTML to hold it. Follow the same instructions as in HW 1 -- write code by hand, make it easy to read, print it from the text editor, timestamp it, and upload it to your private folder. For both problems, you are being provided with some code. Edit and and extend it, and then turn in the whole thing (not just your part). Indicate where you have modified the provided code.

The second part of this homework is a set of written questions. You are not required to write your answers in HTML. However, you should still upload them to your private directory and provide a printout. Upload your file in a format we can read -- plain text, HTML, PDF, Word, or RTF. No timestamp is required.

JavaScript Problems [40 points]

We're going to do some circuit design. Actually, since it's a bit painful to automatically draw a circuit, we'll just design the equivalent Boolean expressions. You might want to do the relevant written problems first, to make sure you're comfortable with the ideas and techniques.

Provided in hw5-logic.html is the basic structure of a program to take in a truth table, generate a Boolean formula, and evaluate the formula with values for the variables.

1. [20 points]
   The first task is to fill in the missing code for generateFormula. It should follow the algorithm from class for generating a circuit / Boolean formula from a truth table. Examine the rows in the truth table. For each row whose checkbox is checked, add to the formula an expression for the row. Separate the row expressions with an or symbol (+). For a row expression, list each of the three variables (A, B, and C), separated by AND signs (*), with a not sign (~) in front of each variable whose truth table entry is false in that row.

   Some hints:

   • The table variable stores the input values for the truth table. You can index it by row and column; e.g. table[0][1] has the value of the variable B in row 0, which is false.
   • In addition to the document.form.name construct we've been using, JavaScript also supports document.form.elements[string]. This allows you to build up the name as a string (e.g., "o0") in the middle of a program. The checkAll function has an example. This will be useful for seeing which rows are checked -- loop over the rows by number, and check the state of the checkbox named "o"+row.
2. [20 points]
   

   Once we have a Boolean formula, we can put values for the variables (e.g., A=true, B=false, C=true) and evaluate the formula to see if the whole thing turns out to be true or false. Fill in the missing code for evaluateFormula to do that. The provided code already extracts the formula and values from the form and puts the result into the form. Your job is to make the result correct.

   The particular structure of formula we're using here -- an OR of groups of ANDs of variables and their negations -- makes it relatively straightforward to evaluate a formula. The whole result starts off as false, and becomes true if any (OR) of the expressions for the rows is true. The partial result for a row starts off as true, and stays true as long as all (AND) the variables have the "right" values. A variable has the "right" value if it is true and shows up as itself in the expression (e.g., A=true for A*~B*C), or if it is false and shows up with a NOT sign in the expression (e.g., B=false for A*~B*C).

   With this in mind, the algorithm marches down the string, character by character. It keeps a partial result for the AND that makes up a single row, and an overall result for the whole formula. For each character, it does a different action based on what that character is:

   • "+" or the end of the string: finished with the expression for a row, so OR the partial result into the overall result, and reset the partial result back to true.
   • "*": nothing to do (we know that the variables are ANDed together).
   • "~": keep track of the fact that the next variable you see will be negated.
   • "A", "B", or "C": AND the partial result with either the value of the variable or its negation (if you just saw a "~" as the previous character).

   Note that in JavaScript, AND is written &&, OR is written || and NOT is written !.

For extra credit (only do this once the whole rest of the homework is in great shape, and only if you want to), generalize the code to handle 4 or more variables (you'll need to use document.write to create the table), simplify the formula, etc.

Written Problems [60 points]

1. [5 points]
   Consider the Boolean formula A*~B*C + ~A*B*~C + A*~B*~C. What is its value if A=true, B=false, C=false? What if A=false, B=true, C=true?
2. [10 points]
   Write the truth table for a circuit that has three inputs and one output, such that the output is 1 if and only if an even number (0 or 2) of the inputs are 1. (This is called an "odd-parity" circuit, and does a kind of error checking like we discussed in the networking lecture: if we know what the parity should be, then if the computed parity doesn't match that, we know that one of the bits is in error.)
3. [10 points]
   Using the circuit construction algorithm from class, construct the following two circuts from AND, OR, and NOT gates.

   XOR (exclusive or -- A or B but not both):

   A	B	out
   0	0	0
   0	1	1
   1	0	1
   1	1	0

   NAND (not both A and B):

   A	B	out
   0	0	1
   0	1	1
   1	0	1
   1	1	0

4. [5 points]
   Consider a machine that uses 6 bits for the instruction opcodes and 18 bits for the arguments. How many different instructions are possible? How many different memory locations can it access?
5. [15 points]
   Write the following pieces of code in the assembly language covered in class and in the textbook. Your code should use labels and .DATA pseudo-ops to define the locations of the variables and jump targets.
   1. Add y+1 to x
   2. If x > 1 then output x and decrement it by 1
   3. If x ≥ y, then set z to x - y, else set z to y - x
6. [15 points]
   Translate the following algorithm to the assembly language covered in class and in the textbook. Your code should use labels and .DATA pseudo-ops to define the locations of the variables and jump targets.

     Get a positive integer x
     Get a positive integer y
     Set z to 0
     While y ≠ 0 do
       Add x to z
       Subtract 1 from y
     End of loop
     Output z
     Halt