Algorithms Challenge

What is the time complexity of bubble sort?

• O(log n)

• O(n)

• O(n^2)

• O(n!)

Explain the working of binary search algorithm.

• The binary search algorithm works by repeatedly dividing the sorted array in half and comparing the middle element with the target value.

• In binary search algorithm, the array is divided into three parts instead of two for comparison with the target value.

• The binary search algorithm works by comparing each element in the array with the target value one by one.

• Binary search algorithm starts from the middle of the array and moves towards the beginning to find the target value.

What is the difference between depth-first search and breadth-first search?

• Depth-first search and breadth-first search are the same.

• Breadth-first search explores as far as possible along each branch before backtracking.

• Depth-first search explores as far as possible along each branch before backtracking, while breadth-first search explores all the neighbor nodes at the present depth before moving on to nodes at the next depth.

• Depth-first search explores all the neighbor nodes at the present depth before moving on to nodes at the next depth.

How does dynamic programming differ from divide and conquer?

• Dynamic programming does not involve overlapping subproblems

• Dynamic programming breaks the problem into smaller subproblems

• Dynamic programming solves subproblems in parallel

• Dynamic programming solves each subproblem only once

Give an example of a problem that can be solved using greedy algorithm.

• Calculating the factorial of a number

• Sorting a list of numbers in descending order

• Finding the shortest path in a graph

• Finding the minimum spanning tree in a graph

Explain the concept of memoization in dynamic programming.

• Memoization is a technique used to delete the results of function calls.

• Memoization is a technique used to slow down the execution of function calls.

• Memoization is a technique used to only store the results of function calls for a limited time.

• Memoization is a technique used to store the results of expensive function calls and reuse them when the same inputs occur again.

What is the main principle behind divide and conquer algorithms?

• Ignore the sub-problems and solve the main problem directly

• Break down a problem into smaller sub-problems, solve them independently, and then combine their solutions

• Combine all the sub-problems into one big problem and solve it

• Solve the sub-problems simultaneously without breaking them down

Compare and contrast quicksort and mergesort.

• Quicksort is a stable sorting algorithm, while mergesort is not

• Quicksort and mergesort both have a time complexity of O(n^2)

• Mergesort is an in-place sorting algorithm, while quicksort requires extra space

• Quicksort is an in-place sorting algorithm with average time complexity of O(n log n), while mergesort is a stable sorting algorithm with time complexity of O(n log n) and requires extra space.

What is the significance of Dijkstra's algorithm in graph theory?

• It is used to find the average path between nodes in a graph.

• It is used to find the shortest path between nodes in a graph.

• It is used to find the longest path between nodes in a graph.

• It is used to find the most common path between nodes in a graph.

How does the knapsack problem relate to dynamic programming?

• The knapsack problem can only be solved using brute force, not dynamic programming

• Dynamic programming is used to solve the knapsack problem by breaking it down into subproblems and storing the solutions to these subproblems.

• Knapsack problem has no relation to dynamic programming

• Dynamic programming is only used for sorting, not for the knapsack problem