Week 3 (Algorithms)

Topics

  • Structs
  • Searching
  • Sorting
  • Running Time
  • Recursion

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

Structs

  • Defining Structs
    • Students come up with sample structs they might use to store information. Then, they write a program that prints out these sample structs.
    • Topics
      • structs
      • Format codes
      • Types
    • Sample solutions
      • A struct for students 
        typedef struct
{
    int id;
    string name;
    float gpa;
}
student;
      • A struct for a date 
        typedef struct
{
    int month;
    int day;
    int year;
}
date;
      • Printing a struct 
        #include <cs50.h>
#include <stdio.h>

typedef struct
{
    int id;
    string name;
    float gpa;
}
student;

int main(void)
{
    student students[3];

    students[0].name = "Alice";
    students[0].id = 10;
    students[0].gpa = 3.6;

    students[1].name = "Bob";
    students[1].id = 20;
    students[1].gpa = 3.7;

    students[2].name = "Charlie";
    students[2].id = 30;
    students[2].gpa = 3.8;

    for (int i = 0; i < 3; i++)
    {
        printf("%s has student id %i and a GPA of %.2f\n", students[i].name, students[i].id, students[i].gpa);
    }
}
  • Create a Custom get Function
    • In get_custom.c, students create their own get function that prompts the user to input attributes into a struct they’ve defined. For exampe, get_candidate or get_student. Students may rely on get_string, get_float, etc., though the function should ultimately return a new instance of their struct.
    • Topics
      • Structs
      • Return values
      • Function definitions
    • Sample Usage 
      $ ./get_custom
Enter a candidate:
Name: Joe
Votes: 100
New candidate has name Joe and 100 votes
    • Sample Solution 
      #include <cs50.h>
#include <stdio.h>

typedef struct {
    string name;
    int votes;
} candidate;

candidate get_candidate(string prompt);

int main(void)
{
    candidate new_candidate = get_candidate("Enter a candidate:");
    printf("New candidate has name %s and %i votes\n", new_candidate.name, new_candidate.votes);
}

candidate get_candidate(string prompt)
{
    // Print prompt
    printf("%s\n", prompt);

    // Declare new candidate
    candidate new_candidate;

    // Assign attributes
    new_candidate.name = get_string("Name: ");
    new_candidate.votes = get_int("Votes: ");

    return new_candidate;
}

