Algorithms Course Exercises 📚

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:

1. Fork the repository
2. Create a feature branch
3. Add tests for new implementations
4. Ensure code follows the existing style
5. 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.