Practic Mode Paper-II & III

Topic List

1 . Discrete Structures
Sets, Relations, Functions, Pigeonhole Principle, Inclusion-Exclusion Principle, Equivalence and Partial Orderings, Elementary Counting Techniques. Probability, Measure(s) for information and Mutual information. Computability : Models of computation-Finite Automata, Pushdown Automata. Non-determinism and NFA, DPDA and PDAs and Languages accepted by these structures. Grammars, Languages, Non-computability and Examples of non-computable problems. Graph : Definition, walks, paths, trails, 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. Central Graphs. Centre(s) of a tree. Hamiltonian and Eulerian graphs, Planar graphs. Groups : Finite fields and Error correcting/detecting codes.

2 . Computer Arithmetic
Propositional (Boolean) Logic, Predicate Logic, Well-formed-formulae (WFF), Satisfiability and Tautology. 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.

3 . Programming in C
Programming in C : Elements of C-Tokens, identitiers, data types in C. Control structures in C. Sequence, selection and iteration(s), Structured data types in C arrays, struct, union, string and pointers.

4 . O-O Programming Concepts with C++
Class, object, instantiation, Inheritance, polymorphism and overloading. 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.

5 . Relational Database Design and SQL
E R diagrams and their transformation to relational design, normalization-1NF, 2NF, 3NF, BCNF and 4NF. Limitations of 4NF and BCNF. SQL : Data Definition language (DDL), Data Manipulation Language (DML), Data Control language (DCL) commands. Database objects like-Views, indexes, sequences, synonyms, data dictionary.

6 . Data and File structures
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 lists and multi-lists B trees and B+ trees.

7 . Computer Networks
Network fundamentals : Local Area Networks (LAN), Metropolitan Area Networks (MAN), Wide Area Networks (WAN), Wireless Networks, Inter Networks. Reference Models : The OSI model, TCP/IP model. Data Communication : Channel capacity, Transmission Media-twisted pair, coaxial cables, fibre-optic cables, wireless transmission-radio, microwave infrared and millimeter waves. Lightwave transmission, Thelephones-local loop, trunks, multiplexing, switching, narrowband ISDN, broadband ISDN, ATM, High speed LANS, Cellular Radio. Communication satellitesgeosynchronous and low-orbit. Internetworking : Switch/Hub, Bridge, Router, Gateways, Concatenated virtual circuits, Tunnelling, Fragmentation, Firewalls. Routing : Virtual circuits and datagrams, Routing algorithms, Conjestion control. Network Security : Cryptography-public key, secret key, Domain Name System (DNS)-Electronic Mail and Worldwide Web (WWW), The DNS, Resource Records, Name servers, E-mail architecture and Serves.

8 . System Software and Compilers
Assembly language fundamentals (8085 based assembly language programming). Assemblers- 2 pass and single-pass. Macros and macroprocessors. Loading, linking, relocation, program relocatability, Linkage editing. Text editors, Programming Environments, Debuggers and program generators. Compilation and Interpretation. Bootstrap compilers. Phases of compilation process. Lexical analysis. Lex package on Unix system. Context free grammars, Parsing and parse trees, Representation of parse (derivation) trees as rightmost and left most derivations. Bottom up parsers-shift-reduce, operator precedence, and LR, YACC package on Unix system. Topdown parsers-left recursion and its removal, Recursive descent parser. Predictive parser, Intermediate codes-Quadruples, Triples, Intermediate code generation, Code generation, Code optimization.

9 . 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. Introduction, Memory management, Support for concurrent process, Scheduling, System deadlock, Multiprogramming system, I/O management, Distributed operating systems.

10 . Software Engineering
System Development Life Cycle (SDLC) : Steps, Water fall model, Prototypes, Spiral model. Software Metrics : Software Project Management. Software Design : System design, detailed design, function oriented design, object oriented design, user interface design. Design level metrics. Coding and testing : Testing level metrics, Software quality and reliability, Clean room approach, software reengineering.

