| Discrete Structures |
| Sets, Relations, Functions. Pigeonhole Principle, Inclusion-Exclusion principle, Equivalence and Partial Orderings. Elementary Counting Techniques. |
| Computability: Models of computation – Finite Automata, Pushdown Automata, Non-determinism and NFA, DPDA and PDA s and Languages accepted by these structures. Grammars – types of grammars – type 0 , type I, type 2 and type 3. The relationship between types of grammars, Languages, Non-computability, Non-computable problems. |
| Groups: Finite fields and Error correcting / detecting codes. |
| Propositional logic. Predicate logic. Well-formed formulae (WFF). Satisfiability and Tautology. |
| Computer Arithmetic |
| Logic families: TTL, ECL and C-MOS gates. Boolean algebra and Minimization of Boolean functions, Flip-flops- types, race condition and comparison, Design of combinational and sequential circuits |
| Representation of Integers: Octal. Hex. Decimal and Binary 2’s complement and 1’s complement arithmetic. Floating point representation. |
| Programming in C and C++ |
| Programming in C: Elements of C – Tokens, identifiers, data types in C, Control constructs in C, Sequence, selection and iteration. Structured data types in C – arrays, structs, unions, strings and pointers. |
| Object-Oriented programming Concepts: Class – object, instantiation, Inheritance -polymorphism and overloading, aggregation, abstract classes, generalization as extension and restriction. Object oriented design. Multiple inheritance |
| C++ – programming: Elements of C++ – Tokens, Identifiers, Variables and constants. Data types, Operators. Control statements, Functions, parameter passing, Class and objects, Constructors and destructors, Overloading, Inheritance, Templates, Exception handling. |
| Relational Database Design and Query Languages |
| E-R diagrams, Transformation of E-R models to relational design, Normalization – INF, 2NF, 3NF, BCNF and 4NF. |
| SQL: Data Definition Language (DDL), Data Manipulation Language (DML), Data Control Language (CDL) Commands. Database objects like- Views, indexes, sequences, synonyms, data dictionary, Embedded SQL, QBE |
| Query Processing and Optimization, Centralized and Distributed Database, Security, Concurrency and Recovery in Centralized and Distributed Database Systems, Object Oriented Database Management Systems – Concepts, Composite objects, Integration with RDBMS applications. |
| Data Structures and Algorithms |
| Data, Information. Definition of data structure, Arrays, stacks, queues, linked lists, trees, graphs, priority queues and heaps. |
| File Structures: Fields, records and files. Sequential, direct, index-sequential and relative files. Hashing, inverted list and multi-lists, B-trees and B+ trees. |
| Graphs: Definition, walks, paths, connected graphs, regular and bipartite graphs, cycles and circuits. Tree and rooted tree, Spanning trees, Eccentricity of a vertex radius and diameter of a graph, Hamiltonian and Eulerian graphs. Planar graphs. |
| Sorting and Searching Algorithms, Analysis of Algorithms, Interpolation and Binary Search. Asymptotic notations – big oh. Omega and theta. Average case analysis of simple programs like finding of a maximum of n elements. Recursion. Quick sort. |
| Design of Algorithms (Divide and Conquer. Greedy method. Dynamic programming. Back tracking. Branch and Bound). |
| Data Communication and Computer Networks |
| Data Communication: Analog and Digital transmission. Asynchronous and Synchronous Transmission. Transmission media. Multiplexing and Concentration, Switching techniques. Polling. Channel capacity. Transmission media – twisted pair, coaxial cables, fiber-optic Cables, wireless transmission- radio, microwave and infrared waves. Light wave Transmission. Telephones – local loop, trunks, multiplexing, switching, narrowband ISDN, Broadband ISDN. ATM, High speed LANs. Cellular Radio, Communication satellites-geosynchronous and low-orbit. |
| Reference Models: The OSI model, TCP/IP model. |
| Topologies, Networking Devices. Protocols for – (i) Data link layer (ii) Network layer, and(iii) Transport layer, TCP/IP protocols, Networks security and Network administration. |
| Local Area Networks (LAN), Metropolitan Area Networks (MAN), Wide Area Networks (WAN). Wireless Networks, Inter Networks. |
| Internetworking: Switch/Hub. Bridge. Router. Gateways. Concentrated virtual circuits.Tunneling, Fragmentation. Firewalls. |
| Routing: Virtual circuits and datagrams. Routing Algorithms. Congestion control. |
| Network Security: Cryptography – public key, secret key, Domain Name System (DNS) – Electronic Mail and World Wide Web {WWW). The DNS, Resource Records. Name servers. E-mail architecture and E-mail Servers. |
| System Software and Compilers |
| Assembly language fundamentals (8085 and 8088 based assembly language programming).Assemblers – 2-pass and single-pass. Macros and macro processors. |
| Loading, linking, relocation, program relocatability. Linkage editing. |
| Text editors, Programming Environments. Debuggers and program generators. |
| Compilation and Interpretation. Bootstrapping. Phases of compilation. Lexical analysis. LEX. |
| Context free grammars. Parsing and parse trees. Representation of parse trees and rightmost and leftmost derivations, Bottom up parsers – shift-reduce. operator precedence and LR. YACC. |
| Top down parsers – left recursion and its removal. Recursive descent parser. Predictive parser. Intermediate codes – Quadruples, Triples. Indirect Triples. Intermediate code generation, Code generation, Code optimization. |
| Operating Systems |
| Main functions of operating systems. Multiprogramming, multiprocessing and multitasking. |
| Memory management; Virtual memory, paging, fragmentation. |
| Concurrent processing: Mutual exclusion. Critical regions, lock and unlock. |
| Scheduling: CPU scheduling. I/O Scheduling. Resource scheduling. Deadlock and scheduling algorithms. Banker’s algorithm for deadlock handling. |
| The Unix system: File system, process management. Bourne shell, shell variables, command line programming. |
| Systems Calls: Creat, open, close, read, write. Iseek, link, unlink, stat, fstat, umask, chmod, exec, fork, wait, system. |
