CSCI 3212 Lab 5

Due Sunday, 10/26/2025, by midnight (23:59, EST), on Blackboard

Announcements

1. Graphs and Graph Search

  • Objective:

This lab aims to provide students with practical experience in binary tree and graph traversals. Through exercises on preorder, inorder, and postorder binary tree traversals, alongside Depth-First and Breadth-First graph searches, students will enhance their understanding of these fundamental algorithms. By the end of the session, participants will be better equipped to apply these concepts in algorithmic problem-solving and data structure manipulation.

1.1. Part I: Binary Tree Traversals

1.1.1. Introduction

  • Binary tree traversal is a cornerstone concept in computer science, essential for navigating and manipulating hierarchical data structures. It involves visiting each node of a binary tree in a systematic manner to perform operations like search, insertion, or deletion. There are three primary methods of traversal: preorder, where the root node is processed before its subtrees; inorder, where the left subtree is visited first, followed by the root, and then the right subtree; and postorder, where the root is processed after the subtrees. Understanding these traversal techniques is fundamental for efficiently solving complex problems related to binary trees.

1.1.2. Exercises:

1.2. Part II: More Graphs

1.2.1. Exercises:

1.3. Lab Report

  • Students should submit a lab report that includes:

    1. Source code for all implemented algorithms.

    2. A brief description of each algorithm’s implementation.

    3. Comparative analysis results with discussion.

    4. Reflection on what was learned and any challenges encountered.

1.3.1. Lab Tasks:

  • Implementation: For each exercise, implement a solution using the required data structure or algorithm. Pay attention to the unique challenges each problem presents.

  • Analysis: After implementing your solution, analyze its time and space complexity.

1.3.2. Lab Report Instructions:

  • Brute Force Approach: Describe and implement a naive solution, analyzing its time and space complexities.

  • Efficient Solution: Outline your approach, providing both pseudocode and source code. Discuss the time and space complexities.

  • Comparative Analysis: Compare the brute force and Efficient 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?

2. Submission Guide

  • Each student only submits one file, lab_4_lastname.zip, including

    1. LeetCode-style Java solutions:

      • One problem → one file: For Problem N, submit exactly one Java file named SolutionN.java. Examples: Problem 1 → Solution1.java; Problem 13 → Solution13.java.

      • Class name = file name: Each file must declare public class SolutionN.

      • Method signatures: Use the exact function names, parameters, and return types from LeetCode’s template. (We will paste your method into LeetCode to grade it.)

      • Optional brute-force version: If you write a brute-force solution, place it in a differently named method (e.g., romanToIntBruteForce). The method matching the LeetCode template must be your final, correct solution.

      • What NOT to include: Do not add main methods, input/output code, package statements, or external libraries.

      • File–problem consistency is critical: If you solve Problem 13 but submit Solution268.java, you will lose many points.

3. Notes

  • Submit your zip file for lab 5 to Blackboard.

  • Lab assignments will typically be due by midnight on Sunday.