# Computer Science

Sr. No. Core Areas Percentage

1. Programming Fundamentals 06%

2. Object Oriented Paradigm 05%

3. Discrete Structures 05%

4. Data Structures and Algorithms 09%

5. Digital Logic and Computer Organization 06%

6. Operating Systems 06%

7. Database Systems 07%

8. Software Engineering & Development 05%

9. Computer Communication and Networks 06%

10. Computer Architecture & Assembly Language 08%

11. Theory of Automata and Formal Languages 10%

12. Analysis of Algorithms 10%

13. Artificial Intelligence 07%

14. System Programming 05%

15. Numerical Computing 05%

Total 100%

# Computer Science (Detailed)

Sr. No. Core Areas Percentage

1.

PROGRAMMING FUNDAMENTALS:

Overview of computers and programming.Overview of language.Basics of structured and Modular programming.Basic Algorithms and problem solving, development of basic algorithms, analyzing problem, designing solution, testing designed solution. Fundamental programming constructs, translation of algorithms to programmes, data types, control structures, functions, arrays, records, files, testing programmes.

6%

2.

OBJECT ORIENTED PARADIGM:

Evolution of Object Oriented (OO) programming, OO concepts and principles, problem solving in OO paradigm, OO programme design process, classes, methods, objects and encapsulation; constructors and destructors, operator and function overloading, virtual functions, derived classes, inheritance and polymorphism. I/O and file processing, exception handling.

5%

3.

DISCRETE STRUCTURES:

Introduction to logic and proofs: Direct proofs; proof by contradiction, Sets, Combinatronics, Sequences, Formal logic, Prepositional and predicate calculus, Methods of Proof, Mathematical Induction and Recursion, loop invariants, Relations and functions, Pigeonhole principle, Trees and Graphs, Elementary number theory, Optimization and matching. Fundamental structures: Functions; relations (more specifically recursions); pigeonhole principle; cardinality and countability, probabilistic methods.

5%

4.

DATA STRUCTURES AND ALGORITHMS:

Introduction to data structures; Arrays, Stacks, Queues, Priority Queues, Linked Lists, Trees, Spanning Trees, Graphs and Traversals. Recursion, sorting and searching algorithms, Shortest path algorithms, Hashing, Storage and retrieval properties and techniques for the various data structures. Algorithm Complexity, Polynomial and Intractable Algorithms, Classes of Efficient Algorithms, Divide and Conquer, Dynamic, Greedy 9%

5.

DIGITAL LOGIC AND COMPUTER ORGANIZATION:

5.1 Digital Logic_______________________________________3%

Overview of Binary Numbers, Boolean Algebra, switching algebra, and logic gates, Karnaugh Map and Quin-McCluskey methods, simplification of Boolean functions, Combinational Design; two level NAND/NOR implementation, Tabular Minimization, Combinational Logic Design: adders, subtracters, code converters, parity checkers, multilevel NAND/NOR/XOR circuits, MSI Components, design and use of encoders, decoders, multiplexers, BCD adders, and comparators, Latches and flip-flops, Synchronous sequential circuit design and analysis, Registers, synchronous and asynchronous counters, and memories, Control Logic Design.

# 5.2 Computer Organiztion________________________________3%

Fundamentals of Computer Designincluding performance measurements & quantitative principles, principles of Instruction Set Design, Operands, addressing modes and encoding, pipelining of Processors: Issues and Hurdles, exception handling features, Instruction-Level Parallelism and Dynamic handling of Exceptions, Memory Hierarchy Design, Cache Design, Performance Issues and improvements, Main Memory Performance Issues, Storage Systems, Multiprocessors and Thread Level Parallelism. 6%

6.

OPERATING SYSTEMS:

History and Goals, Evolution of multi-user systems, Process and CPU management, Multithreading, Kernel and User Modes, Protection, Problems of cooperative processes, Synchronization, Deadlocks, Memory management and virtual memory, Relocation, External Fragmentation, Paging and Demand Paging, Secondary storage, Security and Protection, File systems, I/O systems, Introduction to distributed operating systems. Scheduling and dispatch, Introduction to concurrency.

6%

7.

DATABASE SYSTEMS:

Basic database concepts; Entity Relationship modelling, Relational data model and algebra, Structured Query language; RDBMS; Database design, functional dependencies and normal forms; Transaction processing and optimization concepts; concurrency control and recovery techniques; Database security and authorization. Physical database design: Storage and file structure; indexed files; b-trees; files with dense index; files with variable length records; database efficiency and tuning.

7%

8.

SOFTWARE ENGINEERING AND DEVELOPMENT:

