CS 136 Assignment 8

Due Wednesday, July 15 at 5:30 PM sharp.

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 (and it's not possible to).

If a requirement is that a structure is "valid", you may assume this, and you do are not required to to assert it. If the structure is passed as a pointer you should still assert that the pointer itself is not NULL.

For full marks you must satisfy (or exceed) the specified running times.


Note: For Problems 0a and 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. Unlike the version on slide 21 you may not use any string.h functions (such as strlen and strcpy). Do not write helpers, either. Your implementation must have a running time of O(n) where n is the length of the string s. 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] In this question you will revisit the manifests from A6. 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 until a newline or EOF is encountered. The returned string must NOT include the EOF or newline. The returned array must have a length equal to the length of the string plus 1 (for the null terminator). Your function must have a running time of O(n) where n is the number of characters read. You may assume that all of the characters you read (except for newline) will be in the visible range (ASCII values 32..126).

    TIP: use a "doubling dynamic array" strategy to achieve the O(n) (amoritzed) 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 an interactive text program that will read a line from the user, and then print the length of that line as well as the first and last characrters of the string (or {empty string} if the string is the empty string). The reason it does this rather than printing the entire string is that it can be hard to tell the difference between readstr being slow, and printf being slow.

    The test program can be found in test-readstr.c. We have included a very large input file in alice.in and the expected output when this input is given to the test program is in alice.expect.


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

Write a C module strappend.c that implements a strappend function (see strappend.h for details).

NOTE: For this question, you cannot use string.h

Public test sample:

strappend("hello","world") returns the new string "helloworld"


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

Write a C module afilter.c that provides the abstract array function afilter. See the interface file afilter.h for more details.

Public test sample:
for a dynamic array da of length 6: (4 8 15 16 23 42)
and the following function:
bool is_even(int n) { return n % 2 == 0; }
then, afilter(da, is_even) would modify da to be of length 4: (4 8 16 42)


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

Write a program skipints.c that reads in a sequence of positive integers using scanf("%d", &i) until a 0 is encountered (you can assume only positive integers will be entered in the sequence, and no EOF is encountered). The program then reads in a final positive integer k. The program then prints every k-th integer from the original sequence of integers. Each integer printed is followed by a newline. The running time of your program must be O(n), where n is the number of integers read.

Examples: If k is 1, it prints the full sequence of integers. If k is 2, it prints every other integer, ignoring the first, third, etc. If k is equal to the length of the sequence, it prints out the last integer. If k is larger than the length of the sequence, then no integers are printed out.

Public test sample:
input:
4 8 15 16 23 42 0 2
output:
8
16
42

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

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.

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);


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

In this question, you will see a technique for storing a Binary Search Tree (BST) in an array. We will use the following rules: Consider the following BST:

It would be stored in the following array (blanks would contain INT_MIN):
index012345678910111213141516...
value5310-671242

Write a C module atree.c for managing a BST in an array. See the interface file atree.h for more details. In particular, note that the array must always have a length of 2maxheight.