For any student of Computer Sc he/she must be excelled in:
Discrete Structures
Sets,
relation, Functions,
Pigeonhole Principle,
inclusion-Exclusion Principle, Equivalence and Partial orderings,
elementary counting techniques, Probability, Measure(s) for Information
and total information.
Compatibility
Model of computation-Finite Automata, Pushdown Automata,
Non-determinism and NFS, DPDA and PDAs and languages accepted by these
structure, Grammars languages, non compatibility and example of non
computable problems
Graph
Definitions 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, centers of a tree, Hamiltonian and Eulerian graphs, planar
graphs
Group
Finite field and error correcting / detecting codes
Computer Arithmetic
Propositional (Boolean), 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
Programming in C and C++
Programming in C
Elements of C: Tokens, identifiers, data types in C.
Control structures in C: Sequence, selection and iteration(s).
Structured data types in C: arrays, struct, union, string, and pointers
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 SQL
Relational Database Design
E-R Diagrams and their transformation to relation design, normalization- INF, 2NF, 3NF 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.
Data and File Structures
File Strucure
Fields, records and files.
Sequential, direct, index-sequential and relative files.
Hashing, inverted lists and multi-lists. B trees and B+ trees
Computer Networks
Network Fundaments
Local area Network (LAN), metropolitan Area Network(MAN), Wide area Network(WAN), Wireless Network, Inter Network
Reference Model
The OSI model, TCP/IP model
Data Communication
Channel capacity. Transmission media- Twisted pair, Coaxial cables,
Fiber optic cables, Wireless transmission- radio, microwave, infrared
and millimeter waves. Light wave transmission. Telephones- local loop,
trunks, multiplexing, switching, narrowband ISDN, broadband ISDN, ATM,
High speed LANS, Cellular radio Communication. satellite- Geosynchronous
and low-orbit
Internetworking
Switch/Hub, Bridge, router, Gateways Concatahetsd 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)-
Electronics mail and worldwide web (WWW). The DNS Resource Records, Name
Services. E-Mail Architecture and Servers
System Software and Compilers
Assembly language fundamentals (8085 based assembly language
programming). Assemblers- two-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. 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 leftmost derivations. Bottom up
parsers- shift-reduce, operator precedence. and LR. YACC package on
Unix system
Top-down parsers- left recursion and its removal. Recursive descent
parser. Predictive parser, Intermediate codes- Quadruples, Triples,
Intermediate code generation, Code generation, Code optimization
Operating Systems & Unix Case Study
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, borne 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.
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
Mobile Computing
Mobile connectivity- Cells, Framework, Wireless delivery technology
and switching methods, mobile information access devices, mobile data
internetworking standards, cellular data communication protocols,
mobile, computing applications. Mobile databases- protocols, scope,
tools and technology. M-business.
Simple Applications (in windows)
Scrolling, splitting views, docking toolbars, status bars, common dialogs.
Advanced Windows Programming
Multiple Document Interface (MDI), Multithreading. Object linking and
Embedding (OLE). Active X controls. Active Template Library (ATL).
Network programming.
Digital Systems and Microprocessors
Digital Systems
Combinational Circuit Design, Sequential Circuit Design, Hardwired
and Microprogrammed processor design, Instruction formats, Addressing
modes, Memory types and organisation, Interfacing peripheral devices,
Interrupts
Microprocessors
Microprocessor architecture, Instruction set and Programming (8085, P-III/P-IV). Microprocessor applications
Data Base Management Systems
Database Concepts. ER diagams, Data Models, Design of Relational
Database, Normalisation, SQL and QBE, Query Processing and Optimisation,
Centralised and Distributed Database, Security, Concurrency and
Recovery in Centralised and Distributed Database Systems, Object
Oriented Database Management Systems (Concepts, Composite objects.
Integration with RDBMS applications), ORACLE
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
Programming Concepts
Programming language , concepts, Paradigm and models.
Data,
Data types, Operators, Expressions, Assignments , Flow of
control-Control Structure, I/O Statement, User Defined and Built in
Function parameter passing
Principles , classes, inheritance, Class hierarchies, polymorphism, Dynamic binding, reference semantics and their implementation
Principles, functions, lists, types and polymorphism, higher order functions lazy evaluation equations and pattern matching
Principles , horn clauses and their execution, logical variables relations,
data structure, Controlling the search order, programme development in prolog implementation of prolog, example programme in prolog
Principle of parallelism co routines, Communication and execution,
Parallel virtual Machine (PVM) and message passing interface (MPI),
routine an calls , Parallel programmes in PVM paradigm a swell as MPI,
paradigm for simple problems like matrix multiplication
Preconditions , post conditions, axiomatic approaches for semantic, corrections denotation semantics
Complier structure, Compiler construction tools, coalition phases.
Finite Automata, Pushdown Automata, Non-Determinations, and NFA, DPDA
and PDAs and language accepted by these structure, Grammars,
language-Types of grammar-type,0, type 1, tope 2, type 3, The
relationship between types of grammars, and finite machine, Pushdown
automata and context free Framers, Lexical Analysis-regular express and
regular languages.LEX pacemaker on UNIX, Conversion of NFA to DFA
minimizing the number of states in a DFA, Compilation an interpretation
Bootstrap Compilers.
Context free grammars, Parsing and parse trees, representation of
parse trees as rightmost ma leftmost derivation. Bottom up parsers-shift
reduce, operator precedence an LR, YACC package on UNIX, system, Top
down parsers-Left recursion and its removal , recursive descent Parsers,
Predictive parser Intermediate codes-Quadruples, triples, Intermediate
code generation, Code generation , Code optimization
Data Communication and Networks
Data Communication
Analog and Digital transmission, Asynchronous and Synchronous
transmission, Transmission media, Multiplexing and Concentration,
Switching techniques, Polling
Networks
Topologies, Networking Devices, OSI Reference Model, Protocols for
(i) Data link layer, (ii) Network layer, and (iii) Transport layer,
TCP/IP protocols, Networks security; Network administration
Data Structures and Algoritms
Data Structures
Definition, Simple and Composite structures ,
Arrays, Lists,
Stacks,
queues, Priority queues, Binary trees, B-trees, Graphs
Sorting and Searching Algorithms
Sorting
and Searching Algorithms, Analysis of Algorithms, Interpolation and
Binary Search, Asymptotic notations-big ohm, omega and theta. Average
case analysis of simple programs like finding of a maximum of n
elements. Recursion and its systematic removal. Quicksort- Non-recursive
implementation with minimal stack storage
Design of Algorithms
Design of Algorithms (Divide and Conquer, Greedy method, Dynamic
programming, Back tracking, Branch and Bound). Lower bound theory.
Non-deterministic algorithm
Non-deterministic programming constructs. Simple non-deterministic programs. NP-hard and NP-complete problems
OOP and Web Technologies
Object Oriented Programming
Object, messages,
classes,
encapsulation,
inheritance,
polymorphism,
aggregation, abstract classes, generalization as extension and restriction. Object oriented design. Multiple inheritance, metadata
Web Technologies
HTML, DHTML, XML, Scripting, Java,
Servlets,
Applets
Advanced Software Engineering
Software development models, Requirement analysis and
specifications, Software design, techniques and tools, Software
validation and quality assurance techniques, Software maintenance and
advanced concepts, Software management
Operating Systems
Introduction, Memory management, Support for concurrent process,
Scheduling, System deadlock, Multiprogramming system. 1/0 management,
Distributed operating systems, Study of Unix and Windows NT
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, Butlding expert system and Shell
RTNS. ATNS, Parsing of Ambiguous CFG's. Tree Adjoining Grammars
(TAGs). Systems approach to planning, Designing; Development,
Implementation and evaluation of MIS
Decision-making processes, evaluation of DSS, Group decision
support system and case studies; Adaptive design approach to DSS
development, Cognitive style in DSS, Integrating expert and Decision
support systems
Finite Automata and Formal Languages
Theory of Computation
Formal language, Need for formal computational models, Non-computational problems, diagonal argument and Russel's paradox.
Deterministic Finite Automaton
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
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.
Information Theory and Coding
Model for C Information Channel
Discrete Memoryless Channel, Binary Symmetric Channel (BSC), Burst
Channel, Bit-error rates. Probability, Entropy and Shanno's measure of
information. Mutual information. Channel capacity theorem. Rate and
optimality of information transmission
Variable Length Codes
Prefix codes. Huffman Codes, Lempel-ziev (LZ) codes. Optimality of these codes. Information content of these codes
Error Correcting and Detecting Codes
Finite fields, Hamming distance, Bounds of codes, Linear (Parity
Check) codes, Parity check matrix, Generator matrix, Decoding of linear
codes, Hamming codes
Image Processing
Image Registration, Spatial Fourier Transforms, Discrete Spatial
(2-dimensional) Fourier transforms, Restoration, Lossy Compression of
images (pictures)
Data Compression Techniques
Representation and compression of text, sound, picture, and video files (based on the JPEG and MPEG standards)
Operation Research
Linear Programming Problem
Linear Programming Problem (LPP) in the standard form, LPP in
Canonical form. Conversion of LPP in Standard form to LPP in Canonical
form. Simplex-Prevention of cyclic computations in Simplex and Tableau,
Big-M method, dual simplex and revised simplex. Complexity of simplex
algorithm(s). Exponential behaviour of simplex. Ellipsoid method and
Karmakar's method for solving LPPs. Solving simple LPPs through these
methods. Comparison of complexity of these methods
Assignment and Transportation Problems
Simple algorithms like Hungarian method, etc
Shortest Path Problems
Dijkstra's and Moore's method. complexity
Network Flow Problem
Formulation. Max-Flow Min-Cut theorem. Ford and Fulkersons algorithm.
Exponential behaviour of Ford and Fulkerson's algorithm.
Malhotra-Pramodkumar-Maheshwari (MPM) Polynomial algorithm for solving
Network flow problem. Bipartlte Graphs and Matchings; Solving matching
problems Network flow problems
Matroids
Definition. Graphic and Cographic matroids. Matroid intersection problem
Non-linear Programming
Kuhn-Tucker conditions. Convex functions and Convex regions. Convex
programming problems. Algorithms for solving convex programming
problems- Rate of convergence of iterative methods for solving these
problems
Neural Networks
Perceptron model, Linear separability and XOR problem. Two and three
layered neural nets. Backpropagation-Convergence. Hopfield nets, Neural
net learning, Applications
Fuzzy Systems
Definition of a Fuzzy set, Fuzzy relations, Fuzzy functions, Fuzzy measures, Fuzzy reasoning, App1ications of Fuzzy systems
Unix
Operating system, Structure of Unix Operating System,
Unix Commands,
Interfacing with Unix. Editors and Compilers for Unix, LEX and YACC, File system, System calls.
Filters,
Shell programming
Windows
Windows environment, Unicode, Documents and Views, Drawing in a
window, Message handling, Scrolling and Splitting views, Docking
toolbars and Status bars, Common dialogs and Controls, MDI,
Multithreading, OLE, Active X controls, ATL, Database access, Network
programming
