Samacheer Kalvi Class 12 Computer Science Solutions Chapter 4 Algorithmic Strategies

I. Choose the Best Answer (1 Mark)

 

Question 1. The word comes from the name of a Persian mathematician Abu Ja'far Mohammed ibn-i Musa al Khwarizmi is called?
(a) Flowchart
(b) Flow
(c) Algorithm
(d) Syntax
Answer: (c) Algorithm
In simple words: The term "algorithm" comes from the name of the Persian mathematician Abu Ja'far Mohammed ibn-i Musa al Khwarizmi, who developed systematic ways to solve mathematical problems. His work helped create the idea of step-by-step instructions that computers use.

🎯 Exam Tip: Remember that "algorithm" is a key term in computer science, and its origin from a mathematician's name highlights its historical connection to problem-solving. Knowing the origin can help in recall.

 

Question 2. From the following sorting algorithms which algorithm needs the minimum number of swaps?
(a) Bubble sort
(b) Quick sort
(c) Merge sort
(d) Selection sort
Answer: (d) Selection sort
In simple words: Selection sort is a sorting method that aims to use the fewest possible swaps. It does this by finding the smallest item and putting it in its correct place, then finding the next smallest, and so on. This approach minimizes data movement.

🎯 Exam Tip: Focus on the core mechanism of each sorting algorithm. Selection sort performs at most `\( n-1 \)` swaps, making it efficient in terms of data exchange, even if its time complexity is not optimal.

 

Question 3. Two main measures for the efficiency of an algorithm are
(a) Processor and memory
(b) Complexity and capacity
(c) Time and space
(d) Data and space
Answer: (c) Time and space
In simple words: When we talk about how good an algorithm is, we mostly look at two things: how much time it takes to finish its job, and how much memory (space) it needs to run. These two factors help us compare different algorithms.

🎯 Exam Tip: Always remember that time and space complexity are the fundamental measures for evaluating an algorithm's efficiency. They describe how an algorithm's performance scales with input size.

 

Question 4. The complexity of linear search algorithm is
(a) \( O(n) \)
(b) \( O(\log n) \)
(c) \( O(n^2) \)
(d) \( O(n \log n) \)
Answer: (a) \( O(n) \)
In simple words: Linear search checks each item one by one until it finds what it's looking for. In the worst case, it might have to check all 'n' items. So, its performance grows directly with the number of items.

🎯 Exam Tip: For linear search, the worst-case time complexity is `\( O(n) \)` because you might have to scan the entire list to find an element or confirm its absence. This is a common point of confusion with binary search's `\( O(\log n) \)`.

 

Question 5. From the following sorting algorithms which has the lowest worst-case complexity?
(a) Bubble sort
(b) Quick sort
(c) Merge sort
(d) Selection sort
Answer: (c) Merge sort
In simple words: Merge sort consistently performs well, even in the worst situation. It divides the list into smaller parts, sorts them, and then combines them. This divide-and-conquer method keeps its performance predictable and efficient, avoiding slow downsides.

🎯 Exam Tip: Merge sort guarantees a worst-case time complexity of `\( O(n \log n) \)`. While other algorithms might be faster in best or average cases, Merge sort's consistent performance makes it a good choice for critical applications where worst-case scenarios must be avoided.

 

Question 6. Which of the following is not a stable sorting algorithm?
(a) Insertion sort
(b) Selection sort
(c) Bubble sort
(d) Merge sort
Answer: (b) Selection sort
In simple words: A stable sorting algorithm keeps items with the same value in their original order. Selection sort often moves items far from their original spots, which can change the relative order of identical items, making it unstable.

🎯 Exam Tip: Stability in sorting refers to whether the relative order of equal elements is preserved. Selection sort is generally unstable because it might swap an element with one far away, disturbing the original order of equal elements.

 

Question 7. Time Complexity of bubble sort in best case is
(a) \( \theta (n) \)
(b) \( \theta (n \log n) \)
(c) \( \theta (n^2) \)
(d) \( \theta (n (\log n)^2) \)
Answer: (a) \( \theta (n) \)
In simple words: In the best case, if the list is already sorted, bubble sort will only need to go through it once to confirm that no swaps are needed. This means it only takes time proportional to the number of items in the list.

🎯 Exam Tip: Bubble sort's best-case complexity is `\( \theta (n) \)` if an optimization (a flag to stop if no swaps occur) is used. Without this flag, it would always be `\( \theta (n^2) \)`. Be aware of such nuances in algorithm analysis.

 

Question 8. The \( O \) notation in asymptotic evaluation represents
(a) Base case
(b) Average case
(c) Worst case
(d) NULL case
Answer: (c) Worst case
In simple words: The Big \( O \) notation tells us the most time or resources an algorithm will ever need, no matter how bad the input data is. It describes the upper limit of an algorithm's growth.

🎯 Exam Tip: Big `\( O \)` notation is commonly used to describe the upper bound or worst-case scenario for an algorithm's running time or space requirements. It's crucial for understanding how an algorithm performs under the most challenging conditions.

 

Question 9. If a problem can be broken into sub problems which are reused several times, the problem possesses which property?
(a) Overlapping sub problems
(b) Optimal substructure
(c) Memoization
(d) Greedy
Answer: (a) Overlapping sub problems
In simple words: When solving a big problem, if the same smaller parts of that problem need to be solved many times over, we say it has the property of "overlapping sub problems." Dynamic programming is good for these types of problems.

🎯 Exam Tip: Overlapping sub problems is one of the key characteristics that indicate a problem can be efficiently solved using dynamic programming, as it allows for storing and reusing results of sub problems.

 

Question 10. In dynamic programming, the technique of storing the previously calculated values is called ?
(a) Saving value property
(b) Storing value property
(c) Memoization
(d) Mapping
Answer: (c) Memoization
In simple words: Memoization is a smart way to save the answers to parts of a problem once they've been solved. If that same part comes up again, instead of recalculating, the algorithm just fetches the saved answer, which makes it much faster.

🎯 Exam Tip: Memoization is a top-down dynamic programming technique where results of function calls are cached, significantly improving performance by avoiding redundant calculations for overlapping sub problems.

