Understanding Notations: Math, Science, and Music

• Notations are symbolic representations used to express ideas clearly in mathematics, computer science, and music.

Mathematical Notation

• Infix Notation: Operators are placed between operands (e.g., 3 + 4).
• Prefix Notation (Polish Notation): Operators are placed before operands (e.g., + 3 4).
• Postfix Notation (Reverse Polish Notation): Operators come after operands (e.g., 3 4 +).

Computer Science Notation

• Big O Notation: Describes the efficiency of an algorithm (e.g., O(n²)).
• Binary Notation: Represents numbers using 0s and 1s.
• Hexadecimal Notation: Uses base-16 numbers (e.g., A1F).

Musical Notation

• Standard Notation: Uses staff lines and musical symbols.
• Tablature (TAB): Used for guitar and stringed instruments.

Chemical Notation

• Molecular Formula: Shows the number of atoms in a compound (e.g., H₂O).
• Structural Formula: Represents molecular structure visually.

Scientific Notation

• Expresses very large or small numbers (e.g., 3.2 × 106).

Types of Notations in Arithmetic & Their Precedence & Associativity Rules

• Three main types of notations are used when dealing with arithmetic expressions in mathematics and programming: infix, prefix, and postfix.

Infix Notation

• The operator is placed between two operands (e.g., A + B or 3 * (4 + 5)).
• Operators follow precedence rules (* and / have higher precedence than + and -).
• Parentheses () override precedence.
• Associativity (left-to-right or right-to-left) determines the evaluation order if operators have the same precedence.

Prefix Notation (Polish Notation)

• The operator is placed before the operands (e.g., + A B or * + 3 4 5).
• There is no need for parentheses because the order of evaluation is unambiguous.
• Evaluation starts from right to left.

Postfix Notation (Reverse Polish Notation)

• The operator is placed after the operands (e.g., A B + Or 3 4 + 5 *).
• There is no need for parentheses.
• Evaluation follows a left-to-right approach.

Operator Precedence & Associativity Table

• Parentheses () have the highest precedence and no associativity.
• Exponentiation (^) has a precedence of 2 and is right-to-left associative.
• Multiplication, Division, and Modulus (*, /, %) have a precedence of 3 and are left-to-right associative.
• Addition and Subtraction (+, -) have a precedence of 4 and are left-to-right associative.

Conversion of Infix to Postfix Expression

• Infix Notation: Operators are written between operands (e.g., A + B * C).
• Postfix Notation: Operators come after operands (e.g., A B C * +).

Steps to Convert Infix to Postfix

• Initialize an empty stack for operators and an empty output list for the final postfix expression.
• Scan the infix expression from left to right.
• Add operands (A-Z, 0-9) directly to the output.
• Push operators (+, -, *, /, ^) onto the stack based on precedence.
• Always push left parenthesis "(" onto the stack.
• Pop operators from the stack to the output until a left parenthesis "(" is found when a right parenthesis ")" is encountered.
• Pop any remaining operators from the stack and add them to the output.

Example Conversion

• Convert A + B * C to postfix: A B C * +

Complex Example

• Convert (A + B) * C - D to postfix: A B + C * D -

Evaluation of Postfix Expression (Reverse Polish Notation - RPN)

• In postfix notation, operators appear after their operands.
• Postfix notation eliminates the need for parentheses, making it easier for computers to evaluate expressions.

How to Evaluate a Postfix Expression?

• Use a stack to evaluate the postfix expression.
• Scan the expression from left to right.
• Push operands (numbers) onto the stack.
• Pop the top two operands from the stack when an operator appears.
• Apply the operator on these operands
• Push the result back onto the stack.
• After processing all symbols, the final result is the only value left in the stack.

Key Points

• A stack is used when post fix evaluation is done.
• The order of operations is inherently correct without needing Parentheses
• Calculators and programming languages use it for faster computation.

Tower of Hanoi

• It is a mathematical puzzle that involves moving disks of decreasing size from one peg to another, following specific rules.
• There are three rods (A, B, C).
• A stack of N disks is placed on rod A in decreasing order (largest at the bottom, smallest on top).
• The goal is to move all disks from rod A to rod C, using rod B as an auxiliary.

Rules of the Game

• Only one disk can be moved at a time.
• A larger disk cannot be placed on a smaller disk.
• Disks can only be placed on one of the three rods.

Tower of Hanoi Algorithm

