1.1 Computational Basics

WiSe 2023/2024
Julian Huber

1.1 Binary Information Representation in Computers

Learning objectives

You will be able to

• describe the difference between data and information.
• understand how information can be stored in bits.

Motivation: History of Computation

• 2500 B.C. Abacus/calculating slide
  (probably of Sumerian origin)
  • Representation of numbers
  • Rules for computation (algorithms)

Timeline of Computer History, https://de.wikipedia.org/wiki/Abakus_(Rechenhilfsmittel)

• 1804 Punched cards for controlling looms

• 1833 Charles Babbage calculating machine with punched cards

K-Adder (1937)

• 1937 K-Adder

https://www.computerhistory.org/timeline/1937/#169ebbe2ad45559efbc6eb35720eb5ea

• 1941 Konrad Zuse builds Z3 as first digital computer with programming language Plankalkül.
• 1954 TRADIC first computer based on transistors
• 1977 Commodore as the first personal computer
• 1991 Tim Berners-Lee puts first website online
• 2020 over 27 billion networked devices

https://upload.wikimedia.org/wikipedia/commons/4/4c/Z3_Deutsches_Museum.JPG

https://www.computerhistory.org/timeline/1937/#169ebbe2ad45559efbc6eb35720eb5ea

Half adder

• Simple electrical calculator e.g. implemented as a K-Adder
• Adds values of the input and displays them in the
  output via two lamps
• The information is described in each case by two states
  (keystroke or light on/off)

1. Input:

   • Button A (left)
   • Button B (right)

2. Output

   • Lamp left
   • Lamp right

Task (1/2)

• Visit the website linked below
• There you will find a simulation of the half adder

1. Input:

   • Button A (top left)
   • Button B (bottom left)

2. Output

   • Lamp left (top right)
   • Lamp right (bottom right)

https://www.falstad.com/circuit/e-halfadd.html

Task (2/2)

• Fill in the table for the lamps for all possible combinations of switch positions
  (1 for (on/pressed) or 0 for (off)).
• What numerical value (result of addition) does each result correspond to?
• Can more numerical values be displayed via the two lamps?
• The half adder obviously calculates a result. Would you call it a computer? What distinguishes it from modern computers?

7 minutes

Solution: Completed truth table

• In the results table, the case where both lamps are lit does not occur. This numerical value could represent another numerical value (e.g. 3)
  • Up 0 & Down 0 0
  • Up 0 & Down 1 1
  • Up 1 & Down 0 2
  • Up 1 & Down 1 3
• Modern computers are capable of solving many different tasks. Due to the fixed wiring, the half adder allows only one operation.

https://www.falstad.com/circuit/e-halfadd.html

Bits (Binary Digits)

• each lamp hold a Bit of information
• store value of a Boolean variable
• two states arbitrarily interpretable:
  • 0/1
  • True/False
  • on/off
  • High voltage / low voltage
• easy to store
• easy to transmit

• Not only numbers, all information is stored binary information
• Imaging of data carriers under a scanning electron microscope

https://mybroadband.co.za/news/gadgets/130658-what-cds-dvds-blu-rays-look-like-under-a-microscope.html

Combinatorial power

• $2^n$ different states can be represented per $n$ bit.
• With 1 bit one can represent $2^1 = 2$ different states:
  • [0, 1]
• With 3 bits you can represent $2^2 = 4$ different states:
  • [00, 01, 10, 11]
• With 3 bits you can represent $2^3 = 8$ different states:
  • [000, 001, 010, 011, 100, 101, 110, 111]

How many bits do we need to specify all the states of a traffic light?

• There are 3 states / 4 with everything off.
• 1 bit is not enough [0,1]
• 2 bits are enough [00,01,10,11]

https://www.bertelsmann-stiftung.de/en/themen/aktuelle-meldungen/2021/november/deutsche-blicken-mit-grossen-erwartungen-und-skepsis-auf-die-ampel-koalition

Byte

• data is usually stored in multiples of $8$ Bit

  0101 01011

• one Byte can store $8^2=256$ different states

• Bits can code four different calculation results (decimal numbers)
  • 0 0 0
  • 0 1 1
  • 1 0 2
  • 1 1 3

