7. Data Structures and Algorithm, Database System and Operating System

Data Types, Data Structures, and Abstract Data Types (ADT)
Time and Space Complexity Analysis of Algorithms
- Big-O, Omega, and Theta Notations
Linear Data Structures
- Stack and Queue Implementation
- Stack Applications: Infix to Postfix Conversion, Evaluation of Postfix Expressions
- Array Implementation of Lists
- Stack and Queues as Lists
- Static List Structures, Static vs Dynamic List Structures
- Dynamic Implementation of Linked List
Types of Linked Lists
- Singly Linked List, Doubly Linked List, Circular Linked List
- Basic Operations on Linked Lists
  - Creation, Insertion, Deletion of Nodes at Different Positions
- Doubly Linked Lists and Their Applications
Tree
- Binary Tree Operations: Search, Insertion, Deletion
- Tree Traversals: Pre-order, In-order, Post-order
- Height, Level, and Depth of a Tree
- AVL Balanced Trees

Types of Sorting
- Internal and External Sorting
- Insertion Sort, Selection Sort, Exchange Sort
- Merge Sort, Radix Sort, Shell Sort, Heap Sort (as a Priority Queue)
Big-O Notation and Efficiency of Sorting
Searching Techniques
- Sequential Search, Binary Search, Tree Search
- General Search Trees, Hashing: Hash Function and Hash Tables, Collision Resolution Techniques
Graph Concepts
- Undirected and Directed Graphs
- Graph Representation and Transitive Closure of Graph
- Warshall’s Algorithm
- Graph Traversal Techniques: Depth First Traversal, Breadth First Traversal
- Topological Sorting: Depth First, Breadth First Topological Sorting
- Minimum Spanning Trees: Prim’s, Kruskal’s, and Round-Robin Algorithms
- Shortest-Path Algorithms: Greedy Algorithm, Dijkstra’s Algorithm

Data Abstraction and Data Independence
Schema and Instances
Entity-Relationship (E-R) Model
- Strong and Weak Entity Sets, Attributes and Keys
- E-R Diagram
Normalization
- Different Normal Forms (1st, 2nd, 3rd, BCNF)
- Functional Dependencies, Integrity Constraints, and Domain Constraints
Relational Databases
- Relations (Joined, Derived)
- DDL and DML Commands: Queries, Views, Assertions, Triggers
Relational Algebra and Query Optimization
- Query Cost Estimation and Query Operations
- Evaluation of Expressions and Query Decomposition

ACID Properties
Concurrency in Databases
- Concurrent Executions, Serializability
- Lock-based Protocols, Deadlock Handling and Prevention
- Failure Classification, Recovery, and Atomicity
- Log-based Recovery

Evolution of Operating Systems
Types and Components of Operating Systems
- Operating System Structure and Services
Introduction to Processes
- Process Description, States, Control
- Threads and Process-Thread Relationships
Scheduling and Concurrency
- Types of Scheduling, Principles of Concurrency
- Critical Region, Race Condition, Mutual Exclusion
- Semaphores, Mutex, Message Passing, Monitors
- Classical Synchronization Problems

Memory Management
- Memory Addresses, Swapping, Free Memory Space Management
- Virtual Memory Management, Demand Paging, Page Replacement Algorithms
File Systems
- File, Directory, File Paths, File System Implementation
- Impact of Allocation Policy on Fragmentation
- File System Performance and Mapping File Blocks on the Disk Platter
System Administration Tasks
- User Account Management, System Startup and Shutdown Procedures