Worksheet: C3

Worksheets are self-guided activities that reinforce lectures. They are not graded for accuracy, only for completion. Worksheets are due by Sunday night before the next lecture.

Github Classroom Link: https://classroom.github.com/a/aXobtvT3

Questions

Examine the program below and complete the code.

#include <stdio.h>

#define NUM_ROWS 3
#define NUM_COLS 3

int main() {

    int matrix[NUM_ROWS][NUM_COLS] = { {2, 5, 1},
                                       {3, 9, 6},
                                       {8, 7, 4}};

    // WRITE CODE TO PRINT OUT THE MATRIX

}

Finish the code above so that the output is the following:

5 1 
9 6 
7 4 

Reveal Solution

Examine the program below and complete the code.

#include <stdio.h>

#define NUM_ROWS 3
#define NUM_COLS 3

int main() {

    int matrix_a[NUM_ROWS][NUM_COLS] = { {2, 5, 1},
                                         {3, 9, 6},
                                         {8, 7, 4}};

    int matrix_b[NUM_ROWS][NUM_COLS] = { {4, 1, 6},
                                         {9, 7, 5},
                                         {3, 8, 2}};

    int matrix_c[NUM_ROWS][NUM_COLS];

    // https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm#Iterative_algorithm
    /*
        For i from 1 to num_rows:
            For j from 1 to num_cols:
                Let sum = 0
                For k from 1 to num_cols:
                    Set sum = sum + (Aik * Bkj)
                Set Cij = sum
    */
    
    // USING THE ALGORITHM ABOVE
    // WRITE CODE HERE TO MULTIPLY THE TWO MATRICES
    // PUT THE RESULT IN MATRIX_C

    // PRINT RESULTING MATRIX_C
}

Finish the code above so that the output is the following:

45 39 
114 75 
89 91 

Reveal Solution

The following function deceleration will not compile.
```
void foobar( int a[][]);
```
Provide an explanation for what is wrong and how to fix it.

Reveal Solution

For array that has multiple dimensions, all but the first dimension needs to have bounds. Thus, at the very least, the declaration needs to be void foobar( int a[][NUM_COLS]); where NUM_COLS is an integer constant or variable.

Examine the program below and answer the following questions.

#include <stdio.h>

