1 of 50

Section 1

CA : [Name of the CA]

1

2 of 50

Section 1 agenda

Good/bad pseudocode examples
Review Karatsuba integer multiplication
Review MergeSort & InsertionSort
Review big-Oh notation

Practice in groups

2

3 of 50

What is pseudocode?

3

4 of 50

What is a pseudocode

Pseudocode is a plain language clear description of the steps in an algorithm.
Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine reading.
We’re about to see some high-level guidelines for writing pseudocode, but remember to aim for maximum clarity rather than adhering to any specific rules

5 of 50

What is a good pseudocode?

6 of 50

Example: Light Bulbs and Lost Socket

Siggi used to have n pairs of light bulbs and their matching sockets with distinct sizes such that each light bulb would only match exactly one of the n sockets and vice versa.

But Siggi lost all their sockets while they were moving from one dorm room to another. Lucky found a socket in the hallway and gave it to Siggi with the hopes that it’s one of the lost sockets.

Siggi is extremely organized, so they have already ordered their light bulbs based on their base sizes from small to big. Help Siggi find the matching light bulb with the found socket.

7 of 50

Sample Pseudocodes

8 of 50

find_matching_light_bulb (LightBulbs, Socket)

search the light bulbs and return the matching lightbulb with the socket

9 of 50

Clear description of the steps

find_matching_light_bulb (LightBulbs, Socket)

search the light bulbs and return the matching lightbulb with the socket

find_matching_light_bulb (lightBulbs, socket)

for lightBulb in lightBulbs:

if lightBulb and socket match: return lightBulb

return no matching light bulb found

10 of 50

For the sake of this example, assume the following implementation of binary search was given in the lecture.

Using the algorithms covered during the lectures without their pseudocode

11 of 50

Using the algorithms covered during the lectures without their pseudocode

find_matching_light_bulb (LightBulbs, Socket)

run binary_search to find the matching light bulb.

12 of 50

You can use the algorithms covered during the lectures without their pseudocode, but make sure to specify their inputs and other details clearly.

find_matching_light_bulb (LightBulbs, Socket)

run binary_search to find the matching light bulb.

find_matching_light_bulb (lightBulbs, socket)

ind=modified_binary_search(lightBulbs,

socket)

if lightBulbs[ind] matches with socket:

return lightBulbs[ind]

else:

return no matching light bulb found

Modified_binary_search is binary_search, but we change line 6 to: if array[mid]’s lightBulb size is greater than or equal to socket’s size

13 of 50

Make the Pseudocode as simple as possible�

find_matching_light_bulb (lightBulbs, socket)

if the 1st light bulb matches the socket:

return the first light bulb

if the 2nd light bulb matches the socket:

return the 2nd light bulb

if the 3rd light bulb matches the socket:

return the 3rdlight bulb

.

if the nth light bulb matches the socket:

return the nth light bulb

return no matching light bulb found

14 of 50

Make the Pseudocode as simple as possible�

find_matching_light_bulb (lightBulbs, socket)

for lightBulb in lightBulbs:

if lightBulb and socket match: return lightBulb

return no matching light bulb found

find_matching_light_bulb (lightBulbs, socket)

if the 1st light bulb matches the socket:

return the first light bulb

if the 2nd light bulb matches the socket:

return the 2nd light bulb

if the 3rd light bulb matches the socket:

return the 3rdlight bulb

.

if the nth light bulb matches the socket:

return the nth light bulb

return no matching light bulb found

15 of 50

Divide-and-Conquer

15

16 of 50

Divide and conquer

Break problem up into smaller (easier) sub-problems

Big problem

Smaller problem

Yet smaller problem

[Lecture 1: Slide 76]

17 of 50

Divide and conquer for multiplication

1

2

3

4

One n-digit multiply

Four (n/2)-digit multiplies

Break up an n-digit integer:

Suppose n is even

18 of 50

There are n²1-digit problems

1 problem

of size n

4 problems

of size n/2

4^t problems

of size n/2^t

____ problems

of size 1

…

Note: this is just a cartoon – I’m not going to draw all 4^t circles!

19 of 50

Do Better: Karatsuba integer multiplication

Recursively compute these THREE things:

ac
bd
(a+b)(c+d)

ad + bc = (a+b)(c+d) - ac - bd

Assemble the product:

20 of 50

What’s the running time?

1 problem

of size n

3 problems

of size n/2

3^t problems

of size n/2^t

____ problems

of size 1

…

We aren’t accounting for the work at the higher levels! But we’ll see later that this turns out to be okay.

Note: this is just a cartoon – I’m not going to draw all 3^t circles!

…

21 of 50

MergeSort

A divide and conquer algorithm for sorting an array

Big problem

Smaller problem

Yet smaller problem

22 of 50

MergeSort Pseudocode

MERGESORT(A):

If A has length 1,

