CS 136 Assignment 8

Due Monday, March 23 at 11:59 AM sharp (noon).

Please read the preamble in Assignment 1.

Only the C language features introduced up to section 10 are allowed.


In your code, you do NOT have to check that the value returned from malloc (or realloc) is invalid (NULL).

You may assume that all C strings are null terminated: you do not have to assert this.

If a requirement is that a structure is "valid", you may assume this, and you are not required to to assert it. (But you do need to assert requirements that a pointer to a structure is not NULL).

Unless otherwise stated you can not define new mutable global variables.


Note: For Problem 1, you are NOT allowed to use the string.h library (module).


Assignment 8 Problem 0. [10 Marks correctness]

Problem 0 is a "warm-up" question. You are allowed to collaborate with your fellow classmates and discuss the solution on piazza.
  1. [1 mark] Write the C module strdup.c that implements the my_strdup function described in Module 10 slide 21 (you may use strcpy, but you are not allowed to use the strdup function in string.h).

    char *my_strdup(const char *s);

  2. [2 marks] Write the C module posn.c that provides the make_posn function described in posn.h.

  3. [2 marks] Write the C module reservation.c that provides the functions described in reservation.h.

  4. [5 marks] Write a C module readstr.c that implements a "safe" version of the gets function called readstr (see readstr.h for details).

    Your function must repeatedly call scanf("%c", ... ) until a newline or EOF is encountered (note the lack of a space in the format string, you do not want to ignore whitespace or you will miss the newline). The returned string must NOT include the EOF or newline. You may assume that all of the characters you read (except for newline) will be in the visible range (ASCII values 32..126).

    TIP: You must use a "doubling dynamic array" strategy to achieve the target running time. You will likely require multiple calls to realloc, including one call to set the final (correct) size. You can choose any initial dynamic array size you'd like (e.g., 1, 16, 64...).

    We have included a large file (alice.in) that can be used as a ".in file" to test that your implementation can read a very large string. With a proper O(n) implementation it should take a fraction of a second to read this file. Attempting to print the string that you read in may cause a timeout on Seashell. strlen should be OK though. You can use test-readstr.c to test with this .in file (it prints the string length, and the first and last characters of what was entered). When given alice.in it should print alice.expect.

    Note: This question is long for a warm-up, but it's still a warm-up! Feel free to work together.

Assignment 8 Problem 1. [10 Marks for correctness.]

Write a C module strfilter.c that implements a strfilter abstract array function for strings (see strfilter.h for details). Do not attempt to resize the array.

Basic test sample:
bool is_vowel(char c) {
 return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || 
   c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}

int main(void) {
  char s[] = "hello, world!";
  strfilter(s,is_vowel);
  assert(strcmp(s,"eoo") == 0); 
}
Given that bool is_vowel(char c); returns true if c is a vowel, and false otherwise.

Assignment 8 Problem 2. [10 Marks for correctness.]

For this question, you will be working with sets of integers. Implement the function sym_diff, which takes two arrays representing sets of integers (all elements are unique, but not sorted) and returns a new dynamically allocated array that contains the symmetric difference between these two sets. That is, it contains all of the integers that are in exactly one of the two sets (but not both). The interface has been provided for you in set.h. Write your implementation in the provided implementation file set.c.
Important: The set you return must contain the elements from s1 (but not s2) first, then the elements from s2 (but not s1). They must occur in the same order they occured in the sets s1 and s2. (This means you cannot sort the arrays even though that might allow for more efficient code).

Sample basic test:

struct set *s1 = new_set(5);
struct set *s2 = new_set(5);
s1->count = 5;
s2->count = 5;
for (int i = 0; i < 5; ++i) {
  s1->data[i] = i+1; // s1 = [1,2,3,4,5]
  s2->data[i] = i+4; // s2 = [4,5,6,7,8]
}
struct set *s3 = sym_diff(s1,s2);
free_set(s1);
free_set(s2);
assert(s3->count == 6);
int expected_contents[] = {1,2,3,6,7,8};
for (int i = 0; i < 6; ++i) {
  assert(s3->data[i] == expected_contents[i]);	    
}
free_set(s3);

Notes: Do not modify the interface file set.h as you are only submitting the implementation file! Do not modify the new and free functions provided for you already in set.c! They're fine!

Assignment 8 Problem 3. [15 Marks for correctness.]

Write a program smaller_numbers.c that reads a sequence of integers until it encounters EOF or a non-integer value. It then prints all integers that are strictly less than the last integer entered. Each integer printed must be followed by a newline character (i.e. it prints one integer per line). The numbers must be printed in the same order they were entered. You can assume at least two integers will be entered, but cannot assume a maximum number of integers.

Sample basic test:
smaller_numbers.in
smaller_numbers.expect

Assignment 8 Problem 4. [25 Marks for correctness, 10 Marks hand-marking.]

For this question, you will practice working with dynamically allocated arrays in C. You will write a C module aos.c for managing an array of strings. See the interface file aos.h for more details.

An array of strings is really an array of char pointers, where each pointer can then point to a string.

Note: The sort function cannot use the dynamic memory functions malloc/realloc/free/etc. You must sort the array by changing the order of the pointers within the array, not by changing the strings. You must write your own sort function (meaning do not use qsort). Public test sample:
struct aos *a = create_aos(10);
assert(aos_get(a,5) == NULL);
aos_set(a,"apple",5);
assert(strcmp(aos_get(a,5),"apple") == 0);
assert(aos_add(a,"zebra") == 0);
aos_sort(a);
assert(strcmp(aos_get(a,0),"apple") == 0);
assert(strcmp(aos_get(a,1),"zebra") == 0);
destroy_aos(a);

Things to watch for: The empty string is not the same thing as a NULL char * pointer. Sort places all NULL values at the end of the array (see the example above).


Assignment 8 Problem 5. [20 Marks for correctness.]

In this question you will be implementing an array for dealing with matrices of integers. Use the provided interface file dyn_matrix.h. As in the lectures, rows and columns are indexed starting with 0. Do not modify the interface. All functions must go in dyn_matrix.c We have completed the draw_matrix function to get you started. We have also provided you with an interative testing program test-matrix.c. The file contains usage instructions (it ends when it encounters EOF). It does not handle invalid input.

Sample Basic Test Files: matrix_basic.in | matrix_basic.expect
Note: This doesn't test all of the matrix functions.

Warning: The get_matrix_cell and set_matrix_cell functions are extremely important. If they don't work properly, the interactive testing program doesn't work properly!