CSC 330: Advanced Data Structures

A printable PDF is available.

Assignment 1 - Due Tuesday, September 20

Objectives: This assignment is designed with the following objectives in mind:

  • To give you experience with general tree implementations
  • To give you experience designing and implementing recursive algorithms on general trees

What To Do: The base project/code for this assignment is available through Bitbucket, as a CSC 330 team repository named "Assign1." As in the last assignment, start by forking this repository, renaming it to include your userid at the end, and then granting read access to the group "ClassAdmin." Then you can clone your forked repository in NetBeans to begin work.

The goal of this project is to store information about a tree-structured filesystem, including filenames and file sizes (in blocks), and answer several questions about the filesystem. Included in the main project class (named is code to read the tree data from a file, and a data file is provided in the project as well. This file contains the actual data describing over 20,000 files and directories from the C:\WINDOWS\System32 directory on a Windows 7 computer. Once you have completed implementation of the methods for the Tree and TreeNode classes, the provided code will be able to read in the tree and create its internal representation in memory for you to work with.

Once you have completed the classes needed for the tree implementation, you need to write code to answer the following three questions:

  • How much space does the entire filesystem take on disk?
  • How many files are stored in this filesystem?
  • Which sub-directory takes up the most space (and how much space)?

Stubs (i.e., method declarations but no code) are provided for all functions you are required to write, including Tree and TreeNode methods and stubs for functions addressing the three questions above (in the file). You should fill in code for these methods, but do not change the method signatures at all. Your code will be tested on different data, using testing code that expects these method definitions to be exactly as they are given to you!

Submission Instructions: Using NetBeans, commit all changes to your project as you did in Assignment 0, and do a "push to upstream" to put the most up-to-date files on the Bitbucket server. Unlike Assignment 0, do not do a pull request! I will clone all of your repositories (if they exist and you granted me access) at 12:30PM on the due date, and will assume that is your submission. If you intend to keep working on your project and submit late, please let me know by email, and I will ignore your repository until the late submission deadline.