CSE 373 Su23 Section 9

Final Review

Agenda

• Announcements
• Final Review
• Analyzing Recursive Code
• Graph Design Decisions
• Sorting Design Decisions
• Disjoint Sets: Find and Union
• ADT Design Decisions

​

​

​

​

​

Announcements

• Final Exam tomorrow 1:10 - 2:10 pm in SMITH 120!
• Handwritten notes allowed
• P4 and EX7 due tomorrow night @11:59 pm
• Please fill out TA evaluations
• closes Aug 18 @11:59 PM
• You can find the link to the eval in an email titled “Course Evaluation CSE 373 AA” from UW Course Evaluations via IASystem Notification

Analyzing Recursive Code

Write a Recurrence

public int recursiveFunction(int n){

if(n < 3) {

return 3;

}

for(int int i=0; i < n; i++) {

System.out.println(i);

}

int val1 = recursiveFunction(n/3);

int val2 = recursiveFunction(n/3);

return val1 * val2;

}

+1

+1

+1

base case: +2

non-recursive work: n+2

+2

recursive work: 2T(n/3)

CSE 373 23SU

5

Recurrence to Big-Θ

It’s still really hard to tell what the big-O is just by looking at it.

But fancy mathematicians have a formula for us to use!

​

CSE 373 23SU

6

Understanding Master Theorem

The log of a < c case

• Recursive case does a lot of non recursive work in comparison to how quickly it divides the input size
• Most work happens in beginning of call stack
• Non recursive work in recursive case dominates growth, n^c term

​

The log of a = c

• Recursive case evenly splits work between non recursive work and passing along inputs to subsequent recursive calls
• Work is distributed across call stack

​

The log of a > c case

• Recursive case breaks inputs apart quickly and doesn’t do much non recursive work
• Most work happens near bottom of call stack

• a measures how many recursive calls are triggered by each method instance
• b measures the rate of change for input
• c measures the dominating term of the non recursive work within the recursive method
• d measures the work done in the base case

CSE 373 23SU

7

Graph Design Decisions

Graph Design Decisions

• For each of the following graph-based computational tasks, specify the type of graph most appropriate for the data in question in terms of undirected or directed, and unweighted or weighted.
• State what data the graph stores: what are the vertices, what are the edges?
• Choose the graph algorithm from the following list best suited to computing a solution: BFS, DFS, MST (e.g. Prim’s or Kruskal’s), Dijkstra’s, Topological Sort

1: Minimizing Pizza Costs

Bob runs a pizza shop in a small town in Greenland. There are 100 houses in the town connected by roads. Bob delivers to every house in the town. Unfortunately, Bob can only carry one pizza at a time, so after delivering to one house, he has to come back to the shop to pick up another delivery. Last week, there was a storm that left 4 feet of snow on all the roads in the town. Clearing snow on a road costs Bob some money, but once the snow is cleared the cost to travel on the cleared road (in either direction) is zero. Bob decides that instead of clearing snow from all the roads on his delivery routes at once, he will clear the snow while delivering pizzas.

​

1A: Minimizing Pizza Costs

A: Bob knows he will get an order for each of the 100 houses (they’re all regular customers), so he’d like to plan in advance which roads he is going to clear. How should he choose which roads to use to minimize the total cost?

​

Solution:

• Undirected, Weighted Graph
• Vertices are houses
• Edges are roads
• Edge weights represent cost to clear a road
• Bob should find an MST for the town to determine which roads to clear

​

​

1B: Minimizing Pizza Costs

B: When each new order comes in, how should Bob determine what roads to take to get to that house?

​

​

Solution: Bob should run BFS or DFS on the MST. Since in a MST there is only one path between any two vertices (no cycles), that is the only path Bob can take to get to that house. Running Dijkstra’s on the MST also works but is suboptimal because it’s slower than running BFS or DFS.

2A: Facebook Connections

Suppose we model Facebook users with the following graph representation:

An undirected, unweighted adjacency list where vertices are users and edges represent ‘friend’ relationships.

