CSCI 3212 Lab 3
Due Sunday, 02/23/2025, by midnight (23:59, EST), on Blackboard
Announcements
1. BST and Hashing
-
Objective:
In this lab, we aim to delve into the practical applications and intricate workings of two fundamental data structures in computer science: Binary Search Trees (BST) and Hashing. Through hands-on experience, students will not only implement these structures but also engage in a critical analysis of their operational mechanisms, efficiency, and effectiveness in solving complex problems. By comparing these advanced techniques with brute force approaches, learners will gain a deeper understanding of algorithmic optimization and the significant impact that data structure selection has on the performance of algorithms. Our objectives are twofold: First, to equip students with the technical skills necessary to construct and manipulate Binary Search Trees and Hash tables, fostering an appreciation for their underlying principles. Second, to cultivate analytical abilities that enable students to discern the most appropriate data structures and algorithms for a given problem, considering factors such as time complexity, space efficiency, and real-world applicability. By the conclusion of this lab, participants will emerge with a comprehensive understanding of how and when to employ these sophisticated data structures, fortified by the practical insights gained from applying these concepts to solve a variety of algorithmic challenges. This hands-on exploration is designed to empower students with the knowledge and confidence to tackle complex computational problems, paving the way for further exploration and innovation in the field of computer science.
1.1. Part I: Binary Search Trees (BST)
1.1.1. Introduction to BST:
-
Binary Search Trees are a pivotal data structure in computer science, enabling efficient data storage, retrieval, and manipulation. A BST is a tree structure where each node has at most two children, referred to as the left child and the right child. The key property of a BST is that for any given node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node. This property ensures that operations like search, insertion, and deletion can be performed with time complexity proportional to the height of the tree, making BSTs highly efficient for various applications.
1.1.2. Exercises:
-
108. Convert Sorted Array to Binary Search Tree
-
501. Find Mode in Binary Search Tree:
-
700. Search in a Binary Search Tree:
-
938. Range Sum of BST:
1.1.3. Lab Tasks:
-
Implementation: For each exercise, implement a solution using the BST data structure. Pay attention to the unique challenges each problem presents.
-
Analysis: After implementing your solution, analyze its time and space complexity. Consider the impact of the BST properties on your solution’s efficiency.
1.1.4. Lab Report Instructions:
-
Brute Force Approach: Describe and implement a naive solution, analyzing its time and space complexities.
-
Efficient BST Solution: Outline your approach using BST, providing both pseudocode and source code. Discuss the time and space complexities.
-
Comparative Analysis: Compare the brute force and BST solutions in terms of efficiency. Use empirical data or theoretical analysis to support your comparison.
-
Reflection: Reflect on the learning process. What challenges did you encounter, and how did you overcome them? Which BST properties were most beneficial for solving the problems?
1.2. Part II: Hashing
1.2.1. Introduction to Hashing:
-
Hashing is a fundamental concept in computer science used to map data of arbitrary size to data of fixed size. The structures that implement this concept, such as hash tables or hash maps, are known for their efficiency in data retrieval, insertion, and deletion, often achieving constant time complexity, O(1), for these operations under ideal conditions. Hashing is widely used in various applications, from database indexing to cryptography, due to its ability to handle large sets of data efficiently.
1.2.2. Exercises:
-
1. Two Sum:
-
13. Roman to Integer:
-
141. Linked List Cycle:
-
268. Missing Number:
1.2.3. Lab Tasks:
-
Implementation: Apply hashing techniques to solve each exercise, focusing on how hash maps or sets can optimize the process.
-
Analysis: Evaluate the time and space efficiency of your hashing solutions, noting how the hash function and collision resolution strategy impact performance.
1.2.4. Lab Report Instructions:
-
Brute Force Approach: Describe a non-hashing solution, detailing its implementation and analyzing its efficiency.
-
Hashing Solution: Present your hashing-based solution with pseudocode and actual code. Discuss the choice of hash function and collision resolution (if applicable), along with the complexity analysis.
-
Comparative Analysis: Contrast the brute force and hashing solutions, highlighting the efficiency gains from using hashing.
-
Reflection: Reflect on your experience. Discuss any challenges you faced with hashing and how you addressed them. What insights did you gain about the advantages and limitations of hashing?
1.3. Lab Report:
-
Students should submit a lab report that includes:
-
Source code for all implemented algorithms.
-
A brief description of each algorithm’s implementation.
-
Comparative analysis results with discussion.
-
Answers to all the questions listed above.
-
Reflection on what was learned and any challenges encountered.
-
2. Submission Guide
-
Each student only submits one file, lab_3_lastname.zip (file size less than 5 M), including
-
A Code folder for your Java code files, including all the programming tasks mentioned above.
-
Notes_lab_3_lastname.txt for your notes, including all the writing tasks mentioned above.
-
3. Notes
-
Submit your zip file for lab 3 to Blackboard.
-
Lab assignments will typically be due by midnight on Sunday.