It is already sorted!

Sort the right half

Sort the left half

Merge the two halves

[Lecture 2: Slide 63]

23 of 50

Merge sort in pictures

6

4

3

8

1

5

2

7

6

4

3

8

1

5

2

7

6

4

3

8

1

5

2

7

6

4

3

8

1

5

2

7

This array of length 1 is sorted!

24 of 50

Merge sort in pictures

6

4

3

8

1

5

2

7

1

2

5

7

3

4

6

8

1

2

3

4

5

6

7

8

Merge!

4

3

8

1

5

2

7

6

A bunch of sorted lists of length 1 (in the order of the original sequence).

Sorted sequence!

25 of 50

InsertionSort

An algorithm that builds up the final sorted array by inserting (& sorting) one item at a time
Similar to how you would sort a hand of playing cards

26 of 50

InsertionSort �example

4

6

3

8

5

6

4

3

8

5

6

4

3

8

5

4

3

6

8

5

4

3

6

8

5

4

3

6

8

5

4

3

6

8

5

4

3

5

6

8

Start by moving A[1] toward the beginning of the list until you find something smaller (or can’t go any further):

Then move A[2]:

Then move A[3]:

Then move A[4]:

Then we are done!

4

6

3

8

5

[Lecture 2: Slide 13]

27 of 50

Insertion Sort (the actual algorithm)

Remember our two questions:

Does it work? (Proof by induction)
Is it fast?

def InsertionSort(A):

for i in range(1,len(A)):

current = A[i]

j = i-1

while j >= 0 and A[j] > current:

A[j+1] = A[j]

j -= 1

A[j+1] = current

6

4

3

8

5

4

3

6

8

5

28 of 50

Asymptotic analysis

Aka big-Oh notation

28

29 of 50

In this class we will use…

Big-Oh notation!
Gives us a meaningful way to talk about the running time of an algorithm, independent of programming language, computing platform, etc., without having to count all the operations.

29

30 of 50

Main idea:

Focus on how the runtime scales with n (the input size).

Number of operations	Asymptotic Running Time

We say this algorithm is “asymptotically faster” than the others.

(Only pay attention to the largest function of n that appears.)

Some examples…

30

31 of 50

Informal definition for O(…)

Here, “constant” means “some number that doesn’t depend on n.”

pronounced “big-oh of …” or sometimes “oh of …”

31

32 of 50

T(n) = 2n²+ 10

g(n) = n²

32

33 of 50

T(n) = 2n²+ 10

g(n) = n²

3g(n) = 3n²

33

34 of 50

T(n) = 2n²+ 10

g(n) = n²

3g(n) = 3n²

n₀=4

34

35 of 50

Formal definition of O(…)

“There exists”

“For all”

“such that”

“If and only if”

35

36 of 50

T(n) = 2n²+ 10

g(n) = n²

36

37 of 50

T(n) = 2n²+ 10

g(n) = n²

3g(n) = 3n²

(c=3)

37

38 of 50

T(n) = 2n²+ 10

g(n) = n²

3g(n) = 3n²

n₀=4

(c=3)

38

39 of 50

Formally:

Choose c = 3
Choose n₀ = 4
Then:

T(n) = 2n²+ 10

g(n) = n²

3g(n) = 3n²

n₀=4

39

40 of 50

Formally:

Choose c = 7
Choose n₀ = 2
Then:

T(n) = 2n²+ 10

g(n) = n²

7g(n) = 7n²

n₀=2

There is not a “correct” choice of c and n₀

40

41 of 50

Choose c = 1
Choose n₀ = 1
Then

g(n) = n²

T(n) = n

41

42 of 50

Ω(…) means a lower bound

Switched these!!

42

43 of 50

Choose c = 1/3
Choose n₀ = 2
Then

g(n)/3 = n

T(n) = nlog(n)

g(n) = 3n

43

44 of 50

Θ(…) means both!

44

45 of 50

45

46 of 50

Take-away from examples

To prove T(n) = O(g(n)), you have to come up with c and n₀so that the definition is satisfied.

To prove T(n) is NOT O(g(n)), one way is proof by contradiction:

Suppose (to get a contradiction) that someone gives you a c and an n₀ so that the definition is satisfied.
Show that this someone must by lying to you by deriving a contradiction.

46

47 of 50

Back to Insertion Sort

Seems plausible

Go back to the pseudocode and convince yourself of this!

47

48 of 50

Merge Sort: running time

Size n

n/2

n/4

(Size 1)

…

n/4

n/2^t

…

sub-problem each takes O(n/2^t)

Level 0

Level 1

Level t

Level log(n)

2^tsubproblems at level t.

48

49 of 50

Total runtime…

O(n) steps per level, at every level
log(n) + 1 levels
O( n log(n) ) total!

Asymptotically better than Insertion Sort!

49

50 of 50

Any questions?