Compare the space complexity of iterative vs. recursive algorithms.
Iterative: Generally lower space complexity | Recursive: Can have higher space complexity due to call stack.
What are the differences between a brute-force algorithm and a dynamic programming algorithm?
Brute-force: Tries all possible solutions | Dynamic Programming: Breaks the problem into subproblems and stores the results to avoid redundant computations.
What are the differences between best-case, average-case, and worst-case time complexity?
Best-case: Minimum time required | Average-case: Expected time required | Worst-case: Maximum time required.
Compare and contrast depth-first search (DFS) and breadth-first search (BFS) graph traversal algorithms.
DFS: Explores as far as possible along each branch before backtracking | BFS: Explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
What are the differences between a greedy algorithm and a divide-and-conquer algorithm?
Greedy: Makes the locally optimal choice at each step | Divide-and-conquer: Divides the problem into smaller subproblems, solves them recursively, and combines the solutions.
What are the differences between time complexity and space complexity?
Time complexity: Measures the amount of time an algorithm takes to run as a function of the input size | Space complexity: Measures the amount of memory space an algorithm requires as a function of the input size.
What is the significance of polynomial time?
Indicates an algorithm is generally efficient and scalable.
Why are exponential time algorithms considered inefficient?
Their runtime grows very quickly, making them impractical for large inputs.
When should heuristics be used?
When finding the optimal solution is too computationally expensive.
How does input size affect algorithm efficiency?
Larger inputs generally require more computational resources, impacting efficiency.
What is the trade-off when using heuristics?
Accuracy is sacrificed for speed and feasibility.
What is the goal of algorithm design?
To solve a problem efficiently using minimal resources.
Explain the relationship between problem type and algorithm efficiency.
Optimization problems can be more computationally intensive than decision problems.
What does it mean for an algorithm to be 'scalable'?
The algorithm maintains reasonable efficiency as the input size increases.
What is the importance of understanding algorithm efficiency?
Helps in choosing the best approach for solving a problem within resource constraints.
How do heuristics relate to unreasonable time complexity?
Heuristics provide practical solutions when a problem has unreasonable time complexity.