Algorithms-DataStructures

Algorithms and Data Structures I have coded in some of my college degree courses

How to use

To clone and run this projects at least you need Git, a C++ compiler like g++, and Python3 with pip installed on your computer.

Clone this repository

https://github.com/samueldiaz1004/Algorithms-DataStructures.git

Change directory

cd LinkedList

Compile all the cpp files in the directory

g++ -o linkedList.exe MyLinkedList.cpp main.cpp 

Run the executable created

./linkedList.exe

Table of contents

• Annealing
  • A probabilistic technique for approximating the optimal solution for NP-hard problems, in this case for the traveling salesman problem.
• BST
  • Implementation of a binary search tree that can perform basic insertion, traversal and searching operations.
• Backpack
  • A solution of the 0-1 Knapsack problem using dinamic programming.
• CoinChange
  • Implementation and comparison of the dynamic and greedy algorithm to solve the coin change problem.
• Compilation1
  • Substring search between two strings using the Knuth-Morris-Pratt algorithm.
  • Find the longest palindrome in a string using the Manacher algorithm.
  • Use dynamic programming to find the longest common substring between a pair of strings.
• Compilation2
  • Find the minimum spanning tree in a completly connected graph without cicles using Prim's algorithm.
  • An approach to solve the traveling salesman problem using the Repetitve Nearest Neighbor technique.
  • Calculate the max flux from a starting to an ending node in a directed graph via the Ford-Fulkerson algorithm.
  • Map a collection of points in a 2d space and generate a Voronoi graph to determine the closest point to a new entry.
• FaceTriangulation
  • Application to map a subjects face from a face detection model and then represent using Voronoi graph and Delaunay triangulation.
• Graph
  • A directed graph represented by a 2d array with DFS and BFS traversal options.
• HashTable
  • Implementation of a hash table using using a linked list to store keys and values, it can perform read and write operations and rehash in function of a load factor.
• Heap
  • Implementation of a max heap using an array that can expand periodically.
• LinkedList
  • Implementation of a single linked list that can perform basic insertion, traversal and searching operations.
• Maze
  • Implementation and comparison of the backtracking and branch and bound technique to find the solution to a maze.
• ShortestPath
  • Implementation and comparison of the Dijkstra and Floyd algorithm to find the shortest path between vertices.
• Sort&Search
  • Implementation of some of the most common searching (lineal and binary) and sorting (insertion, bubble and merge) algorithms.

Troubleshooting

Some projects like FaceTriangulation and Compilation2 require the installation of extra libraries, notably CGAL. You can install it via a C/C++ package manager and added the necesary libraries to the project using Cmake or Visual Studio (recommended for Windows users).