Exploring Algorithms and Their Analysis

What is the time complexity of binary search?

• O(n)

• O(n log n)

• O(1)

• O(log n)

Define the term 'algorithm' in computer science.

• An algorithm is a programming language.

• An algorithm is a type of computer hardware.

• An algorithm is a step-by-step procedure for solving a problem or performing a task in computer science.

• An algorithm is a random guess to solve a problem.

What is the difference between a greedy algorithm and a dynamic programming algorithm?

• Greedy algorithms focus on local optimization; dynamic programming focuses on global optimization through subproblem solutions.

• Dynamic programming is faster than greedy algorithms in all cases.

• Greedy algorithms always provide the optimal solution; dynamic programming does not.

• Greedy algorithms solve problems in a single pass; dynamic programming requires multiple passes.

Explain the concept of Big O notation.

• Big O notation provides a high-level understanding of the efficiency of algorithms, typically expressed as O(n), O(log n), O(n^2), etc.

• Big O notation measures the speed of a computer's processor.

• Big O notation is used to calculate the memory size of an algorithm.

• Big O notation describes the number of lines in a program.

What is the worst-case time complexity of bubble sort?

• O(n)

• O(n^2)

• O(n log n)

• O(log n)

Describe the divide and conquer strategy in algorithms.

• Divide and conquer combines all subproblems into one large solution without solving them individually.

• Divide and conquer is a method that avoids breaking down problems into smaller parts.

• Divide and conquer is a strategy that only focuses on the largest subproblem.

• Divide and conquer is an algorithmic strategy that divides a problem into smaller subproblems, solves them independently, and combines their solutions.

What is a hash table and how does it work?

• A hash table is a linear data structure that stores elements in a sequential manner.

• A hash table is a graphical representation of data relationships.

• A hash table is a type of database used for storing large amounts of data.

• A hash table is a data structure that uses a hash function to map keys to values for efficient data retrieval.

Explain the concept of recursion with an example.

• Recursion is a method where a function runs in a loop until a condition is met.

• Recursion is a technique used to optimize code by eliminating unnecessary function calls.

• Recursion is a process where a function is executed only once to return a result.

• Recursion is a method where a function calls itself to solve smaller instances of a problem, exemplified by the factorial function.

What is the purpose of a priority queue?

• To implement a stack data structure for last-in, first-out access.

• To store elements in a sorted order based on their values.

• To allow for random access to any element in constant time.

• The purpose of a priority queue is to manage a collection of elements where each element has a priority, allowing for efficient access to the highest (or lowest) priority element.

How does Dijkstra's algorithm find the shortest path?

• Dijkstra's algorithm only considers direct connections between nodes.

• Dijkstra's algorithm randomly selects nodes to explore.

• Dijkstra's algorithm finds the shortest path by exploring nodes in order of increasing distance from the source, updating paths as shorter ones are found.

• Dijkstra's algorithm finds the shortest path by using a depth-first search.