CSCI 3212 Lab 5

Due Sunday, 03/31/2024, 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_5_firstname_lastname.zip (file size less than 5 M), including

    1. A Code folder for your Java code files, including all the programming tasks mentioned above.

    2. Notes_lab_5_lastname.txt for your notes, including all the writing tasks mentioned above.

3. Notes

  • Submit your zip file for lab 5 to Blackboard.

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