Algorithms Homework

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).

Homework 2

This assignment focuses on graph algorithms.

first.cpp

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

second.cpp

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.

third_slide.cpp and third_tarjan.cpp

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.

Homework 3

This assignment covers dynamic programming.

knapsack.py

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

segments.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.