Due Wednesday, May 11th, 11:59pm

Goals for this Warmup

  • Practice implementing with trees
  • Exercise algorithm development using trees
  • Solidify the notion of an iterator - both implementation and use
  • Practice using static variables

For this lab, you are welcome to get technical help from another student on how to use or install any of the tools involved. You may also get syntax help on C. You may not, however, get help on the algorithmic portion of the exercise outside of office hours or piazza questions to TAs or instructors.

Valgrind

Valgrind is a memory mismanagement detector. It shows you memory leaks, deallocation errors, etc. Actually, Valgrind is a wrapper around a collection of tools that do many other things (e.g., cache profiling); however, here we focus on the default tool, memcheck. Memcheck can detect the following things that are useful to you right now:
  • Use of uninitialised memory
  • Reading/writing memory after it has been free'd
  • Reading/writing off the end of malloc'd blocks
  • Reading/writing inappropriate areas on the stack
  • Memory leaks -- where pointers to malloc'd blocks are lost forever
  • Mismatched use of malloc [] vs free []

Click here for a nice example with explanation for how to use valgrind and interpret its results.

You can use valgrind if you log into the main cs department computers: 

ssh cnetid@linux.cs.uchicago.edu
You can check out your repository there, compile it, and test it. You may use vim to edit your code there.

Set up

Remember to create a new directory in your repository for this lab. 
$  cd CNET-cs152-spr-16
$  mkdir hw6
$ svn add hw6
$  cd hw6

Duet Programming Setup

Do not forget to copy your finished files from your duet repository into your personal repository.. Your duet repository is https://phoenixforge.cs.uchicago.edu/svn/cs152-spr-16-duet-X. with your own pair number in place of X. Remember to create a new directory in your repository for this lab. 
$  cd cs152-spr-16-duet-X
$  svn update  
$  mkdir hw6
$ svn add hw6
$ cd hw6

You also need to copy in some of your solutions from last week's assignment. You need to copy over your queue code and llist code. 

$ cp ../hw5/queue* .
$ cp ../hw5/llist* .

I am providing several files. For each file, create the file in vi and paste in the code I provided. The files are:

Don't forget to svn add* to make sure they are all in the repository!

Good luck and have fun learning together!

Problems:

During this warmup, you are going to implement several functions that exercise trees. If you are using Duet Programming, do not forget to trade off after each function. The functions are ordered to provide specific practice to each student.

In your weekly assignment this week, you are working towards a single problem. During the warmup, you'll complete several binary search tree functions that you'll use in the homework problem.

Problem 1: word struct and functions

You will first create a struct that will be used to test the binary search tree. As you know, to use a binary search tree, the struct being stored needs to provide a compare function for insertion. The word struct contains two fields: a string and a count. You need to implement two functions: compare_counts, and compare_words. The details of the functions are in word.h.

Problem 2: binary search tree

You are writing several binary search tree functions (bst):

  • bst* create_bst(); // create an empty bst
  • void free_bst(bst* tree); // free all of the nodes of a bst
  • void do_to_all(bst*, void (*f)(void*)); // perform a function on all nodes of a bst
  • int accum_all(bst*, int (*f)(void*)); // accumulate the result from this function on all nodes of a bst
  • void* find(bst*,void*,int (*c)(void*,void*)); // find an item in the tree using the compare function provided. If there are multiple matches, you can return any of the matching ones.
  • void bst_insert(bst*,void*,int (*c)(void*,void*)); // inst an item into the tree using the compare function provided. If they match, you may place the item either in the left or right subtree - your choice.
  • void* iterate(bst*); // provide an iterator (more info in .h file)

Think very carefully about the order in which you will implement these. Specifically, what is the minimum number of functions you need to implement in order to fill and print out a bst (putting in wordcount structs)? Choose the simplest functions that will give you this functionality.

You are not expected to complete this in lab. You are welcome to, but not required to, work with your duet partner after lab is over. If you wish, you may copy over your work so far and work independently after lab.

Phase 1: Problem Clarification, Test Design

Remember - for each file you create, "touch" it first, then add it to svn. In this assignment, the .h files and skeleton .c files have been provided so you can get into implementation more quickly.

In this assignment first figure out the order in which you should solve the functions in order to implement the simplest first and get testable functionality.

Then design a test plan for that simplest set of functions. Split the set of functions necessary for minimal testing, and each of you implements a subset of those functions. Make sure you are splitting functions so that each student completes ones of roughly equal difficulty. Giving easy functions to one and complex to another feeds the gap in understanding rather than brings your understanding closer together!

Phase 2: Implementation

Partner A:
Partner B:
Use svn update to receive the starting code from Partner A.
Implement the test cases to problem 1. Don't forget to use good function decomposition techniques (make a function that does the testing).

When you have completed your part of the code, update and commit.

Discussion part 1: Look at the input ranges from the black box tests. Is there separate code to handle each case? If not, are the different ranges equivalent? Also, verify that the boundaries in the input ranges match the boundaries present in the code.

Discussion part 2: Looking at student A's code, jointly develop a set of white box tests that exercise all paths in the code. If you developed more tests than the black box tests, discuss whether that code is necessary, or whether the initial tests were insufficient.

Phase 3: Compilation and Testing

Make sure you have both updated your files. Then you can begin compiling and testing. Whoever wrote the tests for the last group edits the main file, and whoever write the functions edits the functions file.

Roadmap

When you are finished with this phase, make sure you commit your code! Now you're ready to repeat the process with other problems. For this assignment, all problems are slightly different, so there is no complex roadmap. Go through phases 1, 2, and 3 for each problem, reversing your roles each problem. The problems are designed with overlapping skills so that each student gets to practice most of the skills by the end.

Good luck!

Submit

At this point, you should have done the following:
  • Checked out your repository
  • Created a folder named hw6 in your repository and run svn add hw6 
    $ svn add hw6

    $ svn add hw6/*.h

    $ svn add hw6/*.c
  • If you participated in Duet Programming, make sure you svn update your duet repository, then copy over the files into your personal repository. The cp command copies files. 
    mkdir CNET-cs152-spr-16/hw6
cp cs152-spr-16-duet-0x/hw6/* CNET-cs152-spr-16/hw6/*
cd CNET-cs152-spr-16
svn add hw6

  • $ svn add hw6.h hw6.c test_hw6.c Makefile
  • Compiled your executable manually and with the Makefile
  • Executed your code to make sure it runs properly and inspected the results. 
  • $ svn commit -m "hw6 warmup complete"
Now you're ready to move on to hw6!! Remember that the homework is completed individually.