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

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:**

**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

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)

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

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

**Most Important Materials:**

**CS502 Midterm Past Papers Solved by Moaaz**

**CS502 Midterm Past Papers Waqar Siddhu**

## 0 Comments