CS50x 2023 - Lecture 3 - Algorithms

Name: CS50x 2023 - Lecture 3 - Algorithms
Uploaded: 2022-09-19T20:06:11.000Z
Duration: 4 h 2 min 36 s

Introduction

In this section, David Malan introduces the topic of algorithms and their efficiency. He also talks about how we will be formalizing some of the ideas from Week 0 and translating them into actual code.

Algorithms and Efficiency

In Week 0, we talked about algorithms and their efficiency.

We analyzed the efficiency of different algorithms using a graph with x-axis as the size of the problem and y-axis as time required to solve it.

The first two algorithms were linear in terms of efficiency while the third one was logarithmic.

Today, we'll revisit these ideas, formalize them a bit, but also translate some of them to code.

Computer Memory

In this section, David Malan talks about computer memory and how it is represented as a grid of bytes. He also discusses how arrays are stored in memory.

Storing Data in Arrays

Last week, we emphasized storing things in arrays which allowed us to store entire strings or sequences of characters.

However, inside an array in computer memory, finding a value requires opening each door one at a time.

We introduced indices or indexes last week which allowed us to bridge this conceptual world with actual code via square bracket syntax.

Conclusion

In this section, David Malan concludes by introducing a specific type of algorithm that will be discussed further in upcoming lectures.

Specific Type of Algorithm

No bullet points for this section.

Introduction

The problem is to find a number in an array of lockers. Linear search algorithm is introduced as a solution.

Linear Search Algorithm

The input is an array of seven lockers.

For each door from left to right, check if the number 50 is behind that door.

If 50 is found, return true and hold up the 50 proudly for the group.

If 50 is not found after checking all doors, return false.

Execution of Linear Search Algorithm

Stephanie executes the linear search algorithm to find the number 50 hidden behind one of the doors.

Stephanie's Execution

Stephanie checks each locker from left to right.

She finds numbers 20, 500, 10, 5, and 1 before finally finding the number 50.

Using an if and else statement would have caused her to cancel the code before finding the number.

Introduction to Pseudocode and Binary Search

In this section, David Malan introduces the concept of pseudocode and how it can be used to translate high-level English ideas into code. He also explains how binary search works and demonstrates its use in finding a number in an array.

Pseudocode

Pseudocode is a way of expressing algorithms using high-level English-like syntax.

Syntax exists that allows us to treat sets of lockers as arrays using bracket notation.

For loops are expressed in pseudocode as "for i from 0 to n minus 1."

Programmers use pseudocode to express ideas more specifically than high-level English but not as specific as actual code.

Binary Search

Binary search is an algorithm for finding a number in an array by repeatedly dividing the array in half.

The first step in binary search is checking if the middle door contains the desired number.

If the desired number is less than the middle door, we look at the left half of the array. If it's greater, we look at the right half.

We must handle situations where there are no doors left or when we don't have any doors at all.

Jackson demonstrates binary search by finding the number 50 in a sorted array.

Binary Search

In this section, the speaker explains how binary search works and how it can be used to solve problems more efficiently than linear search. The speaker also introduces some terminology that is commonly used when analyzing algorithms.

How Binary Search Works

To find an element in a sorted array using binary search:

Start by looking at the middle element of the array.

If the element you are looking for is equal to the middle element, return true.

If the element you are looking for is less than the middle element, search in the left half of the array.

If the element you are looking for is greater than the middle element, search in the right half of the array.

To find the middle index of an array:

Divide the total number of elements by 2 and round accordingly.

Binary Search vs Linear Search

Binary search is more efficient than linear search when searching through a sorted list or array.

Sorting an unsorted list or array takes time and effort, so it may not always be worth it to use binary search over linear search.

Formalizing Algorithm Analysis

There are common terms and jargon used when analyzing algorithms that programmers and computer scientists use.

Graphing running times can help compare different algorithms.

Big O Notation

In this section, the speaker introduces the concept of big O notation and explains how it is used to analyze algorithms.

Introduction to Big O Notation

The speaker introduces the concept of big O notation and explains that it is used to analyze algorithms.

The speaker explains that big O notation is used to get a sense of how fast or slow an algorithm is, rather than precisely counting the number of steps it takes.

The speaker defines big O notation as "on the order of" and provides examples for different types of algorithms.

Common Formulas in Computer Science

The speaker provides a cheat sheet for common formulas used in computer science when analyzing algorithms.

The formulas are ordered from slowest to fastest: n squared, n log n, n, log n, and 1 (constant time).

The speaker uses linear search as an example to demonstrate how to determine the worst-case scenario for an algorithm using big O notation.

Big O Notation

This section introduces the concept of big O notation, which is used to describe the order of an algorithm's running time. It also discusses upper and lower bounds on algorithms.

Introduction to Big O Notation

Big O notation describes the order of an algorithm's running time.

Logarithm of base 2 is just dividing something again and again.

Big O allows you to describe the order of an algorithm's running time-- like the magnitude of it-- but it also describes, more specifically, an upper bound.

Upper Bound and Lower Bound

Linear search and binary search are pretty good measures of how good or bad an algorithm might be in the worst case scenario.

Omega is a symbol that a computer scientist uses generally to describe a lower bound on an algorithm, often in the context of best case, though not necessarily.

