Data Structures and Algorithms for Engineers - Assignment Portfolio

This repository contains my solutions for five programming assignments from the 04-630: Data Structures and Algorithms for Engineers course. Each project implements custom data structures and algorithms in C/C++ to solve real-world problems, adhering to strict requirements such as no use of STL or generative AI, comprehensive internal documentation, and performance optimization. Below is a summary of each assignment, showcasing the problem tackled, the data structures used, and key features implemented.

Assignment I: Identifying Scanpaths and Saccades for Eye Trackers

• Objective: Analyze eye-tracking data to identify distinct fixation points and compute scanpaths and saccades for studying visual attention.
• Implementation: Designed custom data structures for fixation points (x, y coordinates, duration, timestamp) and implemented algorithms to:
  • Read and parse input from input.txt.
  • Sort fixation points by timestamp using a custom sorting algorithm.
  • Identify distinct fixation points based on spatial (Euclidean distance threshold) and temporal distinctness.
  • Generate scanpaths (sequence of distinct points) and saccades (movements between points with distance and duration).
  • Output results to distinct_fixations.txt, scanpath.txt, and saccades.txt.
• Key Features: Efficient memory management, handling up to 277 fixation points per scanpath, and producing aggregated durations for duplicate points. Included a technical report analyzing complexity and a reflection on optimizations.

Assignment II: Toll Booth Simulation

• Objective: Simulate a toll booth system to minimize vehicle wait times using dynamic booth management and prioritized vehicle processing.
• Implementation: Built custom queue and stack data structures to:
  • Simulate vehicle arrivals following a Poisson distribution with prioritized queuing (emergency vehicles first).
  • Manage toll booths dynamically via a stack, opening/closing based on queue length thresholds.
  • Process payments with varying times (cash: 7-10s, mobile: 5-6s, card: 2-4s; emergency: 2s).
  • Track and output vehicle metrics (ID, arrival/waiting/processing/dwelling times, type, payment method) to output.txt.
• Key Features: Handled multiple test cases, calculated aggregate metrics (e.g., average waiting time), and included a reflection report discussing Big O complexity and memory optimizations.

Assignment III: Text Analysis Using Binary Search Trees

• Objective: Analyze text files to compile alphabetically ordered word lists with frequencies and compute BST probe statistics.
• Implementation: Developed a case-insensitive binary search tree (BST) to:
  • Read words from multiple text files listed in input.txt.
  • Insert words into the BST, tracking frequency and level.
  • Traverse the BST in-order to output words, frequencies, and levels to output.txt.
  • Compute maximum and average probes per file for search operations.
• Key Features: Optimized for memory and time efficiency, handled case-insensitivity without STL, and included a reflection report on memory management and Big O analysis of BST operations.

Assignment IV: Sentence Structure Analysis Using Red-Black Tree

• Objective: Index and query sentence structures for NLP applications using a self-balancing red-black tree (RBT).
• Implementation: Created a custom RBT with nodes storing sentence length, sentences, count, and a custom metric (e.g., average word length), supporting:
  • Parsing sentences from input.txt using a student-specific delimiter.
  • Inserting sentences with balancing via rotations and color properties.
  • Searching by exact length and range queries for sentences and metrics.
  • Comparing RBT performance against a basic BST in performance.txt.
• Key Features: Handled edge cases (e.g., multiple delimiters), provided performance analysis, and included a reflection tying the implementation to a chosen real-world scenario (e.g., news summarization).

Assignment V: Sparse Matrix Operations

• Objective: Efficiently store and manipulate large sparse matrices for addition, subtraction, and multiplication.
• Implementation: Designed a custom data structure in SparseMatrix.h and SparseMatrix.cpp to:
  • Load sparse matrices from files specifying rows, columns, and non-zero entries.
  • Support operations (getElement, setElement) optimizing memory and runtime.
  • Handle input variations (e.g., whitespaces) and throw errors for invalid formats.
• Key Features: Achieved low memory footprint and fast operation times compared to reference implementations, with detailed internal documentation citing reused class code.

Each project includes comprehensive test cases in input.txt, output files, and CMakeLists.txt for building. Reflections and technical reports (where required) discuss optimizations, challenges, and algorithmic trade-offs, ensuring alignment with course goals of correctness, efficiency, and clarity.