Section 4 (Memory)

Topics

  • Pointers
  • Hexadecimal
  • malloc and free
  • File I/O

Programming Exercises

Below are a few example programming exercises that engage students in hands-on practice on the week’s topics. Keep in mind that section might not be long enough to include all exercises, so be sure to pick just a few! For this week, in particular, you might choose one exercise from each of these topics.

  • Practice with malloc
    • Give students practice with malloc and free, allocating memory dynamically, storing data in that memory, and then freeing memory when done with it.
  • Concatenate
    • Write a function concatenate that takes two strings and returns a concatenated version of the two strings.
    • Topics
      • Strings
      • Pointers
      • Memory management
    • Sample Solution
      char *concatenate(char *s1, char *s2)
      {
          int len1 = strlen(s1);
          int len2 = strlen(s2);
          char *s3 = malloc(len1 + len2 + 1);
          for (int i = 0; i < len1; i++)
          {
              s3[i] = s1[i];
          }
          for (int i = 0; i < len2; i++)
          {
              s3[len1 + i] = s2[i];
          }
          s3[len1 + len2] = '\0';
          return s3;
      }
      
      • You can test the solution using a program like:
        int main(void) 
        {
            char *s1 = get_string("s1: ");
            char *s2 = get_string("s2: ");
        
            char *s3 = concatenate(s1, s2);
            printf("%s\n", s3);
            free(s3);
        }
        
  • Copy
    • In copy.c, write a program that copies a text file. Users should be able to run ./copy file1 file2 to copy the contents of text file file1 into file file2.
    • This is a good exercise to do together, as students likely won’t be familiar enough with File I/O to know how to do this on their own yet.
      #include <stdbool.h>
      #include <stdio.h>
      
      int main(int argc, char *argv[])
      {
          if (argc != 3)
          {
              printf("Usage: ./copy infile outfile\n");
              return 1;
          }
          FILE *infile = fopen(argv[1], "r");
          FILE *outfile = fopen(argv[2], "w");
          while (true)
          {
              char c = fgetc(infile);
              if (c == EOF)
              {
                  break;
              }
              fputc(c, outfile);
          }
          fclose(infile);
          fclose(outfile);
      }
      
  • Copy (Extensions)
    • If you’ve already done copy.c, these exercises are good extensions. Students could be expected to attempt these on their own, since they involves only a small amount of additional functionality:
      • In uppercase.c, write a program that takes a file, and generates a new file that converts all of the letters in the original file to uppercase.
      • In caesar.c, write a program that takes a file, and generates a new file that shifts all of the letters in the original file by 1.
  • GIF Detection
    • Write a program gif.c that checks if a file (likely) a GIF (specifically, a GIF 89a file, the latest version of the GIF file format). Note that the first six characters of a GIF 89a file are the characters G, I, F, 8, 9, a.
    • Topics
      • File signatures
      • File I/O
    • Sample Solution
      // Detect if a file is a GIF
      
      #include <stdbool.h>
      #include <stdio.h>
      
      const char signature[6] = {'G', 'I', 'F', '8', '9', 'a'};
      
      bool is_gif(FILE *f);
      
      int main(int argc, char *argv[])
      {
          // Check usage
          if (argc != 2)
          {
              printf("Usage: ./gif0 filename\n");
              return 1;
          }
      
          // Open file
          FILE *f = fopen(argv[1], "r");
          if (!f)
          {
              printf("Could not read file.\n");
              return 1;
          }
      
          // Check for GIF signature
          if (is_gif(f))
          {
              printf("GIF\n");
          }
          else
          {
              printf("NOT GIF\n");
          }
      
          // Close file
          fclose(f);
      }
      
      bool is_gif(FILE *f)
      {
          // Read bytes in to buffer
          unsigned char buffer[6];
          int bytes = fread(buffer, 1, 6, f);
      
          // Check number of bytes read
          if (bytes != 6)
          {
              return false;
          }
      
          // Check each byte
          for (int i = 0; i < 6; i++)
          {
              if (buffer[i] != signature[i])
              {
                  return false;
              }
          }
      
          return true;
      }
      
  • PDF Detection
    • Create a program, pdf.c, that checks whether a file, passed in as a command-line argument, is a PDF. All PDFs will be assumed to begin with a four byte sequence: 0x25 0x50 0x44 0x46.
    • Topics
      • File signatures
      • File I/O
    • Resources
    • Example Usage
      $ ./pdf test.pdf
      Likely a PDF!
      
      $ ./pdf test.jpg
      Hm, not a PDF.
      
    • Sample Solution
      #include <cs50.h>
      #include <stdint.h>
      #include <stdio.h>
          
      int main(int argc, string argv[])
      {
          // Check for usage
          if (argc != 2)
          {
              printf("Improper usage.\n");
              return 1;
          }
          
          // Open file
          FILE *pdf = fopen(argv[1], "r");
          
          // Create buffer for file
          uint8_t buffer[4];
          
          // Create array of signature bytes
          uint8_t signature[] = {0x25, 0x50, 0x44, 0x46};
          
          // Read first 4 bytes from file, then close.
          fread(buffer, 1, 4, pdf);
          fclose(pdf);
          
          // Check buffer against signature
          for (int i = 0; i < 4; i++)
          {
              if (signature[i] != buffer[i])
              {
                  printf("Hm, not a PDF.\n");
                  return 0;
              }
          }
          printf("Likely a PDF!\n");
          return 0;
      }
      

