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 ___________

Quadratic

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

Advance

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

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!

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

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

to read?

This is really interesting, You’re a very skilled blogger.

I have joined your feed and look forward to seeking more of your great post.

Also, I have shared your web site in my social networks!