CS305 Programming Assignment #4: “Files and Trees in Defense” Out:Total points:Lectures:Mar. 17th, 2015. Due: Mar. 31, 2015 by 11:00 pm on the CS305 Moodle site.100. approximately 20% of the total homework grade.File I/O is discussed in Lecture 17.Binary search trees are discussed in Lectures 16, 17, and 18.HW3’s main.c has an example of file parsing in parseInputFile().Program 5.17 has an example of counting the nodes in a tree and determining theheight of a tree.Resources:Textbook pages: This homework assignment has starter code. Go to the course website and download it now.We live in an insecure world largely controlled by computers. Our electrical grid, automobiles, nuclearpower plants, and airplanes are equipped with hundreds of tiny computers that keep us safe and alive.Today’s software developer must write code that works, but working code is not enough. Today’ssoftware developer must also write code that is high-performance and is robust against erroneous input.This assignment is intended to prepare you for writing ! industrial-strength code.This assignment puts you in competition with instructor, who will act as the adversary and try to write amain() function to break your code. !ContextCS305 students are given the opportunity to implement two APIs. At its simplest, an API, or ApplicationProgramming Interface, is a collection of functions that implement some particular task, such as reading afile or building a binary search tree. !The first API, defined in readFile.h, implements the opening, reading, and parsing of a file that has thefollowing format: !1. Each line in the file has two tokens; a token is a contiguous sequence of characters without whitespace.2. The first token of each line is a word, possibly English or possibly nonsensical.3. The second token of each line is a decimal value where the value’s binary digits are regarded in twofields of four bits each. The first field of four bits represents whether or not the word should becapitalized; if the field is equal to 1 it should be capitalized, otherwise the first letter of the word shouldbe lowercase. The second field of four bits represents whether or not the word should be read intomemory; if the field is equal to 4 decimal, it should be read into memory, otherwise it should be! ignored.For example, consider this ! file with the following contents:hello 4allies 4ace 4zimbabwe 16bird 4sendheisen 16zebra 4supercalifragilisticexpialidocious 0taco 20Date: 3/14/2015The file should be read into memory as the following collection of words: hello, allies, ace, bird, zebra,and Taco, though the order is up to the student. Generically speaking, the starter code refers to acollection of words as a WordPile, but it is up to the student to implement the WordPile data type that willstore a collection of words. !The second API, defined in tree.h, implements a binary search tree data structure for strings. For theabove collection of words, inserting the words into a binary search tree one at a time would produce thefollowing tree: !!Part 1. The Basics (50 points)Implement a C API described by the function prototypes summarized in Tables 1 and 2. To achieve thisimplementation:1. Choose how to implement the type WordPile, currently typed as an int in readFile.h.2. Choose how to implement the type TreeNode, currently typed as an int in tree.h.3. Provided with the starter code is a gentle, sample main() function to exercise the APIs described inTables 1 and 2. It is strongly recommended that students implement the two APIs one function at a! time, trying out each function with the sample main() before moving onto the next.!It is not recommended that students type out all of the codefor all of the functions before attempting to compile. !Write a little, compile a little, test a little. Repeat.Date: 3/14/2015“hello”“allies” “zebra”“Taco”“ace” “bird”Table 1. A listing of all function prototypes in readFile.h thatmust be implemented in readFile.c!!Table 2. A listing of all function prototypes in tree.h thatmust be implemented in tree.cPrototype Description Pts.int initialize(WordPile ** wpPtr); Given a pointer to a WordPile, initialize theWordPile datatype.1int readFile(char * filename,WordPile * wp);Given a string representing a filename, openthe file and read its contents according to therules specified above. All of the words readfrom the file should be stored in the WordPilepointed to by wp. There are no restrictionson the order by which the words are stored.The function should return the number ofwords read into memory.10char * getWord(WordPile * wp,int i);Given a pointer to a WordPile, return apointer to the ith word in wp. If there is noith word, return NULL.9void freeWordPile(WordPile **wpPtr);Given a pointer to a WordPile, free all thememory allocated to the WordPile.5Prototype Description Pts.int insert(char * newValue,TreeNode ** rootPtr);Given a string pointed to by newValue,insert the string into the binary search treepointed to by rootPtr.5void printTree(TreeNode * root); Given a binary search tree pointed to byroot, print each node in the tree usinginorder traversal.10int search(char * findMe,TreeNode * root);Given a binary search tree pointed to byroot, find the depth of the given string.Return an int representing the depth of thestring or -1 if the string could not be found.If the string were located at the root, thisfunction would return 0.10int height(TreeNode * root); Given a binary search tree pointed to byroot, print the height of the tree. An emptytree has height 0. A tree with a single nodehas height 1.5void freeTree(TreeNode ** rootPtr); Given a binary search tree pointed to byrootPtr, free all of the nodes allocated forthe tree.5Date: 3/14/2015!Part 2. Using the API.With the provided main() function, the following is the output for the input file ! sample.txt.$ ./hw4 sample.txt+———————— PHASE 1: readFile API ————————–+Opening sample.txt. File contained 6 words that were read into memory.The words read from sample.txt and stored in memory are:hello allies ace bird zebraTaco. !+————————— PHASE 2: tree API —————————+A tree of height 4 was created:Taco ace allies bird hello zebra !Searching for items in the tree:– “hello” was found at depth 0.– “zebra” was found at depth 1.– “taco” was not found.– “allies” was found at depth 1.-! “ace” was found at depth 2.Freed all memory. Thank you! !Part 3. Breaking the API (20 points)With the basic functionality of your API working, it is time to harden your API against erroneous input.As security celebrity Bruce Schneier writes, “Good engineering involves thinking about how things canbe made to work; the security mindset involves thinking about how things can be made to fail” !Your challenge is to anticipate all the ways that I will try to make your API fail. To do this well, studentswill need to create sample input files that are erroneous or make calls to the API from main() that haveerroneous parameters. !To help you get started, make sure these two cases do not cause your program to seg fault or otherwisebehave badly. To earn full points for Part 3, your program must be hardened against at least 10 uniquecases. !1. ! Invoke the program on a file that doesn’t exist:$ ./hw4 missingFile.txt… !!2. Add a call to main() in which you try to get the -5th word from a WordPile, like so: !getWord(dictionary, -5);!Date: 3/14/2015Now, what other evils could I do? Brainstorm here:3. 7.4. 8. 5.6. !Part 4. Timing the API9.10. With the API hardened, it is time to evaluate the performance of your software. A file provided with thestarter code, aWords.txt, contains all of the words listed in the dictionary of the instructor’s computerthat begin with the letter ‘A’, from A to azymous. Every word is coded as ! 4.The time tool gives one the ability to time the performance of a program. For example, here’s a sampletest run of the instructor’s hw4 solution against the large input file ! aWords.txt.$ time ./hw4 aWords.txt+———————— PHASE 1: readFile API ————————–+Opening aWords.txt. File contained 17061 words that were read into memory.The words read from aWords.txt and stored in memory are:…+————————– PHASE 2: tree API —————————+The following tree of height 33 was created:…Searching for items in the tree:– hello was not found– zebra was not found– taco was not found– allies was found at depth 21– ace was found at depth 19 !Freed all memory. Thank you! !real 0m0.078suser 0m0.026ssys ! 0m0.005sThe time tool reports three measurements of the execution time of the program. ! real 0m0.078suser 0m0.026ssys ! 0m0.005sThis is the total time elapsed.This is the time consumed by system overhead.This is the time used to execute the program to stderr. For HW4, the most meaningful measurements are the real time and the user time; in particular, theuser time indirectly measures how many system calls — such as malloc(), free(), or fopen() — theprogram is invoking.Date: 3/14/2015!Students must measure the performance of their program on 10 executions of: !$ ./hw4 aWords.txt !And report the average performance and fastest in the file header of main.c, as described in Part 5. !!Part 5. Reporting (10 points)The top of the main.c you submit with your homework must report on i) the test cases your APIs in tree.hand readLine.h are hardened against and ii) the performance measurements you took. Here is a sampleheader: !/** Filename: main.c* Author: * Created by: Tanya L. Crenshaw* Date created: 3/08/2014**Description: This file contains a gentle main function for the required functionality* for HW4. Correctly implementing the API for this main() function will earn 50/100.* Using good coding style will earn 70/100. To earn full points on this assignment,* students must harden their API against erroneous input and time the performance of* their code. See handout for HW4.*!* This program has been hardened against these 10 test cases:* 1. Input file does not exist.* 2. getWord() handles negative input for parameter i.* ….**Performance measurement:**Measured the average performance of 10 runs of ./hw4 aWords.txt.* Machine used: MacBook Pro, 2014 edition.**real 0m0.078s* user 0m0.026s* sys 0m0.005s**Fastest run:* real 0m0.040s* user 0m0.026s* sys 0m0.005s***/ !!!!!!!Date: 3/14/2015!!To receive 100/100 points on this assignment, you must utilize good programming practice (20points):• Submit your source organized into these files: main.c, readList.h, readList.c, tree.h, tree.c, andmakefile. For hw4, tree.c and readList.c are the only files you will need to create and develop, but it isgood practice to always provide all the files necessary to compile the executable.• Submit your assignment in a zipfile with your username in the zipfile name.• Always give variables meaningful names.• Never use global variables.• Use #define preprocessor directives for constant values; you may not necessarily need constant valuesfor your solution.• Avoid redundant code.• Document code with useful comments. See example program on website for five pieces of guidance! on how to adequately document code with comments. !To achieve maximum points on your submission, consider using this submission checklist beforesubmitting your program to the Moodle course website: !___ “The name of my program files are: main.c, readFile.h, readFile.c, tree.h, tree.c and makefile.”___ “My program compiles successfully using a make command with my makefile.”___ “I followed the five pieces of guidance on commenting programs.”___ “I compressed my files into a zipfile named with my username, e.g., crenshaw16.zip”___ “I did not compress my files using .rar, .z7, or some other proprietary compression program.”___ “I did not compress a DIRECTORY of files.”___ “I uploaded my zipfile to Moodle.” !If you are missing any of the above checklist items,up to 10 points may be deducted from your score.Date: 3/14/2015
- Assignment status: Already Solved By Our Experts
- (USA, AUS, UK & CA PhD. Writers)
- CLICK HERE TO GET A PROFESSIONAL WRITER TO WORK ON THIS PAPER AND OTHER SIMILAR PAPERS, GET A NON PLAGIARIZED PAPER FROM OUR EXPERTS