Conceptual Exercises

These exercises involve thinking and problem-solving, though writing a program is less of the focus here. They still engage students in practice that helps them better understand the week’s concepts!

  • Pointer Prediction
    • Have students mentally walk through the code on the left-hand side of this diagram. Ask: How do the values of the variables and pointers evolve? What will the final values for each variable or pointer be?
    • Afterwards, students should download, compile, and run the same code, in pointers.c to test their predictions against how the code actually runs.
    • pointers.c
      #include <cs50.h>
      #include <stdio.h>
      
      int main(void)
      {
          int a = 28;
          int b = 50;
          int *c = &a;
      
          *c = 14;
          c = &b;
          *c = 25;
          
          // Print results
          printf("a has the value %i, located at %p\n", a, &a);
          printf("b has the value %i, located at %p\n", b, &b);
          printf("c has the value %p, located at %p\n", c, &c);
      }
      
  • Debugging Memory Leaks
    • Debug a program, create.c, that creates a file given as input at the command-line. For example, ./create test.c will create a file test.c. But the code has three memory errors! Can you find and fix them! Try running valgrind ./create test.c to check.
    • Topics
      • Valgrind
      • Memory leaks
      • Common memory errors
      • Debugging
    • create.c
      #include <stdio.h>
      #include <stdlib.h>
      #include <string.h>
          
      int main(int argc, char *argv[])
      {
          // Check for improper usage, otherwise, get filename length
          if (argc != 2)
          {
              printf("Wrong usage: Try ./create [filename]\n");
              return 1;
          }
          int filename_length = strlen(argv[1]);
          
          // Create a new block of memory to store filename
          char *filename = malloc(sizeof(char) * filename_length);
          
          // Copy argv[1] into block of memory for filename
          sprintf(filename, "%s", argv[1]);
          
          // Open new file under the name stored at filename
          FILE *new_file = fopen(filename, "w");
      }
      
    • Three Errors to Identify
      • malloc one additional character, to leave space for NUL terminating character.
      • free filename
      • Close the opened file
    • Sample Solution (Code)
      #include <stdio.h>
      #include <stdlib.h>
      #include <string.h>
      
      int main(int argc, char *argv[])
      {
      
          // Check for improper usage, otherwise, get filename length
          if (argc != 2)
          {
              printf("Wrong usage: Try ./create [filename]\n");
              return 1;
          }
          int filename_length = strlen(argv[1]);
      
          // Create a new block of memory to store filename. Add one additional character for NUL character.
          char *filename = malloc(sizeof(char) * (filename_length + 1));
      
          // Copy argv[1] into block of memory for filename
          sprintf(filename, "%s", argv[1]);
      
          // Free filename
          free(filename);
      
          // Open new file under the name stored at filename
          FILE *new_file = fopen(filename, "w");
      
          if (new_file == NULL)
          {
              printf("Could not create file.");
              return 1;
          }
      
          // Close new file
          fclose(new_file);
      }
      

Discussion Questions

One technique to promote participation in section is a quick, 2–3 minute discussion question. Letting students posit their own reasoning, even if they’re not entirely sure of an answer, can help reinforce material from lecture. One model for introducing these questions is the “Think, Pair, Share” approach, in which students take 30 seconds to think of their own answer and 60 seconds to share their answer with a partner. Afterwards, you can call on random pairs to share their thinking with the larger group. It’s also best to follow up with your own answer, too!

  • Why might each file type need to have a specific set of header bytes? If a file has the header bytes associated with .jpg, why does this not conclusively indicate the file is a .jpg?
  • In Binky Pointer Fun, we saw that Binky attempted to dereference a pointer that hadn’t yet been assigned a “pointee”. Why might this cause an error?

Annotated Sample Slides

Here you’ll find sample slides to adopt or adapt when teaching Section 4.

Some slides contain speaker notes to illustrate why the sample section takes a certain approach to illustrating a concept or leading an exercise. You’re welcome to modify these slides as you see fit, though do try to keep some of the same elements of active learning that have been included in these samples.

Past versions of sample slides are also available under the “Additional Slide Resources” dropdown.