Provides an overview of contemporary networking technologies. This unit covers the basics of Wi-Fi, mobile network generations (2G-5G), and an introduction to Cloud computing and the Internet of Things (IoT).

Read Cheat Sheet

Computer network

Apply learned OOP concepts through the development of practical projects like a Bank Management System or an Online Shopping Cart.

Read Cheat Sheet

oop_syllabus_html

Read Cheat Sheet

Fundamental of Computer

Digital Logic Systems6 Rules

# UNIT 4: Software Design: Design Fundamentals, Effective Modular Design, Data Architectural & Procedural Design, Design Documentation ## 4.1 Fundamentals of Software Design Software design transforms SRS specifications into detailed operational blueprints ready for implementation. ### Key Design Principles 1. **Abstraction**: Procedural abstraction (named sequence of operations) and Data abstraction (named collection of data attributes). 2. **Refinement (Stepwise Refinement)**: Top-down process of decomposing high-level statements into detailed lower-level procedural steps. 3. **Modularity**: Dividing system logic into independently named and addressable software components. 4. **Software Architecture**: Macro-structure organizing modules, relationships, and global control flow. 5. **Information Hiding**: Designing modules such that internal algorithms and data structures are inaccessible to other modules. --- ## 4.2 Effective Modular Design: Cohesion & Coupling ### The Core Architectural Rule Achieve **HIGH Cohesion** within individual modules and **LOW Coupling** between modules. --- ### Module Cohesion (Internal Module Strength) Cohesion measures the functional closeness of processing elements within a single module. (Ranked from Lowest/Worst to Highest/Best): 1. **Coincidental Cohesion (Worst)**: Elements are combined randomly without meaningful functional relationship. 2. **Logical Cohesion**: Elements are logically categorized together (e.g., a module containing all I/O routines) but execute different tasks based on input parameters. 3. **Temporal Cohesion**: Elements are grouped because they execute at the same point in time (e.g., system initialization routine `InitSystem()`). 4. **Procedural Cohesion**: Elements execute in a specific order to accomplish a multi-step procedure. 5. **Communicational Cohesion**: Elements operate on the same input data or produce the same output dataset. 6. **Sequential Cohesion**: Output of one processing element serves as direct input to the next element in a pipeline sequence. 7. **Functional Cohesion (Best)**: Module performs exactly **ONE targeted, well-defined single function** (e.g., `CalculateTax()`). --- ### Module Coupling (Inter-Module Interdependence) Coupling measures the degree of interdependence between separate software modules. (Ranked from Best/Lowest to Worst/Highest): 1. **Data Coupling (Best)**: Modules communicate strictly by passing simple scalar data parameters through function calls. 2. **Stamp (Data Structure) Coupling**: Modules communicate by passing composite data structures (e.g., passing a full `StudentRecord` struct when only `Age` is needed). 3. **Control Coupling**: One module passes control flags/signals to another module to dictate its internal execution logic. 4. **External Coupling**: Modules share an external interface schema or hardware device communication protocol. 5. **Common Coupling**: Modules share access to global data spaces or global shared memory. 6. **Content Coupling (Worst)**: One module directly modifies or accesses internal data, state, or code inside another module, violating encapsulation completely. --- ## 4.3 Cyclomatic Complexity (McCabe) Developed by Thomas McCabe in 1976, Cyclomatic Complexity is a quantitative software metric measuring the number of linearly independent paths through a program's control flow graph $G=(V,E)$. ### Calculating Cyclomatic Complexity $V(G)$ #### Method 1: Edge-Node Formula $$V(G) = E - N + 2P$$ where $E$ = number of edges, $N$ = number of nodes, $P$ = number of connected components (typically $P=1$). #### Method 2: Predicate Node Formula $$V(G) = P_{pred} + 1$$ where $P_{pred}$ = number of decision/predicate nodes (e.g., `if`, `while`, `for`, `case` statements). #### Method 3: Bounded Region Formula $$V(G) = \\text{Number of enclosed bounded regions} + 1$$ ### Risk Threshold Interpretation - $V(G) = 1 \\text{ to } 10$: Simple, low risk, highly testable code. - $V(G) = 11 \\text{ to } 20$: Moderate complexity and risk. - $V(G) = 21 \\text{ to } 50$: High complexity, high risk, difficult to test. - $V(G) > 50$: Untestable, unstable code; mandatory refactoring required. --- ## 4.4 Data, Architectural & Procedural Design ### Data Design Translates data model entities into low-level data structures, database schemas, and object attributes. ### Architectural Design Defines structural organization of system components using established architectural styles: - **Data-Centered Architecture**: Central repository (database) surrounded by independent client applications. - **Data-Flow Architecture**: Pipe-and-filter processing pipeline. - **Call-and-Return Architecture**: Main program/subroutine hierarchy and object-oriented layers. - **Layered Architecture**: Outer user interface layers communicating only with adjacent lower service layers. ### Procedural Design Translates structural design elements into step-by-step procedural logic using Flowcharts, Decision Tables, and Program Design Language (PDL/Pseudocode). --- ---

