UNIT-1:
1. Asymptotic Notations: Asymptotic notations, such as Big O, Big Omega, and Big
Theta, are used to describe the upper and lower bounds and average-case behavior of
algorithms. They play a crucial role in analyzing algorithmic efficiency and
performance.
2. Constructors: Constructors are special member functions in a class used for
initializing objects. Types include default constructor, parameterized constructor,
copy constructor, and constructor overloading. Example:
python
Copy code
class Example:
def __init__(self, x):
self.x = x
obj = Example(5) # Parameterized constructor
3. Inheritance: Inheritance is a feature of OOP where a class inherits properties and
behaviors from another class. Types include single inheritance, multiple inheritance,
hierarchical inheritance, and hybrid inheritance. Example:
python
Copy code
class Parent:
pass
class Child(Parent):
pass
4. Shallow vs. Deep Copying: Shallow copying creates a new object but doesn't create
copies of nested objects. Deep copying creates a new object and recursively adds
copies of nested objects. Example:
python
Copy code
import copy
original = [1, [2, 3]]
shallow_copy = copy.copy(original)
deep_copy = copy.deepcopy(original)
5. Recursive Implementations: Recursive algorithms are functions that call themselves
directly or indirectly. Example: Recursive factorial function.
6. Operator Overloading: Operator overloading allows defining operators for custom
classes. Example:
python
Copy code
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __add__(self, other):
return Point(self.x + other.x, self.y + other.y)
7. Algorithm Analysis Functions: Functions like time complexity, space complexity,
and algorithmic efficiency are used to analyze algorithms.
8. Class Concept: Classes are blueprints for creating objects, encapsulating data and
behaviors. Example:
python
Copy code
class Example:
def __init__(self, x):
self.x = x
obj = Example(5)
UNIT-2:
1. Stack ADT: Stack ADT follows Last In First Out (LIFO) order. Example: Push, Pop,
Peek operations.
2. Applications of Stack: Applications include function call stack, expression
evaluation, and backtracking algorithms.
3. Linked List Operations: Operations include insertion, deletion, traversal, searching,
and updating nodes in a linked list.
4. Deque: Deque (Double Ended Queue) allows insertion and deletion from both ends.
Operations include insertFront, insertRear, deleteFront, deleteRear.
5. Types of Linked Lists: Singly Linked List, Circular Linked List, Doubly Linked List.
Example:
python
Copy code
class Node:
def __init__(self, data):
self.data = data
self.next = None
6. Queue ADT: Queue ADT follows First In First Out (FIFO) order. Example: Enqueue,
Dequeue operations.
UNIT-3:
1. Bubble Sort: Sorting algorithm that repeatedly steps through the list, compares
adjacent elements, and swaps them if they are in the wrong order.
2. Merge Sort: Sorting algorithm that divides the array into halves, recursively sorts
each half, and then merges them.
3. Insertion Sort: Sorting algorithm that builds the final sorted array one item at a time
by inserting elements into their correct position.
4. Selection Sort: Sorting algorithm that repeatedly selects the minimum element from
the unsorted portion and moves it to the beginning.
5. Quick Sort: Sorting algorithm that divides the array into smaller partitions using a
pivot element, and recursively sorts each partition.
6. Hashing and Hash Functions: Hashing is the process of mapping data to a fixed-size
array. Hash functions are used to generate hash codes from data.
7. Collision Handling: Techniques like chaining, open addressing, and rehashing are
used to handle collisions in hashing.
8. Searching Techniques: Techniques like linear search and binary search are used to
search for elements in a collection.
UNIT-4:
1. Binary Search Tree (BST): Binary tree where every node has at most two children,
and the left child is smaller and the right child is larger. Algorithm includes insertion,
deletion, and searching.
2. AVL Tree: Self-balancing binary search tree where the heights of the two child
subtrees of any node differ by at most one. Rotations are used to maintain balance.
3. Heap Tree ADT: Complete binary tree where the parent node is either greater than or
equal to (max heap) or less than or equal to (min heap) its child nodes.
4. Tree Traversal Algorithms: Algorithms like Inorder, Preorder, Postorder, and Level
Order are used to traverse trees.
UNIT-5:
1. Topological Ordering: Arranging the nodes in a directed acyclic graph (DAG) such
that for every directed edge uv, vertex u comes before v in the ordering.
2. Graph Traversal: Algorithms like Depth First Search (DFS) and Breadth First
Search (BFS) are used to traverse graphs.
3. Dijkstra’s Algorithm: Finds the shortest path from a single source vertex to all other
vertices in a weighted graph.
4. Prim’s Algorithm: Finds the minimum spanning tree of a connected, undirected
graph using a greedy approach.
5. Kruskal’s Algorithm: Finds the minimum spanning tree of a connected, undirected
graph by selecting edges in increasing order of weight until all vertices are connected
without forming a cycle.
