What are the differences between decision and optimization problems?
Decision: Yes/No answer | Optimization: Seeks the best solution.
What are the differences between reasonable and unreasonable time?
Reasonable: Polynomial time | Unreasonable: Exponential/Factorial time.
What are the differences between algorithms and heuristics?
Algorithms: Guarantee a correct solution | Heuristics: Aim for a 'good enough' solution.
Compare the time complexity of linear search vs. binary search.
Linear Search: O(n) | Binary Search: O(log n) (for sorted data).
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 does the following code output?
```python
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
print(is_prime(4))```
False
What does the following code output?
```python
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
print(factorial(3))```
6
Identify the error in the following code:
```python
def find_max(list):
max_value = 0
for num in list:
if num > max_value
max_value = num
return max_value```
Missing colon after the `if` condition. It should be `if num > max_value:`
What does the following code output?
```python
def linear_search(list, target):
for i in range(len(list)):
if list[i] == target:
return i
return -1
my_list = [10, 20, 30, 40, 50]
print(linear_search(my_list, 30))```
2
What does the following code output?
```python
def example_function(n):
count = 0
for i in range(n):
for j in range(n):
count += 1
return count
print(example_function(4))```
16
Identify the error in the following code:
```python
def calculate_average(numbers):
sum = 0
for number in numbers:
sum += number
average = sum / len(numbers)
return average
print(calculate_average([]))```
ZeroDivisionError: division by zero. The code attempts to divide by the length of the list, which is zero when the list is empty.
What does the following code output?
```python
def mystery_function(arr):
n = len(arr)
for i in range(n):
for j in range(i+1, n):
if arr[i] > arr[j]:
arr[i], arr[j] = arr[j], arr[i]
return arr
print(mystery_function([5, 2, 8, 1, 9]))```
[1, 2, 5, 8, 9]
Identify the error in the following code:
```python
def recursive_function(n):
if n > 0:
return recursive_function(n-1)
print(recursive_function(5))```
The function lacks a base case that returns a concrete value when n reaches a certain condition (e.g., n == 0). This will result in infinite recursion and eventually a stack overflow error.
What does the following code output?
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([2, 5, 7, 8, 11, 12], 13))```
-1
Identify the error in the following code:
```python
def calculate_sum(numbers):
total = 0
for i in range(1, len(numbers)):
total += numbers[i]
return total
print(calculate_sum([1, 2, 3, 4, 5]))```
The loop starts at index 1 instead of 0, causing the first element of the list to be skipped. The loop should start with `for i in range(len(numbers)):`
What is an algorithm?
A set of instructions designed to solve a specific problem.
What is a problem instance?
A specific input to a problem.
What is a decision problem?
A problem with a yes or no answer.
What is an optimization problem?
A problem that seeks the best solution from many possibilities.
What is algorithm efficiency?
A measure of how many computational resources an algorithm uses.
What is 'reasonable time' in algorithm analysis?
Algorithms that run in polynomial time or lower.
What is 'unreasonable time' in algorithm analysis?
Algorithms that run in exponential or factorial time.
What are heuristics?
Approximation techniques used when finding an exact solution is too difficult or time-consuming.
Define polynomial time.
A running time that increases as a polynomial function of the input size (e.g., n, n^2, n^3).
Define exponential time.
A running time that increases exponentially as the input size grows (e.g., 2^n, 3^n).
