Chapter 1: Introduction to Data Structures and Algorithm Analysis

 

 One Marks Questions

1. Define Data structure. (MAR-19)

Answer: "A data structure is a way of organizing data that considers not only the items stored, but also their relationship to each other." Data Structure can be defined as the group of data elements which provides an efficient way of storing and organizing data in the computer so that it can be used efficiently. 

Some examples of Data Structures are arrays, Linked List, Stack, Queue, etc.

2. Which notation is used to denote lower bound? (MAR-19)

Answer:  The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete. In simple words, when we represent a time complexity for any algorithm in the form of big-Ω, we mean that the algorithm will take at least this much time to complete it's execution. It can definitely take more time than this too.

 3. What are advantages of ADT? (MAR-19)(MAR-18)(APR-17)(APR-17)

Answer: Abstract data types having several advantages:

• Representation Independence: Most of the program becomes independent of the abstract data type's representation, so that representation can be improved without breaking the entire program.
• Modularity: With representation independence, the different parts of a program become less dependent on other parts and on how those other parts are implemented.
• Interchangeability of Parts: Implementations of ADTs can be changed without requiring changes to the program that uses the ADTs. 
• ADTs can be reused in future programs.

4. What is ADT? (OCT-18) (MAR-18) (OCT-17)

Answer: An abstract data type is defined as a mathematical model of the data objects that make up a data type as well as the functions that operate on these objects. A set of data values and associated operations that are precisely specified independent of any particular implementation.

An abstract data type includes:

• Declaration of data.
• A structure defined by a set of rules that put components together.
• A set of operations and encapsulation of data.

A data structure is an actual implementation of a particular abstract data type.

Example: The abstract data type Set has the operations EmptySet(S), Insert(x,S), Delete(x,S), Intersection(S1,S2), Union(S1,S2), Member(x,S), Equal(S1,S2), Subset(S1,S2).

5. Define the term Omega Notation (Ω) (OCT-18) (MAR-18)

Answer: Big - Omega Notation can be defined as, Consider function f(n) as time complexity of an algorithm and g(n) is the most significant term. If f(n) >= C g(n) for all n >= n₀, C > 0 and n₀ >= 1. Then we can represent f(n) as Ω(g(n)).

f(n) = Ω(g(n))

Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on X-Axis and time required is on Y-Axis

In above graph after a particular input value n₀, always C g(n) is less than f(n) which indicates the algorithm's lower bound.

Big - Omega notation is used to define the lower bound of an algorithm in terms of Time Complexity. That means Big-Omega notation always indicates the minimum time required by an algorithm for all input values which describes the best case of an algorithm time complexity.

6. Define theta (Ɵ) notation? (OCT-17)

Answer: The notation θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm's running time.

That means Big - Theta notation always indicates the average time required by an algorithm for all input values. That means Big - Theta notation describes the average case of an algorithm time complexity.

It is represented as follows −
θ(f(n)) = {g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0.} 

7. What are different asymptotic notations?(APR-17)

Answer: When we calculate complexity of an algorithm it does not provide exact amount of resource required. So instead of taking exact amount of resource we represent that complexity in a general form (Notation) which produces the basic nature of that algorithm.

"Asymptotic notation of an algorithm is a mathematical representation of its complexity."

Following are the commonly used asymptotic notations:

➢ Ο Notation
➢ Ω Notation
➢ θ Notation

8. What are the component of space complexity?(APR-17)

Answer: The space complexity of a program is the amount of memory it needs to run to completion. The space need by a program has the following components:

• Instruction space: Instruction space is the space needed to store the compiled version of the program instructions.The amount of instructions space that is needed depends on factors such as:
  
  1. The compiler used to complete the program into machine code.
  2. The compiler options in effect at the time of compilation
  3. The target computer.

• Data space: Data space is the space needed to store all constant and variable values. Data space has two components:

1. Space needed by constants and simple variables in program. 
2. Space needed by dynamically allocated objects such as arrays and class instances.

• Environment stack space: The environment stack is used to save information needed to resume execution of partially completed functions.