Binary Code - CS1302

CS1302 Introduction to Computer Programming

Welcome to this lab where you will explore how computers represent numbers using a fun card-guessing game! Through this lab, you will gain an understanding of how binary numbers are used to represent decimal numbers in computers.

Card Guessing Game¶

Rules¶

Table 1 shows a deck of 52 cards:

Each card is in one of the four suits:
Diamond, Club, Heart, and Spade.
Each card has a value ranging from 1 to 13.

A player guesses a card drawn by a dealer. — Figure 1:Card guessing game

Rules

As depicted in Figure 1, the card-guessing game involves the following steps:

The dealer selects a card without revealing it to the player.
The player's goal is to correctly guess the chosen card.
To make an informed guess, the player can ask up to six yes/no questions.
The dealer must answer each question truthfully and immediately.

Example 1 (Valid questions)

For instance, the player may ask:

Is the suit club?
Is the card diamond 1 (A)?
Is the value at least 10?

Example 2 (Invalid questions)

However, the player cannot ask:

What is the value?
What is the suite?

because the answers are not yes/no.

One strategy is to ask whether the randomly drawn card is a specific card, e.g.,

Is it the Diamond 1?

If the answer is yes, the player can confidently guess that the card is Diamond 1 and win the game. However, if the answer is no, the player can continue to check another card, e.g.,

Is it the Diamond 2?

and so on...

A pseudocode that summarizes the above strategy (or algorithm) is shown below.

Algorithm 1 (Checking one card at a time)


while the number of questions asked is below six and \
the correct card has not been guessed yet:
    pick a new card not chosen before
    ask the dealer whether the randomly drawn card is the chosen one
    if the answer is "yes":
        guess the card
    else:
        increment the number of questions asked

Exercise 1 (chance)

What is the chance of winning using the strategy in Algorithm 1?

Attention

Provide your answer in the following code cell by assigning a fraction to the variable chance such as

chance = 0.5

where the value 0.5 means 50% chance (which is not necessarily the correct answer). Your answer should be accurate at least up to 2 decimal places.

# YOUR CODE HERE
raise NotImplementedError()

# tests
assert chance >= 0
assert chance <= 1

# hidden tests

Virtual Cards¶

Instead of drawing a physical card, the dealer can use programming to generate a virtual deck and draw a pseudo-random virtual card from it. Run the code below to get the required tools.

from collections import namedtuple  # for naming the cards
from random import choice  # for pseudo-randomly drawing cards

To create a deck of cards, run the following cell.

suits = ("Diamond", "Club", "Heart", "Spade")
values = range(1, 14)
Card = namedtuple("Card", ["value", "suit"])
deck = [Card(value, suit) for value in values for suit in suits]
deck

Now, you can use the following program to play the game with your friends:

choice(deck)

YOUR ANSWER HERE

Virtual Player¶

Given you have randomly drawn a card,

run the following code cell, and
answer the 6 questions raised by the player honestly by entering
- 1 for yes and
- 0 for no.

def is_yes(question):
    """Get an answer to a yes/no question."""
    return "1" == input(question + " 1:yes [0:no] ")


suit_idx = number = 0
if is_yes("Is the suite either heart or spade?"):
    suit_idx += 2
if is_yes("Is the suite either club or spade?"):
    suit_idx += 1
for i in range(3, -1, -1):
    number += 2**i * is_yes(f"Is the number {number+2**i} or above?")
print(f"The card is {suits[suit_idx]} {number}")

YOUR ANSWER HERE

Binary Number System¶

Representing non-negative integers¶

The following table gives the binary representions of unsigned decimal integers from 0 to 7.

Table 2:Encoding positive integers

Binary	Decimal
000	0
001	1
010	2
011	3
100	4
101	5
110	6
111	7

Observe that the binary representations of 4, 5, 6, and 7 all have 1 in the leftmost (most significant) bit. Consider that bit as the answer to the following yes/no question:

Is the integer 4 or above?

Now, to convert the entire binary sequence to decimal, we can think of the conversion as a guessing game where

the binary sequence is a sequence of yes (1) or no (0) answers to certain yes/no questions, and
the informed guess is the integer represented by the binary sequence.

YOUR ANSWER HERE

Representing negative numbers¶

The following also uses 3 bits to represent 8 integers but half of them are negative.

Table 3:Encoding positive integers

Binary	Decimal
000	0
001	1
010	2
011	3
100	-4
101	-3
110	-2
111	-1

What is the benefit of the above representation?

To subtract a positive binary number $x$ from another positive binary number $y$ , i.e.,

x - y,

(1)

it seems we can instead perform the binary addition

x + (-y)

(2)

of a positive binary number $x$ and a negative binary number $-y$ .

For example,

\overbrace{011_2}^{3} + \overbrace{100_2}^{-4} = \underbrace{111_2}_{-1}

(3)

It seem to work as well if there are bits carried forward, e.g., $1 + (- 3)$ in binary is

\begin{array}{rrrr} & 0 & \overset{\color{blue} 1}0 & 1 \\ + & 1 & 0 & 1 \\\hline & 1 & 1 & 0 \end{array}

(4)

which translate to $-2$ in decimal as desired.

YOUR ANSWER HERE

Logic Gates¶

A computer is built from transistors that operates on binary states on/off, which is also represented as bits 1/0, or the boolean value true/false. Play with the following simulator to see some examples.

Logic simulator

Click the logic simulator header above.
Select 1-Bit Full Adder.
Change the input and observe the output.

Table 4 gives the input and output relationship of a simpler adder, called the half adder, which computes the addition of two input bits $A$ and $B$ as

A + B = C\circ S

(6)

where $C$ and $S$ are the output bits, and $C\circ S$ is the concatenation of two bits $C$ and $S$ .

Table 4:Adder.

A	B	C $\circ$ S
0	0	00
0	1	01
1	0	01
1	1	10

The operation can be built using transistors, called logic gates, that can carry out basic logic operations such as

$A \operatorname{AND} B$ : which returns $1$ if and only if both $A$ and $B$ are $1$ , and $0$ otherwise.
$A \operatorname{XOR} B$ : which returns $1$ if and only if either $A$ and $B$ are $1$ but not both.

The input and output relationships are listed below:

from pandas import DataFrame

DataFrame(
    [[A, B, A & B, A ^ B] for A in (0, 1) for B in (0, 1)],
    columns=["A", "B", "A AND B", "A XOR B"],
)

YOUR ANSWER HERE

Glossary¶

algorithm: An algorithm is a set of instructions that a computer program follows to solve a problem or complete a task. It is a step-by-step approach designed to be efficient and accurate.
bitwise operator: Bitwise operators are used to manipulate individual bits of binary numbers. They allow for the manipulation of data at a low level, such as setting or clearing specific bits, shifting bits left or right, or performing logical operations on bits.
composite data type: A composite data type groups related data into a single unit so that they can be easily stored and manipulated together.
conditional: A conditional statement is used to perform different actions based on different conditions. It allows the program to make decisions and execute specific code blocks based on the evaluation of a given condition.
iteration: An iteration is a repeated execution until a condition is met. It allows for the efficient repetition of tasks without the need for writing the same code multiple times.
library: A library is a collection of pre-written code that developers can use to perform common tasks. It contains functions, classes, and other reusable code that can be integrated into a larger software application, saving time and effort.
pseudocode: Pseudocode is a high-level description of a program or algorithm, using natural language and code-like syntax to express logic without being bound to a specific programming language. It is used during planning and design phases of software development.

	1	2	3	4	5	6	7	8	9	10	11	12	13
Diamond
Club
Heart
Spade