1 of 66

Algorithm Problem Solving (APS):

Divide-and-Conquer

Niema Moshiri

UC San Diego SPIS 2021

2 of 66

What is an algorithm?

3 of 66

Goals of Algorithm Problem Solving (APS)

4 of 66

Goals of Algorithm Problem Solving (APS)

Introduction to basic algorithmic strategies for solving problems

5 of 66

Goals of Algorithm Problem Solving (APS)

Introduction to basic algorithmic strategies for solving problems
Emphasis on writing solutions precisely and coherently

6 of 66

Goals of Algorithm Problem Solving (APS)

Introduction to basic algorithmic strategies for solving problems
Emphasis on writing solutions precisely and coherently
Practice discovering algorithms and describing them

7 of 66

Goals of Algorithm Problem Solving (APS)

Introduction to basic algorithmic strategies for solving problems
Emphasis on writing solutions precisely and coherently
Practice discovering algorithms and describing them
Analyze algorithms

8 of 66

Example: The Largest Integer Problem

9 of 66

Example: The Largest Integer Problem

Input: A list of integers ints

10 of 66

Example: The Largest Integer Problem

Input: A list of integers ints

7	25	0	42	-9

11 of 66

Example: The Largest Integer Problem

Input: A list of integers ints
Output: An integer x in ints such that, for all integers y in ints, x ≥ y

7	25	0	42	-9

12 of 66

Example: The Largest Integer Problem

Input: A list of integers ints
Output: An integer x in ints such that, for all integers y in ints, x ≥ y

In other words, x is a largest integer in ints

7	25	0	42	-9

13 of 66

Example: The Largest Integer Problem

Input: A list of integers ints
Output: An integer x in ints such that, for all integers y in ints, x ≥ y

In other words, x is a largest integer in ints

7	2	0	4	-9	5	1	-4	3	8	-2	-7	...	-1	-8	6	-3	-6	9	-5	2

14 of 66

Easier Example: The Peanut Butter & Jelly Problem

15 of 66

Easier Example: The Peanut Butter & Jelly Problem

Input: A closed jar of peanut butter jar_pb, a closed jar of jelly jar_jelly, a closed bag of toast bag_toast, and a knife knife

16 of 66

Easier Example: The Peanut Butter & Jelly Problem

Input: A closed jar of peanut butter jar_pb, a closed jar of jelly jar_jelly, a closed bag of toast bag_toast, and a knife knife

Output: A peanut butter & jelly sandwich pbj

17 of 66

Easier Example: The Peanut Butter & Jelly Problem

Input: A closed jar of peanut butter jar_pb, a closed jar of jelly jar_jelly, a closed bag of toast bag_toast, and a knife knife

Output: A peanut butter & jelly sandwich pbj

Let’s solve the problem!

18 of 66

Easier Example: The Peanut Butter & Jelly Problem

Open bag_toast
Remove 2 pieces of toast x and y from bag_toast
Close bag_toast
Open jar_pb
Insert knife into jar_pb
Remove knife from jar_pb
Spread knife onto x
Wipe knife
Close jar_pb
...

19 of 66

What is Algorithm Problem Solving (APS)?

20 of 66

What is Algorithm Problem Solving (APS)?

An algorithm describes a series of operations to perform some task

21 of 66

What is Algorithm Problem Solving (APS)?

An algorithm describes a series of operations to perform some task
A program is a computer-understandable formulation of an algorithm

22 of 66

What is Algorithm Problem Solving (APS)?

An algorithm describes a series of operations to perform some task
A program is a computer-understandable formulation of an algorithm
APS is the process of discovering the algorithm in the first place

23 of 66

What is Algorithm Problem Solving (APS)?

An algorithm describes a series of operations to perform some task
A program is a computer-understandable formulation of an algorithm
APS is the process of discovering the algorithm in the first place

APS → Algorithm → Program

24 of 66

Example: The Largest Integer Problem

Input: A list of integers ints
Output: An integer x in ints such that, for all integers y in ints, x ≥ y

In other words, x is a largest integer in ints

Let’s solve the problem!

25 of 66

Example: The Largest Integer Problem

Algorithm largest_number(ints):

x ← negative infinity

For every integer y in ints:

if y > x:

x ← y

Return x

26 of 66

Example: The Largest Integer Problem

Our algorithm is correct (can you prove it?)

27 of 66

Example: The Largest Integer Problem

Our algorithm is correct (can you prove it?)
However, a single “person” has to look at every integer

28 of 66

Example: The Largest Integer Problem

Our algorithm is correct (can you prove it?)
However, a single “person” has to look at every integer
Even if we had more “people,” they have no way of helping

29 of 66

Example: The Largest Integer Problem

Our algorithm is correct (can you prove it?)
However, a single “person” has to look at every integer
Even if we had more “people,” they have no way of helping
Can we think of a way to speed things up by working in parallel?

30 of 66

Recursion

Algorithm that depends on smaller subproblems of itself

31 of 66

Recursion

Algorithm that depends on smaller subproblems of itself
Typically composed of two “types” of cases:

32 of 66

Recursion

Algorithm that depends on smaller subproblems of itself
Typically composed of two “types” of cases:

Base Case: Can be solved directly

33 of 66

Recursion

Algorithm that depends on smaller subproblems of itself
Typically composed of two “types” of cases:

Base Case: Can be solved directly
Recursive Case: Can be solved using solutions of subproblems

34 of 66

Example: Counting People Recursively

Algorithm num_people(person):