https://www.falstad.com/circuit/e-halfadd.html

Learning Summary

Now, You know

• that data represents stored information.
• that information can be stored in a succession of bits 0, 1

1.2 Binary Number System

Learning objectives

You will be able to

• represent positive and negative integers in the binary system.
• perform addition and subtraction in the binary system.

Decimal System

• The representation uses $10$ as base
• The place of the digit indicates to which exponent
• Representation of the number $4711$ in the decimal system

Binary System

• The same representation can be used to represent natural numbers as a sequence of 0 and 1.
• The base is the number $2$

• Most Significant Bit (MSB) - digit with the highest exponent. In our examples the left

The table contains examples of how natural numbers can be represented in the binary system:

Leibniz 1697

The lamps of the half adder also represent a binary number.

• $A + C = D$
  • $A$ a binary number with one digit: 1 or 0.
  • $B$ a binary number with one digit: 1 or 0
  • $D$ a binary number with two digits: 00, 01, 10, 11

Signed binary number representation

• A sign bit (SB) can be reserved to also represent negative numbers

  SB	$2^2$	$2^1$	$2^0$	Computation	Decimal
  1	1	0	0	$(1 \cdot 4 + 0 \cdot 2 + 0 \cdot 1$)	$-4$

• We call a positive natural number Integer (int)
• In natural number unsigned Integer (uint)

https://zitoc.com/signed-number/

Task

• What is the smallest and largest integer value as a decimal number that a computer can store in each of the following numbers of bits?
• given the schema of encoding of the slides before
• Hint: With a bit reserved for the sign one bit less is available for the binary number

  Number of bits	with sign bit	smallest integer	largest integer
  3	yes
  3	no
  4	yes
  4	no

5 minutes

Solution

• What is the smallest and largest integer value as a decimal number that a computer can store in each of the following memory array?

  Number of bits	with sign bit	smallest integer	largest integer
  $3$	yes	$-(1\cdot 2^1+1\cdot 2^0)= -3$	$(1\cdot 2^1+1\cdot 2^0)= 3$
  $3$	no	$0$	$(1 \cdot 2^2 + 1\cdot 2^1+1\cdot 2^0)= 7$
  $4$	yes	$-7$	$7$
  $4$	no	$0$	$15$

• Note, that there are positive and negative zero

• Modern computers work with another format: twos' complement

Addition in the Binary System

• works analogous to the decimal system
• we work with numbers without sign bit

• Start from right (least significant bit)
• $1+1 = 2$
• In decimal system $2$ is represented as 10
• 0 write to last digit (sum bit s)
• 1 transfer to penultimate digit (carrier bit c)

• add next digits and consider carry (1)
• 0+1+1 = 10
• Write 0 in penultimate place
• 1 transfer to penultimate digit

• add next digit
• 0+1+0 = 1
• In the decimal system $1$ is represented as 1
• write 1 to the second to last digit
• no carry necessary

• add next digit
• 1+0 = 1
• In the decimal system $1$ is represented as 1
• write 1 to the second to last digit
• no carry over necessary

1.2 Encoding complex information

Encoding Pictures

https://computerscience.chemeketa.edu/cs160Reader/DataRepresentation/ImageRepresentation.html

Learning objectives

You will be able to

• store pictures as a succession of bits
• calculate how many bits are needed to store a given amount of information (states).

Task 1

• How many different (unique) images can you store in 1 megapixel?
  • a) in a black and white image (binary image)
  • b) as a greyscale image with 1 byte per pixel (256 different greyscale values are stored)

• Hint:
  • There are two types of black and white images
  • Binary image: There are only black or white pixels (example on the left).
  • Grey-scale image: each pixel can be different light/dark.

Solution 1

• a) binary image

  • 1 million pixels with two states each (black/white):
  • $2^{1.000.000}$

• a) greyscale image

  • 1 million pixels with 256 states each:
  • $256^{1.000.000}$

8-bit color

• In early applications (e.g. games) colours were encoded with 8 bits, i.e. $2^{8}$ colours

• historically a succession of 8 Bit is called a byte

Application in RGB codes

• Colour values are specified as a mixture of red, green and blue
• 8 bits are provided for each colour
• e.g., R goes from 0 to 255 ($2^8$ states)

