In the CSC 301 course, we explored a variety of advanced data structures and algorithms, specifically focusing on pattern searching algorithms and binary tree structures. This project, developed in Java, aimed to compare the performance and efficiency of these algorithms and data structures in various scenarios.
A core component of this project was the implementation and performance comparison of different pattern searching algorithms. The algorithms studied include:
-
Knuth-Morris-Pratt (KMP) Algorithm
- An efficient string-matching algorithm that preprocesses the pattern to minimize unnecessary re-evaluations of the text, achieving linear time complexity relative to the text length.
-
Boyer-Moore Algorithm
- A pattern-matching algorithm that uses heuristics to skip sections of the text, thereby reducing the number of comparisons needed to find the pattern.
-
Brute Force Algorithm
- A straightforward approach to string matching that checks every possible position in the text for the pattern, serving as a baseline for comparison.
These algorithms were implemented using a Linked List to manage both the text and pattern data. The Brute Force algorithm was used as a benchmark to compare the performance of KMP and Boyer-Moore in terms of efficiency and time complexity.
In addition to pattern searching algorithms, the project also involved the implementation of various binary tree structures to explore their performance characteristics in terms of operations like insertion, deletion, and search. The tree structures implemented include:
-
Binary Tree
- A fundamental tree data structure where each node has at most two children. Basic operations such as insertion, traversal (in-order, pre-order, post-order), and search were implemented.
-
AVL Tree
- A self-balancing binary search tree where the height difference between the left and right subtrees is restricted to one. This ensures logarithmic height and improves the efficiency of search, insertion, and deletion operations.
-
Red-Black Tree
- A balanced binary search tree with specific balancing rules that ensure the tree remains balanced, thus guaranteeing logarithmic height for efficient search, insertion, and deletion operations.
The project includes comprehensive performance benchmarks for each of the algorithms and data structures implemented. The analysis focuses on comparing the time complexity and efficiency across various test cases. Key features of the analysis include:
-
Time Complexity Evaluation: A detailed examination of the time complexity for each pattern searching algorithm and tree operation, providing insights into the expected performance based on input size.
-
Benchmarking: Comparative performance tests for the KMP, Boyer-Moore, and Brute Force algorithms to assess efficiency across different pattern and text sizes. Additionally, the performance of the Binary Tree, AVL Tree, and Red-Black Tree was evaluated with respect to insertion, search, and deletion operations.
-
Custom Test Cases: A series of custom-designed test cases specifically created to validate the correctness and performance of each algorithm and data structure. These test cases aim to stress-test the algorithms and trees, ensuring robust and reliable performance.