Algorithms and Data Structures
Master degree in Statistical Methods and Applications
academic year 2023-2024

• Introduction, material -- book, software -- exams
• Definitions: problem, instance, algorithm
• The concepts of "resource", "executor", "operation"
• Examples: find max, check duplicates, subset sum, route finding
• The Russian Peasant multiplication algorithm

• Models of computation: RAM vs Pointer Machine
• Example: sorting on RAM vs. sorting on Pointer Machine
• The Turing machine, computability
• Deriving the complexity of an algorithm: exact evaluation, best case, worst case
• Examples: find maximum, check duplicates
• How to derive complexity: code inspection.

• Landau notations (O, Ω, Θ) to express complexity.
• Complexity of an algorithm: upper bound, lower bound, exact bounds.
• Containment among simple classes of functions.
• Complexity of algorithms vs. (intrinsic) complexity of problems.
• Sorting without comparing: examples for sorting n elements in a universe U in Θ(n+|U|) time and Θ(|U|) space

• Lower bound for minimum/maximum selection, lower bound for comparison-based sorting algorithms
• Divide and Conquer. Recursive implementation of D&C algorithms. Identify base cases, build subinstances, recursive calls, combine subsolutions.
• Complexity of & algorithms: recurrence equations.

• Master Theorem
• Integer multiplication, Karatsuba's algorithm
• Matrix multiplication, Strassen algorithm
• Sorting via Divide & Conquer: Merge Sort.
• Complexity analysis of Merge sort (find the code of Merge Sort here)

• Quick sort, analysis of quick sort: best case, worst case (find the code of Quick sort here).
• Randomized Quick Sort: analysis of average case.
• Quick sort vs. Merge sort: stability, in-place

Sorting algorithms animation https://www.toptal.com/developers/sorting-algorithms

Find here a code showing quick sort behaviour.

k-th element selection algorithm, complexity analysis (find the code of k-selection here).

Worst case linear time k-th element selection algorithm, Median of Medians (Blum et al., 1973)

The concept of Abstract Data Type. Information hiding.

Introduction to OO programming in Python.

Implementation of a simple class Number_set (find it in numModule.py), with an example of use (find it in useNumberSet.py).

The concept of Abstract Data Type. Information hiding.

Introduction to OO programming in Python.

Implementation of a simple class Number_set (find it in numModule.py), with an example of use (find it in useNumberSet.py).

The dictionary problem: time vs. space tradeoffs, trivial mapping from key to integers.

Implementation using lists, sorted lists, arrays, sorted arrays.

Efficiency of the in operator on Python list and Python dict

Sample code used by useSequence.py

1. an implementation using list: moduleSequence.py
2. an implementation using dict: moduleSequenceSmart.py
3. an implementation using set: moduleSequenceSet.py

Hash tables: definition, INSERT/SEARCH/DELETE operations. Hash functions, collisions. External chaining

Resizing the hash table, doubling and halving the table. Amortized analysis

Hash tables: external chaining vs open probing. Sequential/linear probing, quadratic probing, double hashing.

Managing deletions in open probing.

Cryptographic hash functions. Finding collisions by brute force

Pointer based structures: linked lists vs. Python lists (arrays)

Primitives on pointer based lists: insertion, deletion, search

Python implementation of linked lists linkedListClass.py. Use of linked lists in useLinkedList.py

Last In First Out (LIFO) and First In First Out (FIFO) policies: Stacks and Queues

Implementation of a stack by a linked list StackModule.py.

Implementation of a queue (FIFO) by a linked list QueueModule.py, uses module headTailLinkedListClass.py.

Rooted trees: basic definitions. Binary trees.

Height of a binary tree: worst case and best case. Complete binary trees.

Binary tree visits: pre-order, in-order, post-order visits.

Binary search trees: definition, searching in a binary search tree.

Searching in binary search trees.

Max, min, predecessor and successor search in binary search trees.

Insertion and deletion in a binary search tree.

Python implementation of Binary Search Tree.
Code available in bstFirst.py (some methods must be written).

Balanced trees with respect to size or height. Fibonacci trees

Python implementation of Binary Search Tree with dummy leaves.
Code available in bstComplete.py (with rank and print_tree methods)

Rotations in binary search trees

Red-black trees: definition, height of a red-black tree.

Rotations in binary search trees

Balanced trees: red-black trees. Definitions, insertions. Worst case performances.

Priority queues. Primitives.

Complexity of priority queues primitives on linked lists or balanced search trees

Heaps: definition. Get_min and Insert operation

Heaps: Pop_min operation, complexity of delete_min.

Implementation of heaps by lists