CSE 373 AU24 Week 3 AX
Recurrences + Effects of Sorting
Announcements
Micro-Teach: Recurrences (Tree Method)
Big Idea
Two steps:
Model recursive code with recurrence
Apply Tree Method on the recurrence equation
Goal: Analyze the runtime of some recursive code
What is a Recurrence?
An expression that lets us express the runtime of a function recursively.��
What is a Recurrence?
An expression that lets us express the runtime a function recursively.��
Base Case
Recursive Case
What is a Recurrence?
Base Case
Recursive Case
Recursive Call
Q1 Warm-Up: Model Code with Recurrence
Walkthrough: Understand Code Structure
Base case when the input N <= 1
Walkthrough: Understand Code Structure
Recursive case when N > 1
Walkthrough: Understand Code Structure
Non-recursive work
Walkthrough: Understand Code Structure
Recursive work
Walkthrough: Understand Code Structure
Recursive work
Base case when the input N <= 1
Non-recursive work
T(N) =
Base case
Recursive work + Non-recursive work
Recurrence:
Walkthrough: Code to Recurrence
Recurrence Diagram: Format
RECURSIVE WORK
T(N) = size of current
subproblem
T(N) = size of current subproblem
(in recursive call)
T(N) = size of current
subproblem
(in recursive call)
~ NON-RECURSIVE WORK
(for subproblem)
~ non-recursive work
(for subproblem)
~ non-recursive work
(for subproblem)
T(N)
T(N)
T(N)
T(N)
. . .
. . .
~ non-recursive
~ non-recursive
~ non-recursive
~ non-recursive
Worksheet Q2:
T(N) = 3T(N/3) + N
Recurrence relations (solution)
3 * T(N / 3) + N
T(N) =
Case Study #2: Stable Sorting
Scenario: Default vs. Alternative Sorts on Canvas
By default, Canvas sorts students alphabetically by their last name. Help the TA Team brainstorm new criteria to sort by to reduce bias! Develop a metric and provide reasoning for your choice.
Possible Examples:
Scenario: Stable Sorting with Alternative Criteria
Assume we have chosen your criteria to implement a stable sorting algorithm on Canvas. However, when tied entries are found, the algorithm will revert to sorting alphabetically by last name. This reintroduces biases.
Choose a solution and explain your reasoning:
💡Recall: A sort is stable if it preserves the original order of equivalent keys. An unstable sort doesn’t guarantee the original order of elements in the event of a equivalent keys.
Sorting Algorithms & Optimization
The TA Team has an additional request that you determine the most optimal/efficient approach to achieve the desired result. Connect your choice of stability and alternative sorting criteria to the tangible algorithms we have learned.
| Worst-case | Best-case | Stable | In-place | Space Complexity |
Selection | Θ(N2) | Θ(N2) | ❌ | ✓ | Θ(1) |
Insertion | Θ(N2) | Θ(N) | ✓ | ✓ | Θ(1) |
Mergesort | Θ(NlogN) | Θ(NlogN) | ✓ | ❌ | Θ(NlogN) *Θ(N) [w/ timsort] |
Design Decisions: Takeaways
In this process, you see that user needs, developer needs, value systems, etc. often are at odds with one another.
As our criteria shifted and assumptions changed, designs we once thought were perfect or functional can fail to adapt, and loopholes remained with regard efficiency, accessibility, and bias mitigation.
We can connect these ideas back to the Duo ADT; sorting with Binary Search to find duplicates in arrays was great, but soon posed problems with resizing for add operations. Continue to challenge course concepts in their applicability for scenarios and their relative efficiencies!
Any Questions?
Closing Announcements
Please don't hesitate to reach out if you have any
questions or concerns about the course, or if there's
anything else we can help you with! We're here to support
you however we can!