11 . Current Trends and Technologies
Parallel Computing, Mobile Computing, Electronic Commerce : Framework, Media Convergence of Applications, Consumer Applications, Organisation Applications.
Electronic Payment Systems , Electronic Data Interchange (EDI), Digital Libraries and Data Warehousing.
Software Agents, Broadband Telecommunications, Data Warehousing, Data Mining.

12 . Web Technology
Object, messages, classes, encapsulation, inheritance, polymorphism aggregation, abstract classes generalization as extension and restriction, Object oriented design. Multiple inheritance, metadata. HTML, DHTML, XML, Scripting, Java, Servelets, Applets.

13 . Unix
The Unix System : File system, process management, bourne shell shell variables, command line programming. Filters and Commands : Pr, head, tail, cut, paste, sort, uniq, tr, join, etc., grep, egrep, fgrep, etc., sed, awk, etc. System Calls (like) : Creat, open, close, read, write, iseek, link, unlink, stat, fstat, umask, chmod, exec, fork, wait, system.

14 . Theory of Computation
Finite Automata, Pushdown Automata, Non-determinism and NFA, DPDA, and PDAs and languages accepted by these structures. Grammars, Languages-types of grammars-type 0, type 1, type 2 and type 3. The relationship between types of grammars, and finite machines. Pushdown automata and Context Free Grammars. Lexical Analysis-regular expressions and regular languages, LEX package on Unix. Conversion of NFA to DFA. Minimizing the number of states in a DFA. Compilation and Interpretation. Bootstrap compilers. Context free grammars, Parsing and parse trees. Representation of parse (derivation) trees as rightmost and leftmost derivations. Bottom up parsers-shift-reduce, operator precedence, and LR, YACC package on Unix system. Topdown parsers-left recursion and its removal. Recursive descent parser. Predictive parser, Intermediate codes-Quadruples, triples, Intermediate code generation, code generation, Code optimization.Theory of Computation : Formal language, Need for formal computational models, Noncomputational problems, diagonal argument and Russel’s paradox. Deterministic Finite Automaton (DFA), Non-deterministic Finite Automaton (NFA), Regular languages and regular sets. Equivalence of DFA and NFA. Minimizing the number of states of a DFA. Non-regular languages and Pumping lemma. Pushdown Automaton (PDA), Deterministic Pushdown Automaton (DPDA), Non-equilvalence of PDA and DPDA. Context free Grammars : Greibach Normal Form (GNF) and Chomsky Normal Form (CNF), Ambiguity, Parse Tree Representation of Derivations, Equivalence of PDA’s and CFG’s. Parsing techniques for parsing of general CFG’s-Early’s, Cook-Kassami-Younger (CKY) and Tomita’s parsing. Linear Bounded Automata (LBA) : Power of LBA. Closure properties. Turing Machine (TM) : One tape, multitape. The notions of time and space complexity in terms of TM, Construction of TM for simple problems. Computational complexity. Chomsky Hierarchy of languages : Recursive and recursively-enumerable languages.

15 . Computer Graphics
Display systems, Input devices, 2D Geometry, Graphic operations, 3D Graphics, Animation, Graphic standard, Applications. Concepts, Storage Devices, Input Tools, Authoring Tools, Application, Files.

16 . Artificial Intelligence
Definitions, AI approach for solving problems. Automated Reasoning with propositional logic and predicate logic-fundamental proof procedure, refutation, resolution, refinements to resolution (ordering/pruning/restriction strategies). State space representation of problems, bounding functions, breadth first, depth first, A, A*, AO*, etc. Performance comparison of various search techniques. Frames, scripts, semantic nets, production systems, procedural representations, Prolog programming. Components of an expert system, Knowledge representation and Acquisition techniques, Building expert system and Shell. RTNs, ATNs, Parsing of Ambiguous CFGs. Tree Adjoining Grammars (TAGs). Systems approach to planning, Designing, Development, Implementation and Evaluation of MIS.

17 . Computer Organisation
Computer Ogranisation