Recursion

  • Factorial
    • Write a recursive function factorial that takes an integer n and computes its factorial. (The factorial of 5, for example, is 5 * 4 * 3 * 2 * 1 = 120).
    • Topics
      • Recursion
      • Base cases
      • return
    • Sample Solution 
      int factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}
  • Fibonacci
    • Write a recursive function fib that computes the nth Fibonacci number. The 0th Fibonacci number is 0, the 1st Fibonacci number is 1, and every subsequent Fibonacci number is sum of the two preceding Fibonacci numbers.
    • Topics
      • Recursion
      • Base cases
      • return
    • Sample Solution 
      int fib(int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

Algorithms

  • Binary Search
    • Write a recursive function search that takes in four inputs, a value to search for, a sorted array of values, a start index, and an end index. The function should perform binary search, returning true if the number is found between the start and end index, and false otherwise.
    • Topics
      • Searching algorithms
      • Arrays
      • Recursion
    • Distribution Code 
      bool search(int value, int values[], int start, int end)
{
    // TODO
}
    • Sample Solution 
      bool search(int value, int values[], int start, int end)
{
    // if the "end" comes before the "start" then the element can't be in the array
    if (end < start)
    {
        return false;
    }
        
    // Calculate the midpoint of the current array
    int midpoint = (start + end) / 2;
        
    // if we found what we're looking for in the middle, return true
    if (value == values[midpoint])
    {
        return true;
    }
        
    // If the element at the midpoint is too large, repeat with the left half of the array
    else if (value < values[midpoint])
    {
        return search(value, values, start, midpoint - 1);
    }
        
    // Otherwise, repeat with the right half of the array
    else
    {
        return search(value, values, midpoint + 1, end);
    }
}
  • Writing Bubble Sort
    • Write a program bubble.c that sorts an array of integers using bubble sort.
    • Topics
      • Sorting algorithms
      • Arrays
      • break
    • Distribution Code 
      #include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Get input
    int n = get_int("How many values? ");
    int values[n];
    for (int i = 0; i < n; i++)
    {
        values[i] = get_int("Value %i: ", i);
    }

    // TODO: sort numbers

    // Print sorted values
    for (int i = 0; i < n; i++)
    {
        printf("%i\n", values[i]);
    }
}
    • Sample Solutions
      • The simplest solution loops n - 1 times, each time checking the first n - 1 elements of the array to make a swap. 
        for (int i = 0; i < n - 1; i++)
{
    for (int j = 0; j < n - 1; j++)
    {
        if (values[j] > values[j + 1])
        {
            int temp = values[j];
            values[j] = values[j + 1];
            values[j + 1] = temp;
        }
    }
}
      • An optimization can be made by realizing that the inner loop need only loop n - 1 - i times instead of n - 1 times, since each time the outer loop runs, the next highest number will be in its correct position.
      • Another optimization can be made by checking, on each iteration of the outer loop, if any swaps were made. If no swaps were made, then the list is sorted, and the loop can exit even if it hasn’t run all n - 1 times.
      • The final version, then, is: 
        for (int i = 0; i < n - 1; i++)
{
    bool swaps = false;
    for (int j = 0; j < n - 1 - i; j++)
    {
        if (values[j] > values[j + 1])
        {
            swaps = true;
            int temp = values[j];
            values[j] = values[j + 1];
            values[j + 1] = temp;
        }
    }

    if (swaps == false)
        break;
}
  • Analyzing Bubble Sort
    • If working with students who are feeling less comfortable, writing bubble sort might be too steep of an introduction to the algorithm. You might, instead, choose to show students a working implementation of bubble sort and ask them questions that prompt discussion about its features.
    • Topics
      • Sorting algorithms
      • Runtime analysis
    • Distribution code for students can be found here, in bubble_solved.c.
    • Some questions you might pose to students could include:
      • What questions do you have about the code, as written? What seems confusing?
      • Which pieces of code indicate Bubble Sort runs in O(N^2) and Ω(N)?
  • Selection Sort
    • Write a program selection.c that sorts an array of integers using selection sort.
    • Topics
      • Sorting Algorithms
      • Arrays
      • Swapping
    • Distribution Code 
      #include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Get input
    int n = get_int("How many values? ");
    int values[n];
    for (int i = 0; i < n; i++)
    {
        values[i] = get_int("Value %i: ", i);
    }

    // TODO: sort numbers

    // Print sorted values
    for (int i = 0; i < n; i++)
    {
        printf("%i\n", values[i]);
    }
}
    • Sample Solution 
      for (int i = 0; i < n - 1; i++)
{
    int min_index = i;
    for (int j = i + 1; j < n; j++)
    {
        if (values[j] < values[min_index])
        {
            min_index = j;
        }
    }
    int temp = values[i];
    values[i] = values[min_index];
    values[min_index] = temp;
}
  • Analyzing Selection Sort
    • If working with students who are feeling less comfortable, writing bubble sort might be too steep of an introduction to the algorithm. You might, instead, choose to show students a working implementation of bubble sort and ask them questions that prompt discussion about its features.
    • Topics
      • Sorting algorithms
      • Runtime analysis
    • Distribution code for students can be found here, in selection_solved.c.
    • Some questions you might pose to students could include:
      • What questions do you have about the code, as written? What seems confusing?
      • Which pieces of code indicate Selection Sort runs in O(N^2) and Ω(N^2)?

Discussion Questions

One technique to promote participation in class 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!

  • When might it make sense to sort before searching? When would it make sense to simply search?
  • Why might computer scientists be okay with defining algorithm’s runtimes as “on the order of” something—why not use a more specific runtime?

Annotated Sample Slides

Here you’ll find sample slides to adopt or adapt when teaching Week 3.

Some slides contain speaker notes to illustrate why the sample slides take 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.