II. Answer the Following Questions (2 Marks)

 

Question 1. What is an Algorithm?
Answer: An algorithm is a detailed set of instructions that are followed step-by-step to complete a specific task or solve a problem. It has a clear beginning and end. This set of instructions can be written using any programming language to create a working program. A good algorithm makes sure the task is finished correctly and efficiently.
In simple words: An algorithm is like a recipe; it's a list of clear steps to solve a problem.

🎯 Exam Tip: When defining an algorithm, ensure you mention "finite set of instructions," "step-by-step procedure," and its purpose "to accomplish a particular task or solve a problem."

 

Question 2. Define Pseudocode
Answer: Pseudocode is a way to describe an algorithm that looks a bit like a programming language, but it's not real code that a computer can run. It uses simple English words and some common programming ideas to explain what the algorithm does. This makes it easy for people to understand the steps without worrying about strict programming rules.

• Pseudocode is a writing style similar to programming languages but is not executable.
• It blends programming structures with plain English to make algorithms easy to read and understand.

In simple words: Pseudocode is like a simple English outline of a program, using common words and some coding ideas, but it's not actual computer code.

🎯 Exam Tip: Highlight that pseudocode is a high-level description, independent of any programming language, and its main purpose is clarity for human understanding, not execution by a computer.

 

Question 3. Who is an Algorist?
Answer: An algorist is a person who is very good at designing, creating, and analyzing algorithms. They are skilled in finding efficient and effective ways to solve problems using a series of steps. Their expertise lies in developing these computational methods.
In simple words: An algorist is a skilled person who creates and designs algorithms.

🎯 Exam Tip: Define "algorist" directly as someone skilled in algorithm design and analysis. Avoid overly complex descriptions.

 

Question 4. What is Sorting?
Answer: Sorting is a process that arranges a collection of items, like numbers or words, in a specific order. This order can be either increasing (ascending) or decreasing (descending). There are many different ways to sort items, and some common methods used in algorithms include Bubble Sort, Quick Sort, Heap Sort, Selection Sort, and Insertion Sort. Each method has its own way of organizing the items.
In simple words: Sorting means putting a group of items in a specific order, like from smallest to largest or A to Z.

🎯 Exam Tip: When defining sorting, clearly state its purpose (arranging items in ascending or descending order) and be ready to list a few common sorting algorithms as examples.

 

Question 5. What is searching? Write its types.
Answer: Searching is the process of finding a specific item within a larger collection of items or a list. It's about checking if a particular element is present and, if so, where it is located. There are different methods to perform searches. The main types of searching algorithms are:

1. Searching is a process of finding a particular element present in a given set of elements.
2. Some of the searching types are:

• Linear Search
• Binary Search

In simple words: Searching means looking for a specific item in a list. The two main ways to search are Linear Search and Binary Search.

🎯 Exam Tip: Define searching as "finding a particular element." For types, Linear Search and Binary Search are the most common; ensure you can describe the basic idea of each.

III. Answer the Following Questions (3 Marks)

 

Question 1. List the characteristics of an algorithm
Answer: An algorithm has several important characteristics that ensure it is well-defined and effective. These include:

• Input: An algorithm must take zero or more external values as input.
• Output: It must produce at least one value as output.
• Finiteness: An algorithm must always stop after a limited number of steps.
• Definiteness: Each step in the algorithm must be clear and unambiguous, with no room for different interpretations. For example, operations like division by zero are not allowed.
• Effectiveness: Every instruction must be basic enough to be carried out practically and in a reasonable amount of time.
• Correctness: The algorithm must correctly solve the problem it was designed for, meaning it should be error-free.
• Simplicity: It should be easy to understand and implement.
• Unambiguous: All steps, inputs, and outputs must be clear and lead to only one meaning.
• Feasibility: The algorithm should be executable with the available resources (e.g., time, memory).
• Portable: It should be usable across different programming languages or operating systems without significant changes.
• Independent: The algorithm should be described without relying on a specific programming language.

In simple words: An algorithm needs clear steps, inputs, outputs, and must finish in a set time. It should be correct, simple, and work everywhere.

🎯 Exam Tip: When listing characteristics, aim to include key terms like Finiteness, Definiteness, Input/Output, and Effectiveness. Explaining each briefly demonstrates a thorough understanding.

 

Question 2. Discuss Algorithmic complexity and its types
Answer: Algorithmic complexity is a way to measure how efficient an algorithm is. It tells us how the algorithm's performance changes as the size of the input data grows. This is typically measured in terms of time and space. An algorithm's efficiency is often described by a function, say `\( f(n) \)`, where `\( n \)` is the size of the input.

• The complexity of an algorithm `\( f(n) \)` shows the running time or storage space needed based on the input size `\( n \)`.
• Time Complexity: This measures the number of steps an algorithm takes to complete its process.
• Space Complexity: This measures the total amount of memory an algorithm needs to run to its completion.

The memory an algorithm needs (its space complexity) is made up of two main parts:

• A fixed part: This includes the space needed for basic things like variables, constants, and the instructions themselves. For example, simple variables like `a = 5` or `count = 0`.
• A variable part: This changes based on the problem and how many times the algorithm repeats. For example, when an algorithm uses recursion (a function calling itself) to calculate a factorial, the amount of memory used grows with the input number `\( n \)`.

In simple words: Algorithmic complexity measures how fast an algorithm runs and how much memory it uses as the input data gets bigger. It has two types: Time Complexity (how many steps) and Space Complexity (how much memory). Memory includes fixed parts (for variables) and variable parts (for things that grow with the problem, like recursion).

🎯 Exam Tip: Clearly distinguish between Time and Space complexity. For Space Complexity, remember to mention both the "fixed part" (for variables, instructions) and the "variable part" (for dynamic data, recursion stack) to show a complete understanding.

 

