AISD Semester 2: Data Structures and Algorithms

Overview

This repository contains solutions and comparative analyses for various data structures and algorithms implemented in C++. The focus is on performance evaluation and algorithmic efficiency.

Labs

Lab 1: Tree Structures Comparison

This lab implements and compares the efficiency of different types of trees:

1. Red-Black Tree
2. Binary Search Tree (BST)
3. AVL Tree

The lab includes implementations of insertion, deletion, and search operations for each tree type, and provides performance metrics for comparison.

Lab 2: Shortest Path Algorithms

This lab focuses on comparing the performance of different shortest path algorithms using various heap data structures:

1. Dijkstra's Algorithm (Standard Implementation)
2. Dijkstra's Algorithm with Fibonacci Heap
3. Dijkstra's Algorithm with Binary Heap

The lab evaluates the algorithms based on execution time for graphs with varying densities and sizes.

Lab 3: Compression Algorithms

This lab explores various data compression algorithms:

1. Huffman Coding (HA)
2. Run-Length Encoding (RLE)
3. Lempel-Ziv 78 (LZ78)
4. Burrows-Wheeler Transform (BWT)
5. Move-To-Front (MTF)
6. Arithmetic Coding (AC)
7. Prediction by Partial Matching (PPM)

The lab includes implementations and performance evaluations of these algorithms.

Coursework

Sudoku Solver

The coursework involves implementing a Sudoku solver using different algorithmic approaches. The solver aims to efficiently solve Sudoku puzzles of varying difficulty levels.

Requirements

• C++17 or higher
• A C++ compiler (e.g., g++, clang++)