Different algorithms might take different minimum steps such as n squared steps, or on the order of n steps. Some might only take n log n, or n, or log n, or 1.

In linear search best case scenario omega would be 1 step.

Binary search best case scenario omega would be 1 step too.

Upper Bound Coincides with Lower Bound

If some algorithm happens to have an identical upper bound and lower bound then we can use capital Greek theta as well.

Counting everyone literally in this room is in theta of n because in both best and worst cases it's going to take n steps.

Introduction to Linear Search

In this section, the instructor introduces linear search and demonstrates how to implement it in C using arrays.

Implementing Linear Search

Include cs50.h and stdio.h libraries.

Declare a static array called numbers with seven elements and initialize it with specific values.

Ask the user for a number to search for using get_int function.

Implement linear search using a for loop that iterates over the entire array and checks if each element is equal to the number being searched for. If found, print "found" and return 0. Otherwise, print "not found" and return any value other than 0.

Testing Linear Search

Compile the program by running make search in the terminal.

Test linear search by searching for different numbers such as 50, 20, and 1000.

No questions asked on this implementation of linear search.

Arrays in C

In this section, the instructor explains arrays in C programming language.

Declaring Arrays

Declare an array using square bracket notation followed by its size inside square brackets. For example: int arr;

Initialize an array during declaration by enclosing its elements inside curly braces. For example: int arr[] = 1, 2, 3;

Access individual elements of an array using their index inside square brackets. For example: arr= 10;

Multidimensional Arrays

Declare a two-dimensional array using square bracket notation followed by its size inside square brackets. For example: int arr;

Initialize a two-dimensional array during declaration by enclosing its elements inside curly braces and separating each row with a comma. For example: int arr[][] = 1, 2, 3, 4;

Access individual elements of a two-dimensional array using their row and column indices inside square brackets. For example: arr= 10;

Conclusion

In this section, the instructor concludes the lecture on linear search and arrays in C programming language.

Key Takeaways

Linear search is an algorithm for finding an element in an array by iterating over all elements until the desired element is found.

Arrays are collections of variables of the same data type that are stored in contiguous memory locations.

Multidimensional arrays are arrays of arrays that can be used to represent matrices or tables.

Understanding arrays is essential for writing programs that manipulate large amounts of data efficiently.

Introduction to String Comparison

In this section, David introduces the concept of string comparison in C and explains why using == to compare strings is not sufficient. He also introduces the strcmp() function as a solution for comparing strings.

String Comparison in C

Strings are arrays in C.

Using == to compare two strings will not work because it does not compare every character in each string.

The strcmp() function can be used to compare two strings by passing in two string inputs and returning 0 if they are equal.

Debugging Segmentation Faults

In this section, David discusses how switching from integers to strings can cause segmentation faults due to memory issues. He also highlights the importance of properly declaring array sizes and constants.

Memory Issues with Switching from Integers to Strings

Switching from integers to strings can cause segmentation faults due to memory issues.

Hardcoding values instead of declaring them as constants or higher up can lead to errors when iterating over arrays.

Properly declaring array sizes and constants is important for avoiding memory issues.

Linear Search

In this section, David Malan explains how to implement a linear search algorithm in C. He demonstrates how to use loops and conditional statements to search for an item in an array.

Implementing Linear Search

To implement linear search, we need to loop through each element of the array and compare it with the target value.

We can use a for loop to iterate over each element of the array.

If we don't include a return statement at the end of our main function, our program will continue running even after we've found what we're looking for.

It's helpful to include error codes when something goes wrong. Returning 0 in main signifies that our code is done and ready to exit successfully.

Phone Book

In this section, David Malan demonstrates how to create a phone book in C using arrays and strings. He shows how to store names and phone numbers in an array and then search for them using linear search.

Creating a Phone Book

To create a phone book, we can use an array of strings to store names.

We can also include phone numbers by storing them as strings alongside their corresponding names.

To search for a name in the phone book, we can use linear search just like before.

Storing Names and Numbers

In this section, David discusses different ways to store names and numbers in an array. He introduces the idea of using a 2D array but decides to keep it simple by using string numbers instead.

Storing Names and Numbers

A 2D array is one way to store names and numbers.

Instead of complicating things with a 2D array, David decides to use string numbers.

String numbers allow for punctuation like dashes or parentheses, making them more versatile.

Implementing Linear Search

In this section, David implements linear search to enable users to search the phone book. He uses a for loop and str compare function to find the name entered by the user.

Enabling User Search

The user can search the phone book by entering a name.

A for loop is used to iterate through all of the names in the phone book.

Str compare function is used to compare each name with the name entered by the user.

Printing Results

If there's a match between two strings (the name entered by user and one of the names in phonebook), then that person's number will be printed out.

If there's no match found, "not found" will be printed out instead.

Critiquing Design Choices

In this section, David asks students if they have any critiques about his design choices. Students point out potential issues with hardcoding values and assuming consistent ordering of arrays.

Potential Issues with Design Choices

Hardcoding values can lead to issues if the number of people in the phone book changes.

Assuming consistent ordering of arrays can lead to issues if the order is changed or sorted differently.

There's no code preventing inconsistencies between names and numbers in the two arrays.