Question 3. What are the factors that influence time and space complexity?
Answer: The efficiency of an algorithm, measured by its time and space complexity, is influenced by specific factors related to how it operates and the resources it uses. Time complexity focuses on the number of steps, while space complexity focuses on memory usage.
Time Complexity:
The time complexity of an algorithm is determined by counting the exact number of basic operations or steps it takes to finish its task. Each instruction executed contributes to this count, indicating how quickly the algorithm processes information to reach a solution.
Space Complexity:
The space complexity of an algorithm is the amount of memory it needs to run completely. This memory requirement is typically broken down into two components:

• Fixed part: This is the memory needed for things that do not change with the input size, such as the algorithm's instructions, simple variables, and constants. For example, if you define `x = 10`, that space is fixed.
• Variable part: This is the memory that changes depending on the size of the input and the specific operations performed. For instance, if an algorithm uses recursion to calculate a factorial, the memory used for function calls will increase as the input number grows.

In simple words: Time complexity depends on how many steps an algorithm takes to run. Space complexity depends on how much memory it uses, which has a fixed part (for basic items) and a variable part (for things that change with the input, like function calls).

🎯 Exam Tip: When discussing influencing factors, relate them directly to the definitions of time (number of steps/operations) and space (fixed vs. variable memory components) complexity. Providing simple examples helps illustrate each part.

 

Question 4. Write a note on Asymptotic notation
Answer: Asymptotic notations are special "languages" used in computer science to describe how fast an algorithm runs (time complexity) and how much memory it uses (space complexity) as the input data gets very large. They provide a simple way to talk about the behavior of an algorithm's performance.

• Asymptotic Notations are languages that use meaningful statements about time and space complexity.
• The following three asymptotic notations are mostly used to represent the time complexity of algorithms:

Big \( O \):
Big \( O \) is often used to describe the worst-case scenario for an algorithm's performance. It tells us the maximum time or space an algorithm will ever need.
Big \( \Omega \):

• Big \( \Omega \) (Omega) is like the opposite of Big \( O \). If Big \( O \) gives the upper limit (worst case), Big \( \Omega \) describes the lower limit (best-case) of an asymptotic function.
• It is used to describe the lower bound (best-case) of an algorithm's performance.

Big \( \Theta \):
When an algorithm's performance has both a lower limit and an upper limit that are the same, we use Big \( \Theta \) (Theta). For example, if an algorithm has a complexity of `\( \theta (n \log n) \)`, it means its running time will always fall within that range, both in the best-case and worst-case scenarios. This notation provides a tight bound on the algorithm's performance.
In simple words: Asymptotic notations are like special symbols that tell us how an algorithm performs as the input grows very big. Big \( O \) shows the worst it can be, Big \( \Omega \) shows the best it can be, and Big \( \Theta \) shows if it stays in a consistent range for both best and worst cases.

🎯 Exam Tip: Clearly differentiate between Big `\( O \)` (upper bound/worst-case), Big `\( \Omega \)` (lower bound/best-case), and Big `\( \Theta \)` (tight bound/average-case if upper and lower bounds are the same). Use mathematical notation correctly.

 

Question 5. What do you understand by Dynamic programming?
Answer: Dynamic programming is a powerful method for designing algorithms, especially when solving complex problems that can be broken down into smaller, overlapping sub-problems. It works by solving each sub-problem only once and storing its result. If the same sub-problem comes up again, the stored result is reused instead of recalculating it, which saves a lot of time. This approach is similar to "divide and conquer" but is specifically for problems where sub-problems are not independent and often repeat. By building up solutions from smaller parts, dynamic programming aims to find the most optimized solution.
In simple words: Dynamic programming is a way to solve big problems by breaking them into smaller parts. If those smaller parts appear again, their answers are saved and reused instead of being solved repeatedly, which makes the whole process much faster and efficient.

🎯 Exam Tip: Emphasize two key aspects: "overlapping sub-problems" and "storing and reusing results" (memoization) to efficiently solve complex problems. Mentioning its similarity to divide and conquer but addressing repeated sub-problems adds depth.

IV. Answer the Following Questions (5 Marks)

 

Question 1. Explain the characteristics of an algorithm.
Answer: An algorithm is a well-defined computational procedure that takes some value or set of values as input and produces some value or set of values as output. To be considered a good algorithm, it must possess several key characteristics:

In simple words: An algorithm must take input, give output, finish in a set time, and have clear, simple, correct steps. It should be understandable, workable with resources, and not tied to one programming language.

🎯 Exam Tip: Use a table or bullet points for clarity. Ensure you briefly explain each characteristic. Focus on the core idea for each: Input/Output (data flow), Finiteness/Definiteness/Effectiveness (well-defined process), Correctness/Simplicity/Unambiguous (quality), Feasibility/Portable/Independent (practicality).

 

Question 2. Discuss Linear search algorithm
Answer: Linear search, also known as sequential search, is a straightforward method for finding a specific value in a list or array. This method works by checking each element one by one, in order, from the beginning of the list until the desired element is found. If the element is not found by the time the entire list has been checked, then it is considered absent. One advantage of linear search is that the list does not need to be sorted before searching. However, its efficiency decreases significantly with larger lists.
Pseudocode for Linear Search:

• Start by going through each element of the array using a loop.
• In each step of the loop, compare the item you are looking for (the target search key) with the current item in the list.
• If the target item matches the current item, show its position (index) and the item's value in the array.
• If the target item does not match, move on to check the next item in the array.
• If the entire array has been checked and no match is found, then indicate that the search item was not found.

Example for Linear Search:
To search for the number 25 in the array above, a linear search will go through the elements one by one. It starts from the first element. If the element is found, its index is returned. Otherwise, the search continues until the last element of the array. In this example, the number 25 is found at index number 3.
In simple words: Linear search looks for an item in a list by checking each one from start to end until it finds it or runs out of items. The list doesn't need to be sorted.

🎯 Exam Tip: Explain that linear search is a sequential method. Mention its advantage (no need for a sorted list) and its disadvantage (inefficient for large lists). A simple pseudocode or example is helpful.

 