https://www.rapidtables.com/web/color/RGB_Color.html

Learning Summary

Now, You can

• interpret a sequence of bits as a picture if You know the color coding and ratio of the picture
• calculate how many bits You need to store a number of different states

Encoding Numbers

Learning objectives

You will be able to

• explain why computers cannot store floating point numbers with infinite accuracy

The same Bit-Sequence can store different Information

• Data: 100010

• Code

  • Integer in binary system
  • Unsigned integer in binary system
  • Pixel colour in a picture
  • Bases: 00: A, 01: T, 10: G, 11: C

• Information

  • $1\cdot 2^{5}+0\cdot 2^{4}+0\cdot 2^{3}+0\cdot 2^{2}+1\cdot 2^{1}+0\cdot 2^{0}=32+ 2 = 34$
  • $-(0\cdot 2^{4}+0\cdot 2^{3}+0\cdot 2^{2}+1\cdot 2^{1}+0\cdot 2^{0})=-2$
  • 
    
  • GAG

Integers

Floating Point Numbers

• With 64 bits, $2^{64}$ can represent whole, positive numbers.
• But how are negative, larger and non-integer numbers represented?

1. IEEE 754 defines the standard representations for binary floating point numbers in computers

2. 

• General value calculation: $x = (-1)^s \cdot 1,m \cdot 2^{e-B}$
• First digit (always 1) is not stored in mantissa (so-called hidden bit).
• Bias B depends on the length of the exponent representation E: B = 2E-1 - 1
• Valid characteristics: 0 < e < 2E - 1 (values 0 and 2E - 1 are reserved)

Caution: Floating point numbers are not infinitely accurate!

️ Task

• Try to represent Your year of birth:

3 minutes

https://www.h-schmidt.net/FloatConverter/IEEE754.html

Value ranges of floating-point numbers

• There are different names for floating-point numbers:
  float, single, double, real

Encoding Text

Learning objectives

You will be able to

• decode binary coded text using ASCII tables
• decide which character encoding is appropriate for a given text

Example: Base Pairs

• DNA has four different base pairs (bp)
  • G, C, A, T
• how much bits do we need to store $200$ bp?
  • we need $2^n=4$
    • 00 : G
    • 01 : C
    • 10 : A
    • 11 : T

https://www.lecturio.com/concepts/stages-of-transcription/

• we need $2$ bits to encode for $4$ possible base pairs on each position
• hence, we need $400$ bit = $50$ Bytes
• the text file, we use to store the data is four times larger ($216$ Bytes)

https://d-nb.info/1136955135/34

ASCII (American standard code for information interchange)

• A character set assigns a numerical value to each character, which determines the position of the character within the character set.
• one 8-bit word per character (the first bit is not used*)

* can be used as a parity bit

Task

• Decode the following messages using the ASCII character table:
  • 01010011 01000010 01010100
    • SBT

• ASCII has few options for representing special characters.
• That is why other character sets have become established

other character encodings

• ISO-8859 family
  • 15 different 8-bit character sets
  • e.g. ISO 8859-1 for Latin-1, Western European
• Unicode
  • To provide encoding for every text document of all languages and cultures of the world.
  • The 16-bit Unicode is under continuous development
  • 
• UTF
  • A large part of the text 8-bit character set can be represented.
  • Three encodings for Unicode characters (8-, 16- or 32-bit)
  • The first 128 characters of UTF-8 correspond to the 7-bit ASCII code.

Decision for character sets

• ASCII: Space-saving, but no umlauts, special characters, e.g., sequence data: FASTA files)
• Unicode: Higher memory requirement, but many character sets

The Text-Editor translates the Binary Code in Characters

UTF-Table

1.3 Boolean Algebra and Propositional Logic

Learning objectives

You will be able to

• describe logical statements with Boolean variables
• evaluate the Boolean operations AND, OR, NEGATION and EXCLUSIVE OR
• can combine multiple Boolean operations into meaningful expressions

Logic

Epimenides the Cretan said: All Cretans are liars.

If the lamp is not on, it must be off.

IPO principle

• Calculator working according to the IPO principle
  • Input: A and B keys
  • Process: Calculation logic / wiring
  • Output: Lamps
