DAA notes

In algorithm analysis, what are Asymptotic Notations used to describe?

How execution time or memory space scales as input size grows toward infinity ($n$).

Which asymptotic notation represents the upper bound or the worst-case scenario for an algorithm?

Big O notation ($\le$).

Which asymptotic notation represents a strict upper bound ($<$)?

Little o notation.

Term: Big Omega ($\Omega$)

Definition: A notation representing the lower bound or best case, where running time grows at least this fast.

Which asymptotic notation denotes a strict lower bound ($>$)?

Little omega ($\omega$).

Concept: Big Theta ($\Theta$)

Definition: A tight bound where the upper and lower bounds are identical, indicating the running time grows at an exact match rate.

Which algorithm design paradigm breaks problems down into smaller identical sub-problems and then combines them?

Divide and conquer.

List three examples of algorithms that utilise the divide and conquer paradigm.

Merge sort, quick sort, and binary search.

How does the greedy approach make decisions during problem-solving?

It makes the best, most optimal choice at that specific moment (a locally optimal choice).

What is a primary drawback of using a greedy approach for complex problems?

It does not always find the globally optimal solution.

Give three examples of problems typically solved using a greedy approach.

Dijkstra's shortest path algorithm, spanning tree algorithms, and the fractional knapsack problem.

In dynamic programming, where are the results of sub-problems stored to avoid redundant calculations?

In a table, such as an array or hash map (caching).

What are the two main strategies used in dynamic programming?

Top-down (memoisation) and bottom-up (tabulation).

The strategy in dynamic programming involving a top-down approach is commonly known as _____.

Memoisation

The strategy in dynamic programming involving a bottom-up approach is commonly known as _____.

Tabulation

List three examples of problems that can be optimised using dynamic programming.

Longest common sequence, Floyd-Warshall, and Fibonacci sequence optimisation.

How does the backtracking paradigm explore potential solutions?

It models the problem as a tree and explores paths, returning to a previous state if it hits a dead end.

Provide two classic examples of problems solved via backtracking.

N-queens and Sudoku.

Which algorithm design paradigm evaluates every possible configuration to find a solution?

Brute force.

What is the primary advantage of the brute force approach?

It is guaranteed to find the optimal solution if one exists and is easy to code.

Why is the brute force approach often considered impractical for large inputs?

It has terrible time complexity.

Linear search and selection sort are examples of which algorithm design paradigm?

Brute force.

How is recursion defined in the context of algorithm design?

A technique where a function calls itself to solve a problem.

Identify three specific areas where recursion is particularly effective.

Tree and graph traversals, divide and conquer algorithms, and backtracking.

What are the two mandatory structural components of every valid recursive function?

The base case and the recursive case.

Concept: Base Case

Definition: The condition that tells the recursion to stop by providing a direct answer for the smallest possible input.

What happens to a recursive function if the base case is missing?

It will call itself infinitely, leading to a Stack Overflow error.

Concept: Recursive Case

Definition: The part of the function that calls itself with a modified, smaller input to move closer to the base case.

What must happen to the input in each successive recursive call?

It must be modified and made smaller to move closer toward the base case.

What is the difference between direct and indirect recursion?

Direct recursion is when function A calls itself; indirect recursion is when function A calls function B, which then calls A.

Term: Tail Recursion

Definition: A type of recursion where the recursive call is the absolute last statement executed by the function.

How can any problem solvable by recursion alternatively be solved?

Iteratively, using standard for and while loops.

How does recursion generally compare to iteration regarding memory usage?

Recursion typically uses more memory.

What is a common stylistic advantage of recursion over nested loops?

Recursive code is often cleaner and shorter.

What is the primary purpose of Prim's algorithm?

To find a minimum spanning tree in a graph.

In the context of scaling, what does the variable '$n$' typically represent in asymptotic notation?

The input size.

Which notation implies that the growth rate of an algorithm's running time is $\le$ a specific function?

Big O notation.

Which notation implies that the growth rate of an algorithm's running time is $\ge$ a specific function?

Big Omega ($\Omega$).

Which algorithm design paradigm is Dijkstra's shortest path algorithm classified under?

Greedy approach.

Which paradigm is characterised by exploring paths and abandoning them upon reaching a 'dead end'?

