Question 1: What is the definition of an algorithm?

• Step by step instructions used to solve a problem. (Correct answer)
• A decision.
• A flowchart
• A flowchart or pseudocode

Correct answer: Step by step instructions used to solve a problem.

An algorithm is a finite set of well-defined, unambiguous instructions or a step-by-step procedure designed to solve a specific problem or perform a computation. It provides a clear, systematic method to achieve a desired output from a given input. This definition emphasizes the precise and sequential nature required for effective problem-solving.

Question 2: Isn't it true that algorithms are only used in computers?

• A) False (Correct answer)
• B) True

Correct answer: A) False

Algorithms are not exclusively used in computers; they are fundamental to problem-solving in many aspects of daily life. Examples include recipes, assembly instructions for furniture, or even a set of directions to a location. Computers merely automate the execution of these step-by-step procedures, but the underlying logic is universally applicable.

Question 3: What's the difference between pseudocode and a flowchart?

• A flowchart is a diagrammatic description of an algorithm, whilst pseudocode is a textual description of an algorithm. (Correct answer)
• A flowchart is diagrammatic whilst pseudocode is written in a programming language (e.g. Pascal or Java).
• A flowchart and pseudocode are the same thing.
• A flowchart is textual, but pseudocode is diagrammatic.

Correct answer: A flowchart is a diagrammatic description of an algorithm, whilst pseudocode is a textual description of an algorithm.

A flowchart is a diagrammatic representation of an algorithm, using standardized graphical symbols and arrows to visually depict the sequence of operations and decisions. In contrast, pseudocode is a textual description of an algorithm, using a simplified, informal language that resembles programming code but is not executable. Both serve as planning tools to outline an algorithm's logic before actual coding.

Question 4: Why is it necessary to use a flowchart?

• It is easy to use
• To analyze the program
• To plan a program before making it. (Correct answer)
• To execute a program

Correct answer: To plan a program before making it.

Flowcharts are necessary as a visual planning tool to design and understand the logical flow of a program before writing any code. They help in breaking down complex problems into manageable steps, identifying potential issues, and ensuring a clear, efficient solution. By visualizing the algorithm, it becomes easier to communicate, analyze, and refine the program's structure.

Question 5: The upper bound is defined by this algorithm analysis.

• Big Theta
• Big Oh (Correct answer)
• Big Omega

Correct answer: Big Oh

Big O notation (O) is used in algorithm analysis to describe the upper bound of an algorithm's running time or space complexity. It provides a worst-case scenario estimate, indicating the maximum amount of time or space an algorithm will take as the input size grows. This helps in understanding how an algorithm scales and performs under the most demanding conditions.

Question 6: What are the three different types of algorithm constructs?

• Input, output, process
• sequence, selection & iteration (Correct answer)
• Loop, input/output, process
• Input/output, decision, terminator.

Correct answer: sequence, selection & iteration

The three fundamental control structures or constructs in algorithms are sequence, selection, and iteration. Sequence refers to the execution of instructions one after another in a linear fashion. Selection involves making decisions based on conditions (e.g., if-else statements), while iteration allows for repeating a block of instructions multiple times (e.g., loops).

Question 7: This algorithm analysis assesses a program's best case scenario.

• Big Theta
• Big Oh
• Big Omega (Correct answer)

Correct answer: Big Omega

Big Omega notation (Ω) is used in algorithm analysis to describe the lower bound of an algorithm's running time or space complexity. It provides a best-case scenario estimate, indicating the minimum amount of time or space an algorithm will take as the input size grows. This helps in understanding the most efficient performance an algorithm can achieve.

Question 8: Uses of quick sort

• Partitioning (Correct answer)
• Exchanging
• Merging
• Selection

Correct answer: Partitioning

Quick sort is a highly efficient, comparison-based sorting algorithm that primarily utilizes the technique of partitioning. In partitioning, the algorithm selects a 'pivot' element and rearranges the array such that all elements smaller than the pivot are placed before it, and all greater elements are placed after it. This process is then recursively applied to the resulting sub-arrays.

Question 9: Except for one, these are sorting algorithms:

• C) Selection
• D) Merge

The question asks to identify the algorithm that is *not* a sorting algorithm from a given list. However, the provided options "Selection" and "Merge" refer to Selection Sort and Merge Sort, both of which are well-known sorting algorithms. Without the complete list of options or a specified correct answer that is not a sorting algorithm, it is impossible to determine the intended exception. Therefore, a specific explanation for the correct answer cannot be provided based on the given information.

