ANNA UNIVERSITY, CHENNAI

AFFILIATED INSTITUTIONS

R - 2009
M.E.COMPUTER SCIENCE AND ENGINEERING I SEMESTER (FULL TIME) CURRICULUM AND SYLLABI SEMESTER I SL. COURSE NO CODE THEORY 1 MA9219 2 CS9211 3 CS9212 4 SE9213 5 CS9213 PRACTICAL 6 CS 9215 7 CS9216

COURSE TITLE Operations Research Computer Architecture Data Structures and Algorithms Object Oriented Software Engineering Computer Networks and Management Data Structures Lab Networking Lab TOTAL

L 3 3 3 3 3 0 0 15

T 1 0 0 0 0 0 0 1

P 0 0 0 0 0 3 3 6

C 4 3 3 3 3 2 2 20

MA9219

OPERATIONS RESEARCH

LTPC 3104

UNIT I QUEUEING MODELS 9 Poisson Process Markovian Queues Single and Multi-server Models Littles formula Machine Interference Model Steady State analysis Self Service Queue. UNIT II ADVANCED QUEUEING MODELS 9 Non- Markovian Queues Pollaczek Khintchine Formula Queues in Series Open Queueing Networks Closed Queueing networks. UNIT III SIMULATION 9 Discrete Even Simulation Monte Carlo Simulation Stochastic Simulation Applications to Queueing systems. UNIT IV LINEAR PROGRAMMING 9 Formulation Graphical solution Simplex method Two phase method - Transportation and Assignment Problems. UNIT V NON-LINEAR PROGRAMMING 9 Lagrange multipliers Equality constraints Inequality constraints Kuhn - Tucker conditions Quadratic Programming. L : 45 T: 15 TOTAL : 60 PERIODS TEXT BOOKS: 1. Winston.W.L. Operations Research, Fourth Edition, Thomson Brooks/Cole, 2003. 2. Taha, H.A. Operations Research: An Introduction, Ninth Edition, Pearson Education Edition, Asia, New Delhi, 2002. REFERENCES: 1. Robertazzi. T.G. Computer Networks and Systems Queuing Theory and Performance Evaluation, Third Edition, Springer, 2002 Reprint. 2. Ross. S.M., Probability Models for Computer Science, Academic Press, 2002.

CS9211

COMPUTER ARCHITECTURE

LTPC 3003

UNIT I FUNDAMENTALS OF COMPUTER DESIGN AND PIPELINING 9 Fundamentals of Computer Design Measuring and reporting performance Quantitative principles of computer design. Instruction set principles Classifying ISA Design issues. Pipelining Basic concepts Hazards Implementation Multicycle operations. UNIT II INSTRUCTION LEVEL PARALLELISM WITH DYNAMIC APPROACHES 9 Concepts Dynamic Scheduling Dynamic hardware prediction Multiple issue Hardware based speculation Limitations of ILP Case studies. UNIT III INSTRUCTION LEVEL PARALLELISM WITH SOFTWARE APPROACHES 9 Compiler techniques for exposing ILP Static branch prediction VLIW Advanced compiler support Hardware support for exposing more parallelism Hardware versus software speculation mechanisms Case studies.

UNIT IV MULTIPROCESSORS AND MULTICORE ARCHITECTURES 9 Symmetric and distributed shared memory architectures Performance issues Synchronisation issues Models of memory consistency Software and hardware multithreading SMT and CMP architectures Design issues Case studies. UNIT V MEMORY AND I/O 9 Cache performance Reducing cache miss penalty and miss rate Reducing hit time Main memory and performance Memory technology. Types of storage devices Buses RAID Reliability, availability and dependability I/O performance measures Designing an I/O system. TOTAL : 45 PERIODS REFERENCES: 1. John L. Hennessey and David A. Patterson, Computer Architecture A quantitative approach, Morgan Kaufmann / Elsevier, 4th. edition, 2007. 2. David E. Culler, Jaswinder Pal Singh, Parallel Computing Architecture : A hardware/ software approach , Morgan Kaufmann / Elsevier, 1997. 3. William Stallings, Computer Organization and Architecture Designing for Performance, Pearson Education, Seventh Edition, 2006. 4. Behrooz Parhami, Computer Architecture, Oxford University Press, 2006.

CS9212

DATA STRUCTURES AND ALGORITHMS

LTPC 3 003

UNIT I COMPLEXITY ANALYSIS & ELEMENTARY DATA STRUCTURES 9 Asymptotic notations Properties of big oh notation asymptotic notation with several parameters conditional asymptotic notation amortized analysis NP-completeness NPhard recurrence equations solving recurrence equations arrays linked lists trees. UNIT II HEAP STRUCTURES 9 Min-max heaps Deaps Leftist heaps Binomial heaps Fibonacci heaps Skew heaps Lazy-binomial heaps. UNIT III SEARCH STRUCTURES 9 Binary search trees AVL trees 2-3 trees 2-3-4 trees Red-black trees B-trees splay trees Tries. UNIT IV GREEDY & DIVIDE AND CONQUER 9 Quicksort Strassens matrix multiplication Convex hull - Tree-vertex splitting Job sequencing with deadlines Optimal storage on tapes UNIT V DYNAMIC PROGRAMMING AND BACKTRACKING 9 Multistage graphs 0/1 knapsack using dynamic programming Flow shop scheduling 8queens problem graph coloring knapsack using backtracking TOTAL : 45 PERIODS

