(Syllabus for Data Structures and Operating Systems)
CCS-207: Data Structures
Theory: 100 Marks (60 Lectures)
Unit 1: Introduction to data structure: 15 marks (12L)
Definition, Data Objects, Data Types – Primitive and Composite, Asymptotic Notations – Big oh, Omega, Theta, Little oh, Little omega, Arrays and its representation in memory, Operations on Arrays – Traversal, Search, Insertion, Deletion, Sorting, Merging. Unit 2: Linked List: 15 marks (12L) Singly Linked List operations, Implementation in memory, Garbage Collection, Overflow and Underflow, Types – Header, Circular, Doubly and its operations, Application – Representation of Polynomial, Polynomial Addition. Unit 3: Stacks and Queues: 15 marks (12L) Implementation of Stacks and Queues using Array and Linked List, Notation – Infix, Prefix, Postfix, Application of Stack – Infix to Postfix, Evaluation of Postfix expression, Postponed decisions, Circular Queue, Application of Queue – Priority Queues. Unit 4: Trees and Graphs: 15 marks (12 L) Binary Tree and its representation, Operations – Tree Traversal, Counting nodes, Deletion, Graphs – Types and its representation, Traversal – Shortest path, Dijkstra’s Algorithm. Unit 5: Sorting and Searching: 15 marks (12L) Searching techniques – Linear, Binary, Sorting – Bubble, Insertion, Selection, Merge and its complexity.
Books :
1. Data structure using C and C++ : Yedidyah langsam, Moshe J. Augenstein, Aaron M. Tenenbaum , Second Edition, Pearson Prentice Hall.
References:
1. E.Horowitz and S. Shani Fundamentals of Data Structures in C, Galgotia Pub. 1999.
2. Horowitz, S. Sahni, and S. Rajasekaran, Computer Algorithms, Galgotia Pub. Pvt. Ltd., 1998. 3. R. Kruse C.L. Tondo and B. Leung, Data Structures and Program design in C, PHI, 1997. CCS-208: Operating Systems Theory: 100 Marks (60 Lectures)
Unit 1. Introduction 20 marks (14 Lectures)
What is OS? Types of OS, Multiprogramming system, batch system, time sharing system, OS for PC & workstations, Process control & Real time systems, concept of process & threads, concept of interrupts.
Unit 2. Structure of Operating System 15 marks (8 Lectures)
Monolithic, Layered, Virtual, Client Server, System programs.
Unit 3. Concept of Synchronization 10 marks (8 Lectures)
Semaphores, Critical regions, processor & user modes, system calls, Kernels.
1. H.M. Deitel, An introduction to Operating System
2. A.S. Tanenbaum, Modern Operating Systems, 3rd Edition, Pearson Education 2007. 3. A.S. Godbole, A.Kahate, Operating Sytems 4. W. Stallings, Operating Systems, Internals & Design Principles , 5th Edition, Prentice Hall of India. 2008. 5. M. Milenkovic, Operating Systems- Concepts and design, Tata McGraw Hill 1992.
CCS-209: Practical on CCS-207 & CCS -208
SECTION A: Data Structures (Practical): 50 Marks (25 Lectures)
Sample Programs for practical :
1. Implement PUSH, POP operations of stack using Arrays.
2. Implement PUSH, POP operations of stack using Pointers. 4. Implement add, delete operations of a queue using Arrays. 5. Implement add, delete operations of a queue using Pointers. 6. Implement stack using linked list. 7.Conversion of infix to postfix using stack. 8. Postfix Expression Evaluation. 9. Addition of two polynomials using Arrays and Pointers. 10. Creation, insertion, and deletion in doubly linked list. 11. Binary tree traversals (in-order, pre-order, and post-order) using linked list. 12. Depth First Search and Breadth first Search for Graphs using Recursion.
SECTION B: Operating Systems (Practical): 50 Marks (25 Lectures)
1. WRITE A PROGRAM (using fork() and/or exec() commands) where parent and child execute: a) same program, same code. b) same program, different code. c) before terminating, the parent waits for the child to finish its task. 2. WRITE A PROGRAM to report behaviour of Linux kernel including kernel version, CPU type and model. (CPU information) 3. WRITE A PROGRAM to report behaviour of Linux kernel including information on configured memory, amount of free and used memory. (memory information) 4. WRITE A PROGRAM to print file details including owner access permissions, file access time, where file name is given as argument. 5. WRITE A PROGRAM to copy files using system calls. 6. Write program to implement FCFS scheduling algorithm. 7. Write program to implement Round Robin scheduling algorithm. 8. Write program to implement SJF scheduling algorithm. 9. Write program to implement non-preemptive priority based scheduling algorithm. 10. Write program to implement preemptive priority based scheduling algorithm. 11. Write program to implement SRJF scheduling algorithm. 12. Write program to calculate sum of n numbers using thread library. 13. Write a program to implement first-fit, best-fit and worst-fit allocation strategies.
