7. Data Structures and Algorithm, Database System, and Operating System (ACtE07)

7.1 Introduction to Data Structures, Lists, Linked Lists, and Trees (ACtE0701)

Data Types and Abstract Data Types (ADT)

• Data Types: Integer, Float, String, Boolean, etc.
• Abstract Data Types (ADT): Defined by operations (e.g., Stack, Queue).

Time and Space Complexity (Big-O, Omega, Theta Notations)

• Big-O ($O$) Notation: Worst-case complexity.
• Omega ($\Omega$) Notation: Best-case complexity.
• Theta ($\Theta$) Notation: Average-case complexity.

Linear Data Structures

Stack (LIFO - Last In, First Out)

• Operations: push(), pop(), peek().
• Application: Expression evaluation (Infix to Postfix).

  c
  CopyEdit
  stack.push(operand)
  stack.pop(operator)
  

Queue (FIFO - First In, First Out)

• Operations: enqueue(), dequeue().
• Types: Normal Queue, Circular Queue, Priority Queue.

Linked Lists

Types of Linked Lists

• Singly Linked List: Nodes linked in one direction.
• Doubly Linked List: Nodes linked in both directions.
• Circular Linked List: Last node links to the first.

Operations on Linked List

• Insertion: At beginning, middle, end.
• Deletion: Remove node from any position.

Trees and Tree Traversal

• Binary Tree: Each node has at most two children.

• Binary Search Tree (BST): Left < Root < Right.

• Tree Traversals:

  • Pre-Order: Root → Left → Right.
  • In-Order: Left → Root → Right.
  • Post-Order: Left → Right → Root.

• AVL Tree: Self-balancing binary search tree.

7.2 Sorting, Searching, and Graphs (ACtE0702)

Sorting Algorithms

• Insertion Sort: Simple, O(n²).
• Selection Sort: Finds the smallest element, O(n²).
• Bubble Sort: Swaps adjacent elements, O(n²).
• Merge Sort: Divide and conquer, O(n log n).
• Quick Sort: Uses a pivot, O(n log n).
• Heap Sort: Uses heap data structure.

Searching Algorithms

• Sequential Search: Linear search (O(n)).
• Binary Search: Requires sorted array (O(log n)).

Graphs

• Graph Representation:

  • Adjacency Matrix: 2D array representation.
  • Adjacency List: Linked list representation.

• Graph Traversal:

  • Depth First Search (DFS): Uses recursion.
  • Breadth First Search (BFS): Uses a queue.

• Graph Algorithms:

  • Dijkstra’s Algorithm: Finds shortest path.
  • Prim’s Algorithm: Minimum Spanning Tree (MST).
  • Kruskal’s Algorithm: MST using edge sorting.

7.3 Data Models, Normalization, and SQL (ACtE0703)

Database Models

• Hierarchical Model: Tree-like structure.
• Network Model: Graph-based.
• Relational Model: Uses tables (RDBMS).

Normalization in Databases

• 1NF: No duplicate columns.
• 2NF: No partial dependencies.
• 3NF: No transitive dependencies.
• BCNF: Stronger 3NF.

SQL (Structured Query Language)

• DDL (Data Definition Language): CREATE, ALTER, DROP.
• DML (Data Manipulation Language): SELECT, INSERT, UPDATE, DELETE.
• Joins: INNER JOIN, LEFT JOIN, RIGHT JOIN.

7.4 Transaction Processing, Concurrency Control, and Crash Recovery (ACtE0704)

ACID Properties

• Atomicity: Transactions are all or nothing.
• Consistency: Database remains valid.
• Isolation: Transactions execute independently.
• Durability: Changes are permanent.

Concurrency Control

• Lock-based Protocols: Prevent conflicts.
• Deadlock Handling: Wait-Die and Wound-Wait.

Crash Recovery

• Log-Based Recovery: Uses transaction logs.

7.5 Operating Systems and Process Management (ACtE0705)

Operating System Components

• Kernel: Core component.
• Shell: User interface.
• File System: Manages files.

Types of Operating Systems

• Batch OS: Executes jobs in batches.
• Multitasking OS: Runs multiple programs.
• Real-Time OS: Time-sensitive applications.

Process Management

• Process States: New → Ready → Running → Waiting → Terminated.
• Process Control Block (PCB): Stores process information.
• Threads: Lightweight processes.

Scheduling Algorithms

• First Come First Serve (FCFS): Non-preemptive.
• Shortest Job Next (SJN): Chooses shortest task first.
• Round Robin (RR): Assigns time slices to tasks.

Synchronization Issues

• Race Condition: Two processes accessing the same resource.
• Mutual Exclusion: Prevents simultaneous access.
• Semaphores: Used for process synchronization.

7.6 Memory Management, File Systems, and System Administration (ACtE0706)

Memory Management

• Virtual Memory: Uses secondary storage as memory.
• Paging: Divides memory into fixed-size pages.
• Segmentation: Divides memory into variable-sized segments.

Page Replacement Algorithms

• FIFO (First-In, First-Out).
• LRU (Least Recently Used).
• Optimal Algorithm.

File System Concepts

• File Structure: Logical storage of data.
• Directory Structure: Hierarchical file organization.
• File Allocation Methods:
  • Contiguous Allocation.
  • Linked Allocation.
  • Indexed Allocation.

System Administration

• User Account Management: Creating and managing users.
• Startup and Shutdown Procedures: Booting, Restarting, Power Off.