CSE 373 SP25

Section AX Week 2

Runtime Analysis

Warm-Up: What is the difference between case analysis and asymptotic analysis?

Announcements

• Deques
• Project Quiz was due April 8th!
• Code due April 15th
• Analysis due April 16th
• Course Policies
• Finalized on the Course Website

MicroTeach: Runtime Analysis and ADTs

Formal Notation to compare Runtime?

Goal:

• Understanding the behavior or implementation details of the algorithm.

Steps:

1. Model the number of steps or operations needed to run the algorithm.
2. Formalize the result in precise English or mathematical notation.

Case Analysis vs Asymptotic Analysis Confusion

• Case Analysis: Not depending on the size of N
• Asymptotic analysis: analyzing runtime for when N is tending towards ∞, aka large inputs

​

Can we combine the 2 methods? Yes! We can do a best & worst case asymptotic analysis (and you will need to in deques and future projects!).

• Tip: consider different cases that could arise with the stipulation that N is big

​

​

​

The Three Bounds

• O: Upper bound on how quickly function grows.�Informally: “Less than or equal to big-Theta”. (Minus constants, lower order terms).
• Θ: Tight (i.e. “agreed”) bound on how quickly function grows.�Informally: “Equal to”. (Minus constants, lower order terms).
• Ω: Lower bound on how quickly function grows.�Informally: “Greater than or equal to big-Theta”. (Minus constants, lower order terms).

�����If you feel shaky with functions, plot them out as you come across new bounds in this class using Desmos to understand variations in growth!�

What does Θ represent?

​

​

​

f must be both O(g) and Ω(g) to be Θ(g)!�

Think of this as “squeezing” the function from above and below.

​

Visual Reference

big-O

big-Omega (Ω)

Asymptotically “Less than or equal to k * f(n)”

Asymptotically “Greater than or equal to k * f(n)”

big-Theta (Θ)

k₁* n ≤ Θ ≤ k₂* n

ADTs Summary/Review

“Abstract Data Type”, indicates general expected functionality

• EX: List, Map, Queue, Deque (INTERFACES)

​

Client v. Implementer:

• “Contract” to maintain, clients expect specific functions to exist and work properly -> “Promise” of an ADT
• Clients don’t need to know the inner details (abstraction)
• Clients can reliably use tools even during updates (modularity)

​

It’s key for us to navigate these responsibilities and implications as creators of technology to best cater to user needs

Questions?

Worksheet Problems:

Asymptotic Analysis and Design Decisions

Asymptotic Notation

1. If the order of growth of a function f(N) is in Θ(logN), which of the following asymptotic bounds can also be used to describe f(N)? Explain why each of your choices apply.

​

• O(logN)
• O(N)
• O(N²)

• Θ(logN)
• Θ(N)
• Θ(N²)

• Ω(logN)
• Ω(N)
• Ω(N²)

Challenge Q: What if we only knew that the order of growth of some function f(N) was in O(N)?

Asymptotic Analysis (Solution)

1. If the order of growth of a function f(N) is in Θ(logN), which of the following asymptotic bounds can also be used to describe f(N)? Explain why each of your choices apply.

​

• O(logN)
• O(N)
• O(N²)

• Θ(logN)
• Θ(N)
• Θ(N²)

• Ω(logN)
• Ω(N)
• Ω(N²)

Challenge Q: What if we only knew that the order of growth of some function f(N) was in O(N)?

A: We cannot make assumptions for the other bounds beyond O(-). With some given upper bound, we can imagine other applicable bounds >= N, such as O(N^2).

Design Decisions: Restaurant

A restaurant wants to table customers in the order they arrived. When an inspector comes in to check the service by ordering, the restaurant also hopes to give them a table before other customers. Since there is a really long wait time for tables, waiters only look at the ADT representation when giving out tables.

​

​

​

​

​

​

Choose ADTs:

• List
• Stack (LIFO)
• Queue (FIFO)
• Deque
• Map (key, value pairs)

​

Choose data structures to implement your chosen ADTs:

ArrayList

LinkedList

etc…

You do not need to figure out the implementation of the Map if you use one.

Design Decisions: Restaurant

Sample Solution:

I would use the Deque ADT and implement this using a Linked List. This can use front and back pointers, allowing for new customers at the back and the inspector inserted to the front.

​

Cons: Finding specific customers/groups that leave the line

Pros: More efficient since no time is lost to shifting elements, less memory intensive

This can interact with some Map for tabling to place customers accordingly when they are removed from the front.

(key: int number, value: Object tableInfo)

• Likely has info on start time, # people, occupied vs. vacant, etc

​

​

​

​

​

​

Design Decisions: Disneyland

Disneyland has hired you to find a way to improve the processing efficiency of their long lines at attractions. There is no way to forecast how long the lines will be.

