[CS50] Week 3 Review

---

Week 3

: The design of algorithms and how to measure their efficiency

---

 

Lecture Contents

 

 

 

 

1.  Linear Search

 

◇ Recall the idea of an array : blocks of memory that are consecutive 

Think of an array of seven red lockers

 

Q. Is the number 50 inside an array?

→ A computer could look at each locker to find if the number 50 is inside. (= searching)

 

algorithm

We can imagine various instructions we might provide our algorithm to undertake this task as follows (pseudocode):

For i from 0 to n-1
	If 50 is behind doors[i]
    	Return true
Return false

 

 

 

 

 

2. Binary search

 

: another search algorithm 

Assuming that the value within the lockers have been arranged from smallest to largest, the pseudocode being like:

If no doors left
	Return false
If 50 is behind doors[middle]
	Return true
Else if 50 < doors[middle]
	Search doors[0] through doors[middle - 1]
Else if 50 > doors[middle]
	Search doors[middle + 1] through doors[n-1]

 

 

 

 

 

3. Running Time

 

-uses big O notation

 

Computer scientists discuss efficiency in terms of the order of various running times

Some common running times we may see are:

• O(n^2).     : think of each student raising his/her hand (the worst running time)
• O(n log n) 
• O(n)           : linear search 
• O(log n)     : binary search
• O(1)            : (the fastest running time)

big O notation: the worst case, or upper bound
omega (Ω) : the best case, or lower bound 

theta (Θ) : the upper bound and lower bound are the same

 

 

 

 

4. Search.C

 

Let's implement linear search by writing code (in case of int): 

#include <cs50.h>
#include <stdio.h>

