Algorithms¶
Teaching material conceived and developed by Fabio Furini, associate professor at DIAG, Sapienza University of Rome.
The course lecture notes, online, in five parts: basic algorithms (representation of numbers, pseudo-code, sorting, searching, numerical algorithms), programming languages (C++, Python and Java), asymptotic notation and growth, analysis of algorithms (running time and correctness), and recursion (recurrence relations, the Master Theorem and recursive algorithms), with definitions, theorems with their proofs, pseudo-code, examples executed step by step, Colab notebooks in Python, C++ and Java and exercises with solutions.
Start with the basic algorithms The exercises Explore the interactive lab Download the lecture notes (PDF)
How each chapter is organized¶
Each chapter is one of the course notes, with the same numbers and the same colors as the lecture notes: on the website and in the PDF you find everything in the same place.
Definition
The precise meaning of a new concept.
Theorem, proposition, observation
A result to remember, with its hypotheses.
Example
A computation worked out in full, one step at a time.
In green the key point to take away.
Algorithm
The pseudo-code, with the lines numbered as in the lecture notes.
Code
The programs in C++, Python and Java in the chapters on the languages; the algorithms run in the Colab notebooks, with the buttons below the pseudo-code.
Proof — opens with a click
All proofs are included, but folded: first read the statement, then open the proof when you want to study it. The same holds for the solutions of the exercises.
The parts of the course¶
-
1 · Basic algorithms
The representation of numbers and pseudo-code, the language in which all the algorithms of the course are written; the first algorithms: sorting (insertion, exchange and selection sort), linear and binary search, numerical algorithms (change of base, primality test, sieve of Eratosthenes, greatest common divisor). Every algorithm with its pseudo-code and examples executed step by step.
1. Representation of numbers · 2. Pseudo-code · 3. Sorting algorithms · 4. Linear and binary search · 5. Numerical algorithms
-
2 · Programming languages
From pseudo-code to programs: three programming languages, C++ (compiled), Python (interpreted) and Java (compiled to bytecode and run by a virtual machine). For each: variables and data types, input and output, operators, conditional statements, loops, arrays and lists, functions, bitwise operators and a complete algorithm, with the comparison of the three languages.
6. Introduction to C++ · 7. Introduction to Python · 8. Introduction to Java
-
3 · Asymptotic notation and growth
How the functions of a natural variable that count the steps of an algorithm are compared: the asymptotic notations Theta, big O, Omega, little o and omega, their properties and the limit criterion; then the families of increasing functions (logarithms, powers, exponentials, factorial), the hierarchy of infinities and the comparison of orders of growth written with the symbols. Limits and functions of a natural variable are taken from the course of Mathematical Analysis 1.
9. Asymptotic notation · 10. Asymptotic growth
-
4 · Analysis of algorithms
The analysis of algorithms: the input size, the running time in the best, worst and average case, and correctness proved with loop invariants.
11. Input size · 12. Running time · 13. Correctness
-
5 · Recursion
Recursion: classical recursive algorithms, recurrence relations, the Master Theorem, recursive algorithms (array sum, merge sort, binary search, maximum subarray) and the comparison between recursive and iterative versions.
14. Recursion · 15. Recurrences · 16. The Master Theorem · 17. Recursive algorithms · 18. Recursive versus iterative algorithms
Don't miss¶
-
Exercises with solutions
Exercises for every chapter, each with a worked solution that opens with a click.
-
Interactive lab
Run the algorithms one step at a time: sorting, searching, Euclid and the sieve, the bits of numbers, growth of functions, recursion trees and the Master Theorem.
-
Notebooks in Python, C++ and Java
The algorithms of every chapter, to run in Google Colab in the language you prefer.
-
Lecture notes and exercise books in PDF
Five volumes of lecture notes and five exercise books, with the same numbering as the website.
-
Full index
All chapters with their sections, on one page.
By the same author:
- Linear Programming — polyhedra, the simplex algorithm, duality and the dual simplex, with the interactive lab;
- Convex Optimization — convex sets and functions, convex optimization problems, with interactive graphs;
- Integer Linear Programming — LP relaxation, valid inequalities, cutting planes, branch-and-bound and branch-and-cut;
- Combinatorial Optimization — knapsack, bin packing, coloring, TSP, scheduling and lot sizing, solved in every way;
- Network Optimization — graphs, spanning trees, shortest paths, network flows, the network simplex and project management;
- MIP Modelling — integer linear programming models, from the formulation to the solution with solvers;
- Operations Research Lab — modelling and solving optimization problems with Python and solvers;
- Mathematical Analysis 1 — real numbers, functions, limits, derivatives and series, with interactive graphs;
- Linear Algebra — vectors, matrices, determinants, linear systems and eigenvalues, with the computation lab.
Teaching material by Fabio Furini — DIAG, Sapienza University of Rome.
This website is also available in Italian.
Additional teaching materials, including lecture slides, will be added soon.