Question 3. What is Binary search? Discuss with example
Answer: Binary search is an efficient algorithm for finding an element within a *sorted* list or array. Unlike linear search, it does not check each element one by one. Instead, it works by repeatedly dividing the search interval in half. It first compares the target value with the middle element of the array. If they match, the search is complete. If the target value is smaller, the search continues in the lower half; if larger, it continues in the upper half. This process repeats until the element is found or the interval becomes empty. Binary search is much faster than linear search for large sorted lists, as it eliminates half of the remaining elements in each step. It can be implemented using a divide-and-conquer approach and executes in logarithmic time `\( O(\log n) \)`.
Example for Binary Search:
Let's consider an array of sorted elements: `{10, 20, 30, 40, 50, 60, 70, 80, 90, 99}`. We want to find the search element 60.

Step 1: Find the middle element. For an array from index 0 to 9, `mid = 0 + (9 - 0) / 2 = 4` (ignoring fractional part). So, the middle element is at index 4, which is 50.

Step 2: Compare the search element (60) with the mid-value (50). Since 60 is greater than 50, the search element must be in the upper half of the array. We update `low` to `mid + 1`, so `low` becomes 5. The new range is from index 5 to 9.

Step 3: Recalculate `mid` for the new range (5 to 9). `mid = 5 + (9 - 5) / 2 = 7`. The element at index 7 is 80.

Step 4: Compare 60 with 80. Since 60 is less than 80, the search element must be in the lower part of the current sub-array. We update `high` to `mid - 1`, so `high` becomes 6. The new range is from index 5 to 6.

Step 5: Recalculate `mid` for the new range (5 to 6). `mid = 5 + (6 - 5) / 2 = 5`. The element at index 5 is 60.

Step 6: Compare 60 with 60. They match! So, the search element 60 is found at location or index 5. If we had searched for an element like 95, which is not in the array, the binary search would eventually return an unsuccessful result.
In simple words: Binary search finds an item in a sorted list by repeatedly cutting the list in half. It checks the middle, then decides to look in the left half or right half, until it finds the item or realizes it's not there.

🎯 Exam Tip: Emphasize that binary search *requires* a sorted list. Clearly explain the "divide and conquer" approach and how it narrows down the search space in each step. Include an example with `low`, `high`, and `mid` values.

 

Question 4. Explain the Bubble sort algorithm with example
Answer: Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name because smaller or larger elements "bubble" to their correct position over time. While easy to understand, bubble sort is generally slow and less efficient for large lists compared to other sorting methods like insertion sort or quick sort.
Pseudocode for Bubble Sort:

• Start by comparing the first element (at index 0) with the next element in the array.
• If the current element is larger than the next element, swap their positions.
• If the current element is smaller than or equal to the next element, move to the next element without swapping.
• Repeat Step 1 and continue this comparison and swapping process until the end of the array is reached, ensuring all elements are in their correct sorted order.

Example for Bubble Sort:
Let's consider an array with values `{15, 11, 16, 12, 14, 13}`. Here’s a pictorial representation of how bubble sort works through iterations:
This shows one pass, where the largest element (16) "bubbles" to the end. The process continues with multiple such passes (iterations) until the array is fully sorted. For instance, after all iterations, the sorted array would be:

In simple words: Bubble sort works by comparing neighboring items in a list and swapping them if they are in the wrong order. It keeps doing this until the whole list is sorted, with larger items slowly moving to the end, like bubbles rising.

🎯 Exam Tip: Clearly explain the "compare and swap adjacent elements" mechanism. An example demonstrating a few steps, highlighting how elements "bubble" to their positions, is essential. Mention its simplicity but also its inefficiency for large datasets.

III. Answer The Following Questions (3 Marks)

 

Question 4. Explain the Bubble sort algorithm with example
Answer: Bubble sort is a straightforward sorting algorithm. It works by repeatedly moving through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process continues until no more swaps are needed, which means the list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list. While simple to understand, bubble sort is generally slower and less efficient compared to other sorting methods like insertion sort. We can assume a list of 'n' elements, where a swap function exchanges the values of array elements.
Pseudocode:

• Start with the first element (index = 0) and compare it with the next element in the array.
• If the current element is larger than the next element, swap their positions.
• If the current element is smaller than the next element (or on its right side), move to consider the next element.
• Go back to the first step and keep repeating this process until the end of the array's index is reached, ensuring all elements have been compared and moved if necessary.

Let's consider an array with values: {15, 11, 16, 12, 14, 13}. Here's how bubble sort would process it in one pass:

• Compare 15 and 11: 15 > 11, so swap them. Array becomes: {11, 15, 16, 12, 14, 13}
• Compare 15 and 16: 15 < 16, no swap. Array remains: {11, 15, 16, 12, 14, 13}
• Compare 16 and 12: 16 > 12, so swap them. Array becomes: {11, 15, 12, 16, 14, 13}
• Compare 16 and 14: 16 > 14, so swap them. Array becomes: {11, 15, 12, 14, 16, 13}
• Compare 16 and 13: 16 > 13, so swap them. Array becomes: {11, 15, 12, 14, 13, 16}

After several such passes, the array will eventually be sorted. The final sorted array will be: {11, 12, 13, 14, 15, 16}. This method is easy to implement but not ideal for very large lists.
In simple words: Bubble sort compares items next to each other and swaps them if they are in the wrong order. It keeps doing this until the whole list is sorted, like bubbles rising to the top. It's easy to understand but can be slow for many items.

🎯 Exam Tip: Remember the two main steps: comparing adjacent elements and swapping them if needed. Emphasize that it continues until no more swaps are required, signaling a sorted list.

 

Question 5. Explain the concept of dynamic programming with a suitable example.
Answer: Dynamic programming is a method for designing algorithms, useful when a problem's solution can be seen as a series of choices. It works by breaking down a large problem into smaller, overlapping sub-problems. The key idea is to store the results of these sub-problems so they can be reused later, instead of recalculating them. This approach is similar to "divide and conquer" but differs because it reuses solutions for overlapping parts. It helps to find an optimized solution by combining the results of these solved sub-problems.
Steps to do Dynamic programming:

1. The main problem is divided into smaller, overlapping sub-problems.
2. An optimal solution for the big problem can be found by using the results from solving the smaller sub-problems.
3. Dynamic programming algorithms often use a technique called Memoization to store and reuse these results.

