CS502 Fundamentals of Algorithms Quiz 1 Solved

Fundamentals of Algorithms Quiz 1 Solved. Most of the Important Recent CS502 Quiz 1 Solution for Help in Studies or Exams and Improve Knowledge or Learning Skills. Also, Get PDF File Given Below.

CS502 QUIZ 1 SOLVED

1. DFS or BFS yields a _ of the graph.
Traversed Tree
b) Spanning tree
c. Simple Tree
d. Free Tree

2. In Knapsack Problem, the goal is to put items in the knapsack such that the value of the items is subject to weight limit of knapsack.
a) Minimized
b) Decreased
c) Maximized
d) None of the given options

3. Using ASCII code, each character is represented by a fixed-length code of
bits per character.
a) 4
b) 6
c) 8
d) 10

4. Which type of algorithm is harder to prove the correctness?
a) Greedy
b) Brute Force
c) Dynamic Programming
d) Divide and Conquer

5. Consider the string "abcdaacac". if the string is coded with ASCII codes, the message length would be.
a) 70 bits
b) 60 bits
c) 90 bits
d) 75 bits 8*9=72 bits are the right answer

6. In algorithm, you hope that by choosing a local optimum at each step, you will end up at a global optimum.
a) Simple
b) Divide and conquer
c) Greedy
d) Brute force

7. For a digraph G = (V, E), Sum of in-degree(v)
a) Not equal to Sum of out-degree(V)
b) =Sum of out-degree(v)
c) < Sum of out-degree(v)
d) > Sum of out-degree(v)

8. In inductive approach of knapsack problem, we consider 2 cases,
Or _.
a) Median, Mode
b) Recursive, Iterative
c) Leave object, Take an object
d. Sequentially, Parallel

9. A/an is one in which you want to find, not just a solution, but the best solution.
a) Optimization Problem
b) Divide and Conquer
c) NP-Complete problem
d) Best Problem

10. If the graph is represented using an adjacency matrix, then the Breadth-first search takes time.
a) O(E+1)
b) O(V^2)
c) O(V)
d) O(E)

11. If the graph is represented using an adjacency list, then Breadth-first search takes time.
a) O(V^2)
b) O(V)
c) Co(V + E)
d. O(E + 1)

12. A graph is if every vertex can reach every other vertex
a) Connected
b) Cycle
c) Acyclic
d) Loop

13. The number of edges that come out of a vertex is called the _ of that vertex in a digraph.
a) post-degree
b) in-degree
c) out-degree
d) pre-degree

14. Huffman algorithm produces the prefix code tree
a) Optimal
b) Best
c) Worst
d) Better

15. graph is said to be acyclic if it contains _
a) at least one cycle
b) exactly one cycle
c) always more than one cycle
d) no cycles

16. Fractional Knapsack is founded on method.
a) Greedy
b) Recursive
c) Dynamic Programming
d) Divide and Conquer

17. If Matrix-A has dimensions "3x2" and Matrix-B has dimensions "2x3", then multiplication of Matrix-A and Matrix-B will result a new Matrix-C having dimensions
a) 3x2
b) 2x3
c) 2x2
d) 3x3

18. Some places a person wants to visit Starting from a vertex, he wants to visit every place linked to this vertex, and so on. What algorithm does he need to use?
a) Depth First Search
b) Breadth-First Search
c) Greedy Algorithm
d) Divide and Conquer

19. Greedy algorithm can NOT be used to solve all the _ problems.
a) Dynamic programming
b) Memorization programming
c) Edit distance programming
d) Storing value programing

Check Also:

CS502 Handouts PDF

CS502 Short notes Midterm

CS502 Midterm MCQs

20. In Huffman encoding, the is the number of occurrences of a character divided by the total characters in the message.
a) Counting
b) Parsing
c) Relative Probability
d) Weight

21. In Brute Force solution of knapsack Problem, there are possible combinations for n items.
a) 2
b) n
c) 2^n (2 raised to the power n)
d. 3^n (3 raised to the power n)

22. The Binary Tree constructed by Huffman Encoding is a:
a) Full binary tree
b) Partial binary tree
c) Incomplete binary tree
d) None of the given options