Introduction to Computer-based System Engineering; Project Management; Software Specification; Requirements Engineering, System Modelling; Requirements Specifications; Software Prototyping; Software Design: Architectural Design, Object-Oriented Design, UML modelling, Function-Oriented Design, User Interface Design; Quality Assurance; Processes & Configuration Management; Introduction to advanced issues: Reusability, Patterns; Assignments and projects on various stages and deliverables of SDLC. 5%

9.

COMPUTER COMMUNICATION AND NETWORKS:

Analogue and digital Transmission, Noise, Media, Encoding, Asynchronous and Synchronous transmission, Protocol design issues. Network system architectures (OSI, TCP/IP), Error Control, Flow Control, Data Link Protocols (HDLC, PPP). Local Area Networks and MAC Layer protocols (Ethernet, Token ring), Multiplexing, Switched and IP Networks, Inter-networking, Routing, Bridging, Transport layer protocols TCP/IP, UDP. Network security issues. Programming exercises, labs or projects involving implementation of protocols at different layers. 6%

10.

COMPUTER ARCHITECTURE AND ASSEMBLY LANUGUAGE:

Microprocessor Bus Structure: Addressing, Data and Control, Memory Organization and Structure (Segmented and Linear Models), Introduction to Registers and Flags, Data Movement, Arithmetic and Logic, Programme Control, Subroutines, Stack and its operation, Peripheral Control Interrupts.

Objectives and Perspectives of Assembly Language, Addressing Modes, Introduction to the Assembler and Debugger, Manipulate and translate machine and assembly code. Interfacing with high level languages, Real-time application. 8%

11.

# THEORY OF AUTOMATA AND FORMAL LANGUAGES:

Finite State Models: Language definitions preliminaries, Regular expressions/Regular languages, Finite automata (FAs), Transition graphs (TGs), NFAs, Kleene’s theorem, Transducers (automata with output), Pumping ¬¬¬¬¬¬¬lemma and non regular language Grammars and PDA: Context free grammars, Derivations, derivation trees and ambiguity, Simplifying CFLs , Normal form grammars and parsing, Decidability, Chomsky’s hierarchy of grammars Turing Machines Theory: Turing machines, Post machine, Variations on TM, TM encoding, Universal Turing Machine, Context sensitive Grammars, Defining Computers by TMs. 10%

12.

ANALYSIS OF ALGORITHMS:

Asymptotic notations; Recursion and recurrence relations; Divide-and-conquer approach; Sorting; Search trees; Heaps; Hashing; Greedy approach; Dynamic programming; Graph algorithms; Shortest paths; Network flow; Disjoint Sets; Polynomial and matrix calculations; String matching; NP complete problems; Approximation algorithms

10%

13.

ARTIFICIAL INTELLIGENCE:

Artificial Intelligence: Introduction, Intelligent Agents. Problem-solving: Solving Problems by Searching, Informed Search and Exploration, Constraint Satisfaction Problems, Adversarial Search. Knowledge and reasoning: Logical Agents, First-Order Logic, Inference in First-Order Logic, Knowledge Representation. Planning and Acting in the Real World. Uncertain knowledge and reasoning: Uncertainty, Probabilistic Reasoning, Probabilistic Reasoning over Time, Making Simple Decisions, Making Complex Decisions. Learning: Learning from Observations, Knowledge in Learning, Statistical Learning Methods, Reinforcement Learning. Communicating, perceiving, and acting: Communication, Probabilistic Language Processing, Perception and Robotics. Introduction to LISP/PROLOG and Expert Systems (ES) and Applications.

7%

14.

SYSTEM PROGRAMMING:

System Programming overview: Application Vs. System Programming, System Software, Operating System, Device Drivers, OS Calls. Window System Programming for Intel386 Architecture: 16 bit Vs 32 bit, Programming, 32 bit Flat memory model, Windows Architecture. Virtual Machine (VM)Basics, System Virtual Machine, Portable Executable Format, Ring O Computer, Linear Executable format, Virtual Device Driver (V + D), New Executable format, Module Management, COFF obj format 16 bit. (Unix) other 32-bit O.S Programming for I 386; Unix Binaryble format (ELF), Dynamic shared objects, Unix Kernel Programming (Ring O), Unix Device Architecture (Character & Block Devices), Device Driver Development, Enhancing Unix Kernel. 5%

15.

NUMERICAL COMPUTING:

The concepts of efficiency, reliability and accuracy of a method.Minimising computational errors.Theory of Differences, Difference Operators, Difference Tables, Forward Differences, Backward Differences and Central Differences. Mathematical Preliminaries, Solution of Equations in one variable, Interpolation and Polynomial Approximation, Numerical Differentiation and Numerical Integration, Initial Value Problems for Ordinary Differential Equations, Direct Methods for Solving Linear Systems, Iterative Techniques in Matrix Algebra, Solution of non-linear equations. 5%

Total 100%

Sherban

hi