M.Sc. (Computer Science)

MCS-101: Advanced Data Structures Time: 3 Hrs. Max. Marks: 100 Note: (i) The paper setter is required to set eight questions in all and the candidates will be required to attempt any five questions out of these eight questions. All questions will carry equal marks. (ii) The student can use only Non-programmable & Non-storage type calculator. Review of algorithm analysis, Binary search trees, balanced binary search trees (red-black trees), Btrees, AVL Trees, 2-3 trees, 2-3-4 trees. Binary heaps, heap operations, implementation and applications. Priority queue operations, and double-ended priority queues. Binomial heaps, Fibonacci heaps. Data structures for disjoint sets. Amortized analysis, string matching, and graph algorithms. External data structures - external storage, external files, external sorting searching indexing files, external hashing. References: 1. Alfred V. Aho, Jeffrey D. Uuman, John E. Hopcroft, “Data Structures and Algorithms” Addision Wesley, 1983. 2. Dinesh P. Mehta, I. Sartaj Sahni, “Handbook of Data Structures and Applications”, Chapman & Hall/CRC, 2004. 3. Sorenson and Trembley, “An Introduction to Data Structures with Applications, McGraw Hill, 2006 Edition. 4 M.Sc. (Computer Science) (Semester-I) MCS-102: Advanced Computer Architecture Time: 3 Hrs. Max. Marks: 100 Note: (i) The paper setter is required to set eight questions in all and the candidates will be required to attempt any five questions out of these eight questions. All questions will carry equal marks. (ii) The student can use only Non-programmable & Non-storage type calculator. Paradigms of Computing: Synchronous – Vector/Array, SIMD, Systolic Asynchronous – MIMD, reduction Paradigm, Hardware taxanomy: Flynn’s classification, Software taxanomy: Kung’s taxanomy, SPMD. Parallel Computing Models Parallelism in Uniprocessor Systems: Trends in parallel processing, Basic Uniprocessor Architecture, Parallel Processing Mechanism. Parallel Computer Structures: Pipeline Computers, Array Computers, Multiprocessor Systems Architectural Classification Schemes: Multiplicity of Instruction-Data Streams, Serial versus Parallel Processing, Parallelism versus Pipelining Pipelining : An overlapped Parallelism, Principles of Linear Pipelining, Classification of Pipeline Processors, General Pipelines and Reservation Tables References Computer Architecture and Parallel Processing, Faye A. Briggs, McGraw-Hill International, 2007 Edition Computer Systems Organization & Architecture, John d. Carpinelli, Addison Wesley, 2007 Edition. 5 M.Sc. (Computer Science) (Semester-I) MCS-103: Network Design & Performance Analysis Time: 3 Hrs. Max. Marks: 100 Note: (i) The paper setter is required to set eight questions in all and the candidates will be required to attempt any five questions out of these eight questions. All questions will carry equal marks. (ii) The student can use only Non-programmable & Non-storage type calculator. Requirements, planning, & choosing technology: System requirements, traffic sizing characteristics time & delay consideration. Traffic engineering and capacity planning: Throughput calculation traffic characteristics &source models, traditional traffic engineering, queued data & packet switched traffic modeling, designing for peaks, delay or latency Network performance modeling- Creating traffic matrix, design tools, components of design tools, types of design projects. Technology Comparisons- Generic packet switching networks characteristics, private vs. public networking, Business aspects of packet, frame and cell switching services, High speed LAN protocols comparison, Application performance needs, Throughput, burstiness, response time and delay tolerance, selecting service provider, vendor, service levels etc. Access Network Design- N/W design layers, Access N/W design, access n/w capacity, Backbone n/w design, Backbone segments, backbone capacity, topologies, Tuning the network, securing the network, Design for network security. Documentation and network management- Documentation, network management, SNMP, RMON References: 1. James D. McCabe, Network Analysis, Architecture and Design, 2nd Edition, Morgan Kaufman Series in Networking, 2007 Edition. 2. Youeu Zheng, Shakil Akhtar, Network for Computer Scientists and Engineers, Indian University, Oxford University Press, 2007 Edition. 3. A. Forouzan, Data Communications and Networking, Tata McGraw Hill, 2007 Edition. 6 M.Sc. (Computer Science) (Semester-I) MCS-104 Discrete Structures Time: 3 Hrs. Max. Marks: 100 Note: (i) The paper setter is required to set eight questions in all and the candidates will be required to attempt any five questions out of these eight questions. All questions will carry equal marks. (ii) The student can use only Non-programmable & Non-storage type calculator. Sets and Functions: Sets, Relations, Functions, Pigeonhole principle, Inclusion - Exclusion Principle, Equivalence and Partial orderings, Elementary counting techniques, relation of partial order partitions, binary relations. Graph Theory: Definition, Walks, Paths, Directed and Undirected graphs, connected graphs, regular and bipartite graphs, Eulerian chains and cycles. Hamiltonian chains and cycles, planar graphs, Trees and rooted tree, Spanning trees, Chromatic number Connectivity and other graphical parameter application. Combinatorial Mathematics: Basic counting principles Permutations and combinations, Recurrence relations, generating Function, Application. Rings and Boolean algebra: Rings Subrings morphism of rings ideals and quotient rings. Euclidean domains Integral domains and fields Boolean Algebra direct product morphisms Application of Boolean algebra in logic circuits and switching functions. References: 1. Ehrig, H., Mahr, B. Fundamentals of Algebraic Specification I, EATCS Monographs on Theory. Comp. Sc. Vol. 6 spinger, Berlin 1985. 2. Gersting J. Mathematical Structures for Computer Science, W.H. Freman, New York, 1987. 3. Gibons, A. Algorithmic Graph theory Cambridge University Pres, 1985. 4. Knuth, D.E. The art of Computer Programming Vol. I: Fundamental Algorithms. 2nd ed. Reading, Mas, Adison Wesley 1973. 5. Kolman B. Busby R. Discrete Mathematical Structures for Computer Science, Prentice Hall Englewod Clifs. 1987. 6. Sahni, S. Concepts in Discrete Mathematics Fridley MN., Camelot Publ. Comp., 1981. 7. Schmidt G. Strohlein T. Relations Graphs Program, EATS Monograph on Theor. Comp. Sc. Vol. 29 Berlin Spinger 1993. 8. Wheler W. Universal Algebra for Computer S