Algorithms Course Exercises - Vincenzo Imperati

A comprehensive collection of algorithm exercises covering fundamental computer science topics including graph theory, dynamic programming, divide and conquer, and combinatorial generation.

📋 Table of Contents#

Overview
Exercise Collections
Topics Covered
Setup and Usage
Exercise Descriptions
Contributing

🎯 Overview#

This repository contains 12 exercise sets (Esercitazioni 1-12) that cover essential algorithms and data structures concepts. Each notebook contains:

Problem statements in Italian
Algorithm explanations and approaches
Complete implementations in Python
Test cases and examples
Complexity analysis

📚 Exercise Collections#

Exercise Set	Main Topics	Key Algorithms
Esercitazione 1	Graph Theory, DFS	Strongly Connected Components, DAG Generation
Esercitazione 2	Graph Connectivity	Eulerian Paths, Bridge Detection
Esercitazione 3	Graph Traversal	BFS vs DFS, Distance Algorithms
Esercitazione 4	Shortest Paths	Dijkstra’s Algorithm, Path Counting
Esercitazione 5	Minimum Spanning Trees	MST Properties and Theorems
Esercitazione 6	Advanced Graph Algorithms	Semi-connected Graphs, Special Cases
Esercitazione 7	Divide and Conquer	Binary Search Variants, Array Problems
Esercitazione 8	Dynamic Programming I	Stock Trading, Matrix Problems
Esercitazione 9	Dynamic Programming II	Supersequences, Matrix Paths
Esercitazione 10	Dynamic Programming III	M-lists, Sequence/Multiset Problems
Esercitazione 11	Backtracking I	String Generation, Palindromes
Esercitazione 12	Backtracking II	Constraint Satisfaction, Matrix Generation

🔍 Topics Covered#

Graph Algorithms#

Traversal: Depth-First Search (DFS), Breadth-First Search (BFS)
Connectivity: Strongly Connected Components, Bridge Detection
Shortest Paths: Dijkstra’s Algorithm, Path Counting
Minimum Spanning Trees: Prim’s and Kruskal’s algorithms
Special Properties: DAG generation, Eulerian paths

Dynamic Programming#

Classic Problems: Longest Common Subsequence, Supersequence
Matrix Problems: Maximum submatrix, path finding
Optimization: Stock trading, sequence validation
Counting Problems: Valid sequences, multisets

Divide and Conquer#

Binary Search Variants: Fixed points, zeros in continuous arrays
Array Problems: Inversions, maximum finding
Mathematical: Integer square root, rotated arrays

Backtracking#

String Generation: Palindromes, constrained sequences
Combinatorial: Matrix generation with constraints
Optimization: Valid sequences with properties

🚀 Setup and Usage#

Prerequisites#

# Required packages
pip install networkx matplotlib jupyter

Running the Exercises#

# Start Jupyter notebook
jupyter notebook

# Or use Jupyter Lab
jupyter lab

Code Structure#

Each exercise follows this pattern:

# Problem description in markdown
# Idea/approach explanation
# Complete solution implementation
# Test cases and execution examples

📖 Exercise Descriptions#

Graph Theory Fundamentals (Exercises 1-6)#

Esercitazione 1: DFS and Graph Properties#

Edge Classification: Forward, backward, and cross edges in DFS
DAG Generation: Converting undirected graphs to DAGs
Principal Nodes: Finding nodes that can reach all others

Esercitazione 2: Graph Connectivity#

Complement Graphs: Proving connectivity properties
Eulerian Paths: Finding paths that traverse each edge exactly twice
Bridge Detection: Identifying critical edges

Esercitazione 3: BFS Applications#

Equidistant Nodes: Finding nodes with equal distance from two sources
Set Distances: Computing minimum distance between vertex sets
Tree Representations: Converting between different tree formats

Esercitazione 4: Shortest Path Algorithms#

Dijkstra Limitations: Why negative weights break the algorithm
Super-minimum Paths: Finding shortest paths with minimum edge count
Path Counting: Enumerating all shortest paths

Advanced Graph Topics (Exercises 5-6)#

Esercitazione 5: Minimum Spanning Trees#

MST Properties: Invariance under edge weight transformations
Minimum Edge Theorem: Every MST contains a minimum weight edge
Uniqueness: Conditions for unique MSTs

Esercitazione 6: Specialized Graph Problems#

Cycle Properties: Heavy edges never in MSTs
Binary Edge Weights: Special case shortest paths
Semi-connected Graphs: Efficient recognition algorithms

Divide and Conquer (Exercise 7)#

Esercitazione 7: Binary Search and Array Problems#

Fixed Point Detection: Finding indices where array[i] = i
Zero Finding: Locating zeros in continuous arrays
Integer Square Root: Computing floor of square root
Rotated Array Maximum: Finding maximum in shifted sorted arrays
Inversion Counting: Counting out-of-order pairs efficiently

Dynamic Programming (Exercises 8-10)#

Esercitazione 8: Classic DP Problems#

Stock Trading: Optimal buy/sell timing
Binary Matrix: Largest square submatrix of ones

Esercitazione 9: Sequence Problems#

Supersequence: Shortest sequence containing two subsequences
Matrix Paths: Longest increasing paths in matrices
Valid Sequences: Sequences with covering properties

Esercitazione 10: Advanced DP#

M-lists: Minimum value matrix sequences
Counting Problems: Sequences and multisets with given sums

Backtracking and Generation (Exercises 11-12)#

Esercitazione 11: String Generation#

Constrained Strings: Sequences with even-length ‘a’ blocks
Palindromes: Generating all palindromic strings
Distance Constraints: Sequences with minimum element separation
Matrix Generation: Sorted matrices with constraints

Esercitazione 12: Advanced Generation#

Parity Constraints: Strings with odd counts of each character
Occurrence Limits: Sequences with bounded element frequencies
Adjacency Constraints: Binary matrices without adjacent ones

🔧 Key Algorithms Implemented#

Graph Algorithms#

# DFS with edge classification
def DFS_with_classification(graph, start):
    # Implementation with tree, forward, back, cross edges

# Dijkstra's algorithm
def dijkstra(graph, start):
    # Complete implementation with distance tracking

# Strongly connected components
def tarjan_scc(graph):
    # Tarjan's algorithm for SCCs

Dynamic Programming#

# Longest common supersequence
def min_supersequence(X, Y):
    # DP solution for minimum supersequence

# Stock trading problem
def max_profit(prices):
    # Optimal buy/sell strategy

Divide and Conquer#

# Binary search for fixed point
def find_fixed_point(arr):
    # O(log n) solution

# Inversion counting
def count_inversions(arr):
    # Merge sort based counting

Backtracking#

# Generate constrained sequences
def generate_sequences(constraints):
    # Backtracking with pruning

📊 Complexity Analysis#

Each exercise includes detailed complexity analysis:

Time Complexity: Big-O notation for all algorithms
Space Complexity: Memory usage analysis
Optimality: Proof of optimal solutions where applicable

🤝 Contributing#

Contributions are welcome! Please:

Fork the repository
Create a feature branch
Add tests for new implementations
Ensure code follows the existing style
Submit a pull request

📄 License#

This project is licensed under the MIT License - see the LICENSE file for details.

🙏 Acknowledgments#

These exercises cover fundamental computer science algorithms and are designed for educational purposes in algorithm design and analysis courses.

Note: All problem statements are in Italian as they were originally designed for an Italian algorithms course. The implementations and comments include both Italian and English for accessibility.