MAKAUT 5TH SEM CSE

OBJECT ORIENTED PROGRAMMING

FREE NOTES
[share with your friends]

DEBKANTA MAITY

8372021415

[ join in our community]

 UNIT-1

Abstract data types and their speci cation. How to implement an ADT. Concrete state space,
concrete invariant, abstraction function. Implementing operations, illustrated by the Text example.

DEBKANTA MAITY
fi
 Introduction to Object-Oriented Programming
SAQ - 1mark
1.What is an Abstract Data Type (ADT)?
→ An ADT is a logical model of a data structure de ned by its behavior (operations), not by its implementation.
2.Give two examples of ADTs.
→ Stack and Queue.
3.How is an ADT different from a data structure?
→ ADT de nes what operations are to be performed, while a data structure de nes how they are implemented.
4.Why are ADTs important in software DEBKANTA
engineering? MAITY
→ They improve modularity, reusability, and abstraction in program design.
5.What are the main components of an ADT speci cation?
→ Data type name, operations (with signatures), pre-conditions, and post-conditions.
6.What does the speci cation of an ADT include?
→ It includes the name, operations, their signatures, pre-conditions, and post-conditions.
7.De ne the term: Interface of an ADT.
→ The interface is the set of operations available to users of the ADT.
8.What is meant by ADT operation signatures?
→ It de nes the operation name, input parameters, and return type.
9.List any three operations typically de ned in a Stack ADT.
→ push(), pop(), isEmpty().
10.How is pre-condition different from post-condition in ADT speci cation?
→ Pre-condition speci es what must be true before an operation; post-condition speci es what is true after it.
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
11.How is an ADT implemented in a programming language?
→ By using data structures and functions/methods that ful ll its de ned operations.
12.What is meant by the concrete state space of an ADT?
→ It is the actual data representation used in the implementation.
13.De ne concrete invariant with an example.
→ A rule that must always hold for the data, e.g., in a stack, top ≥ -1.
14.What is an abstraction function in ADT implementation?
→ It maps the concrete state to its abstract representation.
DEBKANTA MAITY
15.Explain the relationship between abstract state and concrete state.
→ The abstract state de nes behavior; the concrete state is its implementation, linked via the abstraction
function.
16.What is the purpose of a concrete invariant?
→ To ensure the internal data remains valid throughout execution.
17.How do concrete invariants help in ensuring data consistency?
→ They enforce rules that prevent invalid or inconsistent states.
18.Give an example of a concrete invariant in a Queue implementation.
→ front ≤ rear and both within array bounds.
19.What is a representation invariant?
→ A condition that must always be true for the internal data of an ADT.
20.Differentiate between abstraction function and representation invariant.
→ Abstraction function maps concrete state to abstract state; representation invariant ensures validity
of the concrete state.
fi
fi
fi
fi
21.De ne abstraction function with an example.
→ It maps a concrete state to its abstract meaning.
Example: Maps array [a, b, c] with top = 2 to stack ⟨a, b, c⟩.
22.How does an abstraction function relate the abstract and concrete representations?
→ It translates the internal (concrete) data into its external (abstract) view.
23.Give the abstraction function for a Stack implemented using an array.
→ Stack = ⟨array[0], array[1], ..., array[top]⟩.
24.What are the steps to implement ADT operations?
→ De ne the data structure, ensure invariants, write functions for each operation.
DEBKANTA MAITY
25.How do pre-conditions and post-conditions guide ADT operation implementation?
→ They de ne the required input state and expected output state, ensuring correct behavior.
26.Illustrate the implementation of the Insert operation for a List ADT.
→ Shift elements right from the position, insert the new element, and update size.
27.What is the importance of maintaining invariants while implementing operations?
→ To keep the data in a valid and consistent state after every operation.
28.What is the "Text" ADT used to demonstrate?
→ It demonstrates ADT implementation using complex data and operations.
29.List typical operations in a Text ADT.
→ Insert, Delete, Get, Length, Substring.
30.Describe how the Insert operation works in the Text ADT.
→ Inserts a character or string at a speci ed position, shifting existing content.
31.What could be the concrete state space of a Text ADT?
→ An array or list of characters and a length indicator.
fi
fi
fi
fi
32.Write the abstraction function for the Text ADT.
→ Text = sequence of characters stored in the array from index 0 to length−1.
33.What invariants should be maintained in the Text ADT?
→ 0 ≤ length ≤ max_size, and all characters are valid.
34.How is the Delete operation implemented in the Text ADT?
→ Removes characters from a range and shifts remaining characters left.

