Data Structures & Algorithms - III Lecture Notes

Practice flashcards covering simple sorting algorithms, 5-step problem solving, recursion, and divide and conquer strategies.

According to the lecture, why is sorting considered a prerequisite for searching?

Sorting is an upfront investment that unlocks lightning-fast searching methods, like Binary Search.

Why can sorting massive datasets cause a system to crash or freeze?

Computers must compare elements one pair at a time rather than glancing at the data, making systematic ordering essential to avoid inefficiency.

What are three examples of sorted items providing benefits outside of the computer field?

Waste Management, Organization, and Pattern Recognition.

What is the core execution strategy of the Bubble Sort algorithm?

Compare adjacent items and swap them if the left item is greater than the right item.

Why is Bubble Sort practically unused in professional software development?

It suffers from massive inefficiency on large datasets.

What is the function signature provided in the code for Bubble Sort?

void bubbleSort(int arr[], int size)

How does Insertion Sort compare elements to find the correct position for a target card?

It compares the target with cards already in the hand from right to left, shifting larger elements to the right to create a gap.

In what industrial context is Insertion Sort considered highly efficient?

It is highly efficient for small or nearly sorted datasets.

Which advanced industrial algorithm uses Insertion Sort under the hood for small chunks of data?

Timsort

What is the worst-case Time Complexity for both Bubble Sort and Insertion Sort?

$O(n^2)$ (Quadratic Time)

Under what condition does Insertion Sort achieve $O(n)$ Linear Time complexity?

When the data provided is already sorted.

What is the Space Complexity for both Bubble Sort and Insertion Sort?

$O(1)$ (Constant Space)

What defines an "In-Place" sorting algorithm?

An algorithm that rearranges elements directly within the original space provided for the data structure.

List the 5 steps of the Universal Framework for problem solving.

1. Read/Listen, 2. Visualize (Think of Examples), 3. BRUTE FORCE, 4. Optimize, 5. Test.

What are the 'Key Questions' to ask during Step 1 (Read/Listen) of problem solving?

What is our goal? What are we looking for? What do we start with? What information is given?

In Step 2 (Think of Examples), searching for 'cat' in the array ['bat', 'cat', 'dog'] is an example of what?

A Normal Case (standard, expected input).

What is 'Edge Case Planning' in the context of industry software engineering?

Planning for unexpected or strange user behaviors to prevent application crashes.

What is the primary goal of the BRUTE FORCE step in problem solving?

To overcome "blank page" syndrome by finding the easiest, most straightforward way to make the solution work.

What is a 'Proof of Concept' (POC)?

A demonstration to prove that a concept or idea works to avoid "building castles in the air."

What is the definition of a 'Minimum Viable Product' (MVP)?

The absolute baseline of a product or program that works completely and successfully.

When comparing search algorithms in Step 4 (Optimize), what is the efficiency of Binary Search compared to Linear Search?

Binary Search is $O(\log(n))$ while Linear Search is $O(n)$.

What C++ header and function are suggested for handling case-insensitive string comparisons?

The header file and the strcasecmp() function.

What is the definition of Recursion?

A programming technique where a function calls itself inside its own definition to solve problems by breaking them into smaller, self-similar instances.

What are the two ironclad properties a recursive procedure must have?

The Base Case and the Recursive Step.

What is the 'Base Case' in recursion?

The smallest version of the problem that we know how to solve and where the function stops calling itself.

What system error occurs if a recursive function does not have a base case?

Stack Overflow

In the recursive factorial example, what is the base case for $n!$?

1! = 1

What specific data structure do recursive functions use under the hood?

A Last-In-First-Out (LIFO) structure known as the Stack.

Why does iteration have a lower space complexity than recursion?

Iteration uses $O(1)$ space, while every recursive call requires extra space in the system's Stack Memory.

When is recursion considered the industry standard despite memory costs?

For hierarchical data (like file directories or DOM trees) and Divide-and-Conquer algorithms.

What are the three strict steps of the Divide & Conquer paradigm?

1. Divide, 2. Conquer, 3. Combine.

What is the difference between Divide & Conquer and Recursion theory?

Divide & Conquer is the problem-solving strategy (theory), while Recursion is the mechanism to write the code (implementation).

In Merge Sort, how is the 'Divide' step executed?

The unsorted array is split in half repeatedly until there are $n$ sub-arrays of exactly 1 element.

What is the 'Conquer' step in Merge Sort?

A 1-element array is recognized as completely sorted by definition.

What is the Time Complexity of Merge Sort across all cases (Worst, Average, Best)?

$$O(n \log(n))$$

What is the Space Complexity of Merge Sort and why?

$O(n)$, because it require allocation of temporary sub-arrays to store merged data.

When finding the MAX value using Divide & Conquer, what is the Time Complexity?

$O(n)$ (Linear Time)

Why does finding the MAX value with Divide & Conquer result in $O(n)$ rather than $O(\log(n))$?

The computer must touch every element to find the true maximum; it cannot discard half the array like in Binary Search.

What is the Space Complexity for the Divide & Conquer MAX value algorithm described?

$O(\log(n))$ (representative of the Stack Depth).

According to the lecture, what utility function is used to display the results of Merge Sort?

printArray(int arr[], int size)