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 usevalgrind
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 themap_insert
,map_get
, andmap_free
functions.make lib
andmake 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.