Time Left - 15:00 mins
GATE 2024 algorithm Rank Booster Quiz 23
Attempt now to get your rank among 45 students!
Question 1
In Dijkstra algorithm for shortest path algorithm, the maximum number if relaxing of edges will be
Question 2
Consider the following characters with their frequency in a document
Number of bits required to represent a character ‘b’ if we use Huffman coding algorithm is ___.
Question 3
The difference between the size of the file using Huffman Coding and without using it is _________ for the following occurrences of characters?
Char – Occurrences
a - 4
b - 5
c - 6
d - 7
Char – Occurrences
a - 4
b - 5
c - 6
d - 7
Question 4
Considering the fractional knapsack problem, suppose we have a knapsack of capacity M=20 and three items 
, 
, 
with profit values (
, 
, 
) as (25, 24, 15) respectively and weight values (
, 
, 
) as (18, 15, 10) respectively. What is the maximum profit achievable?
, , with profit values (, , ) as (25, 24, 15) respectively and weight values (, , ) as (18, 15, 10) respectively. What is the maximum profit achievable?Question 5
Four jobs a,b,c,d are there with their respective deadlines 2,1,1,1 The associated profits with them are 20,10,40,30 respectively. Sequence the jobs in order to get the maximum profit. Find the absolute difference of profit earned by completing the jobs and penalty for left out jobs _____________.
Question 6
We are given 6 jobs. The execution of task requires one unit of time. Each job has its own profit and deadline. Profit is earned only if task is completed before deadline.
Which of the following option is true based on the above table?
Which of the following option is true based on the above table?
Question 7
The fractional knapsack problem is defined as:
• Given a list of n objects say [
, 
, 
, ….., 
] and a Knapsack (or bag).
• Capacity of knapsack is M.
• Each object
has a weight 
and a profit of 
.
• If a fraction
(where 
€ [0,……, 1]) of an object 
is placed into a knapsack then a part of 
is earned.
The problem is to fill a knapsack which maximizes the total profit earned.
Mathematically:
Maximize (the profit) =
; subjected to the constraints
=
≤ M and 
€ {[0,…..,1] , 1≤i≤n }
Note that
= 1 if an item is completely placed in the bag and 0 if we do not pick the item otherwise if we take any fraction of the item then its value will be any value between 0 and 1.
In what order must the items be picked in order to maximize the total profit earned?
• Given a list of n objects say [
, , , ….., ] and a Knapsack (or bag). • Capacity of knapsack is M.
• Each object
has a weight and a profit of . • If a fraction
(where € [0,……, 1]) of an object is placed into a knapsack then a part of is earned. The problem is to fill a knapsack which maximizes the total profit earned.
Mathematically:
Maximize (the profit) =
; subjected to the constraints =
≤ M and € {[0,…..,1] , 1≤i≤n } Note that
= 1 if an item is completely placed in the bag and 0 if we do not pick the item otherwise if we take any fraction of the item then its value will be any value between 0 and 1. In what order must the items be picked in order to maximize the total profit earned?
- 45 attempts
- 0 upvotes
- 0 comments
Tags :
GATE & PSU CSAlgorithmsDec 6GATE & PSU CS