Question 10: Except for one, these are algorithm paradigms:

• Greedy
• Searching (Correct answer)
• Divide and Conquer
• Backtracking

Correct answer: Searching

Algorithm paradigms are general approaches or strategies for designing algorithms to solve problems. 'Greedy,' 'Divide and Conquer,' and 'Backtracking' are all established algorithm design paradigms, representing distinct problem-solving methodologies. 'Searching,' however, is a specific computational task or problem type (e.g., finding an element in a data structure), rather than a general design paradigm itself.

Question 11: Which of the following algorithms has a time complexity of n log (n)?

• Selection sort
• Heap sort
• Quick sort
• Insertion sort (Correct answer)

Correct answer: Insertion sort

The question asks which algorithm has a time complexity of O(n log n). Insertion sort, the provided correct answer, typically has a worst-case and average-case time complexity of O(n^2), although its best-case is O(n). Algorithms like Heap Sort and Quick Sort (in its average case) are generally known for O(n log n) complexity. Therefore, the provided correct answer for this question appears to be factually incorrect in a general context.

Question 12: The data for an array utilized in a program will be saved in.

• Activation table
• Register vector
• Dope vector (Correct answer)
• Symbol table

Correct answer: Dope vector

A dope vector is a data structure used by compilers and runtime systems to store essential metadata about an array. This information typically includes the array's base address, its dimensions, and the bounds for each dimension. While the actual array elements reside in memory, the dope vector enables the program to correctly access and manipulate array data, especially for dynamic or multi-dimensional arrays.

Question 13: An algorithm's order determines whether a given boolean function of 'n' variables returns a '1' is

• Exponential (Correct answer)
• Logarithmic
• Constant
• Linear

Correct answer: Exponential

Determining whether a given boolean function of 'n' variables returns '1' is known as the Boolean satisfiability problem (SAT), which is a classic NP-complete problem. Algorithms designed to solve NP-complete problems generally exhibit an exponential time complexity in the worst case. This means their running time grows exponentially with the number of input variables 'n', making them computationally intensive for large inputs.

Question 14: The term "divide-and-conquer" applies to

• The list being divided into smaller sublist, then those sorted sublist are merged back together. (Correct answer)
• The list being divided into sublist with equal numbers of elements in each, then those sorted sublist are merged back together.
• The list being divided into only two sublists, never more or less, which are sorted and merged back together.

Correct answer: The list being divided into smaller sublist, then those sorted sublist are merged back together.

The 'divide-and-conquer' paradigm is an algorithmic strategy that involves breaking down a problem into two or more smaller subproblems of the same or related type. These subproblems are then solved recursively, and their individual solutions are combined to solve the original problem. This approach is exemplified by algorithms like Merge Sort, where a list is divided into smaller sublists, sorted, and then merged back together.

Question 15: Which algorithm solves the shortest path problem for all pairs?

• Worshal's algorithm
• Prim's algorithm
• Dijkastra's algorithm (Correct answer)
• Floyd's algorithm

Correct answer: Dijkastra's algorithm

Dijkstra's algorithm is designed to find the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. To solve the all-pairs shortest path problem, Dijkstra's algorithm can be executed from each node in the graph as a source. While other algorithms like Floyd-Warshall are often more efficient for the all-pairs problem, Dijkstra's can indeed be applied to achieve this by running it N times.

Question 16: The Big-O notation is used to represent

• Growth of functions (Correct answer)
• Reduction of functions
• None of the above

Correct answer: Growth of functions

Big O notation is a mathematical notation used in algorithm analysis to describe the limiting behavior of a function. Specifically, it characterizes the upper bound of an algorithm's running time or space requirements as the input size grows infinitely large. Essentially, Big O notation represents the growth rate of functions, providing a way to classify algorithms by how their performance changes with input size.

Question 17: The Dijkstra Algorithm has the following applications:

• Shortest path finding
• Traffic Optimization
• Routing
• All of the above (Correct answer)

Correct answer: All of the above

Dijkstra's algorithm is a fundamental algorithm with wide-ranging applications due to its ability to find the shortest paths between nodes in a graph with non-negative edge weights. Its uses include general shortest path finding in various networks, optimizing traffic flow in transportation systems, and determining efficient routing protocols in computer networks. Therefore, it is applicable to all the listed scenarios.

Question 18: What is the Dijkstra Algorithm's running time?

