Fundamentals of Algorithms

What is an algorithm?

• A recipe for cooking food.

• A collection of data points without a process.

• An algorithm is a step-by-step procedure for solving a problem.

• A random guess without any steps.

Explain the difference between time complexity and space complexity.

• Time complexity and space complexity are interchangeable terms that mean the same thing.

• Time complexity focuses on execution time, whereas space complexity focuses on memory usage.

• Time complexity is only concerned with the worst-case scenario, while space complexity is always constant.

• Time complexity measures the number of operations, while space complexity measures the speed of the algorithm.

What is Big O notation?

• Big O notation is a way to describe the upper limit of an algorithm's time or space complexity.

• A notation used for defining programming languages.

• A method to calculate the average performance of an algorithm.

• A way to measure the exact runtime of a program.

Describe the concept of divide and conquer in algorithms.

• Divide and conquer is a strategy that eliminates the need for combining results.

• Divide and conquer is an algorithm design paradigm that recursively breaks a problem into smaller subproblems, solves them independently, and combines their results.

• It involves solving the entire problem at once without breaking it down.

• Divide and conquer is a method that only works for sorting algorithms.

What is a greedy algorithm? Give an example.

• An example of a greedy algorithm is sorting a list in ascending order.

• An example of a greedy algorithm is the Coin Change Problem, where the goal is to make change for a given amount using the fewest coins possible. The algorithm selects the largest denomination coin first until the amount is reached.

• A greedy algorithm is one that uses dynamic programming to solve problems.

• A greedy algorithm always finds the optimal solution for all problems.

What is the purpose of a sorting algorithm?

• To analyze data for trends and patterns.

• To compress data to save space.

• To encrypt data for security purposes.

• The purpose of a sorting algorithm is to arrange data in a specified order.

Explain the difference between linear search and binary search.

• Linear search is O(n) in time complexity, while binary search is O(log n) and requires a sorted array.

• Linear search has a time complexity of O(log n).

• Binary search can be performed on unsorted arrays.

• Linear search is faster than binary search for large datasets.

What is dynamic programming? Provide a use case.

• Dynamic programming is a method for solving problems by brute force.

• A use case of dynamic programming is sorting an array using quicksort.

• A use case of dynamic programming is the Fibonacci sequence calculation, where each number is the sum of the two preceding ones. Instead of recalculating Fibonacci numbers multiple times, dynamic programming stores previously computed values.

• A use case of dynamic programming is calculating the area of a circle.

What are the characteristics of a good algorithm?

• Characteristics of a good algorithm include clarity, efficiency, finiteness, definiteness, generality, and measurable performance.

• Infinite length, ambiguity, and specificity

• Simplicity, randomness, and complexity

• Irrelevance, unpredictability, and non-measurable performance

What is the significance of algorithm analysis in computer science?

• Algorithm analysis is irrelevant to real-world applications.

• Algorithm analysis is significant for evaluating efficiency and performance of algorithms.

• Algorithm analysis is only important for sorting algorithms.

• Algorithm analysis helps in writing code without testing.