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

7.1 Introduction to Data Structures, Lists, Linked Lists, and Trees

• 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

7.2 Sorting, Searching, and Graphs

• 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

7.3 Introduction to Data Models, Normalization, and SQL

• 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

7.4 Transaction Processing, Concurrency Control, and Crash Recovery

• ACID Properties

• Concurrency in Databases

  • Concurrent Executions, Serializability

  • Lock-based Protocols, Deadlock Handling and Prevention

  • Failure Classification, Recovery, and Atomicity

  • Log-based Recovery

7.5 Introduction to Operating Systems and Process Management

• 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

7.6 Memory Management, File Systems, and System Administration

• 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