• O(|V|^2 + |E|) (Correct answer)
• O(|V|^4 + |E|)
• None of the above

Correct answer: O(|V|^2 + |E|)

Dijkstra's algorithm finds the shortest paths from a single source to all other vertices in a graph with non-negative edge weights. The running time depends on the data structures used for the priority queue. Using an adjacency matrix and a simple array to extract the minimum, the complexity is O(|V|^2), where |V| is the number of vertices. When using an adjacency list and a min-priority queue (like a binary heap), it can be optimized to O(|E| + |V| log |V|), but O(|V|^2 + |E|) is a common general expression, especially for dense graphs or simpler implementations, as |E| can be up to |V|^2.

Question 19: Which of the following is not a property of an algorithm?

• Generality
• Correctness
• Finiteness
• Infiniteness (Correct answer)

Correct answer: Infiniteness

A fundamental property of any algorithm is finiteness, meaning it must terminate after a finite number of steps for all valid inputs. Infiniteness directly contradicts this essential requirement. Other key properties of algorithms include definiteness (each step is precisely defined), effectiveness (each step is basic and executable), and having clear inputs and outputs.

Question 20: The following algorithms can be used in a snake game.

• MST
• BFS
• DFS
• All of the above (Correct answer)

Correct answer: All of the above

All three algorithms can be relevant in a snake game, depending on the AI's complexity. BFS (Breadth-First Search) is excellent for finding the shortest path to food. DFS (Depth-First Search) can be used to explore longer paths, potentially to avoid trapping the snake or to ensure it covers more ground. While MST (Minimum Spanning Tree) is not a direct pathfinding algorithm, it could be used in advanced AI to analyze the connectivity of the remaining free cells on the board, helping the snake avoid self-entrapment or plan movements to 'span' an area efficiently.

Question 21: Consider two L1 and L2 sorted lists. In the worst-case scenario, the number of comparisons required by my merge sort algorithm will be

• L1+L2-1 (Correct answer)
• L1,L2
• Max(L1,L2)
• Min(L1,L2)

Correct answer: L1+L2-1

When merging two sorted lists, L1 and L2, in the worst-case scenario, the algorithm might need to compare almost every element. For instance, if elements from one list are consistently chosen until only one element remains in the other list, then L1 + L2 - 1 comparisons would be needed. This occurs because each comparison typically places one element into the merged list, and the very last element can be appended without a final comparison.

Question 22: We'll need the following items to organize a binary tree in ascending order:

• Preorder traversal
• Post order traversal
• In-order traversal (Correct answer)
• None of above

Correct answer: In-order traversal

An in-order traversal of a binary search tree (BST) visits nodes in a specific sequence: first the left subtree, then the root node, and finally the right subtree. Due to the inherent property of a BST (where all nodes in the left subtree are smaller than the root, and all nodes in the right subtree are larger), this traversal method naturally processes the elements in ascending order. Preorder and postorder traversals do not produce a sorted sequence.

Question 23: The problem called can be solved with polynomial worst-case complexity.

• Intractable
• Tractable (Correct answer)
• Unsolvable

Correct answer: Tractable

A problem is classified as 'tractable' if there exists an algorithm that can solve it within a polynomial amount of time relative to the size of its input. This means the worst-case running time complexity can be expressed as O(n^k) for some constant k, where n is the input size. Problems that cannot be solved in polynomial time are generally considered 'intractable', while 'unsolvable' problems have no algorithmic solution at all.

Question 24: The best way for arranging library books is

• Quick sort
• Merge sort
• Bubble sort
• Heap sort (Correct answer)

Correct answer: Heap sort

Heap sort is often considered a highly efficient and practical sorting algorithm for large datasets, such as library books. It guarantees a worst-case time complexity of O(n log n), which is optimal for comparison-based sorting, and it sorts in-place, meaning it requires minimal additional memory. While Quick sort is often faster on average, its worst-case performance is O(n^2), and Bubble sort is generally inefficient with O(n^2) complexity.

Question 25: Which method do we use to choose a hash function at random to avoid incorrect hashing behavior caused by a specific set of keys?

• Universal hashing (Correct answer)
• Double hashing
• Division method

Correct answer: Universal hashing

Universal hashing is a technique where a hash function is chosen randomly from a carefully constructed family of hash functions. This method ensures that for any fixed set of keys, the expected number of collisions is small, regardless of the specific input keys. By randomizing the choice of hash function, it effectively prevents an adversary from choosing a set of keys that would consistently lead to worst-case hashing behavior.