Thus, if two users are friends, then we have an edge between those two users.

​

How would you find a person with the most friends in the network? State the runtime of your solution.

​

​

Solution: Iterate through the graph and find a vertex with the maximum degree.

Runtime is O(|V|) to iterate through adjacency list keys and find the value (list) with the largest size(), or O(|V| + |E|) for BFS or DFS.

​

2B: Facebook Connections

The company wants to introduce a new metric for each user called networkSize. The networkSize of a user u is the number of users v such that u → v, i.e., there is a path from u to v. Describe how you would calculate networkSize for a user u. State the runtime of your solution.

​

​

Solution: Run BFS or DFS from u and count the number of unique vertices visited. Runtime is O(|V | + |E|).

Sorting Design Decisions

Sorting Design Decisions: a

Q: Suppose we want to sort an array containing 50 strings. Which of the following five algorithms is the best choice?

insertion sort, merge sort, quick sort, selection sort, heap sort

Main idea:

• Only 50 strings
• When it comes to computer programs, this is not a very large input size

​

A: Insertion Sort

• Fast on small inputs
• May be worst-case Θ(n^2) but it also has a low constant factor
• Merge, quick, and heap sort may also be reasonable choices!�

��� �

​

​

Sorting Design Decisions: b

Q: Suppose we have an array containing a few hundred elements that is almost entirely sorted, apart from one or two elements that were swapped with the previous item in the list. Which of the following algorithms is the best way of sorting this data?

insertion sort, merge sort, quick sort, selection sort, heap sort

Main idea:

• Array is already almost entirely sorted
• Only have to move a few elements, and swap them with their neighbor

​

A: Insertion Sort

• Runs in Θ(n) time for inputs that are already or close to completely sorted

��� �

​

​

Sorting Design Decisions: c

Q: Suppose we want to sort an array of ints, but also want to minimize the amount of extra memory we want to use as much as possible. Which of the following algorithms is the best choice?

insertion sort, merge sort, quick sort, selection sort, heap sort

Main idea:

• We don’t know anything about the input
• Minimize memory!!�

A: Quick Sort

• In place so it uses no extra memory
• Could use in-place heap sort for the same reason

��� �

​

​

Sorting Design Decisions: d

Q: Suppose we have a version of quick sort which selects pivots randomly to create partitions. Explain how you would build an input array that would cause this version of quick sort to always run in O(n^2) time.

What would the array look like? What happens when you try running quick sort on it?

Main idea:

• To get good performance time with quick sort, we partition the input array into roughly halves each time. For bad, O(n^2) performance we would need to do the opposite.

A: Array with all duplicate elements

• Each time you partition, all elements will fall on the left side of the partition, since they are <= to. We will always get O(n^2)

��� �

​

​

Q3: Disjoint Sets Array Representation

Q3: Disjoint Sets Array Representation

Given a mapping of items->their index,

fill out the pointers array representation for this disjoint set

8

11

7

50

4

3

2

1

Size 8

14

10

9

6

Size 4

Array Representation

Items:

Index:

Value:

Acts as “pointers”. Stores parent index or -size if element is set representative.

-8

-8

1

1

-4

1

1

Same parent as 50 and 7, so same index mapping!

1

1

2

2

Same parent!

5

5

5

5

7

7

Now try it yourself on the other set!

Click to next slide for the answer.

9

10

9

Q4: Disjoint Sets Find Set

Q4: Disjoint Sets Find Set

Call findSet(2) on the following disjoint sets. Give the return value of the call, and the updated array representation. Draw the resulting disjoint sets.

Items:

Index:

Value:

8

11

7

50

4

3

2

1

Size 8

3

2

5

1

Return Value:

1

14

10

9

6

Size 4

Q5: Disjoint Sets Union

Disjoint Sets Union

union(3, 14) on the array representation of this Disjoint Set

8

11

7

50

4

3

2

1

Size 8

14

10

9

6

Size 4

Array Representation

Items:

Index:

Value:

Acts as “pointers”. Stores parent index or -size if element is set representative.

