Skip to content

Latest commit

 

History

History
46 lines (40 loc) · 4.01 KB

README.md

File metadata and controls

46 lines (40 loc) · 4.01 KB
Raw

Algorithms and Advanced Data Structures

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.