DEBKANTA MAITY
 Abstract data types and their speci cation.

Abstract Data Types (ADTs) and Their Speci cation

1. De nition of ADT:
• An Abstract Data Type (ADT) is a mathematical model for a data structure that de nes a type purely by
its behavior (semantics) rather than by its implementation.
• It speci es what operations are possible on the data, not how those operations are implemented.

2. Key Features of ADTs:

• Encapsulation of data and operations.
DEBKANTA MAITY
• Hides internal structure (implementation independence).
• Provides a clear interface for users.

3. Common Examples of ADTs:

• Stack
• Queue
• List
• Tree
• Graph
• Text (as a complex ADT)
fi
fi
fi
fi
fi
4. Components of ADT Speci cation:
1. Name of the ADT
2. Set of values / states (abstract state space)
3. Operations with:
◦ Signature (name, input, output)
◦ Pre-condition (what must be true before operation)
◦ Post-condition (what is true after operation)
5. Example (Stack ADT Speci cation):
• Operations: DEBKANTA
Abstract data types MAITY
and their speci cation

◦ push(x): Inserts element x.

◦ pop(): Removes top element.
◦ top(): Returns top element without removing.
◦ isEmpty(): Checks if stack is empty.
• Pre/Post Conditions:
◦ pop() → Pre: stack not empty; Post: top element removed.
◦ push(x) → Pre: stack not full; Post: x is at the top.
fi
fi
fi
 6. Importance of ADTs in Software Engineering:
• Promotes modularity and code reuse.
• Facilitates data abstraction and implementation hiding.
• Enhances maintainability and robustness of programs.

7. Summary:
ADTs de ne what operations a data type must support, allowing developers to focus on usage rather than
internal details. The speci cation guides correct and consistent implementation.
DEBKANTA MAITY
How to implement an ADT.

An ADT speci es:

• Data: The type of data stored (e.g., integers, strings, etc.).
• Operations: A set of functions or methods that can be performed on the data (e.g., push, pop for a stack).
• Abstraction: The implementation details are hidden from the user, who interacts only with the de ned
interface.
fi
fi
fi
fi
Steps to Implement an ADT
To implement an ADT, follow these steps:
1. De ne the ADT Interface:
◦ Specify the operations (methods) that the ADT will support.
◦ De ne the expected behavior of each operation (e.g., what does push do in a stack?).
◦ This is typically done using documentation or an interface in languages that support it (e.g., Java
interfaces, Python abstract base classes).
2. Choose a Data Structure for Implementation:
◦ Select an underlying data structure to store the data (e.g., array, linked list, hash table).
◦ The choice depends on the performance requirements (e.g., time complexity for operations).
3. Implement the Operations:
◦ Write code for each operation de ned in the DEBKANTA
interface. MAITY
◦ Ensure the implementation adheres to the speci ed behavior and handles edge cases (e.g., empty
stack, full capacity).
4. Encapsulate the Data:
◦ Hide the internal representation of the data from the user.
◦ Use access control mechanisms (e.g., private variables in Python, Java, or C++).
5. Test the ADT:
◦ Write test cases to verify that each operation behaves as expected.
◦ Check edge cases, such as empty or full data structures.
6. Optimize and Re ne:
◦ Analyze the performance of the implementation (time and space complexity).
◦ Optimize if necessary, or provide alternative implementations for different use cases.
fi
fi
fi
fi
fi
DEBKANTA MAITY
 Concrete state space, concrete invariant, abstraction function

1. Concrete State Space

• 🔹 Refers to the actual internal representation of an Abstract Data Type (ADT) in a

programming language.
• 🔹 It includes all variables and data structures used to store and manage the data.
• 🔹 It is used during implementation to represent the abstract state.
Example:
For a Stack ADT implemented using an array:
DEBKANTA MAITY
• Concrete state space = array stack[] + integer top (index of top element)

2. Concrete (Representation) Invariant

• 🔹 A condition or rule that must always hold true for the concrete state space.
• 🔹 Ensures the validity and consistency of the internal data representation.
• 🔹 Checked before and after operations to maintain correctness.
Example:
For a stack with array implementation:
• Invariant: top ≥ -1 and top < max_size
• Ensures that the top pointer is within valid bounds.
3. Abstraction Function