• Process follows a simple logic: Add the two numbers

https://www.computerhistory.org/timeline/1937/#169ebbe2ad45559efbc6eb35720eb5ea

Logical deduction

• Description of the state based on the values of the
  Boolean variables $X$ and $Y$ containing one bit of information.
  • $X=\text{True}$: Adam is in the lecture
  • $Y=\text{True}$: Eve is in the lecture

• Possible logical inferences?
  • Are Adam and Eve both there?
  • Is at least Adam or Eve there?
  • Is no one in the lecture?

Which of these are meaningful Boolean variables?

• presence of a particular student
  • yes, binary
• size of a storage unit in megabytes
  • no, its a number
• Name of a pet
  • no, its a string
• Colour of a pixel in an 8-bit colour image
  • no, its a 8-bit information
• Colour of a pixel in a 1-bit binary image
  • yes, black and white can be represented in one bit
• Result of a coin toss
  • yes, two states
• Gender of a person
  • ...

Boolean Algebra

• is used for the formal description of
  statements and logical conclusions based on Boolean values
• Can map switching logic (current/no current)
• Variables only take on two values (are bits)
  • x=True, x=1
  • y=False, y=0

conjunction, AND, $\land$

• Are Adam and Eve both there?
• $y \land x$
• truth table

https://www.ulfkonrad.de/physik/schalter-und-oder

Disjunction, OR, $\lor$

• Is there at least Adam or Eve?
• $y \lor x$
• truth table

https://www.ulfkonrad.de/physik/schalter-und-oder

-, negation, inversion, NOT, $\neg$

• Is Adam not there?

• $\lnot x$

• truth table

Exclusive OR, $\oplus$, =1

• Is there exactly one of Adam or Eve here?
• truth table

Application

• often, we break down more complex questions into boolean expressions:

Evaluations that result in Boolean Variables

• comparison: 1>2 ➜ False
• test for equality: "a" =="a" ➜ True
• test for inequality: "a" !="a" ➜ False

Calculation rules for Boolean variables

• Basic for operations in computers e.g. addition of numbers.

• Helpful for search queries in Google and databases.

• Three operations:

  • $\land$ or $+$ (and)
  • $\lor$ or $\cdot$ (or)
  • $\neg$ (negation) (not)

Four axioms/laws of calculation (Huntington, 1904)

• Commutativity
  $A \lor B = B \lor A$ bzw. $A \land B = B \land A$
• Neutral element
  $0 \lor A = A$ bzw. $1 \land A = A$
• Distributivity
  $(A \lor B) \land C = (A \land C) + (B \land C)$
  $(A \land B) \lor C = (A \lor C) \land (B \lor C)$
• Complementary element
  $A \lor \neg A = 1$ bzw. $A \land \neg A = 0$

https://www.ncbi.nlm.nih.gov/nuccore/advanced

Brackets matter!

• the OCA gene of either human or mouse

• any data regarding humans or (OCA gene of mouse)

Task

• Look for myostatin (Gene is GDF8) in the NCBI-Nucleotides Database
• For what organisms do You find entries?
• Adapt the following search term so that it returns the specific gene for two other the organisms
  • (GDF8[Gene Name]) AND ("Homo sapiens"[Organism] or "Bos Taurus"[Organism])

Significance of Boolean algebra for computer science

• search terms
• Storage of individual bits can be realized very simply by storing electrical charge, e.g. by capacitors or flip-flops:
  • electrical charge present 1
  • electrical charge not present 0
• Conjunction, disjunction and negation can easily be realized by means of switches (transistors, relays) which pass on charge (information) or not.
• controls execution of software code

Example conjunction:

Task

• given the following patient data
• formulate the following equations that result in boolean values
  • $a$ ... patient is heavier than 80 kg
  • $b$ ... patient is younger than 30 years
  • $c$ ... patient is heavier than 80 kg but older than 30 years
• fill in the truth table with the formula and the resulting values

• e.g. $a = (weight > 80)$

Learning Summary

Now, You can

• describe logical statements with Boolean variables.
• evaluate the Boolean operations AND, OR, NEGATION and EXCLUSIVE OR.
• can combine multiple Boolean operations into meaningful expressions.

