Simplified Java Search Engine
Budget: $250 – $750 USD
Linked Lists, Stacks, and Queues
Implement a generic singly linked list (LinkedList<T>) with insertion, deletion, traversal, and size operations.
Build a stack (ArrayStack<T>) using an array and a queue (ListQueue<T>) using your linked list.
Write a tokenizer that reads a text file and stores words in a linked list.
Sorting and Searching
Implement two sorting algorithms (e.g. merge sort and quick sort) for arrays of strings. Measure and document run times for various input sizes.
Implement linear search for unsorted lists and binary search for sorted arrays. Compare their performance and discuss Big‑O differences.
Trees and Hash Tables
Implement a basic binary search tree map (BSTMap<K,V>) and use it as an inverted index mapping words to document IDs.
Implement a separate‑chaining hash table (HashMap<K,V>) and compare its search and insertion times to your BST.
Implement balanced tree variants—an AVL tree and a red–black tree—for the same map interfacecs.wheaton.eduLinks to an external site.. Ensure your trees preserve balance after insertions.
Search Engine Assembly
Build an inverted index from a directory of documents, storing word frequency and document lists.
Process user queries by retrieving and ranking documents containing the search terms.
Use the stack and queue from Part 1 to implement back/forward history navigation for viewed documents.
Performance Analysis and Report
Design experiments to compare average search times across data structures on random and sorted inputs.
Create a concise report (with tables or graphs) summarizing your findings. Reflect on trade‑offs between balanced and unbalanced trees, hash tables, and sorting algorithms.
Submission Requirements
Java source files with clear comments and meaningful names.
JUnit or similar unit tests demonstrating correctness.
A report (approximately 2–3 pages) summarizing experimental results, analysis, and reflections.
All deliverables must be submitted by the deadline specified by your instructor.
Implement a generic singly linked list (LinkedList<T>) with insertion, deletion, traversal, and size operations.
Build a stack (ArrayStack<T>) using an array and a queue (ListQueue<T>) using your linked list.
Write a tokenizer that reads a text file and stores words in a linked list.
Sorting and Searching
Implement two sorting algorithms (e.g. merge sort and quick sort) for arrays of strings. Measure and document run times for various input sizes.
Implement linear search for unsorted lists and binary search for sorted arrays. Compare their performance and discuss Big‑O differences.
Trees and Hash Tables
Implement a basic binary search tree map (BSTMap<K,V>) and use it as an inverted index mapping words to document IDs.
Implement a separate‑chaining hash table (HashMap<K,V>) and compare its search and insertion times to your BST.
Implement balanced tree variants—an AVL tree and a red–black tree—for the same map interfacecs.wheaton.eduLinks to an external site.. Ensure your trees preserve balance after insertions.
Search Engine Assembly
Build an inverted index from a directory of documents, storing word frequency and document lists.
Process user queries by retrieving and ranking documents containing the search terms.
Use the stack and queue from Part 1 to implement back/forward history navigation for viewed documents.
Performance Analysis and Report
Design experiments to compare average search times across data structures on random and sorted inputs.
Create a concise report (with tables or graphs) summarizing your findings. Reflect on trade‑offs between balanced and unbalanced trees, hash tables, and sorting algorithms.
Submission Requirements
Java source files with clear comments and meaningful names.
JUnit or similar unit tests demonstrating correctness.
A report (approximately 2–3 pages) summarizing experimental results, analysis, and reflections.
All deliverables must be submitted by the deadline specified by your instructor.