​

In addition, “the Disability Access Service (DAS) is intended for Guests who have difficulty tolerating extended waits in a conventional line environment due to disability. This service doesn’t provide immediate access to experiences, but rather allows Guests to request a return time for a specific experience that is comparable to the current standby wait.” (Source)

​

​

Design Decisions: Disneyland

The Map ADT for key, value pairs will be used for those utilizing the Disability Access Service and will help with lookup when a customer comes back to check how much time they have left to wait and what place in line they would be in, if they would like to re-join now.

​

Disneyland: Task

Please choose how we should implement the program of the line for the attraction. We want the functionality of the line to be able to:

• Add customers to the end of the line
• Remove customers from the front of the line, when it’s their turn for the specific experience
• Add customers, utilizing DAS, at the xth spot in the line, when they return for the specific experience. When using lookup for customers in the Map, you will receive the place number of how many people are in front of the customer.

Disneyland: Implementation

Please choose from the following:

​

​

​

​

​

​

​

​

Justify your reasoning. You do not need to figure out the implementation of the Map.

​

​

​

Choose ADTs:

• List
• Stack (LIFO)
• Queue (FIFO)
• Deque
• Map (key, value pairs)

​

Choose a data structures to implement your chosen ADTs:

ArrayList

LinkedList

etc…

Disneyland: Implementation

Sample Solution:

I would use the List ADT and implement this using a Linked List. This can include front and back pointers, directly corresponding to the add/remove functions.

For reinsertion at any given place, 2 pointers also work to choose the option with fewer nodes to traverse through.

*(asymptotically, n/2 => n)

​

Cons: Traversal through many nodes to add in at some xth spot, especially at middle

Pros: No issues with shifting of elements or resizing like an ArrayList

​

This can interact with the Map to determine line position for those utilizing DAS.

(key: int userId, value: Object customer info)

• Likely has fields to know which attractions they are waiting for

Sliding Window Practice

Why LeetCode Style Code Challenges?

• Improvement on Algorithmics:
• Be aware that such problems exist
• Practice thinking through problems
• Coming up with various approaches and solutions
• Get comfortable with various data structures and algorithms
• Better sense of what tools, approaches, strategies, refinements you can make
• Improvement on Communication & Comprehension:
• Be able to communicate approaches, solutions, thought processes outloud
• Be able to refine thoughts and convey them effectively
• Real-life interview-style practice
• More about the process than the results
• Get to interact with other classmates and HAVE FUN!

Example Problem - Longest increasing subsequence

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.

A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

​

Input: nums = [1, 3, 5, 4, 7]

Output: 3

Explanation: The longest continuous increasing subsequence is [1, 3, 5] with length 3.

Even though [1, 3, 5, 7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element 4.

Example Problem - Solution & Approach

public int lengthOfLCIS(int[] A) {

int result = 0;

int anchor = 0;

for (int i = 0; i < A.length; i++) {

if (i > 0 && A[i-1] >= A[i]) {

anchor = i;

result = Math.max(

result,

i - anchor + 1

);

}

}

return result;

}

Scan through the array once, extending the window as long as the sequence increases. If it stops increasing, slide the window to the current index.

Anchor: We track the start index of the current increasing subarray using a variable called anchor.

Update Anchor: If the current number is not greater than the previous one, the increasing sequence breaks so we move the anchor to the current index, starting a new subarray.

Subarray Length: The current increasing subarray has length i - anchor + 1, so we update the result with the maximum length found so far.

Instructions

Each group of 3 or 4 students will be assigned one of the following problems:

• LeetCode 219. Contains Duplicates II
• LeetCode 594. Longest Harmonious Subsequence
• LeetCode 643. Maximum Average Subarray I
• LeetCode 1876. Substrings of Size Three with Distinct Characters

For instructions, search online for the problem by ID number, e.g. “LeetCode 219”.

You’ll have about 20 minutes to complete:

• Think individually for 2 min
• Group discussion for 4 min (no computer)
• Group discussion for 4 min with computer
• Presentation prep for 4 min
• Presenting to another group for 6 min

Let's get started!

Think individually for 2 min

Group discussion for 4 min (no PC)

Group discussion for 4 min (with PC)

Presentation prep for 4 min

Presenting to another group for 6 min

Presentation Guidelines

Questions to Ask Yourself:

• What is the problem really asking?
• What operations do I need to perform often?
• In the examples, are there patterns that can help getting started?
• When should I use specific data structures?

Presentation Guidelines

• Explain how you approached the problem
• Run through how you eliminated other options
• Describe the data structure(s) and algorithm(s) you chose and why
• Go through your solution step by step, explaining the logic

Complete the reflection activity in Gradescope and add your groupmates!