Fibonacci Series - An example: The Fibonacci series generates the next number by adding the two previous numbers. It starts with two numbers, usually Fib 0 and Fib 1, set to 0 and 1. The series follows the condition: \( Fib_n = Fib_{n-1} + Fib_{n-2} \).
For example, if we want to find the 8th Fibonacci number, the series would look like this: \( Fib_8 = 0, 1, 1, 2, 3, 5, 8, 13 \). Each number is the sum of the two before it. This iterative approach effectively demonstrates how dynamic programming avoids recomputing values.
In simple words: Dynamic programming solves big problems by breaking them into smaller parts. It remembers the answers to these small parts so it doesn't have to solve them again, which makes it much faster. The Fibonacci sequence is a good example, where each new number is found by adding the two numbers before it, using past results.

🎯 Exam Tip: When explaining dynamic programming, emphasize the "overlapping sub-problems" and "memoization" aspects, as these are its defining characteristics. The Fibonacci sequence is a classic, easy-to-understand example.

12th Computer Science Guide Algorithmic Questions And Answers

Choose The Best Answer: (1 Marks)

 

Question 1. Which one of the following is not a data structure?
(a) Array
(b) Structures
(c) List, tuples
(d) Database
Answer: (d) Database
In simple words: An array, structure, list, or tuple is a way to organize data in computer programs. A database, however, is a separate system used to store and manage a large amount of information, not just a data structure within a program.

🎯 Exam Tip: Understand that data structures are internal ways to organize data in memory for efficient processing, while a database is an external system for persistent storage and retrieval of data.

 

Question 2. Linear search is also called
(a) Quick search
(b) Sequential search
(c) Binary search
(d) Selection search
Answer: (b) Sequential search
In simple words: Linear search checks each item in a list one by one, from start to finish, until it finds what it's looking for. Because it goes in order, it's also known as a sequential search.

🎯 Exam Tip: Remember that "linear" implies a step-by-step, ordered scan, which is why "sequential search" is an accurate synonym.

 

Question 3. Which is a wrong fact about the algorithm?
(a) It should be feasible
(b) Easy to implement
(c) It should be independent of any programming languages
(d) It should be generic
Answer: (c) It should be independent of any programming languages
In simple words: An algorithm is a general plan to solve a problem, which means it should work no matter which programming language you use. Its design doesn't depend on the specific language.

🎯 Exam Tip: Algorithms are high-level, language-agnostic blueprints. While implemented in languages, their core logic is independent of them, making option (c) a misleading statement if interpreted as "the algorithm itself changes based on language."

 

Question 4. Which search algorithm can be done as divide and- conquer search algorithm?
(a) linear
(b) Binary search
(c) Sequential
(d) Bubble
Answer: (b) Binary search
In simple words: Binary search works by repeatedly splitting the list in half. This "divide and conquer" approach helps it find items much faster than searching one by one.

🎯 Exam Tip: Identify algorithms that split problems into smaller sub-problems as "divide and conquer." Binary search is a prime example because it repeatedly halves the search space.

 

Question 5. Which of the following sorting algorithm is too slow and less efficient?
(a) Selection
(b) Bubble
(c) Quick
(d) Merge
Answer: (b) Bubble
In simple words: Among common sorting methods, bubble sort is known to be quite slow and not very good for large lists. It often takes many steps to get the list sorted.

🎯 Exam Tip: Remember that bubble sort, while simple to understand, is generally considered inefficient for large datasets due to its high number of comparisons and swaps in the worst case.

 

Question 6. Which of the following programming is used whenever problems can be divided into similar sub-problems?
(a) Object-oriented
(b) Dynamic
(c) Modular
(d) Procedural
Answer: (b) Dynamic
In simple words: Dynamic programming is a method that solves complex problems by breaking them into smaller, easier-to-solve sub-problems. It then combines the solutions of these smaller parts to find the main answer.

🎯 Exam Tip: The key phrase here is "divided into similar sub-problems" - this points directly to dynamic programming's core principle of optimizing solutions by reusing computations for overlapping sub-problems.

 

Question 7. Which of the following is the reverse of Big O?
(a) Big \( \mu\mu \)
(b) Big \( \Omega \)
(c) Big symbol
(d) Big \( \Omega\Omega \)
Answer: (b) Big \( \Omega \)
In simple words: In computer science, Big O shows the worst possible time an algorithm might take. Big Omega, which is like its opposite, shows the best possible time an algorithm could take.

🎯 Exam Tip: Understand Big O as an upper bound (worst-case scenario) and Big Omega (\( \Omega \)) as a lower bound (best-case scenario) for an algorithm's running time.

 

Question 8. How many different phases are there in the analysis of algorithms and performance evaluations?
(a) 1
(b) 2
(c) 3
(d) Many
Answer: (b) 2
In simple words: When we look at how well an algorithm works, we usually think about two main steps. These two steps help us to truly understand its performance.

🎯 Exam Tip: The two phases are 'a priori estimates' (theoretical analysis) and 'a posteriori testing' (empirical analysis), which evaluate performance before and after implementation, respectively.

 

Question 9. Which of the following is a finite set of instructions to accomplish a particular task?
(a) Flowchart
(b) Algorithm
(c) Functions
(d) Abstraction
Answer: (b) Algorithm
In simple words: An algorithm is like a recipe; it's a clear, step-by-step set of instructions that you follow to solve a specific problem or complete a task.

🎯 Exam Tip: The core definition of an algorithm centers on it being a finite, well-defined sequence of steps to solve a problem. Avoid confusing it with visual representations (flowcharts) or code structures (functions).

 

Question 10. The way of defining an algorithm is called
(a) Pseudo strategy
(b) Programmatic strategy
(c) Data structured strategy
(d) Algorithmic strategy
Answer: (d) Algorithmic strategy
In simple words: The entire method or plan used to design and define an algorithm to solve a problem is referred to as an algorithmic strategy. This plan is crucial before writing any actual code.

🎯 Exam Tip: An "algorithmic strategy" refers to the high-level thought process and design patterns used to develop an algorithm, distinguishing it from specific code or data structures.

 