• Move (N-1) disks from Source (A) to Auxiliary (B), using Destination (C) as a helper.
• Move the largest disk (Nth) from Source (A) to Destination (C).
• Move (N-1) disks from Auxiliary (B) to Destination (C), using Source (A) as a helper.
• Base Case: If N == 1, move the disk directly from A to C.

Tower of Hanoi - Key Takeaways

• It is recursive, solved by breaking into smaller subproblems.
• Complexity grows exponentially with more disks.
• It is used in data storage, recursion problems, and Al algorithms.

Application of Stack in Tower of Hanoi

• The Tower of Hanoi can be solved iteratively with a stack, since recursion uses the system's internal call stack.
• The stack helps track the sequence of moves and keeps track of the state of the problem at each step.
• The recursive approach implicitly uses a stack, but we can implement it iteratively using an explicit stack.

Stack-Based Iterative Approach to Tower of Hanoi

• Instead of recursion, push the initial problem configuration onto the stack to simulate the sequence of moves.
• While the stack is not empty, pop the top element (current problem state).
• If it contains a single disk, move it directly.
• If it has multiple disks, break it down into subproblems and push them onto the stack. Continue until all disks are moved.

How the Stack is Used

• Each problem state (n, src, aux, dest) is stored in the stack instead of using recursion.
• The LIFO (Last In, First Out) order helps break down the problem step by step.
• The stack mimics recursion by storing intermediate states.

Advantages of Using a Stack

• Avoids recursion depth limits in large problems.
• Easier to debug since it has an explicit stack-based approach.
• It is memory-efficient compared to deep recursion.

Evaluation of Prefix Expression (Polish Notation)

• A Prefix expression (Polish Notation) is a mathematical notation in which operators appear before operands.
• For example: + 3 5 (equivalent to 3 + 5 in infix notation).

How to Evaluate a Prefix Expression?

• Use a stack where the evaluation is done from right to left
• Scan the prefix expression from right to left.
• If the symbol is an operand, push it onto the stack.
• Pop two operands from the stack and apply the operator. If the symbol is an operaor
• Push the result back onto the stack
• The final result is the only value left in the stack when the entire expression is processed

Key Takeaways

• Prefix evaluation is done using a stack.
• Operators are applied in the correct order through Right-to-Left Processing
• The order of operations is inherent in notation without Parentheses Needed

Queue

• A circular queue is a linear data structure that follows the First In, First Out (FIFO) principle but connects the last position back to the first position, forming a circle.
• Unlike a normal queue, a circular queue reuses empty spaces efficiently by wrapping around when elements are dequeued.

Why Use a Circular Queue?

• Prevents Wastage of Space: In a normal queue (array-based), space remains unused once an element is dequeued. A circular queue reuses that space.
• Efficient Memory Usage: Useful in buffering, scheduling, and resource management.

Circular Queue - Key Takeaways

• Efficient Space use: effectively uses available space
• Constant time complexity: O(1) for enqueue and dequeue operations.
• Circular Nature: Rear wraps around to the front.
• Useful for Scheduling & Buffering: Used in CPU scheduling, network buffering, and task management

Priority Queue

• A priority queue is a type of queue where each element has a priority, and elements with higher priority are served before elements with lower priority.
• Unlike a normal queue (FIFO), a priority queue does not necessarily follow the order of insertion.
• If two elements have the same priority, they follow the FIFO rule.

Types of Priority Queues

• Min-Priority Queue: The element with the lowest priority value is dequeued first. A patient with a critical condition is an example, treated first based on urgency (lower priority value = higher urgency).
• Max-Priority Queue: The element with the highest priority value is dequeued first. An example is a task scheduler where the highest priority task is executed first.

Queue Representation

• Arrays/List: Simple but inefficient (O(n) for insertion).
• Heap (Binary Heap): Efficient implementation (O(log n) for insertion & deletion).
• Linked List: Maintains sorted order (O(n) insertion, O(1) deletion).

Queue Operations

• enqueue(item, priority): Inserts an item with a priority.
• dequeue(): Removes and returns the element with the highest priority.
• peek(): Returns the highest-priority element without removing it.
• isEmpty(): Checks if the queue is empty.

Applications of Priority Queues

• CPU Scheduling: Executes high-priority tasks first.
• Dijkstra's Algorithm: Used in shortest path algorithms.
• Data Compression (Huffman Coding): Builds optimal prefix trees.
• Event Scheduling: Handles tasks in real-time systems.

