CS 502 – GRAND QUIZ SOLUTION 2020

4
201
Pseudo code of algorithms are to be read by ___________.
RAM
Computer
Compiler
Approach of solving geometric problems by sweeping a line
across the plane is called ________sweep.
Line
Plane
Cube
Box
For average-case time analysis of Quick sort algorithm, Pivot
selection is on average basis from _________
half of the input values
all possible random values
Pivot is input separately
values greater than 5
Insertion sort is an in-place sorting algorithm.
True
False
Heap sort is a/an and _ sorting algorithm.
Not in-place, not stable one
In-place, stable one
In-place, not stable one
Not in-place, stable one
Merge sort is based on___________.
Brute-force
Plan-sweep
Axis-sweep
Divide and Conquer
While solving Selection problem, in Sieve technique we partition
input data __________
In increasing order
In decreasing order
According to Pivot
Randomly
Quick sort is a not a partitioning-based algorithm.
True
False
In Heap Sort algorithm, the first step is to _________
Call Build-Heap procedure
Sort the array in descending order
Call Heapify procedure
Find the number of input elements
In Heap Sort algorithm (using max heap), when every time
maximum element is removed from top ___________
We call merge Sort algorithm
It becomes Order n2 Algorithm
Divide and Conquer strategy helps us
We are left with a hole
The running time of Quick sort algorithm _________
Is impossible to compute
Has nothing to do with pivot selection
Is Random upon each execution
Greatly influenced by the selection of pivot
In asymptotical analysis of n*(5 + 2) – 3 , as n becomes large, the
dominant (fastest growing) term is some constant times ________
n_1
n
n+1
n*n
The total running time for Selection algorithm is ___________
Linear
Geometric
Exponential
Quick sort is a not a partitioning-based algorithm.
True
False
The main purpose of mathematical analysis is measuring the
____________required by the algorithm.
Space
Execution time
Inputs & outputs
Execution time and memory
Result of asymptotical analysis of n(n – 3) and 4n*n is that
___________.
n(n-1) is asymptotically Less
n(n-1) is asymptotically Greater
Both are asymptotically Not equivalent
Both are asymptotically Equivalent
Upper bound requires that there exist positive constants c2 and
n0 such that
f(n) ____ c2n for all n <= n0
Less than
Equal to or Less than
Equal or Greater than
Greater than
Merge sort have running time……running time of Heap sort.
Greater than
Less than
Equal to
Different than
Algorithms having O (order) _______ running time are considered
to be slow ones.
n
n2
n3
log (n)
Boolean operation is a ________ operation on an idealized RAM
model of computation.
Starting
Basic
Normal
The main purpose of mathematical analysis is measuring the
____________required by the algorithm.
Space
Execution time
Inputs & outputs
Execution time and memory
In average-case time analysis of Quick sort algorithm, the most
balanced case for partition is when we divide the list of elements
into _________
Equal no. of pieces as of input elements
Single piece exactly
Two nearly equal pieces
Three nearly equal pieces
Algorithm is a sequence of computational steps that …..the input
into output.
Merge
Assign
Transform
Integrate
The Iteration method is used for ____________
Comparing sorting algorithms only
Solving Recurrence relations
Merging elements in Merge sort
Dividing elements in Merge sort
In plane sweep approach of solving geometric problems, a
________is swept across the plane.
Line
Plane
Cube
Box
Counting sort is suitable to sort the elements in range 1 to k:
K is large
K is small
K may be large or small
None
In ____________ we have to find rank of an element from given
input.
Merge sort algorithm
Selection problem
Brute force technique
Plane Sweep algorithm
Rank of an element can be defined as ____________
One minus the number of elements that are smaller
Two plus the number of elements that are greater
One plus the number of elements that are smaller
Two minus the number of elements that are smaller
In Heap Sort algorithm, the total running time for Heapify
procedure is ____________
Theta (log n)
Order (log n)
Omega (log n)
O (1) i.e. Constant time
A sorting algorithm is called as ________ if duplicate elements
remain in the same relative position after sorting.
Parallel
O(n) algorithm
Stable
Complex
Al-Khwarizmi was a/an…….
Artist
Mathematician
Astronomer
Khalifah
Greedy algorithm can do very poorly for some problems.
True (p97)
False
A greedy algorithm sometimes works well for optimization problems.
True (p97
) False
Question #
A greedy algorithm does not work in phases.
True
False (p97)
Greedy algorithm approach solves both 0/1 Knapsack and Fractional Knapsack problems.
True
False
Dynamic Programming approach solves both 0/1 Knapsack and Fractional Knapsack problems.
True
False
In ________ based solution of knapsack problem, we consider 2 cases. Leave object Or Take object.
Brute force
Dynamic programming (p93)
In brute force based solution of knapsack problem, we consider 2 cases. Leave object Or Take object.
True
False (p93)
In DP based solution of knapsack problem, V[0, j] = _______ if j>=0
-1
0 (p93)
1
2
In DP based solution of knapsack problem, V[0, j] = 1 if j>=0
True
False (p93)
CS 502 GRAND QUIZ SOLUTION 2020
In DP based solution of knapsack problem, to compute entries of V we will imply a/an _______ approach.
Subjective
Inductive (p93)
Brute force
Combination
In DP based solution of knapsack problem, if we decide to take an object i, then we gain a value of _____.
w i-1
vi-1
w i
vi (p93)
In Fractional Knapsack problem, one is allowed to take fraction of an item for _______
for fraction of the weight
for fraction of the value
Both, fraction of the weight and value (p109)
None
______ approach is optimal for the fractional knapsack problem.
Divide and Conquer
Dynamic Programming
Greedy algorithm (p110)
Brute force
In ____ Knapsack Problem, limitation is that an item can either be put in the bag or not-fractional items are not allowed.
0 1
0/1 Fractional
In Fractional Knapsack problem, the goal is to _________
minimize the value of items without exceeding the total weight limit of W
maximize the value of items without exceeding the total weight limit of W (p109)
minimize the value of items even if exceeding the total weight limit of W
maximize the value of items even if exceeding the total weight limit of W
In solving Fractional Knapsack problem, we do not need sorting.
True
False (p109)
Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G? Select correct option:
O(|V |^2)
O(|V | |E|)
O(|V |^2|E|)
O(|V | + |E|) (p116)
For traversing graphs, Breadth-first search can be visualized as a wave front propagating inwards towards root (or source) node.
True
False (p117)
Breadth-first search is not a traversal strategy for graphs.
True
False (p119)
Breadth-first search is not a popular algorithm technique used for traversing graphs.
True
False (p119)
Breadth-first search begins at a root node and inspects all the nodes except neighboring ones.
True
False (117)
Each time we traverse graph by Breath-first search algorithm, we count the distance from ______
Starting node (p117)
neighbors of the starting node
right most node
left most node
Suppose we are given a set S = {a1, a2, … an} of n activities that are to be scheduled to use some resource. Each activity ai must be started at a given start time si and ends at a given finish time fi. We want to schedule the largest number of activities on the resource. It is an example of ____________.
Searching
Dynamic Programming
Activity selection (p105)
Divide and Conquer
CS 502 GRAND QUIZ SOLUTION 2020
In general, the Activity selection problem is to select a ___________
minimum-size set of interfering activities
maximum-size set of mutually non-interfering activities (p105)
maximum-size set of interfering activities
minimum-size set of mutually non-interfering activities
In Activity selection (using Greedy approach), intuitively _________
Short activities are not preferable
There are always short activities as input
We do not like long activities (p105)
It does not matter about the length of activities
The activity schedule is a simple scheduling problem for which the ____ approach provides an optimal solution.
Dynamic Programming
Graph
Divide and Conquer
Greedy Algorithm (p105)
The activity scheduling is a simple scheduling problem for which the greedy algorithm approach provides a/an
________solution.
Simple
Sub optimal
Optimal (p105)
Non optimal
A number of lectures are to be given in a single lecture hall. Optimum scheduling for this is an example of Activity selection.
True (p105)
False
In Activity scheduling algorithm, each activity is represented by a ______
Circle
Square
Triangle
Rectangle (p106)
In Activity scheduling algorithm, the width of a rectangle ____________
Is always ignored
Directs towards recursion
Should be maximized
Indicates the duration of an activity (p106)
In Activity scheduling algorithm, the time is dominated by sorting of the activities by ________
start times
finish times (p106)
The complexity of Activity scheduling algorithm is __________
O (n)
O log n
O (n) log n (p106)
O n^2
In Activity scheduling algorithm, as base case if there are no activities then Greedy algorithm _____
cannot be optimized
is solved using Recursion
is transformed into Dynamic Programming
is trivially optimal (p109)
Bag is a ______
type of algorithm
There are _________ nested loops in DP based algorithm for computing the minimum cost of chain matrix multiplication.
2
3 (p90)
4
5
CS 502 GRAND QUIZ SOLUTION 2020
Time complexity of DP based algorithm for computing the minimum cost of chain matrix Multiplication is —-.
log n
n
n2
n3 (p90)
If you read more quiz cs 502 click

1. I do not even know how I ended up here, but I thought this post was great.

I don’t know who you are but certainly you’re
going to a famous blogger if you are not already 😉 Cheers!

2. Excellent beat ! I wish to apprentice at the same time as you amend your web site, how could i subscribe for a blog website?
The account helped me a acceptable deal. I have been tiny bit familiar of this your broadcast provided vibrant clear concept

3. Write more, thats all I have to say. Literally, it seems as though
you relied on the video to make your point. You definitely
know what youre talking about, why waste your intelligence on just posting
videos to your site when you could be giving us something informative