FoP: 1.1 Computational Basics

1.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 (data structures)
  • Rules for computation (algorithms)

• 1804 Punched cards for controlling looms

• 1833 Charles Babbage calculating machine with punched cards

K-Adder (1937)

• 1937 K-Adder

• 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

Half adder

• Simple electrical calculator
• Adds values of the input and displays them in the
  output via two lamps
• The information is described 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 this website
• 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)

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.

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

Combinatorial power

• different states can be represented per bit.
• With 1 bit one can represent different states:
  • [0, 1]
• With 3 bits you can represent different states:
  • [00, 01, 10, 11]
• With 3 bits you can represent 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]

A Byte

• data is usually stored in multiples of Bit

  0101 01011

• one Byte can store different states

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

Learning Summary

Now, You know

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

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 as base
• The place of the digit indicates to which exponent
• Representation of the number 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

• 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 binary number with one digit: 1 or 0.
  • a binary number with one digit: 1 or 0
  • 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				Computation	Decimal
  1	1	0	0	)

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

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

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?

• 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)
• In decimal system 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 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 is represented as 1
• write 1 to the second to last digit
• no carry over necessary

1.1.3 Encoding complex information

Encoding Pictures

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):

• a) greyscale image

  • 1 million pixels with 256 states each:

8-bit color

• In early applications (e.g. games) colours were encoded with 8 bits, i.e. 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 ( states)

(11111111 0000000 11111111) (0000000 0000000 00000000)  (11111111 11111111 00000000) 
(11111111 0000000 11111111) (0000000 0000000 00000000)  (11111111 11111111 00000000) 
(11111111 0000000 11111111) (0000000 0000000 00000000)  (11111111 11111111 00000000) 

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

  • 
    
  • GAG Codon for Glutamate

Integers

Floating Point Numbers

• With 64 bits, can represent whole, positive numbers.
• But how are negative, larger and non-integer numbers represented?
• IEEE 754 defines the standard representations for binary floating point numbers in computers

• General value calculation:
• 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!

1.1 + 2.2
#> 3.3000000000000003

️ Task

• Try to represent Your year of birth using this calculator

3 minutes

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 bp?
  • we need
    • 00 : G
    • 01 : C
    • 10 : A
    • 11 : T

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

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:
  • 01000010 01001100 01010100
    • BLT

• 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
  • provides 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

01000011 01000011 01010100 01010100 01010100 01000011 <...>

UTF-Table

CCTTTC <...>

1.1.4 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

Logical deduction

• Description of the state based on the values of the
  Boolean variables and containing one bit of information.
  • : Adam is in the lecture
  • : 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,

• Are Adam and Eve both there?
• truth table

Disjunction, OR,

• Is there at least Adam or Eve?
• truth table

-, negation, inversion, NOT,

• Is Adam not there?

• truth table

Exclusive OR, , =1

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

Application

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

  if (warning_level > 2 and slope>35):
      high_avalanche_risk = True
  

Evaluations that result in Boolean Variables

• comparisons: 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:

  • or (and)
  • or (or)
  • (negation) (not)

Four axioms/laws of calculation (Huntington, 1904)

• Commutativity
  bzw.
• Neutral element
  bzw.
• Distributivity
  
  
• Complementary element
  bzw.

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

Brackets matter!

("homo sapiens"[Organism] OR "mus musculus"[Organism]) AND OCA1[Gene Name])

• the OCA gene of either human or mouse

("homo sapiens"[Organism] OR ("mus musculus"[Organism] AND OCA1[Gene Name]))

• 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
  • ... patient is heavier than 80 kg
  • ... patient is younger than 30 years
  • ... patient is heavier than 80 kg but not older than 30 years
• fill in the truth table with the formula and the resulting values

• e.g.

1.1.5 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

We can describe different information

• Booleans: a = True: stored as 1

• Integers: : 101

• Floats:

• Strings: : 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

  0100 0001
  0100 0001
  _________
  0000 0000 == 0
  

• 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

"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

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

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
    • 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

Sequences

• Steps happen in a certain order

(1) Boil water
(2) Put coffee powder into cup
(3) Fill water into cup

Refinement and subroutines

(2) Pour coffee powder into cup

refined to

(2.1) Open coffee glass
(2.2) Take out spoon of coffee
(2.3) Tilt spoon into cup
(2.4) Close coffee glass

conditional execution / selection / if

if <condition>
    then <step>

resp.

if <condition>
    then <step a>
    otherwise <step b>

Selection nesting

if coffee is available
    then open coffee glass
    otherwise go to favorite cafe 
        if favorite cafe open
            then order coffee
        otherwise 
            go on to MCI

Loop (as long as/while)

/* next prime */
repeat
    Add 1;
    test for prime number property
    until number is prime;
output number

Algorithm assemble_sequence()

1) draw a random seed sequence
2) while sequences left
    2.1) draw next sequence
    2.2) compare_beginning(overlap)
        if match glue_fragments_end()
    2.3) compare_end(overlap)
        if match glue_fragments_end()

• 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

1) draw a random seed sequence
2) while sequences left
    2.1) draw next sequence
    2.2) compare_beginning(overlap)
        if match glue_fragments_end()
    2.3) compare_end(overlap)
        if match glue_fragments_end()

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:

graph TD
  start[Start] --> create_list(Create empty temporary list)
  create_list --> start_loop(what is the first/next letter in the original list)
  start_loop -->|Next letter == A| A(Add a T to the temporary list)
  start_loop -->|Next letter == T| T(Add a A to the temporary list)
  start_loop -->|Next letter == G| G(Add a C to the temporary list)
  start_loop -->|Next letter == C| C(Add a G to the temporary list)
  A --> letters_left(are there any letters left in the original list)
  T --> letters_left
  G --> letters_left
  C --> letters_left
  letters_left  -->|yes| start_loop 
  letters_left  -->|no| stop_loop(return the temporary list as complement)
  stop_loop --> Stop

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

graph TD
  start[Start] --> setFound(Found open_reading_frame = False)
  setFound --> loopStart{Iterate through RNA sequence}
  loopStart -->|Next three letters == ATG| noteStart(Note position of A in start_position)
  loopStart -->|Next three letters != ATG| moveNext
  loopStart -->|No letters left| stop
  moveNext[go to next letter] --> loopStart
  noteStart --> loopPairs{Iterate through next three-letter pairs}
  loopPairs -->|pair == TGA| noteStop(Note position of A in stop_position)
  loopPairs -->|pair is not TGA| continuePairs[go to next pair]
  continuePairs --> loopPairs 
  loopPairs -->|no pair left| loopStart
  noteStop --> setTrue(Set found_open_reading_frame to True)
  setTrue --> stop