# 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
`struct`

s they might use to store information. Then, they write a program that prints out these sample`struct`

s. - 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); } }`

- A

- Students come up with sample
- 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; }`

- In

#### 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); }`

- Write a recursive function
- Fibonacci
- Write a recursive function
`fib`

that computes the`n`

th 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); }`

- Write a recursive function

#### 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); } }`

- Write a recursive function
- 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; }`

- The simplest solution loops

- Write a program
- 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)?

- If working with students who are feeling
- 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; }`

- Write a program
- 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)?

- If working with students who are feeling

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

- Slides (2022)
- Additional Slide Resources