Problem 0: Review old programming assignments, lectures, and readings. Use Piazza 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).

#include <stdio.h>
#include <stdlib.h>

typedef struct point
{
  int x;
  int y;
} point;

int main()
{
  int a[] = {3, 15, 7, 0, -99};

  int *b = a + 3;

  int *c = malloc(5 * sizeof(int));
  for (int i = 0; i < 5; i++)
    {
      c[i] = 2 + 7 * i;
    }

  point d = {0, 0};

  point e[] = { {0, 0}, {1, 0}, {2, 0} };

  point **f = malloc(3 * sizeof(point *));
  f[0] = &d;

  f[1] = malloc(sizeof(point));
  f[1]->x = 0;
  f[1]->y = 1;

  f[2] = e + 2;

  int g = 33;

  int *h[] = {&g, a + 4, &f[1]->y};

  return 0;
}

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]; TYPE MISMATCH (char *, char)
(*b)++;
b++;
//b[3]++; NO SUCH ELEMENT b[3]
c = d[0];
// c = &d; TYPE MISMATCH (char *, char ***)
d[0][1] = 'I';
d[1] = a;
d++;
// d[1] = c[1]; TYPE MISMATCH (char *, char)
d[1]++;
// d[2] = &c + 2; TYPE MISMATCH (char *, char **) and NO SUCH ELEMENT d[2]

The memory containing "SLC" and the top "HNL" is inaccessible and so has been leaked.

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.

free(c);
free(d[1]);
free(d[2]);
free(d);

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.

a[2] = 'C';
b = b + 2;
c = d[1];
d[0]++;
d[2][0]++;
d++;

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.

bool read_three(int *x, int *y, int *z)
{
  return(scanf("%d %d %d", x, y, z) == 3);
}

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".

void read_replace(char *s)
{
  int ch;
  while (*s != '\0' && (ch = getchar()) != EOF && !isspace(ch))
    {
      *s = ch;
      s++;
    }
  *s = '\0';
}
  

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.

int same_ia(int* arr1, int* arr2, int size1, int size2){
	//size1 is the size of arr1, size2 is the size of arr2
	
	int count = 0; //counter variable, this is the variable we will return
	int minSize; //minSize is the minimum of size1 and size2
	if(size1 < size2){
		minSize = size1;
	}
	else{
		minSize = size2;
	}
	
	for(int i = 0; i < minSize; i++){ //only iterate up until the end of the smaller array.
		if(arr1[i] == arr2[i]){
			count = count + 1; //if the locations contain the same value, increment count
		}
	}
	
	return count;

   }
			   

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.

int same_s(char* str1, char* str2){
	//this problem is basically the same as 6, just for strings.
	//we assume that uppercase and lowercase count as different characters.
	
	int size1 = strlen(str1);
	int size2 = strlen(str2); //find the lengths of the strings
	
	int count = 0; //counter for number of positions that have the same character
	int minSize; //minSize is the minimum of size1 and size2
	if(size1 < size2){
		minSize = size1;
	}
	else{
		minSize = size2;
	}
	
	for(int i = 0; i < minSize; i++){ //only iterate up until the end of the smaller string
		if(str1[i] == str2[i]){
			count = count + 1; //if the locations contain the same value, increment count
		}
	}
	
	return count;
	
   }

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.

char* concat(char* str1, char* str2)
    {
	int i; //iterator variables
	int size1 = strlen(str1);
	int size2 = strlen(str2); //find the lengths of the strings
	
	int newSize = size1+size2; //size of concatenated string
	char* newString = (char*) malloc((newSize+1)*sizeof(char)); //dynamically allocate memory for the new string
	
	for(i = 0; i < size1; i++){ //copy in the first string
		newString[i] = str1[i]; 
	}
	for(i=0; i < size2; i++){	//copy in the second string
		newString[i+size1] = str2[i]; //note we are putting it into array index [i+size1]
	}
	newString[size1 + size2] = '\0';
	
	return newString;
    }

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.

int* make_range(int m, int n){
	//we assume m < n
	
	int len = n-m; //length of the array we are creating
	int* arr = malloc(len*sizeof(int)); //dynamically allocate memory to arr
	
	for(int i = 0; i < len; i++){
		arr[i] = m+i; //put in m through m+n-1 into the array
	}
	
	return arr;
    }
			   

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.

int count_if(int* arr, int size, bool (*func)(int)){
	//I think the main point of this problem is just to know how to pass/use functions as parameters
	
	int count = 0;
	for(int i = 0; i < size; i++){
		if( (*func)(arr[i]) ){ //pass arr[i] to the function func that is passed as a parameter
			count = count + 1; //if arr[i] returns true (within func) increment the count
		}
	}
	
	return count;
	
}
			   

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.

poll.h

#ifndef __POLL_H__
#define __POLL_H__

struct poll;
typedef struct poll poll;

