Unit - IIntroduction: What is an algorithm? Algorithm specification, Performance analysis, Randomized algorithms. Elementary Data Structures: Stacks and queues, Trees, Dictionaries, Priority queues, Sets and disjoint set union, Graphs.
Unit - IIDivide and Conquer: Binary search, Finding the maximum and minimum, Merge sort; Quick sort, Selection, Strassens, Matrix multiplication, Convex hull. The Greedy Method: Knapsack problem, Tree vertex splitting, Job sequencing with deadlines, Minimum-cost spanning trees, Optimal storage on tapes, Optimal merge patterns, Single source shortest paths.
Unit - IIIDynamic Programming: General method, Multistage graphs, All-pairs shortest paths. Single-source shorthest paths, Optimal binary search trees, 0/1 knapsack, Reliability design, The traveling salesperson problem. Basic Traversal and Search Techniques: Techniques for binary tress, Techniques for graphs, Connected components and spanning trees, Biconnected components and DFS.
Unit - IVBack Tracking: General method, 8-queens problem, Sum of subsets, Graph coloring, Hamiltonian cycles, Knapsack problem. Branch Bound: The method, 0/1 Knapsack problem, Traveling sales person.
Unit - VNP-Hard and NP-Complete Problems: Basic concepts, Cook’s theorem, NPhard graph problems, NP-hard scheduling problems, NP-hard code generation, Some simplified NP-hard problems.
Unit-IIntroduction to DBMS and ER Model: File systems versus DBMS, Advantages of a DBMS, Database design and E-R diagrams, Entities, Attributes and entity sets, Relationships and relationship sets, Additional features of the ER model, Conceptual design with the ER model. The Relational Model: Introduction to relational model, Integrity constraints over relations, Logical database design (ER to relational), Introduction to views, Destroying/altering tables and views. Schema Refinement and Normal Forms: Schema refinement, Functional dependencies, Normal forms, Normalization, Schema refinement in database design.
Unit - IIRelational Algebra and Calculus: Preliminaries, Relational algebra, Relational calculus, Expressive power of algebra and calculus. SQL: Queries, Constraints, Triggers: The form of basic SQL query, Set operators, Nested queries, Aggregate operators, Null values, Triggers and active databases, Designing active databases, Accessing databases from applications using embedded SQL, Cursors, Dynamic SQL.
Unit - IIIOverview of Storage and Indexing: File organizations and indexing, Index data structures, Comparison of file organizations. Tree-structured Indexing: Indexed Sequential Access Method (ISAM), B+ trees, Search, Insert, Delete, B+ trees in practice. Hash-based Indexing: Static hashing, Extendible hashing, Linear hashing, Extendible versus linear hashing.
Unit - IVTransaction Management: ACID properties, Transactions and schedules, Concurrent execution of transactions, Lock-based concurrency control. Concurrency Control: 2PL, Serializability and recoverability, Introduction to lock management, Dealing with deadlock, Specialized locking techniques, Concurrency control without locking.
Unit - VCrash Recovery: Introduction to ARIES, The log, Other recovery related structures, The WAL, Checkpointing, Recovering from a system crash, Media recovery. Security and Authorization: Introduction to database security, Access control, Discretionary access control, Mandatory access control, Additional issues related to security.
Unit-IIntroduction to Operating Systems: OS structure and strategies, Processconcept, Interprocess Communication, Threads, Multithreaded Programming. Process Scheduling: Scheduling Criteria, Scheduling Algorithm, Multiprocessor scheduling, Thread Scheduling.
Unit - IIMemory Management : Swapping, Contiguous allocation, paging, Static and Dynamic Partition, demand paging, page replacement algorithms, thrashing, segmentation, segmentation with Paging. File System Interface: File Concept, Access Methods, Directory Structure, File System Mounting, File Sharing, Protection. File System Implementation: File-System Structure, File-System Implementation, Directory Implementation, Allocation Methods, and Free Space management, Efficiency and Performance,Recovery.
Unit - IIIProcess Synchronization : Critical Section problem, Semaphores, monitors. Deadlocks: Necessary conditions,resource allocation graph, methods for handling deadlocks, preventions, avoidance, detection and recovery. Protection Goal, domain of protection, access matrix.
Unit - IVDevice Management: Disk Structure, Disk Attachment, Disk Scheduling, Disk Management, Swap Space Management, RAID structure, Stable storage Implementation. I/O System: I/O hardware,Application I/O Interface, Kernel I/O Subsystem. Transforming I/O request to hardware operation. STREAMS.
Unit - VCase Studies Linux System: Design Principles, Kernel Modules, Process Management, Scheduling Memory Management, File Systems, Input and Output, Interprocess Communication, Network Structure, Security. Windows XP: General Architecture. The NT Kernel, The NT Executive.
Unit-IThe Software Problem: Cost, Schedule and quality, Scale and change, Software Processes: Processes and project, Component software processes, Software development process models, Project management process.
Unit-IISoftware Requirements Analysis and Specification: Value of a good SRS, Requirements process, Requirements specification, Functional specification with use cases, Other approaches for analysis. Software Architecture: Role of software architecture views, Component and connector view, Architecture styles for C and C view, Documenting architecture design, Evaluating architectures.
Unit-IIIPlanning a Software Project: Effort estimation, Project schedule and staffing, Quality planning, Risk management planning, Project monitoring plan, Detailed scheduling. Design: Design concepts, Function oriented design, Object oriented design, Detailed design, Verification, Metrics.
Unit-IVCoding and Unit Testing: Programming principles and guidelines, Incrementally developing code, Managing evolving code, Unit testing, Code inspection, Metrics. Testing: Testing concept, Testing process, Black box testing, White box testing, Metrics.
Unit-VMaintenance and Reengineering: Software maintenance, Supportability, Reengineering, Business process reengineering, Software reengineering, Reverse engineering, Restructuring, Forward engineering, Economics of reengineering. Software Process Improvement: Introduction, SPI process, CMMI, PCMM, Other SPI frameworks, SPI return on investment, SPI trends.