This repository contains selected coding projects and homework solutions from my Algorithms (CSCI 3104) course:
1. Djkistra’s Shortest Path – Amazing Mazes:
For this project, I implemented Djkistra’s Shortest Path algorithm and used the OpenCV computer vision library to solve several mazes in the most efficient way. I was not allowed to use memoization to retrieve the shortest path, so my algorithm uses a priority queue that creates the nodes as it goes and later retraces the path to solve the maze.
2. Dynamic Programming:
Solved a number of puzzles, such as the minimum number of steps required to jump from 1 to n (with constraints), in incrementally time-efficient ways. For each problem, I first implemented a recursive solution, then applied memoization and recovered the sequence of steps of the minimal-cost solution.
3. Problem solving: AVL trees and Bloom Filters
On problem 1, I completed mathematical proofs by induction for AVL tree balancing rules. On problem 2, analyzed probabilities of false-positive and false-negative results on Bloom Filters, a space-efficient probabilistic data structure that uses hashing.
4. Problem solving: Graphs
Designed algorithms for solving 4 problems with graph data structures, applying shortest path algorithms such as Floyd–Warshall, Dijkstra and Bellman-Ford.
5. Problem solving: Quicksort and Binary Search Tree
On problem 1, analyzed complexity of the Median of Medians pivot selection method on the Quick Sort algorithm step by step, and applied the Akra-Bazzi method to prove it makes Quick Sort run in linear time. On problem 2, designed algorithms to recursively reconstruct a BST from an array of its nodes, previously created by a given form of traversal.
6. Sorting Algorithms in Python:
This project consists of a Python implementation of 4 sorting algorithms: Simple Sort, Bubble Sort, Merge Sort, and Quick Sort. The number of compare operations carried out by each algorithm is computed, and this number is used to plot the average and worst-case running times against input size. Complexity analysis discussion is included for each algorithm.
7. Trie autocomplete
Wrote a small program that uses a trie data structure to add, lookup and count the frequency of words in a dictionary, as well as auto-complete words based on the prefix entered.