Double-Ended Queue

• A Deque (Double-Ended Queue) is a linear data structure where elements can be inserted and removed from both ends (front and rear).
• Unlike a normal queue (FIFO) or a stack (LIFO), a deque is more flexible.
• It can function as both a queue and a stack.
• Key Feature: Insertion and deletion at both ends.

Applications of Deque

• Sliding Window Problems: Used in dynamic programming.
• Undo/Redo Operations: Used in text editors.
• Job Scheduling: Manages tasks with varying priorities.
• Palindromic Checking: Compares both ends of a string efficiently.

Applications of Queue

• A queue is a FIFO (First-In, First-Out) data structure, meaning the element added first is removed first. It is widely used in real-life scenarios and computer science applications.

Real Life Examples

• Queues appear in ticket counters, banks, and supermarket checkout lines, where customers are served in order of arrival.
• Printers process multiple print requests in the order they were submitted.
• A call center answers customer calls in the order in which they are placed in the queue.

Applications of Queue in Computer Science

• Round Robin Scheduling uses queues to allocate CPU time to processes, ensuring fair execution of multiple processes.
• Operating systems schedule tasks (background processes, I/O requests) in order, ensuring tasks are executed in order.
• Routers and switches use queues to manage incoming and outgoing packets, preventing congestion and ensuring data is sent in sequence.

Breadth-First Search (BFS) in Graphs

• BFS explores nodes level by level.
• For example, finding the shortest path in a maze or Google Maps.

Job Scheduling in Operating Systems

• Background jobs (e.g., running a script) are placed in a queue, ensuring tasks are executed based on priority.

Message Queues (Inter-Process Communication)

• WhatsApp and Email servers use queues to store and forward messages, preventing message loss and managing delayed delivery.

Real-time Streaming (YouTube, Netflix)

• Video buffering uses a queue to store packets of data, ensuring smooth playback.

First Come First Serve (FCFS) Scheduling Algorithm

• In FCFS, the process that arrives first is executed first, therefore following the FIFO (First In, First Out) principle.
• Non-preemptive: Once a process starts execution, it cannot be interrupted until it finishes.

Advantages of FCFS

• FCFS is easy to implement, fair for all processes with no starvation, and works well when processes have similar burst times.

Disadvantages of FCFS

• FCFS uses a high waiting time for large processes.
• Shorter processes must wait if a long process arrives first (Convoy Effect).
• Not suitable for interactive systems with Poor Performance for Time-Sharing Systems

Where is FCFS Used?

• Batch processing is used in the order the jobs arrive
• To handle requests on the disk FCFS scheduling
• To manage systems and queues in a ticket booking environment .

Shortest Job First (SJF) Scheduling Algorithm

• SJF selects the process with the smallest burst time for execution first, reducing the average waiting time compared to FCFS. If the processes burst time is the same it goes to the FCFS order.
• This method is the most efficient way to minimize the waiting time
• Preemptive (Shortest Remaining Time First, SRTF) or Non-Preemptive (Standard SJF).

Disadvantages of SJF

• It requires knowledge of the execution time an therefore being difficult to predict burst times.
• May cause the Starvation issue by delaying longer ones indefinitely.
• Is not suitable for time-sharing systems but Preemptive SJF is preferred for modern OS

Round Robin (RR) Scheduling Algorithm

• Round Robin (RR) is a preemptive scheduling algorithm where each process gets a fixed time slice (quantum) to execute. If a process doesn't finish within this time, it is moved to the end of the queue, and the CPU is given to the next process.
• In Time-Sharing Mechanism, Every process gets an equal time slice, and Preemptive ensures no process monopolizes the CPU.
• This ensures RR scheduling is fair and Efficient, and Good for interactive systems.

Disadvantages of Round Robin

• frequent CPU switches cause High Context Switching Overhead slow performance, and is dependent on the set time for quantum
• To small: More context switching (inefficient).
• Too large: Behaves like FCFS and is not always best for minimizing waiting time.

Breadth-First Search (BFS) Algorithm

• Breadth-First Search (BFS) is a graph traversal algorithm that explores all neighboring nodes (same level) before moving to the next level.
• The First-In, First-Out (FIFO) principle is followed using a queue in BFS
• The algorithm explores all nodes at the same depth before going deeper and uses a queue for transversal
• Working for both trees and graphs (directed/undirected) while finding the shortest path in an unweighted graph.