poll *poll_create(int n);
void poll_add_vote(poll *p, int opt);
int poll_get_leader(const poll *p);
void poll_destroy(poll *p);

#endif
  

poll.c

#include <stdlib.h>

#include "poll.h"

struct poll
{
  int *votes;
  int size;
  int leader;
};

poll *poll_create(int n)
{
  poll *p = malloc(sizeof(poll));

  if (p != NULL)
    {
      p->leader = 0;
      p->votes = malloc(sizeof(int) * n);
      p->size = p->votes != NULL ? n : 0;

      for (int i = 0; i < p->size; i++)
	{
	  p->votes[i] = 0;
	}
    }

  return p;
}

void poll_add_vote(poll *p, int opt)
{
  if (p != NULL && opt >= 0 && opt < p->size)
    {
      // add one vote for opt
      p->votes[opt]++;

      // check for new leader (so get_leader works in O(1) time)
      if (p->votes[opt] > p->votes[p->leader]
	  || (p->votes[opt] == p->votes[p->leader] && opt < p->leader))
	{
	  p->leader = opt;
	}
    }
}

int poll_get_leader(const poll *p)
{
  return p != NULL ? p->leader : 0;
}

void poll_destroy(poll *p)
{
  if (p != NULL)
    {
      free(p->votes);
      free(p);
    }
}
  

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.

/**
 * Flips the given 2-D array vertically.  The 2-D array is passed as an
 * array of pointers to the rows.  Since the rows need not have the same
 * width, this function allows for the widths of each row to be passed
 * in a separate array and will update them to reflect the new widths after
 * flipping.  If the array is not ragged (all rows have the same width) then
 * this operation is not necessary and the caller may pass NULL for the array
 * of widths.
 *
 * @param h the height of the given array
 * @param w an array containing the width of each row, or NULL
 * @param arr a pointer to the array, non-NULL
 */
void flip(int h, int *w, int **arr)
{
  // error checking on inputs
  if (arr == NULL || h <= 0)
    {
      return;
    }

  // exchange each row in the top half with the corresponding row in the bottom half
  for (int r = 0; r < h / 2; r++)
    {
      // swap the pointers to the rows
      int *trow = arr[r];
      arr[r] = arr[h - 1 - r];
      arr[h - 1 - r] = trow;

      // swap the widths (if the array of widths was given)
      if (w != NULL)
        {
          int tw = w[r];
          w[r] = w[h - 1 - r];
          w[h - 1 - r] = tw;
        }
   }
}
		      

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

  This is terrible! The hash value of an array of positive integers will always be between 0 and $2n$ where $n$ is the largest value in the array. There are many applications where there keys will be a large number of arrays with a small range and for those applications there will be many collisions, so worse than $O(1)$ expected time for operations on the hash table.

• the hash value is the sum of all the integers in the array

  This is terrible! For arrays where the individual elements are uniformly distributed in some range, the sums will be clustered around half the range times the number of elements. That will lead to many collisions and so worse than $O(1)$ expected time for operations on the hash table.

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)$.

#include <stdio.h>
#include <stdbool.h>

#include "ismap.h"
#include "isset.h"

int hash(int x)
{
  // from StackOverflow user Thomas Mueller
  // https://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key
  unsigned int z = x; // original was written for unsigned ints
  z = ((z >> 16) ^ z) * 0x119de1f3;
  z = ((z >> 16) ^ z) * 0x119de1f3;
  z = (z >> 16) ^ z;
  return (int)z;
}
  
bool distinct_with_hash(int intList[], int lenList, int (*hash)(int)){
  //intList is the array of integers we are comparing.
  //lenList is length of intList
  //hash is an appropriate hash function
  //assumes hash table implementation like in class.
  
  ismap* hashmap = ismap_create(hash); //create the hashmap

  int i = 0;
  while (i < lenList && !ismap_contains_key(hashmap, intList[i]))
      {
	ismap_put(hashmap, intList[i], NULL);
	i++;
      }
  ismap_destroy(hashmap);
  
  return i == lenList;
}


int main()
{
  int test_distinct[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
  int test_not_distinct[] = {5, 4, 8, 33, 20, 22, 33}; // who knows the significance of these?

  printf("Elements are distinct, return values are:\n");
  printf("%d\n", distinct_with_hash(test_distinct, sizeof(test_distinct) / sizeof(test_distinct[0]), hash));
  printf("Elements are not distinct, return values are:\n");
  printf("%d\n", distinct_with_hash(test_not_distinct, sizeof(test_not_distinct) / sizeof(test_not_distinct[0]), hash));
}

Problem : Suppose we have the following hash function:

0: cat
1:
2: eel
3: ant dog
4: fly
5: gnu
6: yak
7: bat

0: cat
1: yak
2: eel
3: ant
4: dog
5: fly
6: gnu
7: bat