Team-Lime-Algorithms

Comparing Knapsacks Experiment

About The Project

This project was developed for students operating in the same team together to demonstrate their proficiency in creating algorithms for knapsack implementations as well as test and analyze the efficiencies of the algorithms. Six Knapsack algorithms have been developed, and an experiment was preformed to analyze the runtimes of these algorithms. With the accumulated and visualized data users can compare the empirical results of the data to theoretical results of the algorithms performance.

Author: Authors
Course: Analysis of Algorithms CSB302
Intructor: Eric Lloyd
Project #: 2

Built With

List of major frameworks and libraries used for the development of this project

• Visual Studio Code Version: 1.108
• Python Version: 3.1
• Ipython version: 8.30
• Jupyter Version: 2025.9.1
• Matplotlib Version: 3.10

Environment Setup

1. Clone or download the project to your local machine

2. Navigate to the root of the project directory

3. Create the environment from the environment.yml file:

   conda env create -f environment.yml

4. Activate the environment:

   conda activate knap_exp_env

5. Verify installation by checking Python version:

   python --version

   Should display Python 3.13.x

Updating the Environment

If dependencies change, while in the environment run:

conda env update -f environment.yml

Deactivating the Environment

When finished working:

conda deactivate

Project Organization

Project1/
   Documents/                           # Contains images, Student design implementation folders, and Images
      images/                           # Contains images used troughout the project 
   Git Screenshots/                     # All screenshots of student git usage
   Input CSVs                           # All provided and generated CSV files to injest
   src/                                 # Holds all files related to the project construction and operation
      algorithms/                       # Folder containing all algorithms
         fractional/                    # Holds all fractional knapsack files
            bea_fractional_knapsack.py  # Bea's fractional knapsack functions
            bruno_brute_force.py        # Bruno's brute force fractional knapsack
            bruno_greedy.py             # Bruno's greedy fractional knapsack
         knapsack_01/                   # Holds all 01 knapsack algorithms
            elton_knapsack_01           # Elton's 01 knapsack algorithm
            Kainen_knapsack_01          # Kainen's 01 knapsack algorithm
      csv_generator.py                  # Program to randomly generate knapsack CSV files
      csv_parser.py                     # Function to ingest CSV files and retrun them as a dictionary
      metric_calculator.py              # Function to print final results of knapsack algorithms
   result.ipynb                      # Main file that prints algorithmic visualizations
    gitignore                           # File of directories for git to ignore
    CONTRIBUTING.md                     # List of all teammates contributions to the project
    README.md                           # Description of the Project
    environment.yml                     # Conda environment configuration

Usage

• Note the algorithm may take over two hours to produce final results.

1. Navigate to the results.ipynb file

2. With your environment already installed, as described in Environment Setup, navigate to the kernel selector, and select knap_exp_env

3. Select "Run All" in the center ribbon of the program to activate all markdown reports, generate algorithm data, visualize algorithm data, and display exploritory analysis conducted by the programs authors.

4. Review our conducted analysis.

Operation of the Program

• csv_generator.py This file contains two function and a main method to run both. create_csv() takes a file number and an array size as an input. Once the function runs, a CSV document is produced and placed into the "Inputs CSV" folder. The csv document will contain the file number, a randomly generated capacity, and two randomly generated arrays in the size thats given to the function. The two arrays sybolizing a row of weights and a row of values. Produce_csv_files is an overarching function that calls the create_csv() function with specified parameters.

• csv_parser.ipynb This file contains the parse_csv() function. This function is used within the algorithms we developed. It's goal is to take a file_path as an input, and parse the lines of the specific type of file given, converting it into a dictionary to iterate off of. These specified CSV files must contain the file number and capacity in the first row, a row of ints representing weights, and a row of ints representing values.

• metric_calculator.py This file contains two functions, test_algorithms, and calculate_metrics. Calculate_metrics() takes a list of algorithmic functions and a csv file as an input. The function then runs each algorithm, injesting the csv data into the algorithm, timing the algorithms runtime, and outputting the all metrics calculated. These metrics being knapsack numbers, capacities, values and weights passed in, and the best result calculated from the algorithm. Test_algorithm() also injests a list of algorithms and csv files then calls the calculate_metrics() function, and returns the results

• results.ipynb This is the main file used to run and visualize our algorithmic data. The first portion of the file calls the metric calculator on all of our chosen algorithms, and displays the best calculated data. The second portion of the main file develops a plot_size_time and plot_profits function that calls the results generated from the first section and visualizes all of the calculated metrics.

• testing.py This file is used my our contibutors to test all developed algorithms and ensure proper functioning. Tests can include initializeng files, and ensuring all algorithms and functions are performing accurate calculations.

Authors

Name	Role(s)	Username
Bea Sauve	Code Developer, Analysis Auditor	bunnybea83
Bruno Christensen	Code Developer, Development Manager	brunochristensen
Elton Nichols	Code Developer, Project Manager	oi12bu
Kainen Osborne	Code Developer, Version Control Manager	kosborne00

Team Video