Data Structures and Algorithms Exam Notes

UNIT I: ABSTRACT DATA TYPES AND LINEAR DATA STRUCTURES

Abstract Data Types (ADTs)
- ADTs define operations but not their implementation.
- They specify what operations are performed, not how.
- They abstract away from implementation details, providing an implementation-independent view.
Stack ADT
- Ordered list where insertion and deletion occur only at the "top".
- Operations:
  - Push: Adds an element to the top of the stack.
  - Pop: Removes an element from the top of the stack.
- LIFO (Last-In-First-Out) data structure.
- Implementations:
  - Array implementation: Fixed size.
    - Top is initialized to -1.
    - Top tracks the index of the most recently pushed element.
  - Linked list implementation: Dynamic size.
- Applications:
  - Balancing Symbols: Checks for balanced delimiters (e.g., parentheses, curly braces, square brackets).
  - Evaluating Arithmetic Expressions: Converts infix to postfix notation and evaluates.
  - Backtracking: Used in algorithms that need to "undo" operations.
  - Delimiter Checking
  - Reverse a Data
  - Processing Function Calls
Queue ADT
- Linear data structure where elements are inserted at the REAR and deleted from the FRONT.
- FIFO (First-In-First-Out) data structure.
- Operations:
  - Enqueue: Adds an element to the rear of the queue.
  - Dequeue: Removes an element from the front of the queue.
- Implementations:
  - Array implementation.
    - Front and rear are initialized to -1 (empty queue).
    - Enqueue increments rear.
    - Dequeue increments front.
  - Linked list implementation.
Circular Queue
- A queue implemented in a circular fashion, where the rear can wrap around to the beginning of the queue.
- Enqueue happens at the first location if the last is full
- Two pointers are used:
  - FRONT tracks the first element.
  - REAR tracks the last element.
- Operations:
  - Enqueue: New element added at the REAR.
    - Check if the queue is full before adding
  - Dequeue: New element removed from the FRONT
    - Check if the queue is empty
Deque (Double-Ended Queue)
- Linear data structure that allows insertion and deletion from both ends.
- Types:
  - Input-restricted: Insertion at only one end, deletion from both ends.
  - Output-restricted: Deletion at only one end, insertion from both ends.
- Operations:
  - Insertion at front.
  - Insertion at rear.
  - Deletion at front.
  - Deletion at rear.
Data Structures
- Mathematical models for storing and organizing data efficiently.
- Characteristics:
  - Correctness: Implementation must adhere to the interface.
  - Time Complexity: Operations should be fast.
  - Space Complexity: Minimal memory usage.
- Need:
  - Efficient data search.
  - Handling processor speed limitations.
  - Managing multiple requests.
Classification of Data Structures
- Linear Data Structures:
  - Elements are arranged in a linear order.
  - Each element has a successor and predecessor (except for the first and last elements).
- Non-Linear Data Structures:
  - Elements are not arranged in a sequence; they have hierarchical relationships.
  - Examples: Trees, graphs.
List Data Structure
- Ordered set of elements: A1, A2, A3, …, An
  - A1: First element.
  - An: Last element.
  - n: Size of the list.
- Implementations:
  - Array implementation.
  - Linked list implementation.
  - Cursor implementation.

Arithmetic Expression Notations

Infix Notation
- Operator is placed between the operands.
- Example: A + B, (C - D)
Prefix Notation (Polish Notation)
- Operator is placed before the operands.
- Example: + A B, -CD
Postfix Notation (Reverse Polish Notation)
- Operator is placed after the operands.
- Example: AB +, CD+

Infix to Postfix Conversion

Process characters from left to right.
Operand: Add to postfix string.
Operator:
- Empty stack or '(' on top: Push operator onto the stack.
- '(': Push onto the stack.
- ')': Pop operators until '(' is encountered; discard parentheses pair.
- Higher precedence than top of stack: Push onto stack.
- Lower precedence than top of stack: Pop and print top operator; then test incoming operator.
- Equal precedence: Use associativity (left-to-right: pop and print; right-to-left: push).
End of expression: Pop and print all operators.

Evaluating Postfix Expressions

Use a stack.
Process elements from left to right.
Operand:
- Push the value onto the stack.
Operator:
- Pop two operands from the stack (A and B, where B is the top, most recent operand and A is the next top, second most recent operand).
  - Perform the operation (A operator B).
    - Push the result back onto the stack.
The final value remaining in the stack is the result.
Following condition must be checked:
- The Stack must contain a pair of operands or intermediate results.
- When an expression has been completely evaluated, the Stack must contain exactly one value
Example code for evaluating postfix:

def evaluate_postfix(postfix_expr):
    stack = []
    operators = set(['+', '-', '*', '/', '%', '^'])
    for elem in postfix_expr:
        if elem not in operators:
            stack.append(float(elem))
        else:
            b = stack.pop()
            a = stack.pop()
            if elem == '+':
                stack.append(a + b)
            elif elem == '-':
                stack.append(a - b)
            elif elem == '*':
                stack.append(a * b)
            elif elem == '/':
                stack.append(a / b)
            elif elem == '%':
                stack.append(a % b)
            elif elem == '^':
                stack.append(a ** b)
    return stack.pop()

Balancing Symbols

Use a stack to verify balanced delimiters.
Algorithm:
- Push opening delimiters onto the stack.
- When a closing delimiter is encountered, pop from the stack and check if it matches the corresponding opening delimiter.
Well-formed conditions:
- Equal number of openers and closers
- Closers never exceed openers when reading from left to right.

Queue Applications

Task Scheduling: Prioritize or order tasks.
Resource Allocation: Manage resources like printers or CPU time.
Batch Processing: Handle batch jobs.
Message Buffering: Buffer messages in communication systems.
Event Handling: Handle events in GUI or simulation systems.
Traffic Management: Control traffic flow.
Operating Systems: Manage processes and resources.

UNIT II NON-LINEAR DATA STRUCTURES – TREES

Data structure
- Collection of elements and possible operations for those elements.
Non-linear data structure:
- Data arranged in a hierarchical fashion.
  - Trees and graphs.
Tree:
- Non-linear data structure representing hierarchical relationships.
Terminology associated with Trees
- Tree: Finite set of nodes with a root.
  - Remaining nodes are partitioned into disjoint sets T1, T2…Tn where each of these set is a tree T1…Tn are called the subtrees of the root.
- Branch: Link between parent and child.
- Leaf: Node with no children.
- Subtree: Subset of a tree that is itself a tree.
- Degree: Number of subtrees of a node.
  - Nodes with degree zero are leaf nodes.
  - Other nodes are non-terminal nodes.
- Children: Nodes branching from a node X.
  - X is the parent.
- Siblings: Children of the same parent.
- Degree of tree: Maximum degree of nodes in the tree.
- Ancestors: Nodes along the path from the root to a node.
  - Root is an ancestor of all nodes.
- Level: Root is at level 1; children are at level L+1.
- Height/Depth: Maximum level of any node in the tree.
- Climbing: Traversing from leaf to root.
- Descending: Traversing from root to leaf.
Binary Tree
- Each node has no more than two children.
  - Left child
  - Right child.
- Types of binary tree:
  - Skewed Binary tree: nodes are added to one side of the binary tree.
  - Strictly binary tree: each node has either two nodes or no nodes at all.
  - Complete binary tree: all node consist of two nodes each except for nodes at the last level.
Properties of Binary Trees
- At least $n= 2^{h+1}$ and at most $n = 2^{h+1}-1$ , where h is the height of the tree.
- A binary tree of n elements has n-1 edges.
- A binary tree of height h has at least h and at most $2^h - 1$ elements
- A tree consisting of only a root node has a height of 0.
- $l= (n+1)/2$ leaf nodes in a perfect tree.
- Internal nodes in a complete binary tree of n nodes is n/2.
Representation of Binary Trees
- Array representation:
  - Root is at index 1.
  - Left child of node i: 2i.
  - Right child of node i: 2i + 1.
  - Parent of node i: i / 2.
  - Empty: -1.
- Linked representation:
  - Nodes with data, left pointer, right pointer.
  - Pointers as addresses of the left and right child of a particular node.
Binary Tree ADT
- Data type organized such that its specifications of object and the specification of operation are separated from the representation of the object and the implementation of the operation.
- Operations:
  - Insertion
  - Deletion.
Binary Tree Traversal
- Preorder (NLR): Process root, traverse left, traverse right.
- Inorder (LNR): Traverse left, process root, traverse right.
- Postorder (LRN): Traverse left, traverse right, process root.
- Recursive implementation example:

def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)

Binary Search Trees
- In each node N of the tree value at N is greater than every value in the left subtree of N and is less than every value in the right subtree of N.
- Goal to improve is searching efficiency.
- Search:
  - If k = info(temp) Loc = temp Break
  - If k < info(temp) Temp = left(temp) else Temp = right(temp)
  - Returns address of the node.
- Insert:
  - Recursively find the right position and insert the new node
- Delete
  - Case A: Node has 0 or 1 child, it is checked whether the node pointed by LOC is left child of PAR or is it the right child of PAR. If it is the left child of PAR, then left of PAR is made NULL else right of PAR is made NULL.
  - Case B: Node has 2 children: find inorder successor and replace the node to be deleted with the inorder successor.
