ALGORITHM MIDTERM EXAM REVIEWER
Studied by 0 people
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/216
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
217 Terms
______ is an algorithm compares the pattern to the text, one character at a time, until un-matching characters are found:
Group of answer choices
Brute force
Transform and conquer
Dynamic programming
Divide and conquer
Brute force
It refers to an algorithm that is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function.
Group of answer choices
Brute force
Greedy
Divide and Conquer
Dynamic Programming
Dynamic Programming
Given input string = "ABCDABCATRYCARCABCSRT" and pattern string = "CAT". Find the first index of the pattern match using quick search algorithm
Group of answer choices
14
2
6
11
6
The main challenge of the traveling salesman is?
Group of answer choices
minimize travel
maximize the cost
None
tour cities
minimize travel
Given input string = "TWO ROADS DIVERGED IN A YELLOW WOOD" and pattern string = "ROADS". Find the first index of the pattern match using quick search algorithm
Group of answer choices
3
5
4
6
4
How many sub-arrays does selection sort maintains?
Group of answer choices
3
5
4
2
2
Which is an advantage of using a brute force from the following list?
Group of answer choices
It is neither as соnѕtruсtіvе nоr as сrеаtіvе as ѕоmе оthеr dеѕіgn tесhnіԛuеѕ
It rаrеlу уіеldѕ еffісіеnt аlgоrіthmѕ
Sоmе brute-fоrсе algorithms are unacceptably slow
It yields ѕtаndаrd аlgоrіthmѕ fоr simple соmрutаtіоnаl tasks, such аѕ sum аnd рrоduсt оf n numbеrѕ, аnd finding the mаxіmum оr mіnіmum іn a lіѕt
It yields ѕtаndаrd аlgоrіthmѕ fоr simple соmрutаtіоnаl tasks, such аѕ sum аnd рrоduсt оf n numbеrѕ, аnd finding the mаxіmum оr mіnіmum іn a lіѕt
Given input string = "THIS IS A TEST TEXT" and pattern string = "TEST". Find the first index of the pattern match using quick search algorithm
Group of answer choices
12
11
9
10
10
Given input string = "THIS IS A TEST TEXT" and pattern string = "TEXT". Find the first index of the pattern match using quick search algorithm
Group of answer choices
15
17
16
14
15
question with images
https://docs.google.com/document/d/1Ias6nwlAKFhZFGDwt_2ud27-gv2frgTefeb-NW3KYuk/edit?usp=sharing
It finds the location of a specific text pattern within a larger body of text?
Group of answer choices
Brute force
pattern matching
string search
seeking
string search
The searching phase in quick search algorithm has good practical behaviour.
Group of answer choices
True
False
No answer text provided.
No answer text provided.
True
In the given code snippet below, pseudocode of brute force string, what does m represents?
for i ← to n-m do
j ← 0
while j
characters representing a pattern
What is the time complexity of the brute force solution?
Group of answer choices
O(n)
O(mn)
O(1)
Exponential
O(mn)
Refers to a string of M characters to search for
Group of answer choices
pattern
string matching
text
string
pattern
It generates a list of all potential solutions to the problem in a systematic manner evaluate potential solutions one by one, disqualifying infeasible ones
Group of answer choices
Divide and Conquer
Traveling Salesman
Exhaustive search
Dynamic programming
Exhaustive search
The Knapsack problem is an example of ____________
Group of answer choices
Greedy
Divide and Conquer
Transform and conquer
Brute Force
Brute Force
The 0-1 Knapsack problem can be solved using Greedy algorithm
Group of answer choices
True
False
True
A process there it involves searching for an element with a special property, usually among combinatorial objects such as permutations, combinations, or subsets of a set.
Group of answer choices
Divide and Conquer
Brute force
Traveling Salesman
Dynamic programming
Brute force
It refers to the general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.
Group of answer choices
Brute force
Divide and Conquer
Dynamic Programming
Greedy
Brute force
There are how many steps in writing the brute force string matching algorithm
Group of answer choices
6
4
3
5
3
A brute force problem that has to visit each one of the cities starting from a certain one (e.g. the hometown) and returning to the same city.
Group of answer choices
Traveling Salesman
Traveling Around
Traveling
Traveling man
Traveling Salesman
A process there it involves searching for an element with a special property, usually among combinatorial objects such as permutations, combinations, or subsets of a set.
Group of answer choices
Traveling Salesman
Divide and Conquer
Exhaustive search
Dynamic programming
Exhaustive search
It's a sorting algorithm that sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning
Group of answer choices
Bubble
Selection
Merge
Quick
Selection
It derives its name from the problem faced by someone who is constrained by a fixed-size backpack and must fill it with the most valuable items.
Group of answer choices
Traveling Salesman
Brute force
Dynamic programming
Knapsack problem
Knapsack problem
There are how many steps in the selection sort algorithm
Group of answer choices
7
4
5
6
5
What is the efficiency of knapsack problem?
Group of answer choices
O(2^n)
Exponential
O(n)
O(1)
O(2^n)
In the travelling salesman problem, what do you call the stating point?
Group of answer choices
Vertex
Starting point
Edge
Top
Vertex
Who was the mathematician who have done works on the knapsack problem
Group of answer choices
Tobby Dantzig
Tobias Dantzig
Tobias Datzig
Tom Dantzig
Tobias Dantzig
What is the time efficiency of the brute force string match?
Group of answer choices
(nm2)
exponential
O(1)
O(mn)
O(mn)
It generates a list of all potential solutions to the problem in a systematic manner evaluate potential solutions one by one, disqualifying infeasible ones
Group of answer choices
Divide and Conquer
Brute force
Traveling Salesman
Dynamic programming
Brute force
An algorithm that calculate the total distance for every possible route and then select the shortest one.
Group of answer choices
Divide and Conquer
Greedy
Dynamic Programming
Exhaustive Search
Exhaustive Search
According to the Stony Brook University Algorithm Repository, what is the ranked of the knapsack problem?
Group of answer choices
19th
20th
18th
17th
19th
This approach is used in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of investments and portfolios
Group of answer choices
Brute force
Dynamic programming
Knapsack problem
Traveling Salesman
Knapsack problem
Complete the code snippet below, pseudocode of brute force string
for i ← to n-m do
j ← 0
while j
return -1
What is the other term use to describe brute force?
Group of answer choices
Full search
Extensive search
Exhaustive Search
In-depth search
Exhaustive Search
Which is an advantage of using brute force from the following list?
Group of answer choices
It hаѕ wide applicability аnd is known for іtѕ ѕіmрlісіtу
It rаrеlу уіеldѕ еffісіеnt аlgоrіthmѕ
Sоmе brute-fоrсе algorithms are unacceptably slow
It is neither as соnѕtruсtіvе nоr as сrеаtіvе as ѕоmе оthеr dеѕіgn tесhnіԛuеѕ
It hаѕ wide applicability аnd is known for іtѕ ѕіmрlісіtу
Complete the code snippet below, pseudocode of brute force string
for i ← to n-m do
j ← 0
while j
J <- j +1
Compares a given pattern with all substrings of a given text.
Group of answer choices
None of the above
Brute force
selection sort
Brute force string matching
Brute force string matching
It refers to the general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.
Group of answer choices
Divide and Conquer
Dynamic Programming
Exhaustive Search
Greedy
Exhaustive Search
What is the time complexity of the brute force algorithm used to solve the Knapsack problem?
Group of answer choices
Exponential
O(2^n)
O(n)
O(1)
O(2^n)
Which of the following methods can be used to solve the Knapsack problem?
Group of answer choices
brute force, recursion
divide and conquer
recursion
dynamic programming
brute force, recursion
You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?
Group of answer choices
200
160
170
90
160
This approach is an example of combinatorial optimization.
Group of answer choices
Traveling Salesman
Dynamic programming
Brute force
Knapsack problem
Knapsack problem
What is the time complexity of quick sort for best case?
Group of answer choices
O (1)
O (n log n)
Exponential
O (n^2)
O (n log n)
What is the correct formula use in binary search
Group of answer choices
mid = low * (high - low) / 2
mid = low + (high - low) / 2
mid = low + (high + low) / 2
mid = low - (high - low) / 2
mid = low + (high - low) / 2
What do you call the step that receives a lot of smaller sub-problems to be solved.
Group of answer choices
Rejoin
Crack
Solve
Answer
Solve
What is the worst-case time complexity of Merge sort?
Group of answer choices
O (1)
Exponential
O (n2)
O (n log n)
O (n log n)
When computing for p1 what is the exact formula?
Group of answer choices
p1=a(f-h)
p1=d(g-e)
p1=a(a-b)h
p1=(c+d)e
p1=a(f-h)
Which of the following areas do closest pair problem arise?
Group of answer choices
graph colouring problems
string matching
numerical problems
computational geometry
computational geometry
The Strassen algorithm is known as a?
Group of answer choices
Matrix subtraction
Matrix Division
Matrix Addition
Matrix multiplication
Matrix multiplication
What is the time complexity of quick sort for worse case?
Group of answer choices
O (n log n)
O (n^2)
Exponential
O (1)
O (n^2)
What is the time complexity of closest pair
Group of answer choices
O(n log n)
Exponential
O(n!)
O(1)
O(n log n)
A method that compute its problem of computational geometry.
Group of answer choices
Strassen Algo
Binary Search
Merge sort
Closest Pair
Closest Pair
What year did Strassen published his algorithm that proves the n3 general matrix multiplication was not optimal?
Group of answer choices
1968
1970
1969
1967
1969
Which of the following sorting algorithms has the lowest worst-case complexity?
Group of answer choices
Insertion Sort
Bubble Sort
Merge Sort
Quick Sort
Merge Sort
There are a total of _______ sub-matrices in solving for the Strassen algorithm
Group of answer choices
7
9
6
8
8
Binary search is similar to that methodology?
Group of answer choices
Greedy Algorithm
Divide and Conquer
Dynamic Programming
Decrease and Conquer
Divide and Conquer
A binary search is to be performed on the list:
3 5 9 10 123
How many comparisons would it take to find number 9?
Group of answer choices
6-7
0-1
4-5
2-3
0-1
What is the optimal time required for solving the closest pair problem using divide and conquer approach?
Group of answer choices
O(1)
O(n log n)
Exponential
O(n!)
O(n log n)
Problem solving approach where the problem in hand, is divided into smaller sub-problems and then each problem is solved independently.
Group of answer choices
Greedy Algorithm
Decrease and Conquer
Divide and Conquer
Dynamic Programming
Divide and Conquer
When computing for p4 what the exact formula?
Group of answer choices
p4=d-(g+e)
p4=d+(g+e)
p4=d+(g-e)
p4=d(g-e)
p4=d(g-e)
What is the running time of Strassen's algorithm for matrix multiplication?
Group of answer choices
O(n^3.8074)
O(n^2.8974)
O(n^3.8974)
O(n^2.8074)
O(n^2.8074)
In divide and conquer, the time is taken for merging the subproblems is?
Group of answer choices
O(n log n)
Exponential
O(1)
O(n!)
O(n log n)
Strassen's matrix multiplication algorithm follows ___________ technique.
Group of answer choices
Backtracking
Divide and Conquer
Dynamic
Dynamic
Divide and Conquer
Strassen's Matrix Algorithm was proposed by _____________
Group of answer choices
Virginia Williams
Victor Jan
Andrew Strassen
Volker Strassen
Volker Strassen
What is the space complexity of Strassen algorithm
Group of answer choices
A O (log n)
O(n^2)
Exponential
O(n^2.8074)
A O (log n)
What is the time complexity of quick sort for average case?
Group of answer choices
O (n^2)
Exponential
O (1)
O (n log n)
O (n log n)
Strassen's algorithm is a/an_____________ algorithm.
Group of answer choices
Recursive
Approximation
Non-recursive
Accurate
Recursive
In this searching algorithm, it is mandatory for the target array to be sorted
Group of answer choices
Quick
Merge
Bubble
Binary
Binary
What do you call a sorting algorithm that partitions an array and then calls itself recursively twice to sort the two resulting subarrays.
Group of answer choices
Insertion Sort
Quick Sort
Merge Sort
Bubble Sort
Quick Sort
Which of the following is true about merge sort?
Group of answer choices
Merge sort outperforms heap sort in most of the practical situations
Merge Sort is stable sort by nature
All of the above
Merge Sort works better than quick sort if data is accessed from slow sequential memory.
All of the above
What is the worse time complexity of Strassen algorithm
Group of answer choices
O(n^2.8974)
O(n^3.8974)
O(n^2.8074)
O(n^3.8074)
O(n^2.8074)
What is the best time complexity of Strassen algorithm
Group of answer choices
Exponential
O(n^2.8074)
O (1)
O(n^2)
O (1)
Describe an advantage of a binary search algorithm
Group of answer choices
Slow with large data sets.
. Can only work on an ordered list. If unordered must use a linear search.
Performs well over large ordered lists.
Data does not need to be in order.
Performs well over large ordered lists.
Is the first geometric problems that were treated at the origins of the systematic study of the computational complexity of geometric algorithms.
Group of answer choices
Strassen Algo
Binary Search
Merge sort
Closest Pair
Closest Pair
Merge Sort can be categorized into which of the following?
Group of answer choices
Decrease and Conquer
Greedy Algorithm
Dynamic Programming
Divide and Conquer
Divide and Conquer
What do you call the step in the divide and conquer that generally takes a recursive approach to divide the problem until no sub-problem is further divisible?
Group of answer choices
Collapse
Break
Breakdown
Halt
Break
There are how many steps in the closest pair algorithm?
Group of answer choices
8
9
7
6
7
When computing for p7 what the exact formula?
Group of answer choices
p7=(a-c)+(e-f)
p7=(a*c)(e+f)
p7=(a-c)(e+f)
p7=(a-c)+(e+f)
p7=(a-c)(e+f)
It is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays
Group of answer choices
Quick Sort
Insertion Sort
Merge Sort
Bubble Sort
Quick Sort
What is the auxiliary space complexity of merge sort?
Group of answer choices
O(n log n)
O(n)
O(1)
Exponential
O(n)
Sorting Algorithm that looks for a particular item by comparing the middle most item of the collection
Group of answer choices
Merge
Binary
Quick
Bubble
Binary
What is the average-case time complexity of Merge sort?
Group of answer choices
O (n log n)
O (n2)
O (1)
Exponential
O (n log n)
Which of the following method is used for sorting in merge sort?
Group of answer choices
partitioning
merging
selection
D exchanging
merging
A binary search is to be performed on the list:
1 5 10 13 48 68 100 101
How many comparisons would it take to find number 101?
Group of answer choices
3-4
C 1-2
0-1
4-5
3-4
What is the space complexity of quick sort?
Group of answer choices
O (1)
O (n^2)
O (n log n)
Exponential
O (n log n)
Select the best description to explain what a binary search algorithm is
Group of answer choices
Elements do not need to be in order, compare to the middle value, split the list in order and repeat
Put the elements in order, compare with the middle value, split the list in order and repeat
Elements do not need to be in order, check each item in turn.
Put the elements in order, check each item in turn.
Put the elements in order, compare with the middle value, split the list in order and repeat
What do you call the step in the Divide and conquer approach that involves breaking the problem into smaller sub-problems?
Group of answer choices
Break
Halt
Breakdown
Collapse
Break
What is the time complexity of binary search?
Group of answer choices
Exponential
O (n^2)
O (1)
O (n log)
O (n log)
What do you call the sorting technique that divides the array into equal halves and then combines them in a sorted manner?
Group of answer choices
Bubble Sort
Quick Sort
Merge Sort
Insertion Sort
Merge Sort
What is the formula use in the binary search if a new mid value needs to be set.
Group of answer choices
low = mid + 1 mid = low + (high + low) / 2
low = mid = low + (high - low) / 2
low = mid + 1 mid = low + (high - low) / 2
low = mid + 2 mid = low + (high - low) / 2
low = mid + 1 mid = low + (high - low) / 2
What do you call the step or stage in the divide and conquer method that recursively combines them until they formulate a solution of the original problem?
Group of answer choices
Pool
Sequence
Chain
Combine
Combine
The Strassen algorithm is named after?
Group of answer choices
Victor Strassen
Volker Strassen
Volkar Strassen
Vilker Strassen
Volker Strassen
A method that easily modified to find the points with the smallest distance
Group of answer choices
Binary Search
Closest Pair
Merge sort
Strassen Algo
Closest Pair
How many recursive calls it will take to solve the Strassen Algorithm?
Group of answer choices
6
9
8
7
7
What is the running time of naïve matrix multiplication algorithm?
Group of answer choices
O(n^3)
O(n^2.8074)
O(n)
O(n^4)
O(n^3)
Questions with images
https://docs.google.com/document/d/1UDmg1hKb71JtEYdXQpitoiCOSRYcAvTSpbhZxkPE1Ko/edit?usp=sharing
What is the basic operation of closest pair algorithm using brute force technique?
Group of answer choices
Manhattan distance
Euclidean distance
Area
Radius
Euclidean distance
When computing for p3 what the exact formula is?
Group of answer choices
p3=(c+d)e
p3=(cd)e
p3=(c-d)+e
p3=(c/d)e
p3=(c+d)e