REFERENCES: 1. E. Horowitz, S.Sahni and Dinesh Mehta, Fundamentals of Data structures in C++, Galgotia, 1999. 2. E. Horowitz, S.Sahni and S. Rajasekaran, Computer Algorithms / C++, Galgotia, 1999. 3. Adam Drozdex, Data Structures and algorithms in C++, Second Edition, Thomson learning vikas publishing house, 2001. 4. G. Brassard and P. Bratley, Algorithmics: Theory and Practice, Printice Hall, 1988. 5. Thomas H.Corman, Charles E.Leiserson, Ronald L. Rivest, Introduction to Algorithms, Second Edition, PHI 2003.

SE9213

OBJECT ORIENTED SOFTWARE ENGINEERING

LTPC 3 0 03

UNIT I INTRODUCTION 9 System Concepts Software Engineering Concepts Development Activities Managing Software Development Unified Modeling Language Project Organization Communication UNIT II ANALYSIS 9 Requirements Elicitation Concepts Activities Management Analysis Object Model Analysis Dynamic Models UNIT III SYSTEM DESIGN 9 Decomposing the system Overview of System Design System Design Concepts System Design Activities Addressing Design Goals Managing System Design UNIT IV OBJECT DESIGN AND IMPLEMENTATION ISSUES Reusing Pattern Solutions Specifying Interfaces Mapping Models to Code Testing 9

UNIT V MANAGING CHANGE 9 Rationale Management Configuration Management Project Management Software Life Cycle TOTAL : 45 PERIODS REFERENCES: 1. Bernd Bruegge, Alan H Dutoit, Object-Oriented Software Engineering, 2nd ed, Pearson Education, 2004. 2. Craig Larman, Applying UML and Patterns, 3rd ed, Pearson Education, 2005. 3. Stephen Schach, Software Engineering 7th ed, McGraw-Hill, 2007.

CS9213

COMPUTER NETWORKS AND MANAGEMENT

LTPC 3 003

UNIT I HIGH SPEED NETWORKS 9 Frame Relay Networks Asynchronous transfer mode ATM Protocol Architecture, ATM logical Connection, ATM Cell ATM Service Categories AAL. High Speed LANs: Fast Ethernet, Gigabit Ethernet, Fibre Channel Wireless LANs. UNIT II CONGESTION AND TRAFFIC MANAGEMENT 9 Queuing Analysis- Queuing Models Single Server Queues Effects of Congestion Congestion Control Traffic Management Congestion Control in Packet Switching Networks Frame Relay Congestion Control. UNIT III TCP AND ATM CONGESTION CONTROL 10 TCP Flow control TCP Congestion Control Retransmission Timer Management Exponential RTO backoff KARNs Algorithm Window management Performance of TCP over ATM. Traffic and Congestion control in ATM Requirements Attributes Traffic Management Frame work, Traffic Control ABR traffic Management ABR rate control, RM cell formats, ABR Capacity allocations GFR traffic management. UNIT IV INTEGRATED AND DIFFERENTIATED SERVICES 9 Integrated Services Architecture Approach, Components, Services- Queuing Discipline, FQ, PS, BRFQ, GPS, WFQ Random Early Detection, Differentiated Services. UNIT V PROTOCOLS FOR QoS SUPPORT 8 RSVP Goals & Characteristics, Data Flow, RSVP operations, Protocol Mechanisms Multiprotocol Label Switching Operations, Label Stacking, Protocol details RTP Protocol Architecture, Data Transfer Protocol, RTCP. TOTAL : 45 PERIODS TEXT BOOKS: 1. William Stallings, HIGH SPEED NETWORKS AND INTERNET, Pearson Education, Second Edition, 2002. REFERENCES: 1. Warland & Pravin Varaiya, HIGH PERFORMANCE COMMUNICATION NETWORKS, Jean Harcourt Asia Pvt. Ltd., II Edition, 2001. 2. Irvan Pepelnjk, Jim Guichard and Jeff Apcar, MPLS and VPN architecture, Cisco Press, Volume 1 and 2, 2003.

CS9215

DATA STRUCTURES LAB

LTPC 0032

1. Min Heap 2. Deaps 3. Leftist Heap 4. AVL Tree 5. B-Tree 6. Tries 7. Quick Sort 8. Convex hull 9. 0/1 Knapsack using Dynamic Programming 10. Graph coloring using backtracking TOTAL : 45 PERIODS

CS9216

NETWORKING LAB

LTPC 0032

1. Socket Programming a. TCP Sockets b. UDP Sockets c. Applications using Sockets 2. Simulation of Sliding Window Protocol 3. Simulation of Routing Protocols 4. Development of applications such as DNS/ HTTP/ E mail/ Multi - user Chat 5. Simulation of Network Management Protocols 6. Study of Network Simulator Packages such as opnet, ns2, etc. TOTAL : 45 PERIODS