If person is at the front of the line:

Return 1

Else:

neighbor ← the person in front of person

Return num_people(neighbor) + 1

35 of 66

Divide-and-Conquer Algorithms

36 of 66

Divide-and-Conquer Algorithms

Divide a given problem into several subproblems

37 of 66

Divide-and-Conquer Algorithms

Divide a given problem into several subproblems
Solve each subproblem recursively

38 of 66

Divide-and-Conquer Algorithms

Divide a given problem into several subproblems
Solve each subproblem recursively
Combine the solutions of the subproblems to solve the problem

39 of 66

Divide-and-Conquer Algorithms

Divide a given problem into several subproblems
Solve each subproblem recursively
Combine the solutions of the subproblems to solve the problem
Tip: Try to balance the sizes of the subproblems as much as possible

40 of 66

A Protocol for Solving Problems

41 of 66

A Protocol for Solving Problems

Articulate the problem

42 of 66

A Protocol for Solving Problems

Articulate the problem
Work out concrete examples, making note of boundary cases

43 of 66

A Protocol for Solving Problems

Articulate the problem
Work out concrete examples, making note of boundary cases
Brainstorm about the algorithm

44 of 66

A Protocol for Solving Problems

Articulate the problem
Work out concrete examples, making note of boundary cases
Brainstorm about the algorithm
Design an algorithm

45 of 66

A Protocol for Solving Problems

Articulate the problem
Work out concrete examples, making note of boundary cases
Brainstorm about the algorithm
Design an algorithm
Analyze the algorithm

46 of 66

A Protocol for Solving Problems

Articulate the problem
Work out concrete examples, making note of boundary cases
Brainstorm about the algorithm
Design an algorithm
Analyze the algorithm
Write the solution

47 of 66

A Protocol for Solving Problems

Articulate the problem
Work out concrete examples, making note of boundary cases
Brainstorm about the algorithm
Design an algorithm
Analyze the algorithm
Write the solution
Revise

48 of 66

Example: The Largest Integer Problem

Input: A list of integers ints
Output: An integer x in ints such that, for all integers y in ints, x ≥ y

In other words, x is a largest integer in ints

Let’s solve the problem!

49 of 66

Example: The Largest Integer Problem

largest_integer(ints, start, end)

0	1	2	3	4	5	6	7
a	b	c	d	e	f	g	h

50 of 66

Example: The Largest Integer Problem

largest_integer(ints, 0 , 7 )

0	1	2	3	4	5	6	7
a	b	c	d	e	f	g	h

51 of 66

Example: The Largest Integer Problem

largest_integer(ints, 0 , 3 )

0	1	2	3	4	5	6	7
a	b	c	d	e	f	g	h

52 of 66

Example: The Largest Integer Problem

largest_integer(ints, 0 , 1 )

0	1	2	3	4	5	6	7
a	b	c	d	e	f	g	h

53 of 66

Example: The Largest Integer Problem

largest_integer(ints, 0 , 0 )

0	1	2	3	4	5	6	7
a	b	c	d	e	f	g	h

54 of 66

Example: The Largest Integer Problem

largest_integer(ints, 0 , 0 )

a

0	1	2	3	4	5	6	7
a	b	c	d	e	f	g	h

55 of 66

Example: The Largest Integer Problem

largest_integer(ints, 1 , 1 )

b

0	1	2	3	4	5	6	7
a	b	c	d	e	f	g	h

56 of 66

Example: The Largest Integer Problem

largest_integer(ints, 0 , 1 )

i = max(a,b)

0	1	2	3	4	5	6	7
i		c	d	e	f	g	h

57 of 66

Example: The Largest Integer Problem

largest_integer(ints, 2 , 3 )

0	1	2	3	4	5	6	7
i		c	d	e	f	g	h

58 of 66

Example: The Largest Integer Problem

largest_integer(ints, 2 , 2 )

c

0	1	2	3	4	5	6	7
i		c	d	e	f	g	h

59 of 66

Example: The Largest Integer Problem

largest_integer(ints, 3 , 3 )

d

0	1	2	3	4	5	6	7
i		c	d	e	f	g	h

60 of 66

Example: The Largest Integer Problem

largest_integer(ints, 2 , 3 )

j = max(c,d)

0	1	2	3	4	5	6	7
i		j		e	f	g	h

61 of 66

Example: The Largest Integer Problem

largest_integer(ints, 0 , 3 )

k = max(i,j)

0	1	2	3	4	5	6	7
k				e	f	g	h

62 of 66

Example: The Largest Integer Problem

largest_integer(ints, 4 , 5 )

l = max(e,f)

0	1	2	3	4	5	6	7
k				l		g	h

63 of 66

Example: The Largest Integer Problem

largest_integer(ints, 6 , 7 )

m = max(g,h)

0	1	2	3	4	5	6	7
k				l		m

64 of 66

Example: The Largest Integer Problem

largest_integer(ints, 4 , 7 )

n = max(l,m)

0	1	2	3	4	5	6	7
k				n

65 of 66

Example: The Largest Integer Problem

largest_integer(ints, 0 , 7 )

n = max(k,n)

0	1	2	3	4	5	6	7
n

66 of 66

Example: The Largest Integer Problem

Algorithm largest_number(ints, start, end):

If start equals end:

Return ints[start]

Else:

mid ← floor((start + end) / 2)

left ← largest_number(ints, start, mid)

right ← largest_number(ints, mid+1, end)

Return max(left, right)