Syllabus

Introduction to data structure, list, linked lists and trees

data types, data structures and abstract data types; time and space analysis of algorithms (Big oh, omega and theta notations), Linear data structure (Stack and queue implementation); Stack application: infix to postfix conversion, and evaluation of postfix expression, Array implementation of lists; Stack and Queues as list; and Static list structure, Static and dynamic list structure; Dynamic implementation of linked list; Types of Linked list: Singly Linked list, Doubly Linked list, and Circular Linked list; Basic operations on Linked list: creation of linked list, insertion of node in different positions, and deletion of nodes from different positions; Doubly linked lists and its applications, Concept of Tree, Operation in Binary tree, Tree search, insertion/deletions in Binary Tree, Tree traversals (pre-order, post-order and in-order), Height, level and depth of a tree, AVL balanced trees.

Sorting, searching, and graphs

types of sorting: internal and external; Insertion and selection sort; Exchange sort; Merge and Redix sort; Shell sort; Heap sort as a priority queue; Big ‘O’ notation and Efficiency of sorting; Search technique; Sequential search, Binary search and Tree search; General search tree; Hashing: Hash function and hash tables, and Collision resolution technique, Undirected and Directed Graphs, Representation of Graph, Transitive closure of graph, Warshall’s algorithm, Depth First Traversal and Breadth First Traversal of Graph, Topological sorting (Depth first, Breadth first topological sorting), Minimum spanning trees ( Prim’s, Kruskal’s and Round- Robin algorithms), Shortest-path algorithm (Greedy algorithm, and Dijkstra’s Algorithm)

Introduction to data models, normalization, and SQL

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

Transaction processing, concurrency control and crash recovery

ACID properties, Concurrent Executions, Serializability Concept, Lock based Protocols, Deadlock handling and Prevention, Failure Classification, Recovery and Atomicity, and Log-based Recovery.

Introduction to Operating System and process management

Evolution of Operating System, Type of Operating System, Operating System Components, Operating System Structure, Operating System Services, Introduction to Process, Process description, Process states, Process control, Threads, Processes and Threads, and Types of scheduling, Principles of Concurrency, Critical Region, Race Condition, Mutual Exclusion, Semaphores and Mutex, Message Passing, Monitors, and Classical Problems of Synchronization.

Memory management, file systems and system administration

Memory address, Swapping and Managing Free Memory Space, Virtual Memory Management, Demand Paging, Performance, and Page Replacement Algorithms, introduction to File, Directory and File Paths, File System Implementation, Impact of Allocation Policy on Fragmentation, Mapping File Blocks on The Disk Platter, File System Performance, Administration Tasks, User Account Management, Start and Shutdown Procedures.