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

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

• 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, lower 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
• Sorting without comparing: examples for sorting n elements in a universe U in Θ(n+|U|) time and Θ(|U|) space

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

• using the interpreter
• variables, expressions, assignments
• type conversions
• input() and print() functions
• the if: ... else: ... statement
• boolean expressions
• using Thonny

Thonny IDE for Windows, Mac or Linux, including a Python interpreter, can be downloaded here.

Lesson recording from 2021-2022 is available at this Zoom link Passcode: 1^6D#mUW
this video is for personal use only, and is restricted to students of Algorithms and Data Structures course of Statistics Dept., Sapienza.

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

• defining functions with def
• lists, slicing on sequences
• while statement
• for statement: scanning positions vs. scanning elements in a list

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

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).

Worst case 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.

Dictionaries: implementation via lists, sorted lists, arrays, sorted arrays.

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.

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.

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).

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

Rotations in binary search trees

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

The external memory model of computation: block transfer, I/O efficiency

B-trees and B*-trees: definition, height bound, searching in a B*-tree

Insertion and deletion in a B*-tree

Priority queues. Primitives.

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

Heaps: definition. Get_min and Insert operation

Heaps: delete_min operation, complexity of delete_min.

Implementation of heaps by lists

Implementation of heapify operation.

Building a heap in O(n) time: make_heap

An implementation is available in priority.py

An example of use is in UsePriority.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

Graphs: definitions and basic properties

• multigraph
• subgraph, induced subgraph
• path, cycle, clique, bipartite, complete bipartite
• connected graph, connected components
• trees, forests
• number of edges in a tree
• spanning trees
• 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
• directed graphs: strongly connected components
• acyclic graphs, DAGs, DAG of strongly connected components
• Hamiltonian paths and Eulerian tours/paths: definitions.
• Existence of Eulerian tours/paths by vertices degrees.
• Graphs traversals: Depth First Search (DFS) and Breadth First Search (BFS)

Dictionaries in Python

Representing graphs: adjacency matrix vs. adjacency lists.

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

Exercise: add methods for deleting vertices or edges

Pseudocode of BFS and DFS

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

Python implementations of BFS and DFS visit: Graph.py

Minimum spanning tree and minimum spanning forest.

The cycle rule for minimum spanning trees.

Outline of Kruskal's algorithm. Complexity of Kruskal's algorithm: O(m log n) variant.

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

Definition of cut. The cut rule for minimum spanning trees.

Prim's algorithm.

Code is available 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 using a min priority queue that implements primitive decrease_priority PriorityQueue.py

Complexity of Dijkstra's algorithm

The All Pairs Shortest Paths problem: relation to matrix multiplication.