University project of the course "ANALISI E PROGETTAZIONE DI ALGORITMI" of the computer science university of Genoa. The course was divided into two modules:

Module 1: Techniques, Graphs and NP-Completeness

In this module I studied:

• Asymptotic notations (Big O, Omega, Theta) and analysis of algorithms complexity
• Recurrence relations and substitutions method
• Proof of correctness of recursive and iterative algorithms
• Graph algorithms: representations, visits, Dijkstra, Prim, Kruskal, topological sorting, strongly connected components
• Dynamic programming, Longest Common Subsequence, Floyd-Warshall algorithm
• NP-completeness theory: decision problems, NP class, polynomial time reduction, examples of reductions

Module 2: Randomized Algorithms

In this module I learned about:

• Las Vegas algorithms: sorting, linear programming, game tree evaluation
• Monte Carlo algorithms: minimum cut, distributed consensus, primality testing, equality verification
• Connections with Game Theory

Course Labs and Assignments

This project includes code I wrote for course assignments and labs:

• Byzantine fault
• Implementations of classic graph algorithms and dynamic programming solutions
• Experimental analysis of sorting algorithms complexity
• Applying randomized techniques for primality testing and distributed consensus

Specifically, the labs covered:

Lab 2.1: Las Vegas algorithm for Quicksort

Lab 8.1: Miller–Rabin primality test

What I Learned

By completing this course, I strengthened my skills in algorithms analysis, design and implementation using various techniques. I gained solid knowledge of fundamental graph algorithms, dynamic programming, randomized methods and complexity theory that provide a base for advanced computer science topics.