Question 11. Time is measured by counting the number of key operations like comparisons in the sorting algorithm. This is called as ___________.
(a) Space Factor
(b) Key Factor
(c) Priori Factor
(d) Time Factor
Answer: (d) Time Factor
In simple words: When we measure how fast a sorting algorithm works by counting how many main steps, like comparisons, it does, we are looking at its time factor. This helps us understand its speed.

🎯 Exam Tip: The "time factor" specifically relates to the operational count (e.g., comparisons, swaps) which dictates an algorithm's efficiency, in contrast to "space factor" which concerns memory usage.

 

Question 12. Efficiency of an algorithm decided by
(a) Definiteness, portability
(b) Time, Space
(c) Priori, Postriori
(d) Input/output
Answer: (b) Time, Space
In simple words: How good an algorithm is depends on two main things: how fast it runs (time) and how much memory it uses (space). These are the most important measures of its efficiency.

🎯 Exam Tip: Always associate algorithm efficiency with its time complexity (how fast it runs) and space complexity (how much memory it uses), as these are the primary evaluation metrics.

 

Question 13. Which of the following should be written for the selected programming language with specific syntax?
(a) Algorithm
(b) Pseudocode
(c) Program
(d) Process
Answer: (c) Program
In simple words: A program is the actual set of instructions written in a specific programming language. It follows that language's rules and structure, unlike a general algorithm or pseudocode.

🎯 Exam Tip: Distinguish between an algorithm (a general solution idea), pseudocode (a language-independent description), and a program (the algorithm coded in a specific language with its strict syntax).

 

Question 14. How many components required to find the space required by an algorithm?
(a) 4
(b) 3
(c) 2
(d) 6
Answer: (c) 2
In simple words: To figure out how much memory an algorithm needs, we consider two main parts that make up its total space usage. These parts help us understand its memory footprint.

🎯 Exam Tip: Remember the two components of space complexity: the fixed part (for variables, constants) and the variable part (which depends on input size and recursion depth).

 

Question 15. Which of the following component is defined as the total space required to store certain data and variables for an algorithm?
(a) Time part
(b) Variable part
(c) Memory part
(d) Fixed part
Answer: (d) Fixed part
In simple words: The "fixed part" of an algorithm's memory use is the space it needs for things that don't change, like its main variables and constants. This amount of memory stays the same no matter how big the input is.

🎯 Exam Tip: The fixed part of space complexity is distinct because it remains constant regardless of the input size, contrasting with the variable part that scales with input or recursion.

 

Question 16. Which is true related to the efficiency of an algorithm?
(I) Less time, more storage space
(II) More time, very little space
(a) I is correct
(b) II is correct
(c) Both are correct
(d) Both are wrong
Answer: (c) Both are correct
In simple words: An algorithm can be efficient in different ways. Some algorithms might run very fast but need a lot of memory, while others might use very little memory but take more time to run. Both situations can be considered "efficient" depending on what is needed.

🎯 Exam Tip: Efficiency is a trade-off. Algorithms are often designed to prioritize either time or space. A good algorithm balances these two based on problem constraints, making both scenarios valid depending on context.

 

Question 17. Time and Space complexity could be considered for an
(a) Algorithmic strategy
(b) Algorithmic analysis
(c) Algorithmic efficiency
(d) Algorithmic solution
Answer: (b) Algorithmic analysis
In simple words: When we study an algorithm to see how fast it runs and how much memory it uses, we are doing an "algorithmic analysis." This helps us understand its performance.

🎯 Exam Tip: Time and space complexity are the fundamental metrics used in "algorithmic analysis" to predict and measure the performance of algorithms. These are not just aspects of efficiency but tools for deep analysis.

 

Question 18. Which one of the following is not an Asymptotic notation?
(a) Big O
(b) Big \( \Theta \)
(c) Big \( \Omega \)
(d) Big \( \otimes \)
Answer: (d) Big \( \otimes \)
In simple words: In computer science, Big O, Big Theta, and Big Omega are special symbols used to describe how fast or slow an algorithm will run. The symbol Big X (otimes) is not a standard asymptotic notation used for this purpose.

🎯 Exam Tip: Familiarize yourself with the three primary asymptotic notations: Big O (upper bound), Big Omega (\( \Omega \)) (lower bound), and Big Theta (\( \Theta \)) (tight bound), as they are critical for complexity analysis.

 

Question 19. How many asymptotic notations are mostly used to represent time complexity of algorithms?
(a) Two
(b) Three
(c) One
(d) Many
Answer: (b) Three
In simple words: There are three main types of special symbols we use to talk about how fast an algorithm works. These three symbols give us a clear way to measure its time performance.

🎯 Exam Tip: The three main asymptotic notations are Big O, Big Omega, and Big Theta, each describing different bounds (worst-case, best-case, average-case respectively) of an algorithm's performance.

II. Answer The Following Questions (2 And 3 Marks)

 

Question 1. Define fixed part in the space complexity?
Answer: The fixed part in space complexity refers to the portion of total memory an algorithm needs for its basic operations. This includes space for certain data and variables like simple variables, constants, and instruction space. This amount of memory does not change regardless of the size of the input data. For example, if you declare an integer variable `x`, it will always take the same amount of memory.
In simple words: The fixed part of memory is the basic space an algorithm always needs for things like its constant values and regular variables, which stays the same no matter how much data it processes.

🎯 Exam Tip: Highlight that the 'fixed part' is independent of the input size, consisting of elements like constants, simple variables, and the code itself, distinguishing it from the variable part of space complexity.

 

Question 2. Write a pseudo code for linear search
Answer: Linear search, also known as sequential search, is a method to find a specific item in a list. Here is a pseudocode that explains its steps:

• Use a 'for loop' to go through each item in the array.
• In each loop, compare the target item you are searching for with the current item in the list.
• If the items match, show the current position (index) and the value from the array.
• If the items do not match, move to the next item in the array.
• If the loop finishes and no match is found, state that the search item was not found.

This method always checks elements one by one until the item is located or the entire list has been checked.
In simple words: To do a linear search, you look at each item in a list one by one. If you find what you're looking for, you stop. If you reach the end of the list and haven't found it, then it's not there.

