This repository contains solutions to various homework assignments for an algorithms course. The assignments are organized into directories by homework number (e.g., HW02, HW03).

This assignment focuses on graph algorithms.

This program finds the connected components of an undirected graph using Breadth-First Search (BFS).

To run:

1. Compile the C++ code: g++ first.cpp -o first
2. Provide the graph as input to the program, with the first line being the number of vertices and edges, followed by the edges. For example:

   4 3
   0 1
   1 2
   2 3
   

3. Run the program: ./first

This program finds the maximum size of an independent set in a graph. An independent set is a set of vertices in a graph, no two of which are adjacent.

To run:

1. Compile the C++ code: g++ second.cpp -o second
2. The program will generate several text files in the second/ directory, which are used by the Python scripts for visualization.
3. To visualize the output, you will need Python with matplotlib and networkx installed: pip install matplotlib networkx
4. Run the Python scripts:
   • python second/second.py to see the graph with the independent set colored.
   • python second/chart.py to see a 3D plot of performance data.

These programs find the strongly connected components (SCCs) of a directed graph. third_slide.cpp uses Kosaraju's algorithm, while third_tarjan.cpp uses Tarjan's algorithm.

To run:

1. Compile the C++ code: g++ third_slide.cpp -o third_slide or g++ third_tarjan.cpp -o third_tarjan
2. The programs will generate text files in the third/ directory, which are used by the Python scripts for visualization.
3. To visualize the output, you will need Python with matplotlib and networkx installed: pip install matplotlib networkx
4. Run the Python scripts:
   • python third/third.py to see the graph with the SCCs colored.
   • python third/chart.py to see a 3D plot of performance data.

This assignment covers dynamic programming.

This script solves the 0/1 knapsack problem using two different dynamic programming approaches: a top-down (memoization) approach and a bottom-up (tabulation) approach.

To run:

• python HW03/knapsack.py

This script solves the segmented least squares problem. It finds the optimal way to break a sequence of points into segments, where each segment is fit with a line, to minimize the total error plus a penalty for each segment.

To run:

• python HW03/segments.py
• The script will prompt for the number of points, and then the points themselves, one per line, with x and y coordinates separated by a space.