Skip to content

Homework 3: BST

Due Monday, July 10, 2023 at 11:59pm

In this assignment, you will implement free, insert, and get functions of a binary search tree.

  • Compile and test frequently
  • Read the entire assignment first before you start
  • Start early and do not do all of the assignment in one sitting; coding is fun but fighting for hours with broken code is not
  • Do not hesitate to seek help if you are stuck

Synopsis

In this homework, you will work in the lib directory.

lib/src/map.c: All code you are going to write for this assignment lives in this file. This file should implement the header at lib/include/map.h.

Written: You will answer some simple questions at the end.

Learning Objectives:

  • Even more pointer juggling
  • Understand the structure of a binary search tree
  • Practice heap allocation and manual memory management

Getting started

We will keep using the coursework repository, same repository where you wrote hw0. First of all, you should run git status to see if you have any uncommitted changes; if so, commit and push them before proceeding.

Run git pull upstream main. Doing this almost certainly triggers an automerge by git. When vim is launched that shows the merge commit message, press <esc> : x <enter> to save and quit the editor (look at the bottom-left corner of your screen if you don't know where you're typing).

Pay attention to any error messages that you might encounter and please ask for help if you run into any problems.

Updates in the unit-test framework

The generated executable (bin/*-test) now takes the following command-line arguments:

  • --capture: without this option, if your implementation crashes, the test program also crashes. This is useful when you want to use valgrind to figure out which functions/lines in your code cause the crash. With --capture, the test program will not crash but report the test as FAILED.
  • --keep-going: without this option, the test program will stop at the first failed test. --keep-going tells the program to run all tests even when some tests fail.

You should be very familiar with other parts of the infrastructure now.

Before you start, read through unittests/map-test.c and understand the interface include/map.h fully before you start implementing.

Running unit tests

You know the drill now: make test and ./bin/map-test.

make -C <dir>

When you run make, make will look for a file called Makefile in your current directory. You can tell make to look for Makefile somewhere else by passing make -C <dir>, where <dir> contains the Makefile that you want. For example, if you are in bin and want to run make, you can run make -C .. or make -C .. test to use the Makefile in .., which is the parent directory of bin.

./bin/map-test

You don't have to be in the directory of an executable to run that executable. If you are in coursework/lib, instead of running cd bin; ./map-test; cd .., you can simply run ./bin/map-test without changing the directory. This works with valgrind as well: e.g. valgrind ./bin/map-test.

Specification

The specification of map is documented in the header file. If anything is uncleared, please let me know.

For bonus points, implement map_free, map_get and map_insert iteratively (i.e. do not use recursion).

  • Iterative map_free: +5%
  • Iterative map_insert: +3%
  • Iterative map_get: +2%

The implementation of everything other than map_free, map_get, and map_insert is given to you as starter code. Read through the provided functions because they will give you a big hint for the functions that you will write.

Written

You need to answer some questions in hw3/WRITTEN.txt.

Submission checklist

In lib/:

  • src/map.c contains your implementation of the map_insert, map_get, and map_free functions.
  • make lib and make test produce no errors.

In hw3/:

  • WRITTEN.md is finished.

All changes are committed and pushed to your github repository. Submit your program to Gradescope by selecting your coursework directory and the correct branch.

Grading

Percentage
Correctness 70%
Style 20%
Written 10%
Bonus 10%

Warning: If your program cannot be compiled using the commands above without error or warning, you will receive 0 points in correctness since there is no executables for us to run.