SA3-Algorithm Flashcards by BRYANT PAGALING

What does the Decrease and Conquer algorithm primarily exploit?
Group of answer choices

The relationship between unrelated problems

The division of a problem into equal parts

The relationship between a problem and its smaller instance

The combination of subproblem solutions

The relationship between a problem and its smaller instance

How well did you know this?

Not at all

Perfectly

Which of the following best describes the Divide and Conquer technique?
Group of answer choices

Reducing a problem to a single smaller instance

Solving a problem by reducing it by a constant factor

Solving a problem iteratively without recursion

Dividing a problem into multiple subproblems and solving them recursively

How well did you know this?

Not at all

Perfectly

Which sorting algorithm is an example of the Decrease and Conquer approach?
Group of answer choices

Heap Sort

Merge Sort

Quick Sort

Insertion Sort

How well did you know this?

Not at all

Perfectly

What is the time complexity of the worst-case scenario for Insertion Sort?
Group of answer choices

O(log n)

O(n)

O(n log n)

O(n²)

How well did you know this?

Not at all

Perfectly

In which variation of Decrease and Conquer is the problem size reduced by the same constant on each iteration?
Group of answer choices

Variable size decrease

None of the above

Decrease by a constant

Decrease by a constant factor

Decrease by a constant

How well did you know this?

Not at all

Perfectly

Which algorithm is an example of the “Decrease by a constant factor” approach?
Group of answer choices

BFS

Topological Sorting

Binary Search

Insertion Sort

Binary Search

How well did you know this?

Not at all

Perfectly

What is the primary difference between Divide and Conquer and Decrease and Conquer?
Group of answer choices

Divide and Conquer uses recursion, while Decrease and Conquer does not

Decrease and Conquer is iterative, while Divide and Conquer is recursive

Divide and Conquer generates multiple subproblems, while Decrease and Conquer generates one

There is no difference

Divide and Conquer generates multiple subproblems, while Decrease and Conquer generates one

How well did you know this?

Not at all

Perfectly

Which graph traversal algorithm uses a stack explicitly or implicitly?
Group of answer choices

Both DFS and BFS

Neither DFS nor BFS

Depth First Search (DFS)

Breadth First Search (BFS)

Depth First Search (DFS)

How well did you know this?

Not at all

Perfectly

What is the time complexity of Depth First Search (DFS)?
Group of answer choices

O(V²)

O(V + E)

O(log V)

O(E)

O(V + E)

How well did you know this?

Not at all

Perfectly

What is the best-case time complexity of Insertion Sort?
Group of answer choices

O(log n)

O(n)

O(n²)

O(n log n)

O(n)

How well did you know this?

Not at all

Perfectly

Which algorithm uses a queue for traversal?
Group of answer choices

Depth First Search (DFS)

Both DFS and BFS

Neither DFS nor BFS

Breadth First Search (BFS)

How well did you know this?

Not at all

Perfectly

Which of the following is NOT a variation of Decrease and Conquer?
Group of answer choices

Decrease by a constant factor

Variable size decrease

Increase by a constant

Decrease by a constant

Increase by a constant

How well did you know this?

Not at all

Perfectly

What is the space complexity of Depth First Search (DFS)?
Group of answer choices

O(V + E)

O(E)

O(V)

O(log V)

O(V)

How well did you know this?

Not at all

Perfectly

Which algorithm is used to solve the “Fake Coin Problem”?
Group of answer choices

BFS

Insertion Sort

Decrease by a constant factor

Merge Sort

Decrease by a constant factor

How well did you know this?

Not at all

Perfectly

Which of the following algorithms is iterative in nature?
Group of answer choices

Recursive DFS

Iterative Insertion Sort

Recursive Binary Search

Recursive Merge Sort

Iterative Insertion Sort

How well did you know this?

Not at all

Perfectly

What is the principle behind Insertion Sort?
Group of answer choices

Use a pivot to partition the array

Compare all elements with each other simultaneously

Insert elements at their correct position sequentially

Divide the array into two halves

Insert elements at their correct position sequentially

How well did you know this?

Not at all

Perfectly

Which algorithm is best suited for finding the median of a dataset?
Group of answer choices

Insertion Sort

Decrease by a constant factor

Variable size decrease

Binary Search

Study These Flashcards

Variable size decrease

Which traversal method explores all neighbors at the present depth before moving to the next level?
Group of answer choices

Breadth First Search (BFS)

Both DFS and BFS

Depth First Search (DFS)