Read Cheat Sheet

Software Engineering8 Rules

Read Cheat Sheet

Database Management Systems

3 Topics

Subject Syllabus

Database Management Systems4 Rules

ACID Properties & Atomicity

ACID guarantees form the bedrock of transactional database systems. Atomicity ensures that if an error occurs midway through a transaction (e.g. money deducted from Account A but system crashes before crediting Account B), the database engine automatically rolls back all changes so no partial updates remain.

Read Cheat Sheet

Database Management Systems4 Rules

B+ Trees & Disk Indexing

In relational databases (like PostgreSQL, MySQL, Oracle), B+ Trees are the gold standard for disk indexing. Unlike standard B-Trees where data pointers are scattered across internal nodes, B+ Trees store all record pointers in leaf nodes. Because the leaf nodes are linked sequentially, scanning a range of keys (e.g., `WHERE age BETWEEN 20 AND 30`) simply traverses the leaf linked list without re-traversing the tree structure.

Read Cheat Sheet

Database Management Systems4 Rules

Normal Forms & BCNF

Database normalization organizes attributes to reduce data redundancy and update anomalies. BCNF addresses functional dependencies where a non-prime or prime attribute is functionally determined by a non-superkey. By enforcing that every determinant X in X -> Y must be a superkey, BCNF eliminates all redundancy based on FDs.

Read Cheat Sheet

Operating Systems

3 Topics

Subject Syllabus

Operating Systems

Operating System

Read formulas, common mistakes, and MCQs.

Read Cheat Sheet

Operating Systems4 Rules

Round Robin CPU Scheduling

Round Robin scheduling is designed for time-sharing systems. The CPU scheduler cycles through the ready queue, giving each process a fixed slice of time (quantum). If a process does not complete within its quantum, it is preempted and pushed to the back of the ready queue. As the quantum approaches infinity, no process is ever preempted, resulting in standard FCFS execution.

Read Cheat Sheet

Operating Systems4 Rules

System Calls & CPU Execution Modes

Modern CPUs use hardware-enforced protection rings to prevent user applications from corrupting system memory or hardware devices. When an application needs to read a file, send network packets, or allocate memory, it cannot execute these actions directly. Instead, it triggers a System Call trap, switching the CPU to Kernel Mode (Ring 0). The kernel processes the request and switches execution back to User Mode.

Read Cheat Sheet

Network Security

2 Topics

Subject Syllabus

Network Security

1.Cryptography and network securtiy

Read formulas, common mistakes, and MCQs.

Read Cheat Sheet

Network Security

Read formulas, common mistakes, and MCQs.

Read Cheat Sheet

Data Structures & Algorithms

1 Topics

Subject Syllabus

Data Structures & Algorithms12 Rules

Data Structures & Algorithms