Height Balanced Tree (AVL Tree)
- Balance factor: difference between the height of the left and right subtrees (-1, 0, 1).
- AVL Rotations:
  - Left-of-Left rotation
  - Right-of-Right rotation
  - Right-of-Left rotation
  - Left-of-Right rotation
Red-Black Trees
Structural Properties:
Every node is either red or black.
Every leaf (the sentinel) is black.
If a node is red, then both its children are black.
Every simple path from a node to a descendant leaf contains the same number of black nodes(the black height).
Operations:
Insertion
Deletion
Rotations
Splay Trees
- Self-adjusting binary search tree.
- Recently accessed nodes are moved to the root.
- Rotations:
  - Zig rotation
  - Zig-zig rotation
  - Zag rotation
  - Zag-zag rotation
  - Zig-zag rotation
  - Zag-zig rotation

UNIT III: DIVIDE AND CONQUER AND GREEDY STRATEGIES

Divide and Conquer
Divide: Divide the array into two sub arrays
Conquer: Recursively divide the sub-arrays
Combine: Combine all the sorted elements in a group.
Algorithms under this category:
Quicksort: Sorts an array by picking a pivot.
Mergesort: Divides, sorts and merges two arrays
Strassen’s Matrix Multiplication: An efficient algorithm to multiply two matrices.
Integer Multiplication
- Dumb Approach: Multiply digit by digit and add all the results
- Clever Approach: Divide the intger into two parts (high and low) . With reduction of numbers of multiplications to three c2 = a1 * b1 c1 = (a1 + a0) * (b1 + b0) – (c2 + c0) c0 = a0*b0
Greedy Strategy
An approach for solving a problem by selecting the best option available at the moment.
It doesn't worry whether the current best result will bring the overall optimal result.
Used to solve an optimization problem.
Characteristic components of greedy algorithm:
The feasible solution.
Optimal solution.
Objective Function
- Huffman coding
- Shortest path algorithms
  - Dijkstra’s Algorithm
    Minimum Cost Spanning Problem
  - Prim’s Algorithm
  - Kruskal’s Algorithm
    Heap sort algorithm:
    Heapsort is a comparison-based sorting algorithm to create a sorted array

UNIT IV - DYNAMIC PROGRAMMING AND BACKTRACKING

Dynamic Programming
- Breaks problems into subproblems, saves the result, and uses memorization.
- Two approaches:
  - Top-down (memorization).
  - Bottom-up (tabulation).
Computing binomial coefficient Many sub problems are called again and again since they have an overlapping sub problems property
- C(n, k) = C(n-1, k-1) + C(n-1, k)

Knapsack Problem Given a set of items, each having different weight and value or profit associated with it

Two variations: 0/1 (binary) and fractional. Select items from X and fill the knapsack such that it would maximize the profit.
Warshall Algorithm
- rij(k) = rij(k-1) or (rik(k-1) and rkj(k-1))
- Algorithm is used to determine the transitive closure of a directed graph or all paths in a directed graph by using the adjacency matrix
Floyd Warshall Algorithm Floyd Warshall Algorithm is used to find the shortest paths between all pairs of vertices in a graph, where each edge in the graph has a weight which is positive or negative.
Exhaustive Search Algorithm : Exhaustive search is a brute force approach to solving a problem that involves searching for an element with a special property.For example Travelling salesman problem In many cases, exhaustive search (or variation) is the only known way to solve problem exactly for all its possible instances TSP knapsack problem Iterative Deepening Depth First Search(IDDFS) The iterative deepening algorithm is a combination of DFS and BFS algorithms combines the benefits of Breadth-first search's fast search and depth- first search's memory efficiency
BACKTRACKING After determining that a node can lead to nothing but dead end, we go back (backtrack) to the nodes parent and proceed with the search on the next child. N-Queens Problem Place eight queens on an 8 x 8 chessboard so that no two “attack”, that is, no two of them are on the same row, column, or diagonal Explicit constraints rules that restrict each xi to take on values only from a given set. Implicit constraints are rules that determine which of the tuples in the solution space of I satisfy the criterion function. Hamiltonian Circuits A Hamiltonian cycle is a round-trip path along n edges of G that visits every vertex once and returns to its starting position

UNIT V: BRANCH-AND-BOUND, NP PROBLEMS AND APPROXIMATION ALGORITHMS

Branch and Bound differs from backtracking: It has a branching function, it uses breadth first search, It has a bounding function, which goes far beyond the feasibility test