int main() {
    int array[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

    printf("%d\n", *(*array + 4));
}

Attempt to answer these questions without running the code!

What is the output of this program?
Explain the memory layout of a two-dimensional array?

Reveal Solution

Examine the program below and answer the following questions.

#include <stdio.h>
#include <string.h>
int main(){
    int a[2][3] = { {10,20,30}, {5,6,7} };
   
    int * p = (int *)a+4;

    p[1] = 42;
    //MARK
}

Attempt to answer these questions without running the code

What are the values of a at MARK
In plain English, provide a description of how the line int * p = (int *)a+4 works when the array dimensions are int[2][3].
Draw the memory diagram at MARK

Reveal Solution

Examine the program below and answer the following questions.

int main(){
  int a[][3] = { {10,20,30}, 
                {5,6,7},
                {-1,-2,-3},
                {17,19,21}};

  int ** p = &a[1];
  int * q =  &p[1];
  
  q[1] = 42;
  //MARK
}

Attempt to answer these questions without running the code

What are the values of a after at MARK
Offer a plain English explanation for what exactly int * q = &p[1] is referring to in a
Draw the memory diagram at MARK

Reveal Solution

What are the two possible byte ordering and which byte ordering does nearly all modern computers use?

As an example of this byte ordering, explain how the integer 513 would be stored, byte-by-byte.

Reveal Solution
- Threr are Little Endian and Big Endian and most modern computers use Little Endian.
- The integer 513 would be stored as the following:
  .------+------+------+------. | 00 | 00 | 01 | 02 | \\ In hexadecimal '------+------+------+------'

Examine the program below and answer the following questions.

int main(){

  //two ints in hexadecimal
  int a[] = {0x42434445, 
             0x20212223};
             
  short * b = (short *) &a[1]; //MARK
  
  //prints the two bytes of the short as a hexaxdecimal
  // like 0xbeef or 0xdead
  
  printf("0x%0hx",b[0]);
  
  //so what is the short in b[0] as a hexadecimal?
}

Attempt to answer these questions without running the code

What is the output?
Offer an explanation for the output
Draw a memory diagram at MARK

Reveal Solution

Below are the results of two Tic-Tac-Toe games. Unfortunately one of the players (x or o) has inserted some evil code to change the boards.
```
#include <stdio.h>
#include <string.h>

int main() {
  char *game_1[3] = {
    "o|x| ",
    "o|o|x",
    "x|x|o"};

char *game_2[3] = {
      "x|x|o",
      "o|x| ",
      "o|x|o",
  };
  
  //Begin Evil Code
  for (int i = 0; i < 3; i++) {
    char **tmp = &game_1[i];
    game_1[i] = game_2[i];
    game_2[i] = *tmp;
  }
  //End Evil Code

  printf("The winner is...");
}
```
After the evil code was inserted, one player won. Which player, x or o inserted the evil code, so that they won?

Reveal Solution
- Player x inserted the evil code so that they won.
- In the evil code, it seems like the two boards are swapped line by line with the help of the tmp variable. However, the reality is that game_2 is copied to game_1 because tmp is given the address, not value, of each string in game_1. This means after the line game_1[i] = game_2[i], both tmp and game_1[i] are pointing to game_2[i]. Therefore, when the for loop is completed, everything in game_2[i] is copied to game_1[i] resulting in two identical boards.

A computer science major who can’t do algebra is trying to modify their grades. The student was able to hack into the administrative code and insert some Evil Code to change their grade.

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

typedef struct {
  char *name;
  char grade;
} course_t;

int main() {

  course_t *courses[3];

  courses[0] = malloc(sizeof(course_t));
  courses[0]->name = "Basket Weaving";
  courses[0]->grade = 'A';

  courses[1] = malloc(sizeof(course_t));
  courses[1]->name = "Complex Tic Tac Toe Analysis";
  courses[1]->grade = 'A';

  courses[2] = malloc(sizeof(course_t));
  courses[2]->name = "Algebra for CS Majors";
  courses[2]->grade = 'D';

  //... some admin code

  // Begin Evil Code inserted by student
  courses[2] = malloc(sizeof(course_t));
  courses[2]->name = "Algebra for CS Majors";
  courses[2]->grade = 'B';

  // Rest of program
  // ...

  printf("Your grades for the semester are ...\n");
  // prints grades
  free(courses[0]);
  free(courses[1]);
  free(courses[2]);
}

Did the student introduce a memory leak?
If so, how many bytes were leaked?
Explain the memory leak or why there can’t be a memory leak.

Reveal Solution

What is the difference between a memory violation and a memory leak? Provide a small code example of each.

Reveal Solution

Consider the following code
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
  char * name;
  short x;
  short y;
} point_t;

int main() {
  point_t * a = malloc(sizeof(point_t));

  char * tmp_name = "Point of Interest";
  a->name = malloc(sizeof(char)*strlen(tmp_name)+1);
  strcpy(a->name, tmp_name); //Copies the string on the right to the left
  a->x = 4;
  a->y = 1;

  point_t b;
  b = *a;
  free(a);

  printf("%s",b.name); //MARK
  free(b.name);
}
```
Attempt to answer these questions without running the code
- Is printing at the indicated MARK a memory violation? Does this program leak any memory?
- If so, how many bytes of a memory violation occur? If not, explain why there is no violation.
- What is the output?
Reveal Solution
- Printing at the indicated MARK is not a memory violation. The program does not leak any memory.
- There is no memory violation because b is on the stack and b.name is the only thing in b pointing to the heap. b.name is also not freed when a is freed because a->name is pointing to a char * on the heap that has nothing to do with a itself.
- The output is Point of Interest.

For the next few questions, consider that your implementing a Linked List in C using the following struct

typedef struct node{
    int val;
    struct node * next;

} node_t;
typedef struct llist{
   node_t head;
   int len;    
} llist_t;

Write the following functions:

llist_t * new_list() : allocates a new empty linked list
void del_list(llist_t * list) : dealocates a linked list list

Reveal Solution

Referring to the linked list structures above, complete the following recursive functions over these lists

int sum(llist_t * list){
    return _sum(list->head);
}

int _sum(node_t * node){
  //FINISH ME!
}


int min(llist_t * list){
    return _min(list->head);
}

int _min(node_t * node){
  //FINISH ME!
}

void append(llist_t * list, int new_value){
   list->head = _append(list->head, new_value);
}

node_t * _append(node_t * node, int new_value){
  //FINISH ME! --- this one is tough!
}

Reveal Solution