🎯 Exam Tip: Ensure your pseudocode clearly shows the loop, comparison, and the two possible outcomes (found or not found). Emphasize the sequential nature of the comparison.

 

Question 3. Design an algorithm to find the square of the given number and display the result. The algorithm can be written as:
Answer: To design an algorithm for finding the square of a given number and displaying the result, we can follow these steps:

1. Start the process.
2. Get the input number, let's call it 'x'.
3. Calculate the square by multiplying 'x' by itself (e.g., square \( \leftarrow x * x \)).
4. Display the calculated square as the result.
5. Stop the process.

This simple algorithm effectively transforms a single input into its squared value, illustrating fundamental computational steps.
In simple words: This algorithm is a set of steps to find the square of any number. First, you start, then you take a number, multiply it by itself, and show the answer, then you stop.

🎯 Exam Tip: When writing algorithms, always include clear start and stop points, and specify input, processing, and output steps. Use simple, unambiguous language for each step.

 

Question 4. Write a pseudo code for bubble sort
Answer: Here is a pseudocode for the bubble sort algorithm:

• Begin by looking at the first element (at index 0). Compare this element with the very next element in the array.
• If the current element is larger than the next element, swap their positions.
• If the current element is smaller than the next element (or on its right side), move to consider the next element.
• Go back to the first step and keep repeating this process until the end of the array's index is reached, ensuring all elements have been compared and moved if necessary.

This repetitive comparison and swapping ensures that the largest elements gradually "bubble" to their correct positions at the end of the list.
In simple words: To bubble sort, you start at the beginning of a list and compare each number to the one next to it. If they are in the wrong order, you swap them. You keep doing this until all numbers are sorted.

🎯 Exam Tip: Pseudocode for sorting algorithms should clearly show the comparison logic and the swapping mechanism. Emphasize the iterative nature of bubble sort.

 

Question 5. Write a pseudo code for selection sort.
Answer: Here is a pseudocode for the selection sort algorithm:

• Start from the first element (index = 0). Search through the entire array to find the smallest element. Once found, swap this smallest element with the element currently at the first position.
• Next, move to the second element's position (index = 1). Now, search for the smallest element within the remaining unsorted part of the array (from the second index to the last index).
• Then, replace the second smallest element found in the previous step with the element at the second position in the array. This is also called placing it in the first position of the remaining sub-array.

This process of repeatedly finding the minimum element from the unsorted part and putting it at the beginning of the unsorted section is the core of selection sort.
In simple words: For selection sort, you find the smallest item in the whole list and put it at the very start. Then, you find the next smallest item in the remaining list and put it next. You repeat this until everything is in order.

🎯 Exam Tip: The key idea of selection sort is to find the minimum element in the unsorted portion and place it at the correct sorted position. Clearly define the "unsorted sub-array" in your explanation.

 

Question 6. Write a note on Big omega asymptotic notation
Answer: Big Omega (\( \Omega \)) is an asymptotic notation used to describe the lower bound of an algorithm's running time. Essentially, it provides a best-case scenario or the minimum time an algorithm will take to complete.

• Big Omega is the opposite of Big O. While Big O describes the upper bound (worst-case), Big Omega describes the lower bound (best-case) for an asymptotic function.
• It tells us that an algorithm will take *at least* a certain amount of time, no matter what.

For example, if an algorithm has a Big Omega of \( \Omega(n) \), it means that its running time will be at least proportional to 'n' for large inputs.
In simple words: Big Omega is a way to say how fast an algorithm will run at its quickest. It describes the "best-case" time, meaning the algorithm will never run faster than this speed.

🎯 Exam Tip: Clearly differentiate Big Omega (\( \Omega \)) as the lower bound (best-case) from Big O (upper bound/worst-case). This distinction is crucial for understanding algorithm performance guarantees.

 

Question 7. Name the factors where the program execution time depends on?
Answer: The time a program takes to run (execution time) depends on several factors:

1. **Speed of the machine:** A faster processor and overall computer hardware will execute instructions more quickly.
2. **Compiler and other system software tools:** The efficiency of the compiler and other tools used to translate and run the code can impact performance.
3. **Operating System:** The operating system manages resources, and its efficiency can affect how quickly a program runs.
4. **Programming language used:** Different languages have different execution overheads; compiled languages are often faster than interpreted ones.
5. **The volume of data required:** Processing more data usually takes more time.

These factors collectively determine the actual real-world performance of an algorithm.
In simple words: How fast a program runs depends on things like how quick the computer is, how good the software that runs it is, and how much information the program needs to process. All these parts work together to decide its speed.

🎯 Exam Tip: When listing factors affecting execution time, ensure you include both hardware (machine speed) and software aspects (compiler, OS, language, data size) for a comprehensive answer.

 

Question 8. Write a note on memoization.
Answer: Memoization is an optimization technique used in computer programming to speed up functions or algorithms. It works by storing the results of expensive function calls and then returning the cached (saved) result when the same inputs occur again. This prevents the function from recalculating the result multiple times for identical inputs. It's especially useful for algorithms that have overlapping sub-problems, a key characteristic of dynamic programming.
In simple words: Memoization is a clever trick where a computer program remembers the answers to calculations it has already done. If it needs the same answer again, it just looks it up instead of doing the math all over, making it much faster.

🎯 Exam Tip: The core concept of memoization is "storing results for future reuse." Link it directly to dynamic programming and the idea of avoiding redundant computations for identical inputs.

 

Question 9. Give examples of data structures.
Answer: Data structures are specialized formats for organizing, processing, retrieving, and storing data. They are crucial for writing efficient programs.
Examples of common data structures include:

• **Arrays:** A collection of items stored at contiguous memory locations.
• **Structures:** User-defined data types that allow grouping different types of data under a single name.
• **Lists:** Ordered sequences of elements, which can be modified.
• **Tuples:** Ordered, immutable sequences of elements, meaning they cannot be changed after creation.
• **Dictionary (or Map/Hash Table):** A collection of key-value pairs, where each key is unique and maps to a specific value.

