ECS 20: Discrete Mathematics for Computer Science PS3.Problems UC Davis — Prof. October 5, 2021
Problem Set 3 – Due Tuesday, October 12, at 5pm
1. The standard way to represent a number in base-r (also called radix-r) (with r ≥ 2 an integer) is as sequence of one or more digits (symbols), each digit c representing a value v(c) ∈ {0, 1, . . . , r − 1}. The sequence of digits an an−1 · · · a2 a1 a0 (subscripted by r if one wants to explicitly name the base) represents the number v(an)rn + v(an−1)rn−1 + · · · + v(a2)r2 + v(a1)r + v(a0).
(a) Represent numbers 18710 and 11910 as binary (base-2) numbers. Then add up the binary num- bers using the base-2 analog of grade-school addition. Finally, convert the sum back to decimal.
(b) Represent numbers 18710 and 11910 in base-3. Then add up the base-3 representations using the base-3 analog of grade-school addition. Finally, convert the sum back to decimal.
(b) The C/C++ programming language allows logical operators to be applied to pair of integers, applying the named operator bitwise (that is, to corresponding bit positions in the binary represen- tations of the two numbers). What integer will result from taking the AND of integers 187 and 119 (written 187 & 119)? From taking their OR (written 187 | 119)?
2. If you know Python: We all know that P ∨ Q ≡ Q ∨ P . Still, write the simplest Python program you can where the line
print(P() or Q())
causes the program to print False, while replacing it with
print(Q() or P())
causes it to print True. Unlike the example we gave in class, your program should never crash.
If you don’t know Python but know some other programming language, you can use that instead (adjusting the syntax as needed). If you don’t know any programming language, you may say so and skip this problem.
Try your program out. You can use an online python interpreter, if you like, at
https://www.onlinegdb.com/online_python_interpreter
3. (a) In class we showed that the necessary functionality to add bits a, b, and c to generate a sum s and carry-out of c′ is: s = s(a,b,c) = a⊕b⊕c and c′ = c′(a,b,c) = ab∨bc∨ac. Consider the following circuit “WFA”:
A B
Cin
S
Cout
Does WFA compute the desired functions s and c′? (Treat labels A, B, Cin, S, and Cout as synonyms for a, b, c, s, and c′). Explain how you made your determination.
(b) Suppose we construct a 64-bit adder in the manner described in class using the circuit above. It adds two 64-bit values to generate a 65-bit sum. How many gates will your circuit employ, and what will be its depth? (The depth is the length of a longest path from an input wire to an output wire, measured in terms of the number of gates traversed.)
2
4.
ECS 20 PS3.Problems: Problem Set 3 – Due Tuesday, October 12, at 5pm
Chess is played on an 8 × 8 board. A knight placed on one square can move to any unoccupied square that is at a distance of two squares horizontally and one square vertically, or else two squares vertically and one square horizontally. The complete move therefore looks like the letter L (in some orientation). A knight cannot move off the board. Unlike other chess pieces, the knight can “jump over” other pieces in going to its destination.
Consider a chess board on which we place any number m ∈ {0, 1, . . . , 64} of knights, at most one knight on each square. Call the configuration of knights valid if no knight can move to a square occupied by another knight.
Carefully specify a Boolean formula φ over 64 Boolean variables X where the number of truth assignments to φ is exactly the number of valid knight configurations.
Write a BNF ( Form) definition for a number (regarded as no more than a sequence of characters), the number written either in fixed point or scientific notation. Numbers should include values like
0 314159 -27182 3.14159 -2.7182 0.0000000000000000000000013 6.0221515E23 6.023e23 6.626068e-34 6.67300E-11 -1.234e-10 .29 -.999 100E100
You can decide edge cases as you see fit—for example, whether or not 00 or -000 should count as numbers. I suggest to do what’s easiest.
5.