Algorithms in AI and Data Science 1 (AKIDS 1)

Course Description (English and German)

*English*

Content: Introduction to algorithms and algorithmic thinking, introduction to Artificial Intelligence and Data Science; Algorithms fundamentals (building blocks, determinism, functional vs. imperative paradigm); Core data structure (lists, sets, stack, queue, heap), together with programming basics (in Python); Algorithmic complexity: time and memory complexity, growth of functions, asymptotic notation and "Big-O"; Sorting (bubble, insert, heap, merge and quick sort) and order statistics algorithms; Advanced Data Structures with associated algorithms: Hashtables (and hashing functions), Trees (binary search tree, red-black trees), and Graphs (connected components, shortest path, minimum spanning tree); Algorithm design and recursion; Dynamic programming; State space search: uninformed (depth/breadth first search), heuristic (A* algorithm), adversarial (MiniMax, Alpha-Beta pruning) and metaheuristic search (genetic algorithm, ant colony optimization); Function optimization (convex vs. non-convex optimization, numeric optimization with gradient descent) and constrained optimization algorithms (linear and quadratic programming, branch-and-bound algorithm); Learning from data: lightweight introduction to machine learning (parametric and non-parametric classification models, clustering);

Learning outcome: Students will obtain fundamental knowledge on algorithms and data structures used throughout computer science, with a special focus on fundamentals alghorithms of artificial intelligence and data science (e.g., state space search or optimization). They will obtain both theoretical and practical knowledge (as they will be required to implement most of the covered algorithms). They will be able to analyse practical problems from an algorithmic perspective, identify the type of the problem, and choose an optimal algorithmic approach to solving it. In this course, the students will obtain fundamental algorithmic knowledge that they will extend and build upon in the rest of the study program.

*German*

Inhalt: Einführung in Algorithmen und algorithmisches Denken, Einführung in Künstliche Intelligenz und Data Science; Grundlagen der Algorithmen (Bausteine, Determinismus, funktionales vs. imperatives Paradigma); Kerndatenstrukturen (Listen, Mengen, Stack, Queue, Heap), zusammen mit Grundlagen der Programmierung (in Python); Algorithmische Komplexität: Zeit- und Speicherkomplexität, Wachstum von Funktionen, asymptotische Notation und "Big-O"; Sortierung (Bubble, Insert, Heap, Merge und Quick Sort) und Algorithmen der Ordnungsstatistik; Fortgeschrittene Datenstrukturen mit zugehörigen Algorithmen: Hashtabellen (und Hash-Funktionen), Bäume (binäre Suchbäume, Rot-Schwarz-Bäume) und Graphen (zusammenhängende Komponenten, kürzester Pfad, minimaler Spannbaum); Algorithmenentwurf und Rekursion; Dynamische Programmierung; Zustandsraumsuche: uninformierte (Tiefe/Breite erste Suche), heuristische (A*-Algorithmus), adversarische (MiniMax, Alpha-Beta-Beschneidung) und metaheuristische Suche (genetischer Algorithmus, Ameisenkolonieoptimierung); Funktionsoptimierung (konvexe vs. nicht-konvexe Optimierung, numerische Optimierung, numerische Optimierung mit Gradientenabstieg) und eingeschränkte Optimierungsalgorithmen (lineare und quadratische Programmierung, Branch-and-Bound-Algorithmus); Lernen aus Daten: leichte Einführung in maschinelles Lernen (parametrische und nicht-parametrische Klassifikationsmodelle, Clustering);

Lernergebnis: Die Studierenden erwerben grundlegende Kenntnisse über Algorithmen und Datenstrukturen, die in der gesamten Informatik verwendet werden, mit besonderem Schwerpunkt auf den Grundlagen der Algorithmen der künstlichen Intelligenz und der Datenwissenschaft (z.B. Zustandsraumsuche oder Optimierung). Sie werden sowohl theoretische als auch praktische Kenntnisse erwerben (da sie die meisten der behandelten Algorithmen implementieren müssen). Sie werden in der Lage sein, praktische Probleme aus einer algorithmischen Perspektive zu analysieren, die Art des Problems zu identifizieren und einen optimalen algorithmischen Ansatz zur Lösung des Problems zu wählen. In diesem Kurs erwerben die Studierenden grundlegende algorithmische Kenntnisse, die sie im weiteren Verlauf des Studiums erweitern und ausbauen werden.

Detailed Content and Course Plan

