Design and Analysis of Algorithms: Assignment 1

Implement convex hull algorithms with the help of C++ and Python

Basic Structures

It consists of two main packages

• Refactored Code: Optimized code to monitor performance
• Vizard Vision: The same code without performance gimmicks to visualize the performance of algorithms.

Algorithms Implemented

• Performance for Graham Scan
• Performance for Jarvis March
• Performance for Kirkpatrik Siedel

Instructions to run

The entry point for each packages is the corresponding main.cpp

Use the following command to compile

g++ main.cpp graph.cpp edge.cpp data.cpp node.cpp

taken from Dependency.txt

Run Visualization

You can run the Visualizations with the help of Vizard_Vizon/script.sh

  
#! /usr/bin/bash
g++ main.cpp graph.cpp edge.cpp data.cpp node.cpp
./a.out
python3 das_plotz.py

Test the Performance

You can test the performance with the help of Refactored Code/script.sh

#! /bin/bash
g++ main.cpp graph.cpp edge.cpp data.cpp node.cpp
./a.out

Link to the Performance Report

Authors

• Tanmay Kulkarni
• Aditya Srikanth
• Vishal Chokala