• 🔹 A mapping from the concrete state (implementation) to the abstract state (speci cation).
• 🔹 Bridges the gap between how data is stored and how it is perceived logically.
• 🔹 Helps in reasoning about the correctness of the implementation.
Example:
For a stack implemented with array S[] and variable top:
• Abstraction function: Stack = ⟨S[0], S[1], ..., S[top]⟩
• This maps the array to an abstract sequence representing the stack contents.
DEBKANTA MAITY

fi
Implementing operations, illustrated by the Text example.

DEBKANTA MAITY
DEBKANTA MAITY
What do you mean by object oriented programming ? difference between procedure oriented and
object oriented programming point wise table .[WBUT 2004,2007,2005,2017,2022,2023]

✅ What is Object-Oriented Programming (OOP)?

Object-Oriented Programming (OOP) is a programming paradigm based on the concept of "objects",
which contain data (attributes) and code (methods). It focuses on modeling real-world entities as software
objects.
DEBKANTA MAITY
🔹 OOP enables modular, reusable, and maintainable code by using principles like Encapsulation,
Inheritance, Polymorphism, and Abstraction.
DEBKANTA MAITY
What is the difference between JAVA and C++ in respect of language function ?

DEBKANTA MAITY
 Short note on List ADT,Stack ADT,Queue ADT.
✅ 1. List ADT (Abstract Data Type)

De nition:
List ADT is a linear collection of data elements where each element has a position (index). It allows insertion, deletion, and
access of elements based on their position in the sequence.
Key Features:
• Elements are stored in a speci c order.
• Can contain duplicate elements.
• Supports both static (array) and dynamic (linked list) implementation.
Common Operations: DEBKANTA MAITY
• insert(position, element) – Adds element at given index.
• delete(position) – Removes element at a speci c index.
• get(position) – Returns element at a given position.
• search(element) – Finds the position of an element.
• length() – Returns number of elements.
Types of List:
• Singly Linked List
• Doubly Linked List
• Circular Linked List
Applications:
• Managing ordered data (e.g., contact lists, playlists). • Storing and processing sequences of data.
• Dynamic memory allocation.
fi
fi
fi
✅ 2. Stack ADT

De nition:
Stack ADT is a linear data structure that follows the Last-In-First-Out (LIFO) principle, meaning the most recently added
element is the rst to be removed.
Key Features:
• Access is only at the top of the stack.
• Think of a stack like a pile of plates – you add and remove from the top.
Basic Operations:
DEBKANTA MAITY
• push(element) – Adds element to the top of the stack.
• pop() – Removes and returns the top element.
• peek() or top() – Views the top element without removing it.
• isEmpty() – Checks if the stack is empty.
• size() – Returns the number of elements.
Implementation:
• Array-based
• Linked List-based
Applications:
• Function call management in recursion.
• Undo features in editors.
• Parsing expressions (in x to post x conversion, evaluation).
• Backtracking algorithms.
fi
fi
fi
fi
✅ 3. Queue ADT

De nition:
Queue ADT is a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning the element added rst is the
one to be removed rst.
Key Features:
• Elements are inserted at the rear and removed from the front.
• Useful for tasks requiring ordered processing.
Basic Operations:
DEBKANTA MAITY
• enqueue(element) – Adds element to the rear of the queue.
• dequeue() – Removes and returns the front element.
• peek() or front() – Views the front element without removing.
• isEmpty() – Checks if the queue is empty.
• size() – Returns the number of elements.
Types of Queues:
• Simple Queue
• Circular Queue
• Priority Queue
• Double-Ended Queue (Deque)
Applications:
• Job scheduling.
• Print queues.
• CPU task management. • Breadth- rst search in graphs.
fi
fi
fi
fi
fi
 What is a class and object ? what is the relationship between them ?

✅ What is a Class?

• A class is a blueprint or template for creating objects.

• It de nes attributes (data members) and behaviors (methods) that the objects created from the class will have.
• It is a user-de ned data type in object-oriented programming.

DEBKANTA MAITY
fi
fi
✅ What is an Object?

• An object is a real-world instance of a class.

• It contains actual values for the attributes and can perform actions de ned by the class methods.
• Multiple objects can be created from the same class.

DEBKANTA MAITY

fi