MCA AND OTHERS - OSMANIA UNIVERSITY III SEM

Design and Analysis of Algorithms

Syllabus

Unit - I

Introduction: 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 - II

Divide 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 - III

Dynamic 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 - IV

Back 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 - V

NP-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.

Database Management Systems

Syllabus

Unit-I

Introduction 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 - II

Relational 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 - III

Overview 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 - IV

Transaction 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 - V

Crash 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.

Operating Systems

Syllabus

Unit-I

Introduction to Operating Systems: OS structure and strategies, Processconcept, Interprocess Communication, Threads, Multithreaded Programming. Process Scheduling: Scheduling Criteria, Scheduling Algorithm, Multiprocessor scheduling, Thread Scheduling.

Unit - II

Memory 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 - III

Process 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 - IV

Device 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 - V

Case 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.

Operations Research

Syllabus

Unit-I

LINEAR PROGRAMMING

Introduction, Concept of linear programming model, Development of LP models, Graphical method, Linear programming methods, Special cases of linear programming, Duality, Sensitivity analysis.

Unit-II

TRANSPORTATION PROBLEM

Introduction, Mathematical model for transportation problem, Types of transportation problem, Methods to solve transportation problem, Transshipment model.

Unit-III

ASSIGNMENT PROBLEM

Introduction, Zero-one programming model, Types of assignment problem, Hungerian method, Branchand- bound technique for assignment problem.

INTEGER PROGRAMMING

Introduction, Integer programming formulations, The cutting-plane algorithm, Branch-and-bound technique, Zero-one implicit enumeration algorithm.

Unit-IV

DYNAMIC PROGRAMMING

Introduction, Applications of dynamic programming, Solution of linear programming problem through dynamic programming.

Unit-V

GAME THEORY

Introduction, Game with pure strategies, Game with mixed strategies, Dominance property, Graphical method for 2 × n or m × 2 games, Linear programming approach for game theory.

Software Engineering

Syllabus

Unit-I

The 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-II

Software 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-III

Planning 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-IV

Coding 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-V

Maintenance 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.