Week 2

Published

April 22, 2025

VL 3 - 22.04.2025

  • review of previous lecture: data-structure triangle
  • for ADTs there’s lot’s of wiggle room for the concrete representation (the concrete bit sequences)
    • example: integers
      1. “unsigned” or “signed”
      2. the number of allocated bits: uint8, int8 => uint16, int16 => uint32, int32 => uint64, int64 => infinite precision (python) (faster => slower). Python automatically switches to infinite precision if the numbers get too large.
        • smaller number of bits => overflow:
          • overflow in uint8:
            • \(255_D = 1111,1111_B\)
            • \(255_D + 1_D = 256_D = 1,0000,0000_B\)
          • How to react to this? Solutions:

            1. Increase the number of bits dynamically (python): not practical because not easy to implement in hardware.

            2. Error warning: not practical because way too frequent.

            3. Don’t do anything: e.g.: \(255_D + 1_D = 255_D\): Associativity doesn’t hold anymore \(255_D + (1_D - 1_D) = 255_D \neq 254_D = 255_D - 1_D = (255_D + 1_D) - 1_D\)

            4. (Cyclical) Modulo arithmetic, k bits => modulo-\(2^k\) (% in python):

              \(255_D + 1_D = 0_D\)

              advantages:

              1. very efficient in hardware => simply perform the operations where the overflow is ignored
              2. algebraic laws of basic operations still hold: associativity and commutativity

Elementary Operations

Elementary operations are ones that are defined for all data types:

  1. constructor:
  • create a new instance of a data type & allocate memory to it
  • the memory is initialized to a valid initial state. (otherwise we can’t be sure if operations performed on this object will deliver correct results)
  • in python the constructor has the same name as the data type: 
    • i = int(); f = float(); a = list()
i2 = int(7); f2 = float(10); b = [1, 2]
print("i:", i, "f:", f, "a: ", a)
print("i2:", i2, "f2:", f2, "b: ", b)
      i: 0 f: 0.0 a:  []
i2: 7 f2: 10.0 b:  [1, 2]
    • constructors for custom-data types (classes): the function __init__(self, ...) has to be implemented.
  1. destructor: deallocating the memory
  2. comparison operator (==). Two different equalities:

    • equal: same value / contents

    • identical: same object in the memory

    • comparing the identity of objects with id() or with is

      a = [1, 2]
b = [1, 2]
c = b
print("1:", id(a) == id(b))
print("2:", id(c) == id(b))
print("3:", a == b)
print("4:", id(c) == id(b))
print("5:", c == b and c == a)

print("6:", a is b or a is c)
print("7:", c is b)
      1: False
2: True
3: True
4: True
5: True
6: False
7: True

      c and b refer to the same memory location, different from the location of a. all of a, b, c have equal values; [1, 2].

    • consequense: value-semantics vs reference-semantics (see below)

Value-semantics vs Rerence-semantics

Analogy: Accessing a website:

  • value-semantics: store a copy of website.
    • advantage: we have control over the contents of the copy
    • disadvantage: possibly out-of-date.
  • reference-semantics: store the URL of the website
    • advantage: always up-to-date
    • disadvantage: no control over the content; possibly deleted.

What does it mean for programming languages, specifically for python:

  • value-semantics: data is copied and stored at another location (== is True and is is False)
  • reference-semantics: two varibles refer to the same location (both == and is are True)
  • In python all assignments use reference semantics, and in general python uses reference semantics

    • Example

      a = [1, 2]
b = a
a[0] = -1
print("1:", a, b);
print("2:", a is b)
      1: [-1, 2] [-1, 2]
2: True

      if we want to create another list object with a different identity but same value as a we use .copy() operator:

      a = [1, 2]
b = a.copy()
print("1:", a == b)
print("2:", a is b)
b[0] = -1
print("3:", a, b)
      1: True
2: False
3: [1, 2] [-1, 2]

      Elementary data-types like numbers or booleans are immutable by default, which gives the ‘illusion’ of reference semantics.

      a = 1
