CS50 for JDs

Algorithms, Data Structures

abstraction

seminars

Innovative Algorithms and Their Applications

Fri, Jan 6, 9:00 AM – 11:00 AM EST in WCC Room 1010, �with Catherine Deskur

shorts

input → 

→ output

algorithms

linear search

For each door from left to right

If number is behind door

Answer is true

Answer is false

For each door from left to right

If number is behind door

Answer is true

Else

Answer is false

binary search

​

​

If number behind middle door

Return true

Else if number < middle door

Search left half

Else if number > middle door

Search right half

If no doors

​

If number behind middle door

Return true

Else if number < middle door

Search left half

Else if number > middle door

Search right half

If no doors

Return false

If number behind middle door

Return true

Else if number < middle door

Search left half

Else if number > middle door

Search right half

size of problem

time to solve

size of problem

time to solve

O(n)

O(n/2)

O(log₂n)

size of problem

time to solve

O(n)

O(n/2)

O(log₂n)

size of problem

time to solve

O(n)

O(n)

O(log n)

O(n²)

O(n log n)

O(n)

O(log n)

O(1)

O(n²)

O(n log n)

O(n) linear search

O(log n) binary search

O(1)

Ω(n²)

Ω(n log n)

Ω(n)

Ω(log n)

Ω(1)

Ω(n²)

Ω(n log n)

Ω(n)

Ω(log n)

Ω(1) linear search, binary search

input → 

→ output

unsorted → 

→ output

unsorted → 

→ sorted

6 3 8 5 2 7 4 1

selection sort

For i from 0 to n-1

Find smallest item between i'th item and last item

Swap smallest item with i'th item

(n – 1)

​

​

​

​

(n – 1) + (n – 2)

​

​

​

​

(n – 1) + (n – 2) + (n – 3)

​

​

​

​

(n – 1) + (n – 2) + (n – 3) + ... + 1

​

​

​

​

(n – 1) + (n – 2) + (n – 3) + ... + 1

n(n – 1)/2

​

​

​

(n – 1) + (n – 2) + (n – 3) + ... + 1

n(n – 1)/2

(n² – n)/2

​

​

(n – 1) + (n – 2) + (n – 3) + ... + 1

n(n – 1)/2

(n² – n)/2

n²/2 – n/2

​

(n – 1) + (n – 2) + (n – 3) + ... + 1

n(n – 1)/2

(n² – n)/2

n²/2 – n/2

O(n²)

O(n²) selection sort

O(n log n)

O(n)

O(log n)

O(1)

Ω(n²) selection sort

Ω(n log n)

Ω(n)

Ω(log n)

Ω(1)

6 3 8 5 2 7 4 1

bubble sort

Repeat n-1 times

For i from 0 to n-2

If i'th and i+1'th elements out of order

Swap them

(n – 1) × (n – 1)

​

​

​

​

(n – 1) × (n – 1)

n² – 1n – 1n + 1

​

​

​

(n – 1) × (n – 1)

n² – 1n – 1n + 1

n² – 2n + 1

​

​

(n – 1) × (n – 1)

n² – 1n – 1n + 1

n² – 2n + 1

O(n²)

​

O(n²) bubble sort

O(n log n)

O(n)

O(log n)

O(1)

Ω(n²) bubble sort

Ω(n log n)

Ω(n)

Ω(log n)

Ω(1)

bubble sort

Repeat n-1 times� For i from 0 to n-2� If i'th and i+1'th elements out of order� Swap them

Repeat until no swaps� For i from 0 to n-2� If i'th and i+1'th elements out of order� Swap them

O(n²) bubble sort

O(n log n)

O(n)

O(log n)

O(1)

Ω(n²)

Ω(n log n)

Ω(n) bubble sort

Ω(log n)

Ω(1)

recursion

1 Pick up phone book

2 Open to middle of phone book

3 Look at page

4 If person is on page

5 Call person

6 Else if person is earlier in book

7 Open to middle of left half of book

8 Go back to line 3

9 Else if person is later in book

10 Open to middle of right half of book

11 Go back to line 3

12 Else

13 Quit

1 Pick up phone book

2 Open to middle of phone book

3 Look at page

4 If person is on page

5 Call person

6 Else if person is earlier in book

7 Open to middle of left half of book

8 Go back to line 3

9 Else if person is later in book

10 Open to middle of right half of book

11 Go back to line 3

12 Else

13 Quit

1 Pick up phone book

2 Open to middle of phone book

3 Look at page

4 If person is on page

5 Call person

6 Else if person is earlier in book

7 Open to middle of left half of book

8 Go back to line 3

9 Else if person is later in book

10 Open to middle of right half of book

11 Go back to line 3

12 Else

13 Quit

1 Pick up phone book

2 Open to middle of phone book

3 Look at page

4 If person is on page

5 Call person

6 Else if person is earlier in book

7 Search left half of book

8

9 Else if person is later in book

10 Search right half of book

11

12 Else

13 Quit

1 Pick up phone book

2 Open to middle of phone book

3 Look at page

4 If person is on page

5 Call person

6 Else if person is earlier in book

7 Search left half of book

8 Else if person is later in book

9 Search right half of book

10 Else

11 Quit

merge sort

If only one item

Return

Else

Sort left half of items

Sort right half of items

Merge sorted halves

If only one item

Return

Else

Sort left half of items

Sort right half of items

Merge sorted halves

O(n²)

O(n log n) merge sort

O(n)

O(log n)

O(1)

Ω(n²)

Ω(n log n) merge sort

Ω(n)

Ω(log n)

Ω(1)

data structures

bool Boolean value

float floating-point value

int integer

str string

...

dict

list

range

set

tuple

...

arrays

O(n²)

O(n log n)

O(n)

O(log n)

O(1)

O(n²)

O(n log n)

O(n) insert

O(log n) search

O(1)

linked lists