Algorithm Design & Optimization Projects

Description

This repository contains a comprehensive suite of Python scripts developed for a Design of Algorithms course. It provides robust solutions to a diverse set of algorithmic problems, bridging the gap between theoretical computer science concepts and practical implementation.

The project covers three main pillars of algorithm design:

1. Computational Geometry: Efficiently solving problems like the Closest Pair of Points and Convex Hull construction.
2. Graph Theory: Implementing custom traversal and shortest path algorithms for weighted and unweighted graphs.
3. Optimization & Data Science: Utilizing mathematical optimization for Support Vector Machines (SVM) to classify data.

Each solution is encapsulated in its own script, complete with input parsing and formatted output, making them ready for testing against competitive programming-style test cases.

Features & Problem Sets

This repository includes solutions for the following 7 specific challenges:

1. The Closest Pair (Divide & Conquer)

• File: q1.py
• Story: In the "Nemo" game, players are located on a 2D plane. To form optimal teams, we need to identify the two players who are closest to each other to pair them up.
• Use Case: Given a set of $n$ points with $(x, y)$ coordinates, find the minimum Euclidean distance between any two distinct points. The solution must be more efficient than the naive $O(n^2)$ approach, utilizing a Divide and Conquer strategy (typically $O(n \log n)$).
• Test Case:
  • Input:

    5
    1 4
    2 6
    5 6
    4 2
    7 3
    

  • Output:

    2.236
    

2. Hogwarts Navigation (Graph Algorithms)

• File: q2.py
• Story: Harry needs to sneak out of the Hogwarts dormitory to hunt unicorns at night. He has the Marauder's Map, which shows the dormitory as a graph of rooms and corridors. Guards patrol specific locations. Harry needs to find a path from his room to the exit that avoids guards or minimizes the probability of getting caught/time taken.
• Use Case: Given a graph where nodes are rooms and edges are corridors with weights (travel time), find the shortest path or determine reachability from a source node $S$ to a destination node $T$ under specific constraints (e.g., guard positions). This implements Dijkstra's Algorithm or BFS.
• Test Case:
  • Input:

    4 4
    1 2 2
    2 3 1
    1 3 5
    3 4 1
    1
    4
    

  • Output:

    4
    

3. The Valid Parentheses (Stack/String Processing)

• File: q3.py
• Story: A string of parentheses is provided. We need to check if the arrangement is valid. If it's invalid, we must find the "cost" to make it valid or identify the longest valid substring.
• Use Case: Analyze a string containing ( and ) characters. Determine if it is balanced. If not, calculate the minimum number of insertions/deletions required to balance it, or find the length of the longest valid parenthesis substring.
• Test Case:
  • Input:

    (()))
    

  • Output:

    4
    

    (Explanation: The longest valid substring is (()) which has length 4).

4. Graph Reconstruction (Graph Theory)

• File: q4.py
• Story: You are given a sequence of numbers representing the degrees of vertices in a graph. You need to determine if a valid simple graph can be constructed from this degree sequence.
• Use Case: This problem implements the Havel-Hakimi algorithm or a similar verification method to check if a given list of integers can represent the degree sequence of a simple graph.
• Test Case:
  • Input:

    5
    4 4 3 2 1
    

  • Output:

    NO
    

    (or the reconstructed adjacency matrix/list if YES).

5. Convex Hull Construction (Computational Geometry)

• File: q5.py
• Story: We have a set of points representing locations. We need to build a fence (boundary) that encloses all these points using the minimum perimeter.
• Use Case: Given a set of 2D points, compute the Convex Hull—the smallest convex polygon containing all points. This is typically solved using Graham Scan or Monotone Chain algorithms ($O(n \log n)$).
• Test Case:
  • Input:

    7
    0 3
    2 2
    1 1
    2 1
    3 0
    0 0
    3 3
    

  • Output:

    0 0
    3 0
    3 3
    0 3
    

6. Soft Margin SVM (Optimization/Machine Learning)

• File: q6.py
• Story: We have two classes of data points that are not perfectly linearly separable. We want to find the best line (hyperplane) that separates them while allowing for some misclassifications (soft margin) to maximize generalization.
• Use Case: Implement a Support Vector Machine (SVM) classifier from scratch or using cvxpy. The goal is to solve the quadratic optimization problem to find the weight vector $w$ and bias $b$ that maximize the margin while minimizing the slack variables $\xi$ (hinge loss).
• Test Case:
  • Input:

    5 3
    0 1 2 2 0
    1 2 2 3 2
    5
    3
    2
    4
    5
    1
    

  • Output:

    3
    1
    1
    1
    0
    

7. Unicorn Hunting (Tree Algorithms/Optimization)

• File: q7.py
• Story: Hagrid wants to help Harry find a unicorn hiding in the Forbidden Forest (represented as a tree). Harry can query a region (node). Hagrid will either say "Yes" (found) or point to the edge leading towards the unicorn. Each query costs 1 Galleon. Harry wants to minimize the worst-case cost to find the unicorn.
• Use Case: This problem is equivalent to finding the Tree Separator or Centroid Decomposition height. The goal is to find a query strategy (root of the query tree) that minimizes the maximum depth of the search, effectively ensuring $O(\log n)$ queries.
• Test Case:
  • Input:

    5
    1 2
    2 3
    4 3
    5 3
    

  • Output:

    2
    

Installation

1. Clone the repository:

   git clone [https://github.com/yourusername/Algorithmic-Design-Solutions.git](https://github.com/yourusername/Algorithmic-Design-Solutions.git)
   cd Algorithmic-Design-Solutions

2. Install dependencies: Most scripts use standard libraries, but the SVM problem (q6.py) and plotting scripts require specific packages.

   pip install numpy matplotlib cvxpy

Usage

Each problem is contained in a separate python file (q1.py to q7.py). You can run them directly from the command line. They are designed to accept input from stdin (standard input).

Example: Running the Closest Pair problem (q1.py)

1. Create an input file (e.g., input.txt) with the test case data:

   5
   1 4
   2 6
   5 6
   4 2
   7 3
   

2. Run the script piping the input:

   python q1.py < input.txt

Example: Running the SVM problem (q6.py)

python q6.py
# Paste input data into the terminal or pipe from a file

Contributing

1. Fork the repository.
2. Create a feature branch (git checkout -b feature/NewAlgorithm).
3. Commit your changes (git commit -m 'Optimized Dijkstra implementation').
4. Push to the branch (git push origin feature/NewAlgorithm).
5. Open a Pull Request.

License

This project is open-source. Please consult the LICENSE file for details (if available).

Contact

For questions or clarifications regarding the algorithms used:

• Maintainer: Nima Kelidari
• Email: kelidari.nima@gmail.com