b = a
print("1:", a is b)
print("2:", a == b)
print("3:", a, b)
a = 2
print("4:", a is b)
print("5:", a == b)
print("6:", a, b)
      1: True
2: True
3: 1 1
4: False
5: False
6: 2 1

VL 4 - 24.04.2025

Containers - Data types

  • Containers contain other data.
  • Efficient & systematic managmeent of large amounts of data
  • Efficient repeated application of the same operation
  • Efficient & simple querrying (seeking) of data
  • Data structures are constructed hierarchically in all programming languages. (composite) Ex.: hierachically composing new structures from simple (atomic) ones
    1. natural numbers: atomic data type
    2. 3 numbers: RGBValue
    3. 1024 x 1024 RGBValue: Image
    4. Sequence of Images: Video

ADT Array

Array (list in python) is the most important / fundamental container data type:

  • Operation (pseudocode): a = new_array(size, initial_value)

    • interpretation: create an array with size elements all of which initially have initial_value as value

    • axioms:

      • precondition: -
      • postcondition: len(a) == size and for all i in [0,..., size - 1]: get(a, i) == initial_value

    • python:

      a = list() # empty array with size == 0
b = [3] * 10
c = [-1, 2, 3, 'c']
print(a, b, c, sep="\n")
      []
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
[-1, 2, 3, 'c']
  • Operation (pseudocode): k = len(a)

    • interpretation: number of elements in a

    • axioms:

      • precondition:
      • postcondition: k == size

    • python:

      a = [None] * 10
len(a)
      10
  • Operation (pseudocode): v = get(a, i )

    • interpretation: get the element at the position i

    • axioms:

      • precondition: 0 <= i <= size - 1 and v == element of a at position i
      • postcondition: len(a) == size and for all i in [0,..., size - 1]: get(a, i) == initial_value

    • python:

      a = [1, 2, 3]
v = a.__getitem__(2)
v = a[2]
print(a)
      [1, 2, 3]
  • Operation (pseudocode): set(a, i, v)

    • interpretation:

    • axioms:

      • precondition: 0 <= i <= size - 1
      • postcondition: get(a, i) == v

    • python:

      a = [-1, 2, 3]
a.__setitem__(1, 'c')
a[2] = 'd'
print(a)
      [-1, 'c', 'd']
  • Arrays store their elements consequtively => more efficient than other container types, since CPU’s process consecutive memeory cells faster.
  • python allows i < 0: -size <= i <= size - 1. Then:
    • Axiom: i < 0 => get(a, i) == get(a, len(a) - |i|)

Dyanmic arrays: here we simply give the operations

  • operation: append(a, v)
    python: a.append(v) # efficient in pyton
  • operation: append(a, other_array)
    python: a.extend(other_array) # efficient
  • operation: insert(a, i, v) inserts and elements after position i
    python: a.insert(i) # less efficient
  • operation: pop(a) (remove last eelment)
    python: a.pop() # efficient in python
  • operation: remove(a, i) (remove the ith element)
    python: a.pop(i) or del a[i]
  • operation: clear(a) delete everything
    python: a.clear() # now len(a) == 0

Associative Array

Associative arrays are called dictionary in python.

  • Main idea of assoc. arrays is that they allow arbitrary data structures as index.
    Ex.:
    • Immatriculation number as index: students[1234567] => "Alice Smith"
    • Strings as index, e.g. Name: `alda_grade[‘Bob Miller’]
    • In general: any data type that implements a hash function can be an nidex
  • Associative arrays are internally implemented as a dynamic array, where the index is computed by the hash function.

Stack

In python lists are automatically also stacks. (They can be used as stacks)
only the operations and python versions:

  • Operation: top()
    python: s[-1]
  • Operation: top()
    python: s[-1]
  • Operation: pop()
    python: s.pop()
  • Operation: push(s, v)
    python: s.append(v)