int main(void)
{
	int numbers[] = {20, 500, 10, 1, 100, 5, 50};
    
    int n = get_int("Number: ");
    for (int i = 0; i < 7; i++)
    {
    	if (numbers[i] == n)
        {
        	printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

 

-return 0 : to indicate success and exit the program

-return 1 : to exit the program with an error

 

(in case of string within an array) :

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

int main(void)
{
	string strings[] = {"battleship", "boot", "cannon", "iron", "thimble", "top hat"};
    
    string s = get_string("String: ");
    for (int i = 0; i < 6; i++)
    {
    	if (strcmp(string[i], s] == 0)
        {
        	printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

 

Notice that we used a function strcmp (), which comes from the string.h library, in order to compare strings.

 

We can combine these ideas of both numbers and strings into a single program (phonebook.c):

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

int main(void)
{
	string names[] = {"Carter", "David", "John"};
    string numbers[] = {"+1-617-495-1000", "+1-617-495-1000", "+1-949-468-2750"};
    
    string name = get_string("Name: ");
    for (int i = 0; i < 3; i++)
    {
    	if (strcmp(names[i], name) == 0)
        {
        	printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

→ However, there are numerous inefficiency. 

    There is a chance that people’s names and numbers may not correspond.

 

 

 

 

5. Data Structures

 

Would it be nice to create our own data type where we could associate a person with the phone number?

• typedef struct

        {

          variables;

         }

         new name of data type;

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

typedef struct
{
	string name;
    string number;
}
person;

int main(void)
{
	person people[3];
    
    people[0].name = "Carter";
    people[0].number = "+1-617-495-1000";
    
    people[1].name = "David";
    people[1].number = "+1-617-495-1000";
    
    people[2].name = "John";
    people[2].number = "+1-949-468-2750";
    
    string name = get_string("Name: ");
    for (int i = 0; i < 3; i++)
    {
    	if (strcmp(people[i].name, name) == 0)
        {
        	printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

 

Notice that a new datatype called person is defined.

: inside a person is a string called name and a string called number.

 

Notice how the dot notation such as people[0].name

: allows us to access the person at the 0th location and assign that individual a name.

 

 

 

 

6. Sorting

 

: the act of taking an unsorted list of values and soriting it.

  There are many different types of search algorithms :

 

ⓐ Selection Sort

 

: n개의 숫자들을 처음부터 끝까지 스캔하면서 가장 작은 숫자와 자리를 바꾸는 것

for i from 0 to n-1
	Find smallest number between numbers[i] and numbers[n-1]
    Swap smallest number with numbers[i]

: a lot of comparison → inefficiency

 

▷ How many steps?

= (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)

= Ω(n^2), Θ(n^2)

 

 

ⓑ Bubble Sort

 

: n개의 숫자들을 양 옆에 있는 숫자끼리 비교해서 자리를 바꾸는 것

Repeat n-1 times
	For i from 0 to n-2
    	If numbers[i] and numbers[i+1] out of order
        	Swap them
        If no swaps
        	Quit

: We only need to compare the pairs of numbers that haven't been sorted yet

 

▷ How many steps?

=  (n-1) * (n-1) = n^2 -2n +1 = O(n^2)

= Ω(n), because at least you have to check each pair)

 

 

 

★ <recursion>

: a concept within programming where a function calls itself

 

Pick up phone book
Open to middle of phone book
Look at page
If person is on page
	Call person
Else if person is earlier in book
	Open to middle of left half of book
    Go back to line 3
Else if person is later in book
	Open to middle of right half of book
    Go back to line 3
Else
	Quit

In our pseudocode for Week 0, this could've been simplified using recursion as follows:

Pick up phone book
Open to middle of phone book
Look at page
If person is on page
	Call person
Else if person is earlier in book
	Search left half of book
Else if person is later in book
	Search right half of book
Else
	Quit

Notice that we used 'Search' function inside of it. (recursion)

 

In Week 1, we created a pyramid structure as follows:

#
##
###
####

#include <cs50.h>
#include <stdio.h>

void draw(int n);

int main(void)
{
    draw(1);
}

void draw(int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("#");
    }
    printf("\n");

    draw(n + 1);
}

Notice that the draw function calls itself : recursion used

However, this code may get caught in an infinite loop because there's nothing telling the program to end.

 

We can correct our code as follows:

#include <cs50.h>
#include <stdio.h>

void draw(int n);

int main(void)
{
    int height = get_int("Height: ");
    draw(height);
}

void draw(int n)
{
    //If nothing to draw
    if(n <= 0)
    {
        return;
    }

    //Draw pyramid of height n-1
    draw (n - 1);

    for (int i = 0; i < n; i++)
    {
        printf("#");
    }
    printf("\n");
}

★ if(n <=0) : terminates the recursion because the problem have been solved.

    At some point, n-1 will equal 0, resulting in the draw function returning and the program will end.

 

 

ⓒ Merge Sort

 

: n개의 숫자를 반으로 계속 갈라 합쳐나가는 방법, a very efficient sort algorithm

If only one number
	Quit
Else
	Sort left half of number
    Sort right half of number
    Merge sorted halves

 

▷ How many steps?

= log(base)2(of)n  * n = O(n log n)

= Ω(n log n), because the algorithm still must visit each place in the list

= Θ(n log n)

 

---

Week 3에는 알고리즘에 대해서 배워보았어요

알고리즘은 a procedure used for solving a problem or performing a computation인데, 직역하면 문제를 해결할 때 쓰는 과정이나 방법입니다. Computer science를 배우게 된 계기 중 하나도 문제 해결 능력과 관련해서 다양한 방면으로 생각해보고 싶어서였어요. 하나의 문제를 푸는 데에도 한 가지 방법만 있는 것이 아니라, 더 효율적인 방법들을 찾아나가는 방법을 고심해보게 되었습니당

 

이번 주에 배운 것들 중 기억에 남는 것은 나만의 data type을 만들어 그 속에 정보를 담아 사용하는 typedef struct, 그리고 함수 안에 스스로의 함수를 call 하는 효과적이었던 recursion 개념입니다! 특히 recursion은 저 같은 코딩 초보에게는 실제 코드에서 어떻게 쓸 수 있을지.. 많은 고민을 하게 하는 것 같아요! Pset3에서 직접 이 방법을 사용해보고 정리해서 오도록 하겠슴니당! 이번 주도 홧팅 홧팅 ㅎㅎ