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

• Introduction, material -- book, software -- exams
• Definitions: problem, instance, algorithm
• The concepts of "resource", "executor", "operation"
• Models of computation: RAM vs Pointer Machine
• Examples: find sum, route in a map, sort a sequence, solve a polynomial equation by bisection

• Introductory lesson given in 2020-2021 is available at this Zoom link Passcode: H42F6ug&
• the second part of today's lesson is available at this Zoom link Passcode: snTW=e^0

• 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|)
• Sorting by comparison in optimal time: Merge Sort

A brief introduction to Python 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 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, matrix multiplication (Strassen algorithm)

Sorting via D&C: 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).

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.

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

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

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

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. Implementation by arrays.

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

• Paths, simple paths, walks in a graph
• 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

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

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

Pseudocode of 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.

Python implementations of BFS visit: Graph.py (DFS and the subclass concept will be discussed in next lesson)

Subclasses in Python, inheritance

Python implementations of 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 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.

Minimum spanning tree and minimum spanning forest.

Definition of cut. The cut rule.

Prim's algorithm.

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

Code is available in Graph.py

Python implementation of Kruskal'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).

Description and complexity of Boruvka's algorithm

Basic notions on symmetric and asymmetric cryptography. Digital signatures, public key certificates.