Neither DFS nor BFS

Study These Flashcards

Breadth First Search (BFS)

What is the time complexity of Breadth First Search (BFS)?
Group of answer choices

O(E)

O(V²)

O(V + E)

O(log V)

Study These Flashcards

O(V + E)

Which algorithm would you use to search for an element in a sorted array efficiently?
Group of answer choices

BFS

Insertion Sort

DFS

Binary Search

Study These Flashcards

Binary Search

What does the “Transform and Conquer” algorithm strategy primarily focus on?
Group of answer choices

Transforming a problem into a simpler or more convenient form

Ignoring problem instances

Solving problems without modifying them

Increasing the complexity of problems

Study These Flashcards

Transforming a problem into a simpler or more convenient form

Which of the following is NOT one of the three major variations of the Transform and Conquer approach?
Group of answer choices

Representation Change

Instance Simplification

Data Duplication

Problem Reduction

Study These Flashcards

Data Duplication

What is the primary benefit of presorting in algorithms?
Group of answer choices

It reduces the need for sorting

It eliminates duplicates automatically

It increases computational time

It simplifies searching and other operations

Study These Flashcards

It simplifies searching and other operations

What is the efficiency of checking if all elements in an array are unique using a brute-force algorithm?
Group of answer choices

O(n^2)

O(log n)

O(n log n)

O(n)

Study These Flashcards

O(n^2)

What is the efficiency of a presorting-based algorithm that uses efficient sorting followed by binary search? Group of answer choices Θ(n log n) O(n^2) O(n) O(log n)

Θ(n log n)

How many comparisons are necessary in the worst case to sort a list of size n using any comparison-based algorithm? Group of answer choices n log n + n n^2 n ⌈log2 n!⌉ = n log2 n

⌈log2 n!⌉ = n log2 n

What is the final form of a matrix after performing Gaussian elimination? Group of answer choices Reduced row echelon form Lower triangular matrix Symmetric matrix Diagonal matrix

Reduced row echelon form

Which operation is NOT an elementary row operation in Gaussian elimination? Group of answer choices Adding a multiple of one row to another row Multiplying a row by a nonzero number Swapping two rows Dividing a column by a nonzero number

Dividing a column by a nonzero number

Which ancient civilization used a form of Gaussian elimination as early as 179 CE? Group of answer choices Roman Egyptian Chinese Greek

Chinese

What is the name of the process that stops row operations before the matrix is completely reduced for computational reasons? Group of answer choices Complete Row Reduction Gaussian Elimination Partial Row Reduction Gauss-Jordan Elimination

Gaussian Elimination

What is the defining property of an AVL tree? Group of answer choices All nodes have the same height The heights of the two child subtrees of any node differ by at most one The tree is always complete The tree is unbalanced

The heights of the two child subtrees of any node differ by at most one

Which rotation technique is performed when a node is inserted into the right subtree of the right subtree? Group of answer choices Left rotation Left-Right rotation Right-Left rotation Right rotation

Left rotation

What is the time complexity of lookup, insertion, and deletion in an AVL tree? Group of answer choices O(n) O(1) O(log n) O(n log n)

O(log n)

What is the balance factor in an AVL tree? Group of answer choices Total height of the tree Height(right-subtree) − height(left-subtree) Number of nodes in left subtree − number of nodes in right subtree Height(left-subtree) − height(right-subtree)

Height(left-subtree) − height(right-subtree)

Which of the following is a double rotation technique in AVL trees? Group of answer choices Left-Right rotation Left rotation Single rotation Right rotation

Left-Right rotation

What is the primary use of AVL trees in databases? Group of answer choices Reducing storage space Randomizing data Indexing large records Storing unsorted records

Indexing large records

Which of the following problems is made easier by presorting? Group of answer choices Generating random numbers Sorting arrays Computing the median Calculating the sum of elements

Computing the median

Which of the following is NOT a step in solving a system of linear equations using Gaussian elimination? Group of answer choices Swapping rows Sorting columns Multiplying rows by scalars Adding multiples of rows

Sorting columns

What is the mode of the list: 2, 6, 7, 8, 6, 1, 6, 3, 6, 2? Group of answer choices 2 8 7 6

Who are the inventors of the AVL tree? Group of answer choices Adelson-Velsky and Landis Newton and Leibniz Liu Hui and Carl Friedrich Gauss Gauss and Jordan

Adelson-Velsky and Landis

SA3-Algorithm Flashcards

(40 cards)