23. In Huffman encoding when a new node is created by combining two nodes, the new node is placed in the _ .
a) Priority queue
b) Linked list
c) Min heap tree
d) Graph traversal

24. In general, the Activity Selection Problem is to select a.
a) Minimum-size set of interfering activities
b) Maximum-size set of mutually non-interfering activities
c) Maximum-size set of interfering activities
d) Minimum-size set of mutually non-interfering activities

26.In the Activity selection problem, intuitively.
a) There are always short activities as input
b) Short activities are not attractive
c) Duration of the activities does not matter
d) We do not like long activities

27. Which of the following ways can be used to represent a graph?
a) Adjacency List
b) Incidence Matrix
c) Adjacency Matrix Adjacency List
d) No way to represent

28. Which of the following algorithms solves the fractional knapsack problem most effectively?
a) Divide and conquer
b) Greedy algorithm
c) Dynamic programming
d) Backtracking

29. The prefix code generated by Huffman algorithm _ the expected length of the encoded string.
a) Minimizes
b) Balances
c) Maximizes
d) Keeps Constant

30. In context of activity selection algorithm, time is dominated by sorting of the activities by _ .
a) Start Times
b) Finish Times
c) Average Times
d) CPU Burst Times

31. Huffman algorithm generates an optimum _ code.
a) Prefix
b) Postfix
c) Infix
d) None of the given options

32. If a matrix has three rows and two columns, then dimensions of matrix will be:
a) 3 x 2
b) 2 x 3
c) 3 x 3
d) 2 x 2

33. In greedy algorithm, at each phase, you take the _ you can get right now, without regard for future consequences.
a) Worst
b) Minimum
c) Good

d) Best

34. Which of the following algorithms provides an optimal solution for the activity selection problem?
a) Divide and Conquer
b) Brute Force
c) Greddy
d) Recursive

35. Suppose you are given infinite coins of 1, 2, 3, and 4. Select the ways of the minimum number of coins that required to achieve a sum of 6:
a) 1
b) 2 (4+2=6)
c) 3
d) 4

36. Using ASCII standard the string "greedy" will be encoded with
a) 48 bits 8n=8(6)=48 bits ascii encode
b) 120 bits
c) 44 bits
d) 40 bits

37. For graph traversal, Breadth-first search strategy _
a) is always recursive
b) Cannot be recursive
c) Cannot be non-recursive
d) Can be both recursive and non-recursive

38. The greedy approach gives us an optimal solution when the coins are all powers of a denomination.
b) Fixed
c) Variable
d) Constant
c) Static

39. In Activity Selection, we say that two activities are non-interfering if their start-finish interval overlap.
a) Do
b) Do not
c) Sometimes
d) Once

40. Bag is a _.
a) type of algorithm
b) data structure
c) program
d) compiler

41. The running time of brute-force algorithm to solve Knapsack problem is
.
a) O(n)
b) O(n3)
c) O(n!)
d) O(2^n)

42. In Activity scheduling algorithm, the width of a rectangle _.
a) Is always ignored
b) Directs towards recursion
c) Should be maximized
d) Indicates the duration of an activity

43. In a digraph, the number of edges coming out of a vertex is called the of that vertex.
a) In-degree
b) Complete degree
c) Node
d) Out-degree

44. How many steps are involved to design the dynamic programming strategy?
a) 2
b) 3
c) 1
d) 4

45. The Huffman codes provide a method of data efficiently.
a) Reading/Writing
b) Encoding/Decoding
c) Divide/Conquer
d) Inserting/Deleting

46. Time complexity of the "0 - 1" knapsack algorithm depends on.
a) Number of items
b) Capacity of the knapsack
c) Size of the table
d) Number of items and capacity of knapsack

47. If the string "lmncde" is coded with ASCII code, the message length would be _ bits.
a) 24
b) 36
c) 48 8*6=48
d) 60

48. Each time we traverse graph by Breadth-first search algorithm, we count the distance from _.
a) Starting node
b) neighbors of the starting node
c) rightmost node
d) Left most node

49. The coin change problem is to find the minimum number of coins required to get the sum S of infinite coins of denominations al, a2, a3,, an. This problem can be solved using.
a) Greedy algorithm
b) Dynamic programming
c) Divide and conquer
d) Backtracking