# Data Structures & Algorithms (DSA) Master Revision Cheatsheet > **Target Exam**: Competitive Programming & CS Entrance Exams (GATE, RPSC Computer Inspector, Technical Officer) > **Subject**: Data Structures & Algorithms > **Topic Page**: [https://upscorer.in/topics/data-structures-algorithms](https://upscorer.in/topics/data-structures-algorithms) --- ## 🌟 Key Concepts & Core Rules ⭐⭐⭐⭐⭐ ### 1. Asymptotic Notations & Complexity Analysis - **Big-O ($O$)**: Upper bound of execution time (Worst-case performance guarantee). - **Big-Omega ($\Omega$)**: Lower bound of execution time (Best-case performance guarantee). - **Big-Theta ($\Theta$)**: Tight bound (Average & exact growth rate when upper and lower bounds match). - **Growth Rate Hierarchy**: $$\mathcal{O}(1) < \mathcal{O}(\log n) < \mathcal{O}(n) < \mathcal{O}(n \log n) < \mathcal{O}(n^2) < \mathcal{O}(n^3) < \mathcal{O}(2^n) < \mathcal{O}(n!)$$ --- ### 2. Linear Data Structures #### A. Arrays - **Memory Layout**: Contiguous memory allocation. - **Access Time**: $\mathcal{O}(1)$ via index arithmetic: $\text{Address}(A[i]) = \text{Base} + i \times \text{Size}$. - **Insertion/Deletion**: $\mathcal{O}(n)$ worst-case due to element shifting. #### B. Linked Lists - **Structure**: Nodes containing Data + Pointer to next node. - **Access Time**: $\mathcal{O}(n)$ sequential traversal. - **Insertion/Deletion**: $\mathcal{O}(1)$ at known pointer location (no shifting required). - **Variants**: Singly Linked List, Doubly Linked List ($\mathcal{O}(1)$ backward traversal), Circular Linked List (last node points to head). #### C. Stacks - **Principle**: Last-In, First-Out (LIFO). - **Primary Operations**: `push(x)` $\mathcal{O}(1)$, `pop()` $\mathcal{O}(1)$, `peek()` $\mathcal{O}(1)$. - **Key Applications**: Function call stack, Infix to Postfix/Prefix evaluation, Balancing Parentheses, Backtracking. #### D. Queues - **Principle**: First-In, First-Out (FIFO). - **Primary Operations**: `enqueue(x)` $\mathcal{O}(1)$, `dequeue()` $\mathcal{O}(1)$. - **Circular Queue**: Solves space wastage of array queue using modulo arithmetic: $\text{rear} = (\text{rear} + 1) \pmod N$. - **Applications**: CPU Scheduling (Round Robin), BFS Graph Traversal, Buffer management. --- ### 3. Non-Linear Data Structures #### A. Trees & Binary Search Trees (BST) - **Binary Tree**: Each node has at most 2 children. - **Tree Traversals**: - **Inorder** (Left, Root, Right): Returns sorted sequence for BST! - **Preorder** (Root, Left, Right): Used for expression trees and tree duplication. - **Postorder** (Left, Right, Root): Used for tree deletion and Postfix generation. - **Level-Order**: Breadth-First search using Queue. - **BST Property**: $\text{Left Child} < \text{Root} \le \text{Right Child}$. - Search, Insert, Delete Time Complexity: $\mathcal{O}(h)$ where $h$ is tree height ($\mathcal{O}(\log n)$ balanced, $\mathcal{O}(n)$ skewed). #### B. Binary Heaps - **Complete Binary Tree** stored in array ($i$'s left child = $2i+1$, right child = $2i+2$, parent = $\lfloor(i-1)/2\rfloor$). - **Min-Heap**: Parent $\le$ Children. Max-Heap: Parent $\ge$ Children. - **Heap Operations**: Insert $\mathcal{O}(\log n)$, Extract Min/Max $\mathcal{O}(\log n)$, Heapify array $\mathcal{O}(n)$. #### C. Graphs - **Representations**: Adjacency Matrix ($\mathcal{O}(V^2)$ space) vs Adjacency List ($\mathcal{O}(V + E)$ space). - **Graph Traversals**: - **BFS**: Level-by-level using Queue. Time: $\mathcal{O}(V + E)$. Finds shortest path in unweighted graphs. - **DFS**: Deep exploration using Stack / Recursion. Time: $\mathcal{O}(V + E)$. Used for Topological Sorting and Cycle Detection. --- ### 4. Sorting & Searching Algorithms Summary Table | Algorithm | Best Time | Avg Time | Worst Time | Space | Stable? | | :--- | :---: | :---: | :---: | :---: | :---: | | **Linear Search** | $\mathcal{O}(1)$ | $\mathcal{O}(n)$ | $\mathcal{O}(n)$ | $\mathcal{O}(1)$ | Yes | | **Binary Search** | $\mathcal{O}(1)$ | $\mathcal{O}(\log n)$ | $\mathcal{O}(\log n)$ | $\mathcal{O}(1)$ | Yes | | **Bubble Sort** | $\mathcal{O}(n)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(1)$ | Yes | | **Selection Sort** | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(1)$ | No | | **Insertion Sort** | $\mathcal{O}(n)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(1)$ | Yes | | **Merge Sort** | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n)$ | Yes | | **Quick Sort** | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(\log n)$ | No | | **Heap Sort** | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(1)$ | No | --- ## 🚨 Common Exam Pitfalls & Misconceptions 1. **Array Indexing vs Element Shift**: Direct index access in array is $\mathcal{O}(1)$, but insertion/deletion requires shifting $\mathcal{O}(n)$ elements. 2. **Inorder Traversal of BST**: Inorder traversal of any Binary Search Tree ALWAYS yields elements in strictly sorted ascending order. 3. **Queue Space Wastage**: Linear array queue runs out of space when `rear = N-1` even if front elements are dequeued. Use Circular Queue with modulo arithmetic $(\text{rear} + 1) \pmod N$. 4. **Binary Search Requirement**: Binary Search CANNOT be performed on an unsorted array or a standard Singly Linked List in $\mathcal{O}(\log n)$ time due to lack of random access. 5. **Quick Sort Worst Case**: Quick sort degenerates to $\mathcal{O}(n^2)$ time complexity when the pivot is chosen poorly on an already sorted array. 6. **Heap Build Time**: Building a heap from an unsorted array of size $n$ takes $\mathcal{O}(n)$ time using Floyd's algorithm, NOT $\mathcal{O}(n \log n)$. 7. **Stack Overflow vs Underflow**: Stack Overflow occurs when `push()` is called on a full stack (`top == MAX-1`). Stack Underflow occurs when `pop()` is called on an empty stack (`top == -1`). 8. **BFS Data Structure**: BFS requires a **Queue**, whereas DFS requires a **Stack** (or recursive call stack). 9. **Stability in Sorting**: A sorting algorithm is stable if two elements with equal keys appear in the same relative order in output as in input (e.g. Merge Sort is stable, Quick Sort & Heap Sort are unstable). 10. **Recursion Space**: Recursive algorithms require $\mathcal{O}(h)$ auxiliary call stack space where $h$ is maximum recursion depth. --- ## 🇮🇳 हिंदी मास्टर सारांश (Hindi Revision Summary) # डेटा स्ट्रक्चर्स एवं एल्गोरिदम (Data Structures & Algorithms) - **ऐरे (Array)**: लगातार (Contiguous) मेमोरी लोकेशन पर डेटा स्टोर करता है। इंडेक्स द्वारा एक्सेस टाइम $\mathcal{O}(1)$ होता है। - **लिंक्ड लिस्ट (Linked List)**: नोड्स में डेटा और अगले नोड का पॉइंटर होता है। एलिमेंट्स को खिसकाए बिना $\mathcal{O}(1)$ में इंसर्ट/डिलीट संभव है। - **स्टैक (Stack)**: LIFO (Last-In, First-Out) सिद्धांत पर कार्य करता है। मुख्य ऑपरेशन्स: Push, Pop, Peek ($\mathcal{O}(1)$)। - **क्यू (Queue)**: FIFO (First-In, First-Out) सिद्धांत पर कार्य करता है। सर्कुलर क्यू (Circular Queue) मेमोरी की बर्बादी रोकता है: $(\text{rear}+1) \pmod N$। - **बाइनरी सर्च ट्री (BST)**: बायां बच्चा < रूट $\le$ दायां बच्चा। इनऑर्डर (Inorder) ट्रैवर्सल हमेशा सॉर्टेड (Sorted) क्रम देता है। - **बाइनरी सर्च (Binary Search)**: केवल सॉर्टेड ऐरे पर कार्य करता है। समय जटिलता (Time Complexity) $\mathcal{O}(\log n)$ है। - **सॉर्टिंग जटिलता**: - Merge Sort: $\mathcal{O}(n \log n)$ (सर्वदा स्थाई/Stable)। - Quick Sort: औसतन $\mathcal{O}(n \log n)$, वर्स्ट केस $\mathcal{O}(n^2)$ (अस्थाई/Unstable)। - Heap Sort: $\mathcal{O}(n \log n)$ (इन-प्लेस/In-Place, $\mathcal{O}(1)$ अतिरिक्त स्पेस)।

Read Cheat Sheet

Computer Science

1 Topics

Subject Syllabus

Computer Science

Introduction to Programming

Read formulas, common mistakes, and MCQs.

Read Cheat Sheet