Backtracking.

In the divide and conquer paradigm, what must be true about the sub-problems created?

They must be identical sub-problems of the same type as the original.

Which DP strategy involves 'tabulation'?

The bottom-up strategy.

Which DP strategy involves 'memoisation'?

The top-down strategy.

What is the result of an infinite recursive loop on computer memory?

It causes a Stack Overflow error by exhausting available memory.

Another name for indirect recursion is _____ recursion.

Mutual

Which algorithmic strategy is used to solve the Fractional Knapsack problem?

Greedy approach.

Merge sort is an example of the _____ paradigm.

Divide and conquer

Selection sort is an example of the _____ paradigm.

Brute force

Is it possible for an iterative loop to solve the same problems as recursion?

Yes, any problem solvable by recursion can also be solved iteratively.

What is the 'Exit Door' of a recursive function called?

The base case.

What is the 'Step Down' of a recursive function called?

The recursive case.

In which notation is the running time growth rate an exact match to the bound?

Big Theta ($\Theta$).

The Floyd-Warshall algorithm is an application of which paradigm?

Dynamic programming.

Solving the N-queens problem is a typical application of _____.

Backtracking

Binary search belongs to the _____ paradigm because it repeatedly halves the search space.

Divide and conquer

A locally optimal choice is the hallmark of the _____ approach.

Greedy

What does a lower bound (Big Omega) indicate about an algorithm's running time?

It indicates the algorithm will run at least that fast or take at least that much time.

In recursion, when function A calls function B and function B calls function A, it is known as _____ recursion.

Indirect (or Mutual)

Dynamic programming solves sub-problems _____ time(s) and caches the result.

One

Which paradigm is often easy to code but suffers from high time complexity?

Brute force.

Fibonacci sequence optimisation using a table is an example of _____.

Dynamic programming

The absolute last statement in a tail-recursive function must be the _____.

Recursive call

Big O notation describes the _____ bound of an algorithm.

Upper (or worst-case)

Big Omega notation describes the _____ bound of an algorithm.

Lower (or best-case)

A tight bound means that the upper and lower bounds are _____.

Identical

Why is recursion considered 'cleaner' than iteration for certain problems?

It avoids the complexity of multiple nested loops.

What specific graph structure is Prim's algorithm designed to find?

A minimum spanning tree.

Which notation represents a growth rate strictly greater than the given bound?

Little omega ($\omega$).

Which notation represents a growth rate strictly less than the given bound?

Little o.

When a recursive call is made, how should the input relate to the original input?

It should be a modified, smaller version of the input.

The _____ case provides a direct, non-recursive answer for the smallest possible input.

Base

Which algorithm is a classic example of the Greedy approach for finding the shortest path?

Dijkstra's shortest path algorithm.

Greedy algorithms are generally _____ but do not always find the globally optimal solution.

Fast

How does dynamic programming improve upon simple recursion for problems with overlapping sub-problems?

By caching the results of sub-problems to avoid re-calculating them.

Which search algorithm is a brute force method?

Linear search.

What model does backtracking use to explore paths to a solution?

A tree model.

If an algorithm's running time grows at exactly the same rate as its upper and lower bounds, it is a _____ bound.

Tight

In terms of memory, recursion uses more space because it needs to maintain the _____.

Call stack (or stack frames).

Which sorting algorithm mentioned is an example of Brute Force?

Selection sort.

Quick sort uses the _____ paradigm to sort elements.

Divide and conquer

Huffman encoding algorithm

compression algorithm to reduce size of files

universal hashing

choosing has function randomly from a family of hash functions so that no adversarial input can consistently cause collisions which is a weakness of using a single fixed hash function

best technique for finding the lower bound of a problem like sorting

decision tree model

recurrence relations

used to analyze runtime of divide and conquer algorithms like merge and quick sort

components of space complexity

data space and instruction space

environmental stack space

component of space complexity used to save info needed to resume execution of partially completed functions

constant space

subset of data space reserved for values that dont change

principle of optimality

an optimal solution to a problem contains optimal solutions to its subproblems.

what data structure does BFS use?

queue

what data structure does DFS use?

stack

is DFS recursive or iterative?

recursive