Vorlesungsseite: https://lec.inf.ethz.ch/math/informatik_cse/2024/
Vorlesungssckript: (provisorisch) [[infln.pdf]]
Prüfungsstoff: Vorlesungsinhalte, Handout, Übungen + Übungsstunden

Übungen

Prüfung

Todo

Lab

Zusammenfassung

Algorithm

Algorithmus: Handlungsweise zur schrittweisen Loesung eines Problems
3 Abstraktionsstufen:

  1. Kernidee (abstrakt)
  2. Pseudocode (semi-detailliert)
  3. Implementierung (sehr detailliert)

links vom Zuweisungoperatur is immer ein Ausdruck mit Adresse

r- & l-values

Auswertungsreihenfolge -> anzuwendende gueltige Reihenfolge in C++ nicht spezifiziert

a = (a/b) * b * a%b

increment

++expr -> pre-increment, returns new value
++expr -> post-increment, returns old value

binary numbers

binary -> prefix 0b
hexadecimal -> prefix 0x
octal -> prefix 0
unsigned int -> prefix 1u/`17u

int: B ≥ 16 ({2(B2),…,−1,0,1,…,2(B2)−1})
unsigned int: {0,…,2B−1}
overflow, underflow is undefined behaviour (for int)
overflow , underflow is modulo 2B (for unsigned int)

in mixed operations (uint, int), int gets converted to unit -> may return wrong results -> avoid uint

Conditionals

Vollständigkeitsbeweis

xor

(entweder .. oder)

x⊕y=(x∨y)∧¬(x∧y)
y = (x||y) && !(x && y)
y !=x

charakteristischer Vektor: f0111

können "verordert" werden
z.B.: f1011=f0011+f1000

int-bool conversion

-> schlechter Stil, nicht benutzen

Kurzschlussauswertung

z.B. x!= && z/x > y -> verhindert Division durch 0

Loops

for vs while

Note

redundanz ist schlecht

goto

Float, Double

literale:

#timestamp 2024-10-14

A Floating-point number system is defined by the four natural numbers:

Notation:

F(β,p,emin,emax)

IEE Standard 754

rules

  1. Do not test rounded floating-point numbers for equality.
  2. Do not add two numbers of very different orders of magnitude.
  3. Avoid the subtraction of numbers of similiar sizes

Tip

when calculating a sum, always start with the smaller numbers -> when starting with the large numbers, the smaller dissapear when rounding float/doubles

#timestamp 2024-10-21

code structuring

forward declaration, scope

function scope: the union of all scopes of its declarations (there can be more than one)

#include <iostream>
int f(int i); // Scope from here

int main() {
	std::cout << f(1);
	return 0;
}

int f(int i) {
	return i;
}

header files

namespaces

header file:

namespace informatik {
	double pow(double b, int e);
}

can be called like this:

#include <cmath>
#include "mymath.h"
int main() {
	double x = std::pow(2.0, -2); // <cmath>
	double y = informatik::pow(2.0, -2); // mymath.h
}

#timestamp 2024-10-28

Vectors

vector<int> fivezeros = vector<int>(5);
//The five elements of fivezeros are intialized with 0)
vector<int> fivetwos = vector<int>(5, 2);
//the five elements of fivetwos are initialized with 2
vector<int> countdown = {5, 4, 3, 2, 1};
//the vector is initialized with a list of values directly
vector<int> empty;
//Declares and initialises an empty vector
Warning

Accessing elements outside the valid bounds of a vector leads to undefined
behavior.

std::vector<int> a {1,2,3,4,5,6,7,8,9};
// append
a.push_back(10);
// read value
a.at(2)
a[2]
// check size of vector (unsigned int!!!!!!!)
a.size()
int(a.size()) // better
std::ssize(a) // cpp >= 20
// matrix
std::vector<std::vector<int>> m = {
{1, 0, 0, 0},
{0, 1, 0, 0},
{0, 0, 1, 0},
{0, 0, 0, 1}
};
// matrix init with rows, cols
int rows = ...;
int cols = ...;
std::vector<std::vector<int>> m;
m = std::vector<std::vector<int>>(rows, std::vector<int>(cols, 1));
// matrices do not have to be rectangular !!!
std::vector<std::vector<std::string>> cantons = {
{"ZH", "BE", "SG", "GE", "LU", "SO", "NE", "ZG"},
{"FR", "VD", "VS", "JU"},
{"AI", "OW", "NW", "AR", "BS", "BL"}
};
// type alias
using imatrix = std::vector<std::vector<int>>;
// auto init
auto all_ones_matrix = std::vector<std::vector<int>>(rows, std::vector<int>(cols, 1));

Reference types

A reference is an alias, an alternate name for an object. It is not an object itself (and in that way is not a pointer, even if some of their uses overlap with uses of pointers).

References have certain limitations to their handling, related to their non-objectness. For example, you can't create an array of references. They have to be initialized (bound, seated) as soon as they are declared, since they can't possibly exist without an object to alias.

You can however store them, and they obey the rules of automatic variables or member variables. One of their uses is to poke through C++'s pass-by-value function calls.

// T-reference (T being the type of reference)
T&
// initalization
int& darth_vader = anakin_skywalker;
darth_vader = 22; // effect: anakin_skywalker = 22
// must be initalised with an L-value
int& k = 5; // Error: literal 5 has no address
//
Reference Guideline

When a reference is created, the object referred to must “stay alive” at
least as long as the reference.

pass by reference vs pass by value

Say I want to share a web page with you. If I tell you the URL, I'm passing by reference. You can use that URL to see the same web page I can see. If that page is changed, we both see the changes. If you delete the URL, all you're doing is destroying your reference to that page - you're not deleting the actual page itself.

If I print out the page and give you the printout, I'm passing by value. Your page is a disconnected copy of the original. You won't see any subsequent changes, and any changes that you make (e.g. scribbling on your printout) will not show up on the original page. If you destroy the printout, you have destroyed your copy of the object - but the original web page remains intact.

void egvector<int>& vec {
...
}

std::vector<int> v = {0, 1, 2, 3};
eg(v)

int& egvector<int>& vec, int index {
	return vec[index];
}

std::vector<int> v = {0, 1, 2, 3};
std::cout << eg(v, 2);

const references

const T& r = lvalue;
// with r-value (compiler generates a temporary object with value of rvalue)
const T& r = rvalue;

#timestamp 2024-11-04

chars and strings

Character: Value of the fundamental type char

Zeichen -> {0, . . . , 127}
’A’, ’B’, ... , ’Z’ -> 65, 66, ..., 90
’a’, ’b’, ... , ’z’ -> 97, 98, ..., 122
’0’, ’1’, ... , ’9’ -> 48, 49, ..., 57

Text: std::string ≈ vector of char elements

#Declaration, and initialisation with a literal:
std::string text = "Essen ist fertig!"
#Initialise with variable length:
std::string text = std::string(n, ’a’)
# Comparing texts:
if (text1 == text2) ...
# Querying size:
int length = text.size();
# Size not equal to text length if multi-byte encoding is used, e.g. UTF-8
# Reading single characters:
if (text[0] == 'a') ... // or text.at(0)
# text[0] does not check index bounds, whereas text.at(0) does
# Writing single characters:
text[0] = 'b'; // or text.at(0)
# Iterating over characters
for (int i = 0; i < text.size(); ++i) std::cout << text[i];
# concatenate strings
text += ")";
' for char, " for string

recursion

#timestamp 2024-11-11

Recursive strategies

decrease and conquer divide and conquer
remove one element, one recursive call on remainder halving the elements, one recursive call per half
limitedly parallelizable oftentimes well-parallelizable
large recursion depth smaller recursion depth
Recursion vs Iteration

custom data types

struct

struct extended_int {
	// represents value if is_positive==true
	// and -value otherwise
	unsigned int value;
	bool is_positive;
};
# initalise
extended_int t; // member values uninitalised
extended_int t = {200, false}; // member-wise initalization
extended_int s = t; // member-wise copy
s = t; // member-wise copy

operator/function overloading

double sq(double x) { ... } // f1
int sq(int x) { ... } // f2

std::cout << sq(3); // compiler chooses f2
std::cout << sq(1.414); // compiler chooses f1

extended_int operator+ (extended_int a, extended_int b) {
	...
}

// minus
extended_int operator-
// increase
extended_int operator+=
// compare
bool operator==
// print
std::ostream& operator<<
// input
std::istream& operator>>

Information hiding

Encapsulation

idea:

Classes

class rational {
	public:
		# in-class member function
		# const member function (n cannot be changed via this function)
		int numerator() const {
			return n
		}
		# member function (n can be changed via the function)
		void set_numerator (int N) {
			n = N;
		}
		# user-defined conversion !!!
		operator double () {
			return double (n)/d;
		}
		# constructor
		rational (int num, int den)
			: n (num), d (den) {
			assert (den != 0);
		}
		# constructor with only one variable
		rational (int num)
			: n (num), d (1)
		{}
		# default constructor
		rational ()
			: n (0), d (1)
			{}
	private:
		int n;
		int d;
}

# out-of-class member function
# needs scope operator
int rational::numerator2 () const {
	return n;
}


# call cuonstructor directly...
rational r (1,2);
# or indirectly
rational r = rational (1,2);
# call empty constructor
rational r;

Containers, Iterators

=> container ("collection" in e.g. Java)

Iterators

# pointing to first element
it = c.begin()
# pointing __behind__ the last element
it = c.end()
# dereference operator (access to current element)
it*
# advance iterator by one element
++it

std::vector<int> v = {1, 2, 3};
for iterator it = v.begin(); it != v.end(); ++it {
	*it = -*it;
}

std::list<int> l = {0, 0, 0};

# sequential iteration
for iterator it = l.begin(); it != l.end(); ++it
	std::cout << *it; // prints 000
# also possible
for (int& e : l)
	e += 3; // modifies
for (int e : l)
	std::cout << e; // prints 333

llvec::const_iterator llvec::cbegin() const;
llvec::const_iterator llvec::cend() const;

const int& llvec::const_iterator::operator*() const;
...

#timestamp 2024-11-25
#timestamp 2024-12-02

Pointers

A cpp variable that stores the memory address of another variable.

int a = 42;
int* p = &a; // Pointer 'p' stores the address of 'a'
cout << *p;  // Outputs the value of 'a' (42)
*p = 100;    // Changes the value of 'a' to 100

int* p = new int(42); // Allocates memory for an int initialized to 42
delete p;            // Deallocates memory
Key notes

  • Always initialize pointers to prevent them from being wild pointers.
    • Use nullptr
  • For memory allocated with new, always use delete to prevent memory leaks.

pointer types

  1. Null Pointer (nullptr): A pointer that does not point to any valid memory address.
int* p = nullptr;
  1. Void Pointer (void*): A generic pointer that can point to any type but cannot be dereferenced directly.
void* ptr;
int a = 10;
ptr = &a;  // Allowed
  1. Dangling Pointer: A pointer that points to a memory location that has been freed or deleted. dangerous, leads to undefined behaviour, since the memory might contain totally different data=
int* p = new int(5);
delete p;  // 'p' becomes dangling
  1. Wild Pointer: A pointer that is declared but not initialized. dangerous, leads to undefined behaviour, since the pointer points to a random memory address
int* p;  // Uninitialized, points to a garbage location
  1. Constant Pointer: A pointer whose value (memory address it points to) cannot be changed.
int a = 10, b = 20;
int* const p = &a;  // 'p' always points to 'a'
  1. Pointer to Constant: A pointer to a variable whose value cannot be modified through the pointer.
const int a = 10;
const int* p = &a;

const pointer

int const p1;
//p1 is a constant integer
int const* p2;
// p2 is pointer to constant integer (read-only pointer to integer)
int* const p3;
// p3 is constant pointer to integer (non-changeable pointer to integer)
int const* const p4;
// p4 is constant pointer to constant integer (non-changeable read-only pointer)

smart pointer

alternative to [[#deconstructor, copy, assignment operator]]

using <memory>

std::shared_ptr<T> sp1 = std::make_shared<T>(...);
std::shared_ptr<T> sp2 = sp1;
std::cout << sp1.use_count(); // 2
sp1 = nullptr; // explicitly remove pointer sp1 to object
std::cout << sp2.use_count(); // 1
// if the number goes down to 0, the object gets deleted

cpp|using <memory>

dynamic data structures

idea: elements in list, which contain pointers pointing to the next element

-> idea behind linked list

deconstructor, copy constructor , assignment operator

alternative to [[#smart pointer]]

Rule of three

If a type (that manages dynamic memory) defines one of these structures, it needs to implement all three

  • Deconstructor
  • Copy Constructor
  • Assignment operator

GC cons

Garbage Collector (GC): in other programming languages, the GC takes care
of cleaning up old data

Data structures with shared objects need management

#timestamp 2024-12-09

dynamic memory

T* p = new T[expr] // new contiguous chunk of memory n elements of type T is allocated

delete[] expr // delete array, release memory

pointer arithmetic

// yields the address of the element
p
// yields the value of the element
*p
pointer arithmetic

  • pointer arithmetic operates in units of the size of the type pointed to. For example, if int is 4 bytes, incrementing a pointer increases its value by 4.
  • Pointer arithmetic is valid only within the bounds of an allocated memory block.

pointer iteration

char* p = new char[3]{'x', 'y', 'z'};

for (char* it = p; it != p + 3; ++it) {
	std::cout << *it << ' '; // x y z
}

for (int i = 0; i < 3; ++i)
	std::cout << p[i] << " ";

-> less efficient

CPP convention

#timestamp 2024-12-16

Note