Module 1
2mks
Q.1. Why Data Structure is Important and discuss its classification.
Ans. Data Structures Help Create Robust, Efficient, Maintainable Software Systems —
Integral To An Organization’s Performance.
They Are The Foundation For Various Algorithms And Processing Techniques.
Q.2. Discuss the Advantage and Disadvantage of Data Structure.
Ans.
Disadvantage: -
Some of the data structures are complex to handle for a new programmer.
Some of the data structures provide slower access to data due to the complex structure.
Advantage: -
Efficiency: Efficiency of a program depends upon the choice of data structures.
Reusability: Data structures are reusable, i.e., once we have implemented a particular data
structure, we can use it at any other place.
Abstraction: Data structure is specified by the ADT which provides a level of abstraction.
The client program uses the data structure through interface only, without getting into the
implementation details.
Q.3. What is Space complexity? Also Discuss its types.
Q.4. Discuss the type of Time complexity.
Q.5. What is Time complexity?
Q.6. Compare Time and Space complexity in brief.
Ans.
Types of Space Complexity:
Constant Space (O(1)): The algorithm uses a fixed amount of memory space regardless of
the input size. For example, an algorithm that swaps two numbers.
Linear Space (O(n)): The memory required grows linearly with the input size. An example is
creating a list of 'n' elements.
Quadratic Space (O(n²)): The space requirement grows quadratically with the input size,
commonly seen in algorithms that create two-dimensional arrays based on the input size.
Types of Time Complexity:
Constant Time (O(1)): The execution time remains constant regardless of the input size.
Linear Time (O(n)): The execution time increases linearly with the input size. For instance,
finding an item in an unsorted list.
Quadratic Time (O(n²)): The time increases quadratically with the input size. This is common
in algorithms with nested loops over the input data.
Q.7. Similarities Between Time Complexity and Space Complexity.
Ans.
Q.8. Discuss the Different types of asymptotic notations with
graphs
Ans. Mainly there are three different types of asymptotic notations:
• Big O Notation
• Omega Notation
• Theta Notation
Big-O Notation (O): Big O notation is a mathematical concept used in computer science to
describe the upper bound of an algorithm's time or space complexity. It provides a way to
express the worst-case scenario of how an algorithm performs as the size of the input
increases.
Omega Notation(Ω): Omega notation is used to denote the lower bound of the algorithm; it
represents the minimum running time of an algorithm. Therefore, it provides the best-case
complexity of any algorithm.
Theta Notation(θ): Theta notation is used to denote the average bound of the algorithm; it
bounds a function from above and below, that’s why it is used to represent exact
asymptotic behaviour.
Q.9. Explain what is algorithm and why we need to do algorithm.
Ans. An algorithm is a process or a set of rules required to perform calculations or some
other problem-solving operations especially by a computer.
We need algorithms because of the following reasons:
● Scalability: It helps us to understand the scalability. When we have a big real-world
problem, we need to scale it down into small-small steps to easily analyze the problem.
● Performance: The real-world is not easily broken down into smaller steps. If the
problem can be easily broken into smaller steps means that the problem is feasible.
Q.10. Find upper bound, lower bound and tight bound for the
following function f(n)= 3n+5.
Q.11. Find upper bound, lower bound and tight bound for the
following function f(n)= 2n+2.
Module-2
Q.1. Compare B tree and B+ tree.
Ans.
Module-3
Q.1.Whatis Divide and Conquer? Explain the Characteristics.
Ans. 1) Divide and Conquer Algorithm involves breaking a larger problem into smaller
subproblems, solving them independently, and then combining their solutions to solve the
original problem.
2) The basic idea is to recursively divide the problem into smaller subproblems until they
become simple enough to be solved directly.
3) Once the solutions to the subproblems are obtained, they are then combined to produce
the overall solution.
Characteristics of Divide and Conquer Algorithm:
Dividing the Problem: The first step is to break the problem into smaller, more manageable
subproblems. This division can be done recursively until the subproblems become simple
enough to solve directly.
Independence of Subproblems: Each subproblem should be independent of the others,
meaning that solving one subproblem does not depend on the solution of another. This
allows for parallel processing or concurrent execution of subproblems, which can lead to
efficiency gains.
Conquering Each Subproblem: Once divided, the subproblems are solved individually. This
may involve applying the same divide and conquer approach recursively until the
subproblems become simple enough to solve directly, or it may involve applying a different
algorithm or technique.
Combining Solutions: After solving the subproblems, their solutions are combined to obtain
the solution to the original problem. This combination step should be relatively efficient and
straightforward, as the solutions to the subproblems should be designed to fit together
seamlessly.
Q.2. Discuss the Advantages and Disadvantages of Divide and
Conquer.
Ans.
Advantages of Divide and Conquer:
1) It efficiently uses cache memory without occupying much space because it solves simple
subproblems within the cache memory instead of accessing the slower main memory.
2) It is more proficient than that of its counterpart Brute Force technique.
3) Since these algorithms inhibit parallelism, it does not involve any modification and is
handled by systems incorporating parallel processing.
Disadvantages of Divide and Conquer:
1) Since most of its algorithms are designed by incorporating recursion, so it necessitates
high memory management.
2) An explicit stack may overuse the space.
3) It may even crash the system if the recursion is performed rigorously greater than the
stack present in the CPU.
