Basics of algorithm design and analysis

Which of the following is true about Big O notation?

• It describes the lower bound of an algorithm's time complexity

• It describes the average case of an algorithm's time complexity

• It describes the upper bound of an algorithm's time complexity

• It describes the exact time complexity of an algorithm

What is the convex hull problem in computational geometry?

• It is a problem where we have to find the polygon that encloses a given set of points, such that all the points lie on or inside the polygon.

• It describes the upper bound of an algorithm's time complexity

• It describes the average bound of an algorithm's time complexity

• It is a problem where we have to find the two points in a set that are closest together.

Which of the following time complexities grows the fastest as the input size increases?

• O(n)

• O(1)

• O(log n)

• O(n log n)

Which of the following is true about an algorithm with O(n^2) time complexity?

• It is faster than an algorithm with O(n) time complexity

• Its running time increases linearly as the input size increases

• t is slower than an algorithm with O(n log n) time complexity

• Its running time increases quadratically as the input size increases

Can a given algorithm have multiple time complexities for different inputs?

Why or why not? (More than 1 correct answer)

• Yes, a given algorithm can have multiple time complexities for different inputs. This is because the time complexity depends on the size and nature of the input, and different inputs may require different amounts of computation. For example, an algorithm for sorting integers may have a different time complexity for arrays of different sizes or arrays with different degrees of sortedness.

• No, a given algorithm always has a single time complexity regardless of the input. This is because the time complexity of an algorithm is a property of the algorithm itself, not the input. While different inputs may require different amounts of computation, this does not change the inherent time complexity of the algorithm.

• It depends on the algorithm. Some algorithms have fixed time complexities that do not vary with the input, while others have time complexities that depend on the size or structure of the input. For example, an algorithm for computing the sum of a list of integers has a fixed time complexity of O(n), where n is the length of the list. In contrast, an algorithm for computing the shortest path between two nodes in a graph may have a time complexity that depends on the number of nodes and edges in the graph.

Choose correct statements

• An algorithm is a step-by-step procedure for solving a problem or accomplishing a task in a finite amount of time using a computer. It is a sequence of computational steps that transforms the input into the desired output.

• The order of growth represents an upper bound on the number of operations a function takes to complete. This means that it is a measure of the worst-case scenario for the function's performance.

• To compare the order of growth of functions, we look at the term with the highest exponent and the coefficient of that term.

What is an example of a well-known algorithm that uses the divide and conquer approach?

• QuickSort

• Selection Sort

• Insertion Sort

• Bubble Sort

How can the divide and conquer approach be applied to sorting algorithms, and what are some examples of sorting algorithms that use this approach?

• Divide and conquer can be used to sort arrays of integers by recursively splitting them into sub-arrays, sorting them independently, and then merging them back together. Examples include QuickSort and MergeSort.

• Divide and conquer can be used to sort arrays of strings by recursively comparing them and swapping them if necessary. Examples include Bubble Sort and Selection Sort.

• Divide and conquer cannot be used to sort arrays, as sorting requires a different approach.

• Divide and conquer can only be used to sort arrays of a certain size or complexity.

How does the QuickSort algorithm use the divide and conquer approach?

• It divides the input array into two sub-arrays, sorts them independently, and then merges them back together

• It repeatedly divides the input array into smaller sub-arrays, sorts them independently, and then combines them using a pivot element.

• It divides the input array into sub-arrays of equal size, sorts them independently, and then merges them back together using a heap data structure.

• It uses a binary search tree to divide the input array into sub-arrays, sorts them independently, and then combines them using a traversal algorithm.

Which of the following sorting algorithms has a worst-case time complexity of O(n^2)?

• MergeSort

• QuickSort

• Bubble Sort

• Heap Sort