Mastering Sorting, Stacks, Queues, HashTables, BSTs, and Graph Traversal: A Comprehensive CSCI 251 Study Guide

Introduction to CSCI 251 Projects

Welcome to this comprehensive study guide for CSCI 251 projects one through five. In this tutorial, you will learn how to implement fundamental data structures and algorithms in Java, including sorting algorithms, stacks, queues, hash tables, binary search trees, and graph traversals. These projects are designed to reinforce key concepts from your textbook and prepare you for real-world programming challenges. Let's dive into each project step by step.

Project One: Sorting Algorithms

The first project requires you to implement four classic sorting algorithms: Insert Sort, Select Sort, Quick Sort, and Merge Sort. You will create a class called MySort.java with the specified public methods. These algorithms are essential for organizing data efficiently, whether you're sorting a leaderboard for a gaming tournament or arranging student grades.

Insert Sort

Insert Sort builds the final sorted array one element at a time. It is efficient for small datasets and works like sorting a hand of playing cards. Here's a simple implementation:

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Select Sort

Select Sort repeatedly finds the minimum element from the unsorted part and puts it at the beginning. It's simple but not suitable for large datasets.

public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

Quick Sort

Quick Sort is a divide-and-conquer algorithm that picks a pivot and partitions the array. It's widely used in practice, similar to how social media algorithms quickly rank trending posts. Implement the recursive version with a pivot method:

private static int pivot(int[] arr, int begin, int end) {
    int pivotVal = arr[begin];
    int left = begin + 1;
    int right = end;
    while (true) {
        while (left <= right && arr[left] <= pivotVal) left++;
        while (left <= right && arr[right] >= pivotVal) right--;
        if (left > right) break;
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
    arr[begin] = arr[right];
    arr[right] = pivotVal;
    return right;
}

private static void quickSortRecursive(int[] arr, int begin, int end) {
    if (begin < end) {
        int pivotIdx = pivot(arr, begin, end);
        quickSortRecursive(arr, begin, pivotIdx - 1);
        quickSortRecursive(arr, pivotIdx + 1, end);
    }
}

public static void quickSort(int[] arr) {
    quickSortRecursive(arr, 0, arr.length - 1);
}

Merge Sort

Merge Sort also uses divide-and-conquer and guarantees O(n log n) performance. It's like merging two sorted playlists into one. Implement the merge and recursive methods:

private static void merge(int[] arr, int start, int middle, int end) {
    int n1 = middle - start + 1;
    int n2 = end - middle;
    int[] left = new int[n1];
    int[] right = new int[n2];
    for (int i = 0; i < n1; i++) left[i] = arr[start + i];
    for (int j = 0; j < n2; j++) right[j] = arr[middle + 1 + j];
    int i = 0, j = 0, k = start;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    while (i < n1) { arr[k] = left[i]; i++; k++; }
    while (j < n2) { arr[k] = right[j]; j++; k++; }
}

private static void mergeSortRecursive(int[] arr, int begin, int end) {
    if (begin < end) {
        int middle = (begin + end) / 2;
        mergeSortRecursive(arr, begin, middle);
        mergeSortRecursive(arr, middle + 1, end);
        merge(arr, begin, middle, end);
    }
}

public static void mergeSort(int[] arr) {
    mergeSortRecursive(arr, 0, arr.length - 1);
}

Project Two: Stacks and Queues

This project reinforces knowledge of stack (LIFO) and queue (FIFO) data structures using ArrayList. You will implement a palindrome checker, which is useful in DNA sequence analysis or text processing apps.

Stack Implementation

Use an ArrayList to create a stack with push, pop, peek, and isEmpty methods.

Queue Implementation

Similarly, implement a queue with enqueue, dequeue, and isEmpty.

Palindrome Checker

To check if a string is a palindrome, push each character onto a stack and enqueue into a queue. Then compare pop and dequeue results.

Project Three: Hash Table

Hash tables are fundamental for fast data retrieval, like caching in web apps or indexing in databases. You will implement MyHashEntry and MyHashTable as generic types.

MyHashEntry

Each entry holds a key-value pair and a boolean flag to mark deletion.

MyHashTable

Implement linear probing for collision resolution. Include methods like put, get, remove, and rehash. Remember that the table size should be a prime number for better distribution.

Project Four: Binary Search Tree

BSTs are used in decision trees, file systems, and AI search algorithms. You will implement TreeNode and BinarySearchTree with recursive traversals.

Insert and Search

Recursively insert nodes and search for values. The toString method uses a recursive node traversal to produce a parenthesized representation.

public String toString() {
    return "(" + nodeTraversal(root) + ")";
}
private String nodeTraversal(TreeNode node) {
    if (node == null) return "--";
    return node.getData() + "(" + nodeTraversal(node.getLeft()) + "," + nodeTraversal(node.getRight()) + ")";
}

Project Five: Graph Traversal

Graphs are everywhere: social networks, GPS navigation, and recommendation systems. You will implement BFS and DFS on a directed weighted graph using an adjacency matrix.

Breadth-First Search (BFS)

Use a queue to explore neighbors level by level, like finding the shortest path in a game map.

Depth-First Search (DFS)

Use a stack (or recursion) to go deep first, useful for maze solving or topological sorting.

Conclusion

By completing these projects, you will gain hands-on experience with core CS concepts that are essential for technical interviews and real-world software development. Practice by running the provided JAR files to verify your implementations. Good luck with your assignments!