These examples represent various ways data can be logically organized and accessed within a program.
In simple words: Data structures are different ways to organize information inside a computer program. Some examples are arrays (like a numbered list), structures (like a record card with different details), lists, tuples, and dictionaries (like a phone book where you look up a name to find a number).

🎯 Exam Tip: For each example, briefly explain its main characteristic (e.g., arrays for ordered collection, dictionaries for key-value pairs) to show a deeper understanding beyond just listing names.

 

Question 10. Define- Algorithmic Strategy?
Answer: An Algorithmic Strategy refers to the general approach or method used when defining and designing an algorithm. It outlines the overall plan or blueprint for how a problem will be solved computationally, guiding the selection of techniques like divide and conquer, dynamic programming, or greedy methods. This strategy is decided before the detailed steps of the algorithm are written.
In simple words: An algorithmic strategy is the overall plan or method you choose to solve a problem with an algorithm. It's like deciding what kind of map to use before you start driving.

🎯 Exam Tip: Emphasize that an algorithmic strategy is a high-level design choice, dictating the fundamental approach to problem-solving, rather than the detailed step-by-step instructions of the algorithm itself.

 

Question 11. Define algorithmic solution?
Answer: An algorithmic solution is a specific algorithm that, when given valid input, consistently produces the expected and correct output. It represents a complete and effective set of instructions designed to solve a particular problem, delivering accurate results for all appropriate inputs. It's the practical application of an algorithmic strategy to yield a working solution.
In simple words: An algorithmic solution is a working set of instructions (an algorithm) that correctly solves a problem. When you give it the right information, it always gives you the right answer.

🎯 Exam Tip: An algorithmic solution must be both correct (produces expected output for valid input) and effective (solves the problem) - highlight these two aspects in your definition.

 

Question 12. Define- Algorithm Analysis?
Answer: Algorithm analysis is the process of examining an algorithm to estimate its time and space complexities. This means determining how much time the algorithm will take to run and how much memory it will require, especially as the size of the input data changes. This analysis helps to predict and understand an algorithm's performance without needing to actually run it.
In simple words: Algorithm analysis is like checking how good a recipe is before cooking. We figure out how fast an algorithm will work and how much computer memory it will use, especially with different amounts of data.

🎯 Exam Tip: Focus on the two primary metrics of algorithm analysis: time complexity (how runtime scales with input) and space complexity (how memory usage scales with input).

 

Question 13. What are the different phases in the analysis of algorithms and performance?
Answer: The analysis of algorithms and their performance evaluation typically involves two main phases:

1. **A Priori Estimates:** This is a theoretical performance analysis of an algorithm. It involves evaluating the algorithm's efficiency based on assumptions about external factors, without actually running it. This phase predicts how the algorithm will behave using mathematical tools and reasoning.
2. **Posteriori Testing:** This is the practical performance measurement phase. It involves running the algorithm on real data and collecting actual statistics, such as the running time and memory usage required for the algorithm's execution.

Both phases are important for a complete understanding of an algorithm's performance.
In simple words: When we study how well algorithms work, there are two main steps. First, we guess how fast and efficient it will be just by looking at its design (a priori). Second, we actually run it and measure how fast it really is (posteriori).

🎯 Exam Tip: Clearly define 'a priori' as theoretical analysis (pre-implementation) and 'a posteriori' as empirical testing (post-implementation), explaining what each phase aims to measure.

 

Question 14. Define the Best algorithm?
Answer: The "best" algorithm to solve a given problem is generally defined as the one that is most efficient in terms of resources. This means it requires the least amount of space in memory (space complexity) and takes the minimum amount of time to execute its instructions and generate the desired output (time complexity). The optimal choice often involves balancing these two factors based on specific problem constraints.
In simple words: The best algorithm is the one that solves a problem using the least amount of computer memory and takes the shortest amount of time to finish. It's about being very efficient.

🎯 Exam Tip: When defining the "best" algorithm, always connect it to optimizing both time complexity and space complexity. Emphasize that these two factors are often in a trade-off relationship.

 

Question 15. Write a note Asymptotic Notations?
Answer: Asymptotic notations are special mathematical languages or tools used in computer science to describe the running time and space requirements of algorithms, especially as the input size grows very large. They provide a way to express the efficiency of an algorithm by focusing on its growth rate.
The three most common asymptotic notations are:

• **Big O notation (\( O \)):** Describes the upper bound or worst-case complexity.
• **Big Omega notation (\( \Omega \)):** Describes the lower bound or best-case complexity.
• **Big Theta notation (\( \Theta \)):** Describes the tight bound or average-case complexity.

These notations allow algorithm designers to compare the efficiency of different algorithms in a standardized way.
In simple words: Asymptotic notations are like special symbols (like Big O, Big Omega, Big Theta) that help us talk about how fast an algorithm works or how much memory it needs, especially when it deals with a lot of data. They show us how its performance "grows."

🎯 Exam Tip: Clearly define asymptotic notations as tools for analyzing algorithm efficiency in relation to input size, and briefly explain what each of the three main notations (O, \( \Omega \), \( \Theta \)) represents.

III. Answer The Following Questions (5 Marks)

 

Question 1. Differentiate Algorithm and program
Answer: Here is a comparison between an algorithm and a program:

This table highlights that an algorithm is a high-level logical plan, while a program is its concrete, language-specific realization.
In simple words: An algorithm is like a general recipe or a step-by-step plan to solve a problem. A program is the actual computer code written in a specific language (like Python or Java) that brings that recipe to life and makes the computer follow the steps.

🎯 Exam Tip: Clearly state that an algorithm is an abstract, language-independent logic, while a program is its concrete, language-specific implementation. Focus on the 'how-to' versus 'the actual doing' distinction.

 

Question 1. Differentiate Algorithm and program
Answer:

In simple words: An algorithm is a logical step-by-step plan to solve a problem, like a recipe. A program is that recipe written down using a specific computer language that a computer can understand and run.

🎯 Exam Tip: Remember that an algorithm is the idea or logic, while a program is the practical implementation of that idea using a coding language.