1.4 Programming Computers

Learning objectives

You will be able to

• describe the task of a compiler
• formulate an algorithm using a an UML-Sequence diagram

Software as interface between human and machine

• Computer are hardware that purely operate with boolean algebra
• The machine program interpreted by the processor is a sequence of zeros and ones (incomprehensible to most humans)
• Users need to write, read and understand programs.
  Programming languages are approaches to develop programs with less effort and in a form that is more comprehensible to humans

Compiler

https://medium.com/young-coder/the-difference-between-compiled-and-interpreted-languages-d54f66aa71f0

We can describe different information

• Booleans: a = True: stored as 1

• Integers: $b = 5 = 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0$: 101

• Floats: $c = 3.14$

• Strings: $d = \text{"AB"}$: 01000001 01000010

• The computer stores it in binary code

  • Implication: The computer must know, what is stored with what code
  • we say the variable (e.g, a) has a certain data type (e.g., Boolean, Integer, etc.)

• What the programmer writes
  • "a" == "a" ?
• What the compiler translates
  0100 0001 == 0100 0001
• What the computer computes

• A compiler is the computer program that translates source codes of a particular programming language into executable machine language.

Examples of Programming Languages

• General Purpose Languages
  • for almost any application, fast
  • C, C++,C#, Java, Python, ...
• Scripting Languages
  • controlling what a computer shall do
  • Shell, R, Python, VBA, Matlab, Funktionsplan
• Languages for Databases
  • Filling and queries on data bases
  • SQL

Algorithms

Learning objectives

You will be able to

• name examples of algorithms
• describe central properties of an algorithm
• recognize basic elements of an algorithm

Task: Shotgun Sequencing / Assembly

https://www.genome.gov/sites/default/files/media/images/tg/Shotgun-sequencing.jpg

"Shotgun sequencing is a laboratory technique for determining the DNA sequence of an organism’s genome. The method involves randomly breaking up the genome into small DNA fragments that are sequenced individually. A computer program looks for overlaps in the DNA sequences, using them to reassemble the fragments in their correct order to reconstitute the genome." genome.gov

You have a list of fragmented DNA-snippets that have to be ordered in the right order. Your task is to implement an algorithm, that brings the DNA-sequence into thr right order.

• Randomly pick a sequence of eight nucleotides (read) from the following original sequence and write them on a piece of paper

"TAGCTAGCTAGCTTTTAGTTAGCAGCC"

Building blocks for algorithms

• loops (same steps several times)
  we to compare all the sequences available
• conditional execution (e.g., =if x == True:)
  we only add a sequence is we have a match
• elementary operations (e.g., and, =)
  starting from the seed, we expand the final sequence
• sequential execution
  the algorithm only makes sense if we keep the sequence

Algorithms

• Precise (written in a specified language)
  finite description of a general procedure
  using executable elementary (processing) steps.

• Examples
  • find an open reading fame
  • Translating a DNA into an mRNA sequence
  • Addition of two binary numbers
  • Calculating the number $\pi$

Properties: Termination

An algorithm is called terminating if it terminates (stops) (for any allowed input of parameter values) after finitely many steps.

• Question: Do the algorithms in the previous slide terminate?
  • Translating a DNA into an mRNA sequence
    • yes, the DNA sequence ends and the translation stops
  • Addition of two binary numbers
    • yes, there is a result at the end
  • calculating the number $\pi$
    • no, the calculation can continue up to any precision

Properties: Determinism

establishes "freedom of choice" or "randomness" in execution

• Forms
  • deterministic sequence: unambiguous specification of the sequence of steps to be executed.
  • deterministic result: unambiguous result for given parameter values

• Deterministic algorithm:

  • Computer makes a copy of a DNA strand

• Non-determined "algorithm"

  • Cell makes a copy of a DNA strand

Building blocks for algorithms

• Inputs: Data that goes in should be in a well defined format
• Storage: Data that is stored during execution, to make things easier
• Outputs: Data that comes out

Building blocks for algorithms

• elementary and boolean operations (e.g. +, and, =, etc.)
• sequential execution (one processor)
• parallel execution (multiple processors)
• conditional execution (e.g. if)
• loop (same steps several times) (e.g. while, for)
• subroutines
• recursion: application of the same principle to smaller subproblems

