Problem 0: Review old programming assignments, lectures, and readings. Use Ed to suggest a question you feel is missing from this collection of practice problems.

Problem : Write the declarations and initializations to reflect the memory diagram shown below (for this and subsequent diagrams, assume that the numeric values are ints, the character values are chars, and there is a struct point with int fields x and y).

Problem : Assume that variables have been declared and initialized according to the following memory diagram.

Illustrate the results of the following statements on the memory diagram, indicating which statements would cause compiler errors or warnings and which would cause undefined behavior, and identifying any leaked memory. Assume the results are cumulative, assuming the statements that cause undefined behavior or compiler errors and warnings have been commented out.

b = a[1];
(*b)++;
b++;
b[3]++;
c = d[0];
c = &d;
d[0][1] = 'I';
d[1] = a;
d++;
d[1] = c[1];
d[1]++;
d[2] = &c + 2;

Problem : Assume that variables have been declared and initialized according to the following memory diagram.

Write the statements to free all of the dynamically allocated memory.

Problem : Assume that variables have been declared and initialized according to the following memory diagram, where the original state is shown in black.

Write the statements that would cause the changes to the memory diagram shown in red.

Problem : Write a function read_three that reads three integers separated by whitespace from standard input and returns them through reference parameters; the return value should be true if all three were read successfully and false otherwise.

Problem : Write a function that takes a modifiable string as its argument and reads from standard input, replacing characters in the original string until either 1) whitespace or EOF is read; or 2) as many characters as were in the original string have been read. For example, if the string originally contains "code" and the next input on standard input is "money" then the string is changed to "mone" and the 'y' is not read; and if the next input is "in rainbows" then the string is changed to "in" and the next input on standard input will be "rainbows".

Problem : Write a function same_ia that takes two arrays of integers and their sizes as arguments and returns a count of how many locations at which they contain the same value. For example, if the two arrays are {0, 1, 3, 4, 9} and {-3, 0, 3, 6, 9, 12} then the function would return 2 since both arrays contain 3 at index 2 and 9 at index 4.

Problem : Write a function same_s that takes two strings as arguments and returns the number of positions at which they contain the same character. For example, it the two strings are "smile" and "shelter" then the function would return 2 since both strings have 's' in position 0 and 'l' in position 3.

Problem : Write a function concat that takes two strings as arguments returns a dynamically allocated string that contains the first string followed by the second string.

Problem : Write a function make_range that takes as arguments two integers $m$ and $n$ with $m \lt n$ and returns a dynamically allocated array containing the integers $m, m + 1, ..., n - 1$ in that order.

Problem : Write a function count_if that takes as argments an array of integers, its length, and a pointer to a function that takes an integer and returns true or false; count_if returns the number of integers in the array for which the function it is passed returns true.

Problem : Write the header and implementation of a POLL ADT using an opaque struct, where POLL provides the following functions:

• poll *poll_create(int n) which returns a dynamically allocated poll with $n$ options, each with a vote count initialized to 0;
• void poll_add_vote(poll* p, int opt), which adds one vote for the given option in the given poll, or does nothing if the option is invalid (not in the range $0, \ldots n-1$ where $n$ was the value given when the poll was created);
• int poll_get_leader(const poll *p), which returns the index of the option currently with the most votes, with ties broken in favor of lower index; and
• void poll_destroy(poll *p), which frees the memory for a poll created by poll_create and any memory held by that poll.

Problem : Write a function that takes a dynamically allocated, possibly ragged, 2-D array as its argument and flips the array vertically: the top row swaps with the bottom, the second-from-top with the second-from-bottom, etc. Try to write your function so it works in $O(n)$ time.

Problem : Comment on the quality of the two suggested hash functions for arrays of integers, considering the conditions that are required for hash table operations to work in $O(1)$ expected time.

• the hash value is the bitwise exclusive-or of all the integers in the array
• the hash value is the sum of all the integers in the array

Problem : Consider the problem of, given a list of integers, checking whether they are all different. Give an algorithm for this problem with an average case of $O(n)$ under reasonable assumptions. Give an algorithm that has a worst case $O(n \log n)$.

Problem : Suppose we have the following hash function:

s	hash(s)
ant	43
bat	23
cat	64
dog	19
eel	26
fly	44
gnu	93
yak	86

Show the results of adding the strings in alphabetical order into a hash table of size 8, first using chaining, then using open addressing with linear probing.