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).
memory diagram with pointers 

#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.
memory diagram with pointers
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]
memory diagram with arrays and pointers to elements

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.
memory diagram with pointers
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.
memory diagram with pointers
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.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;
        }
   }
}