=====================================================================================================
Block I: ADS Fundamentals
=====================================================================================================
> Week 1: 
	V1.  Introduction
		-> What are algorithms, data structures? What is AI & DS? Brief history of AI
		-> Course structure and organization
	V2. Algorithms: fundamentals
		-> Building blocks of algorithms (operations, conditions, loops, recursion, subprograms)
		-> Determinism in algorithms, functional (applicative) vs. imperative algorithms/programming
	Ü. Introduction to Python 
	   -> Setup (Jupyter notebook or Colab)
	   -> Python basics (operations, atomic data types, loops, conditions, functions)

> Week 2: 
	V1. Programming basics
		-> Programming paradigms
		-> Basics of OO and imperative programming
	V2. Core Data structures 
		-> Lists, Sets, Stack (LIFO), Queue (FIFO), Heap
	Ü. Data structures in Python:
		-> Implement own, e.g., stack/queue (classes with methods, practicing OO design in Python)
		-> Use/cover existing Collections in Python

> Week 3: Algorithm Complexity & Sorting
	V1. Complexity and running time analysis
		-> Time and memory complexity, growth of functions, asymptotic notation and “Big-O”
		-> sorting as running example for complexity (insert sort)
	V2. Sorting
		-> Heap sort, merge sort, quicksort
		-> Running times of sort algorithms: best, average, worst
		-> Order statistics algorithms (?)
	Ü. Sorting in Python
		-> Implement sorting algos
		-> Compare execution times: for different (best, worst, avg) sorting tasks
		-> Compare own implementations again built-in Python sorting functions
	
> Week 4: Advanced Data Structures I 
	V1. Hashing
		-> Hashing functions, hashtables
	V2. Trees
		-> Binary search tree
		-> Red-black trees
	Ü. Hashing & Trees implementation
		-> Implement an own hashtable class, compare against Python's dictionary
		-> Search with a binary tree / balanced tree

> Week 5: Graphs (Advanced DS II)
	V1. Graphs: introduction 
		-> types and representations of graphs
		-> Elementary algorithms: BFS, DFS
	V2. Some prominent algorithms on graphs
		-> Connected components
		-> Shortest path: Dijkstra
		-> Minimum spanning trees
	Ü. BFS/DFS & Dijkstra
		-> BFS & DFS on toy examples on paper and implement in Python
		-> Implement Dijkstra, on paper exercises with Dijkstra

> Week 6: Algorithms design
	V1. Algorithms design
		-> Step-by-step algorithms, complete enumeration, greedy, divide & conquer, backtracking and DP
	V2. Divide-and-conquer: Recursion
		-> Recursion with examples
		-> Max. subarray problem, Strassen's matrix multiplication
	Ü. Recursion exercises (in code)
	
> Week 7: Dynamic programming
	V1. Properties of problems that call for DP
		-> Elements of dynamic programming
		-> Rod-cutting as the running example
		-> Recursive vs. matrix-based DP
	V2. Popular DP Problems
		-> Knapsack
		-> Edit distance
		-> Longest common subsequence
	Ü. Implement DP solution for Edit distance
		- a) top-down recursively
		- b) bottom-up with a matrix

=====================================================================================================
Block II: KI & DS Algorithms
=====================================================================================================

> Week 8: State space search I
	V1. Uninformed search
		-> State space search problems, DFS & BFS recap
		-> Depth-limited search, iterative deepening, bidirectional search
	V2. A* search
		-> Greedy search, A* algorithm
		-> Heuristics in A*
	Ü. Implement A* solution for a concrete problem
	
		
> Week 9: State space search II
	V1. Adversarial search
		-> MiniMax
		-> Alpha-Beta pruning
	V2. Metaheuristic search
		-> Genetic algorithm
		-> Ant colony optimization
	Ü. Minimax and GA implementation
		-> Implement minimax (e.g., for criss-cross)
	
> Week 10: Optimization
	V1. Function optimization
		-> Convex vs. non-convex function, global vs. local optima
		-> Gradient descent, Newton method
	V2. Constrained optimization algorithms
		-> Linear programming, quadratic programming
		-> Branch-and-bound
	Ü. Implement (S)GD and optimize a few functions with it
		
> Week 11: Learning from data
	V1. Introduction to ML
		-> Predictive problems, limitations of imperative algorithms
        -> Classification vs. regression, supervised vs. unsupervised learning, parametric vs. non-parametric models
	V2. Classification: parametric
		-> Linear regression (regression)
		-> logistic regression (classification)
	Ü. Implement training and inference with Logistic Regression
		-> Use the SGD implementation from 8
		
> Week 12. Learning from data
	V1. Classification: non-parametric
		-> k-NN
		-> Decision trees
	V2. Clustering
		-> K-means
		-> Hiearchical agglomerative clustering
	Ü. Implement k-NN and K-means
		-> Let them fill A vs. B survey and then cluster them based on that