Algorithms and Data Structures
Master degree in Statistical Methods and Applications
academic year 2020-2021

• Introduction, material -- book, software -- exams
• Definitions: problem, instance, algorithm
• The concepts of "resource", "executor", "operation"
• Models of computation: RAM vs Pointer Machine
• Examples: find maximum, check duplicates

• Deriving the complexity of an algorithm: exact evaluation, best case, worst case
• Examples: find maximum, check duplicates
• Landau notations (O, Omega, Theta) to express complexity.
• Complexity of an algorithm: upper bound, exact bounds.
• Containment among simple classes of functions.
• How to derive complexity: code inspection.

• Complexity of algorithms vs. (intrinsic) complexity of problems.
• Lower bound for minimum/maximum selection, lower bound for comparison-based sorting algorithms

A brief introduction to Python language (see here for a basic textbook on Python)

• using the interpreter
• variables, expressions, assignments
• type conversions
• input() and print() functions
• using Thonny

A brief introduction (II) to Python language (see here for a basic textbook on Python)

• precedence between operators
• conditional statements, boolean expressions and operators
• lists, slicing on sequences
• while statement
• input() and print() functions
• defining functions with def
• exercises:
  • find maximum between 3 numbers
  • primality test in O(n) e O(√n)

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, matrix multiplication (Strassen algorithm)

Sorting via D&C: Merge Sort.

A brief introduction (III) to Python language (see here for a basic textbook on Python)

• for loop
• range()

Examples of recursive algorithms in Python

• factorial.py
• KaratsubaProduct.py
• mergeSort.py

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

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

Linear time k-th element selection algorithm, (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).

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 class headTailLinkedListClass.py.

Implementation of arrays, map functions for uni-dimensional and bi-dimensional arrays.

Dictionaries: time vs. space tradeoffs, trivial mapping from key to integers.

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

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

Managing deletions in open probing.

Resizing the hash table, doubling and halving the table. Amortized analysis for the number of (re)-insertions.

Trees: basic definitions. Binary trees.

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

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

Height of a binary tree: worst case and best case. Complete binary 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 bstNoRank.py (rank and print_tree methods must be written).

The implementation in bstNoRank.py must be modified as follows:

• nodes of the BST contain both a "key" value and an "info" value;
• items are organized according to the "key" value;
• insert operation has three parameters (self, key, info);
• search operation has only the (self, key) parameters, and returns the "info" value associated to "key";
• Delete operation has only (self, key) parameters;
• Rank operation has to be written;
• Print_tree operation has to be written.

Representing binary search trees with dummy leaves. An implementation is available in bstDummy.py

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. Insertion and pop_max operations. Complexity.

Implementation of heapify.

Building a heap in O(n) time

An implementation is available in prioritySimple.py

An example of use is in UsePrioritySimple.py

Implementation of heaps, with O(n) make_heap priority.py

Algorithm heap sort. Complexity analysis of heap sort. Implementation available in heapSort.py

Animation of several sorting algorithms can be seen at https://www.toptal.com/developers/sorting-algorithms

Graphs: definitions and basic properties

• directed, undirected
• sparse vs dense graphs
• multigraph
• subgraph, induced subgraph
• path, cycle, clique, bipartite, complete bipartite
• planar graph, embedding, faces
• characterization of planar graphs (Kuratowsky theorem)
• relation among the number of vertices, edges and faces of a (connected) planar graph

Graphs: definitions and basic properties

• transitive closure of a relation: reachability (directed, undirected) as transitive closure of edges
• connected graph, connected components
• directed graphs: strongly connected components
• acyclic graphs, DAGs, DAG of strongly connected components
• trees, forests
• number of edges in a tree
• spanning trees

Paths, simple paths, walks in a graph

Graphs traversals: Depth First search (DFS) and Breadth First search (BFS)

Pseudocode of DFS and BFS

DFS trees and BFS tree, BFS trees as Single Source Shortest Path (SSSP) trees for unweighted graphs.

Hamiltonian paths and Eulerian tours/paths: definitions.

Existence of Eulerian tours/paths by vertices degrees.

Complexity theory: definition of classes P and NP. The P vs NP conjecture.

Dictionaries in Python

Representing graphs: adjacency matrix vs. adjacency lists.

A Python class implementing graphs by dictionaries: basic version in basicGraphs.py

Exercise: add methods for deleting vertices or edges

Subclasses in Python, inheritance

Python implementations of BFS visit and DFS visit: Graph.py

See the recursive implementation of DFS visit and DFS tree in Graph.py

Single source shortest path trees for non-negative weighted graphs: Dijkstra algorithm.

Python implementation of Dijkstra's algorithm: updated version of Graph.py

Minimum spanning tree and minimum spanning forest.

Definition of cut. The cut rule.

Prim's algorithm.

Outline of Kruskal's algorithm and Boruvka's algorithm.

Python implementation of Prim's algorithm for minimum spanning forest: Graph.py

Complexity analysis of Kruskal's algorithm

Python implementation of Kruskal's algorithm for minimum spanning forest (same Python source code as above).