elementary operations

• Assignment (of a variable a value)
  Result = 2
• boolean operation
  True and False (operation)
  True == True (comparison)
• Arithmetic operation
  5+2

Sequenz

• Steps happen in a certain order

Refinement and subroutines

refined to

conditional execution / selection / if

resp.

Selection nesting

Loop (as long as/while)

Algorithm assemble_sequence()

• does the algorithm terminate?
  • yes, at one point we can not find any matches
  • but, we cannot be sure, that we found the whole original sequence
• is the algorithm deterministic?
  • it depends on how we select the sequences
  • we can get stuck, if we do it in the wrong order
  • hence, we should draw by random and do it multiple times

UML activity diagrams

Graphical description of the flow of an algorithm

Example: Cooking noodles

• Start and stop are marked
• activities can be kept very rough at first
• Branches are provided with conditions (boolean expressions)
• Does this algorithm always terminate?

Task: Algorithm assemble_sequence()

• Create and UML activity diagram that creates the complement of a DNA sequence

Task: Algorithm Complement of a DNA sequence

• Create and UML activity diagram that creates the complement of a DNA sequence

• e.g., TCCACTGTGGCGTTCGGAATATAATCG

• verbal description

  • go through the list
  • replace each letter by its complement
  • T➜A
  • A➜T
  • C➜G
  • G➜C

• input: list to complement: TCCACTGTGGCGTTCGGAATATAATCG
• output: complemented list: AGG...
• storage: temporary list:

https://mermaid.live/6qJRv7el2OuCMr0aF-N-amufwAlQIeyA

Bonus Task

• Create and UML activity diagram on how to find an open reading frame
• If we have multiple, it is ok to stop after You found the first one

Open Reading Frames

• have the potential to be transcribed into RNA and translated into protein
• from a start codon (e.g., ATG), through a subsequent region which usually has a length that is a multiple of 3 nucleotides to a stop codon (e.g., TGA) in the same reading frame.

What are the Inputs and Outputs to our Algorithm?

• Inputs:
  • String (text) of a RNA sequence
• Outputs:
  • found_open_reading_frame: True or False
  • start_position: number of the first letter of the reading frame (A in the ATG)
  • stop_position: number of the last letter of the reading frame (A in the TGA)

Verbal Description

• set found_open_reading_frame to False
• Iterate through the RNA sequence in steps of 1
  • Look at the next three letters
  • if the letters are ATG
    • note the position of A in start_position
    • Iterate through the next three-letter pairs
    • if any of them is TGA
      • note the position of A in stop_position
      • set found_open_reading_frame to True
      • terminate algorithm
  • else go to ne next letter
• if at the end of RNA sequence
  • terminate algorithm

• this graphical interpretation of the algorithm is not very precise
• anyone could interpret this a litte differently
• computers cannot work with this ambiguity
• programming languages provide a precise way to describe algorithms

https://mermaid.ink/img/pako:eNqNk9FqwjAUhl_lLFcK-gKCg4Iou5iM6dWsSGhPNdDmZOnp2FDffTmpLXM62E0Iyff_OflzclQZ5agmau-1O8B6llqAmrXnzUrGLYzHj1Ajz6mx-SCOQA7tzqPOjd3vCq8rhCnMdVnjMMovdJSWRC46HZ8YvWYEPnhq9gd4XSYBfW_QZngWXY-K8LTETxYWEUrkoK1hOoVkvTiBJcYIDpZhBo5qw4YsUAEJGNvWv-uWh__yfrh4V_SBsn1HRD1cYsGncAw5wTrJZk_ABFbMW3J7HYHAfe391os2vr5Jx_YljlsvcML1QUVVrEvWJZr1IumiIfdnMuRug_nlZWqxaf0ysmxsgxH5eUEht2JwRVxfCm4PsBSVlwTvJEOu67i1b3CwQoZCmml3p-lCLQJ1TSfzVhwfRo1Uhb7SJg_tfRQmVXzAClM1CdMcC92UnKrUngOqG6bVl83UhIPNSDUuD88xMzp8jEpNCunukcLcMPnn9svEnzNSTts3oo45fwPwvi0D?type=png