50. Each vertex can reach every other vertex is called.
a) Unordered graph
b) Unconnected graph
c) Connected graph
d) Ordered graph

51. data structure is used to perform the Depth-first search.
a) Array
b) Queue
c) Stack
d) Tree

52. In general, a graph G = (V, E) consists of a and E, a binary relation on V called edges.
a) Infinite set of vertices V
b) Infinite set of nodes
c) Finite set of vertices V
d) Infinite set of objects

53. The general coin change problem can be solved using _.
a) Dynamic programming
b) Greedy Algorithm
c) Divide and Conquer
d) Recursion

54. For traversing the graphs, can be visualized as a wave front propagating inward towards root node.
a) Depth-first Search
b) Breadth-first search
c) Binary search
d) Linear search

55. Counting Money problem:
a) Can be optimally solved by greedy algorithm
b) cannot be optimally solved by greedy algorithm
c) Cannot be solved by brute force algorithm
d) Can be solved by simple recursive algorithm

56. The activity scheduling is a simple scheduling problem for which the greedy algorithm approach provides a/an _ solution.
a) Simple
b) Suboptimal
c) Optimal
d) Nonoptimal

57. Which of the following is true about Huffman Coding?
a) Huffman Codes may not be optimal lossless codes in some cases
b) Huffman coding may become Lossy in some cases
c) Huffman coding is not an efficient coding way
d) In Huffman coding, no code is a prefix of any other code

58. One of the limitations in 0/1 knapsack is that an item can either be _ in the bag or not.
a) Use
b) Put
c) Move
d) Store

59. In involves breaking up the problem into subproblems whose solutions can be combined to solve the global problem.
a) Complexity Theory
b) Dynamic programming solution
c) Divide and Conquer Strategy
d) Greedy Algorithms

60. The time complexity of activity selection algorithm is.
a) O(NlogN)
b) O(N)
c) O(logN)
d) O(NlogN)

61. The is a problem for which the greedy algorithm approach provides an optimal solution.
a) Activity selection
b) Dynamic programming
c) Knapsack Problem
d) NP-complete problem

62. Which of the following is true about the graph?

a) A graph may contain no edges and many vertices
b) A graph may contain many edges and no vertices
c) A graph may contain no edges and no vertices
d) A graph may contain no vertices and many edges

63. In Huffman encoding fixed-length codes are popular because it is very easy to break up a into its individual.
a) Number, string
b) Character, Number
c) String, Characters
d) Floating number, string

64. In general in comparison with Fractional Knapsack problem,
a) 0 – 1 knapsack problem is very easy to solve
b) 0 – 1 knapsack problem is hard to solve
c) Both are easy to solve
d) We cannot compare them

65. In an undirected graph, we say that an edge is _ on a vertex if the vertex is an endpoint of the edge.
a) Incident
b) Directed
c) Undirected
d) Tree

66. In Huffman Encoding, the characters with smallest probabilities are placed at the depth of the tree
a) Minimum
b) Average
c) Maximum
d) Root

67. The probability in Huffman encoding is the number of occurrences of a character divided by the total in the message
a) Numbers
b) Frequencies
c) Strings
d) Characters

68. The Knapsack problem belongs to the domain of problems
a) Optimization
b) Sorting
c) Linear solution
d) Searching

69. In recursive formulation of Knapsack Problem:
V[0, j] = for j>=0
a) -1
b) 0
c) 1
d) 2

70. An optimization problem is one in which you want to find the
solution
a) Simple
b) Good
c) Best
d) Worst

71. If we implement the bag by using a queue, we have.
a) BFS
b) DFS
c) Graph
d) Loop

72. Which graph traversal algorithm uses a stack to keep track of vertices?
a) Divide and Conquer
b) Breadth-First Search
c) Greedy Algorithm
d) Depth First Search

73. In Dynamic Programming based solution of Knapsack Problem, if we decide to take an object ‘i’, then we gain.
a) W (Total Weight of Knapsack)
b) V (Total Value of all items)
c) vi (Value of object i)
d) None of the given options

74. If there are no cycles in the graph, what is the maximum number of edges present in a simple directed graph with 5 vertices?
a) 3
b) 4
c) 5
d) 6