Disjoint Sets Union

union(3, 14)

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

findSet(3)

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

findSet(3)

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

findSet(3)

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

Items:

Index:

Value:

Found representative!

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

Items:

Index:

Value:

Time to do path compression!

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

Items:

Index:

Value:

Time to do path compression!

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

findSet(14)

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

findSet(14)

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

findSet(14)

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

findSet(14) = 9

Items:

Index:

Value:

Found representative!

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

findSet(14) = 9

Items:

Index:

Value:

Time to do path compression!

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

findSet(14) = 9

Items:

Index:

Value:

Time to do path compression!

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

findSet(14) = 9

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

findSet(3) = 1

findSet(14) = 9

findSet(3) == findSet(14)

No! 3 and 14 belong to different sets within our disjoint set.

Items:

Index:

Value:

?

⁇

︖

¿

?

Disjoint Sets Union

union(3, 14)

findSet(3) = 1 → get set’s size

findSet(14) = 9 → get set’s size

Assign the smaller set’s rep. to point to the larger set’s rep. for the union by size optimization.

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

findSet(3) = 1 → -1 * array.get(1) = 8

findSet(14) = 9 → -1 * array.get(9) = 4

Assign the smaller set’s rep. to point to the larger set’s rep. for the union by size optimization.

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

findSet(3) = 1 → -1 * array.get(1) = 8

findSet(14) = 9 → -1 * array.get(9) = 4

Assign the smaller set’s rep. to point to the larger set’s rep. for the union by size optimization.

Items:

Index:

Value:

Update larger set’s size

Update smaller set’s parent

Disjoint Sets Union

union(3, 14)

Final Result!

Items:

Index:

Value:

Disjoint Sets Union

union(3, 14)

8

11

7

50

4

3

2

1

Size 12

14

10

9

6

Array Representation

Items:

Index:

Value:

ADT Design Decisions

ADT Design Decisions: A

Q: You are writing a program to manage a todo list with a very specific approach to tasks. This program will order tasks for someone to tackle so that the most recent task is addressed first. How would you store the transactions in appropriate order?

​

Main idea: Most recent task should be handled first, also known as…

L.I.F.O: Last in, first out

​

A: Stack -> Our go-to LIFO data structure!

ADT Design Decisions: B

Q: You are writing a study support program that creates flash cards where each flash card has two pieces of crucial information: the question to be asked and the correct answer. How would you store these flash card objects?

​

Main idea: Questions have an associated correct answer

​

A: Dictionary (or map) -> We can use the question to look up the answer!�

��� �

​

​

ADT Design Decisions: C

Q: You are writing a program to store the history of transactions for a small business. You need to maintain the order in which the transactions occurred and be able to access entries based on the order in which they were received

​

Main idea: Keep the relative order, and be able to access elements

​

A: List -> We can get elements without manipulating the data!�

��� �

​

​

ADT Design Decisions: D

Q: You are writing a program to surface candidates for a job. As candidates are met and evaluated, they are added to a collection from which hiring managers can request the next best applicant whenever they have an open job position. How would you store the candidates and their evaluations for hiring managers to be able to quickly get the next best applicant?

​

Main idea: Quickly access the best candidate

​

A: Priority Queue -> Priority = goodness of the candidate. We can return the best applicant quickly!�

��� �

​

​

ADT Design Decisions: E

Q: You are writing a program to schedule jobs sent to a laser printer. The laser printer should process these jobs in the order in which the requests were received. How would you store the jobs in appropriate order?

​

Main idea: Process jobs in order received. Also known as...

F.I.F.O: First in, first out

​

A: Queue-> Our goto FIFO data structure�

��� �

​

​

ADT Design Decisions: F

Q: You are developing a video game where you play as the Roman Empire. Every time you conquer a city-state, that city-state and everything they own is added to your empire.

​

Main idea: Easily add everything from a city-state to belong under us.

​

A: Disjoint Sets -> Each city-state and the Roman Empire are sets. Whenever a city-state is taken over, add it to the Roman Empire set!�

��� �

​

​