(r4) Homework3 < CS385spring11

CS385spring11 Web>Syllabus>Homeworks>Homework3 (revision 4) (raw view)~~EditAttach~~
---+ DRAFT
---+ Homework 3 - Data structures in C

In this homework, we practice our C skills by implementing a String data structure, and testing our implementations against each other. An implementation of the String data structure consists of a .o file that provides the following set of functions:

<verbatim>
// hw3_string.h
struct String;
struct String* string_new(char* str);
void string_free(struct String* s);
struct String* string_clone(struct String* s);

int string_length(struct String* s);
void string_append(struct String* a, char* b);
char string_charAtIndex(struct String* s, int index);
char* string_range(struct String* s, int start, int length);
char* string_chars(struct String* s);
</verbatim>

The template for hw3 is available at =svn://bits.cs.uic.edu/cs385s11/notes/homeworks/hw3=. This contains the =hw3_string.h= above, an implementation of the String data structure called =simple_string.c=, and programs that use String data structures and tests their correctness and runtime performance. 

---++ Rope - a binary tree representation of Strings

Your task is to create an alternative implementation of the String data structure, called =fast_string.c=. The name Rope is more of a guideline than a rule - you may implement your data structure whichever way you please, as long as the following conditions hold:

   * it passes all tests run by =make testunit=
   * =make testspeed= runs in less than 1 second

Do not change the files in the template. Instead, copy =simple_string.c= to a new file =fast_string.c=, and edit the first line of the =Makefile= to use =fast_string.c= instead. Make and commit your changes to fast_string.c. 

---++ Testing correctness and performance

To test the correctness of your code, run =make testunit=. This performs several unit tests on the String functions declared above. Try running =make testunit= with =STRING_CODE= in the =Makefile= set to =simple_string.c= to see the expected output. 

To test the performance of your code, run =make testspeed=. This downloads a large book, concatenates the entire book into one large string, line by line, and applies the string functions on the resulting string.
Topic revision: r4 - 2011-01-22 - 20:06:19 - Main.jakob
CS385spring11
WISEST
Helping Women Faculty Advance
Funded by NSF