This repository contains my solutions for the 4 Assignments within the Course of Algorithms and Advanced Data Structures, 1DV516 at Linnaeus University (exchange semester via Erasmus+, 2nd year of studies, Autumn 2022). The assignments are organized into the following folders:
1. UnionFind - contains classes that implement Union (disjoint-set) data structures.
- Union Find (UF),
- Quick Union Find (QUF),
- Weighted Quick Union Find (WQUF) with weighting and path compression,
- Percolation Model based on WQUF, which uses Monte-Carlo method for estimating percolation threshold in a N x N grid.
2. Lists-Queues-Trees - contains classes that implement Linked-list, Queue and Tree data structures.
- Single-Linked List,
- Double-Ended Queue,
- Randomized Queue,
- Directory Tree, for listing files and folders inside a directory,
- BinarySearchTree (BST),
- AVL Balanced Tree.
3. HashTables-Sorting - contains a class with Hash table, as well as classes with implementations of Sorting algorithms.
- Insertion Sort,
- Heap Sort,
- Quick Sort,
- Merge Sort (recursive and iterative instances),
- Shell Sort (instances that use basic gap sequence, as well as sequences that work through Knuth's increments and Hibbard's increments),
- Counting Sort,
- Radix Sort.
- 4. Graphs - contains classes with various implementations of Graphs and algorithms used on them.
- Simple graph implementation using only edge lists (BasicGraph class),
- IGraph interface that implements Graph (unweighted, undirected) and Digraph (unweighted, directed) classes,
- IWGraph interface that implements WeightedGraph (weighted, undirected), WeightedDigraph (weighted, directed) classes,
- Edge class for creating edges used in WeightedGraph and WeightedDigraph classes,
- GraphIterator class for iterating through edge lists, adjacency lists and DFS/BFS paths,
- Depth-First Search (DFS and WeightedDFS classes),
- Breadth-First Search (BFS and WeightedBFS classes),
- Cycle-Finding Algorithm (CF and WeightedCF classes),
- Connected Components (CC and WeightedCC classes),
- Topological Sorting (TopoSort and WeightedTS classes),
- Strongly-Connected Components (Kosaraju's Algorithm) (SCC and WeightedCC classes),
- Kruskal's algorithm for minimum spanning tree/forest (Kruskal class, uses EdgeHeap class),
- Prim's algorithm for minimum spanning tree (Prim class),
- Shortest path in a Directed Acyclic Graph (SPDAG class),
- Dijkstra's algorithm for shortest paths and shortest path distances (Dijkstra class, uses Pair and PairHeap classes),
- Bellman-Ford's algorithm (BellmanFord class),
Apart from the listed classes, each folder has its own DriverClass for testing mentioned algorithms and data structures.