| Subject |
Topic |
Teaching Hours |
| TOC |
UNIT 1: Finite Automata, DFA, NFA, NFA to DFA, NFA with E-transition, Minimization of a DFA, Mealy Machine, Moole Machine
Unit 2: Regular Expressions, RE to FA, FA to RE, Closure properties of regular languages, Pumping lemma, Myhill Nerode Theorum
Unit 3: Grammer, Context Free languages, Chomsky Normal Form (CNF), Greibach Normal Form (GNF)
Unit 4: Push Down Automata (PDA), Construction of PDAs, Closure Properties of CFLS
Unit 5: Turing Machine and undecidability |
(30hrs) |
| COMPILER DESIGN |
UNIT 1: Introducton, Basics of Compiler, Language Processing system, Phases of Compiler.
UNIT 2:Lexicol Analysis, Syntax Analysis, Top Down Parsing, LL(1) Parsing, Bottom up Parsing, LR (K) Parsing
UNIT 3: Syntax Directed Translation
UNIT 4: Intermediate Code Generation
UNIT 5: Code Optimization, Code Generation, Run Time Environment |
(20hrs) |
| COMPUTER ORGANISATION |
Computer Arithmetic, Instruction Cycle, Addressing Modes, Interrupt Cycle, IInstruction Pipelining, Cache Memory. |
(35hrs) |
| SOFTWARE ENGINEERING |
SOFTWARE VS HARDWARE, SOFTWARE PROCESS MODELS, SOFTWARE ASSESSMENT MODELS, SOFTWARE ESTIMATIONS MODEL, RISK ANALYSIS, WHITE BOX TESTING, BLACK BOX TESTING, SDLC. |
|
| DESIGN AND ANALYSIS OF ALGORITHMS |
Introduction: Algorithm, Performance Analysis-Space complexity, Time complexity, Asymptotic Notations- Big oh notation, Omega notation, Theta notation and Little oh notation., Time and Space Complexity Calculation of simple algorithms. Analysis of Recursive Algorithms: Recurrence Equations, Solving Recurrence Equations – Iteration Method, Recursion Tree Method, Substitution method and Master’s Theorem, Divide and conquer: General method, applications-Binary search, Quick sort, Merge sort, Strassen’s matrix multiplication., Greedy method: General method, applications-Job sequencing with deadlines, knapsack problem, Minimum cost spanning trees, Single source shortest path problem., Dynamic Programming: General method, applications- Optimal binary search trees, 0/1 knapsack problem, All pairs shortest path problem, Traveling sales person problem, Reliability design., NP-Hard and NP-Complete problems: Basic concepts, non deterministic algorithms, NP - Hard and NP-Complete classes, Cook’s theorem., Graph and Tree Algorithms: Traversal algorithms: Depth First Search (DFS) and Breadth First Search (BFS); |
(30hrs) |
| DATABASE MANAGEMENT SYSTEM |
Introduction to File and Database systems- Database system structure, View of Data – Data Abstraction –Instances and Schemas – data Models, Relational Model , ER diagrams – Entities, Attributes and Entity sets – Relationships and Relationship sets – Additional features of ER Model – Concept Design with the ER Model, Relational Algebra – Selection and projection set operations – renaming – Joins – Division – Examples of Algebra overviews – Relational calculus – Tuple relational Calculus – Domain relational calculus – Expressive Power of Algebra and calculus., Form of Basic SQL Query – Examples of Basic SQL Queries – Introduction to Nested Queries – Correlated Nested Queries Set – Comparison Operators – Aggregative Operators – NULL values – Comparison using Null values – Logical connectivity’s – AND, OR and NOT – Impact on SQL Constructs – Outer Joins , Schema refinement – Problems Caused by redundancy – Decompositions – Problem related to decomposition – reasoning about FDS – FIRST, SECOND, THIRD Normal forms – BCNF – Lossless join Decomposition – Dependency preserving Decomposition , Data on External Storage – File Organization and Indexing – Cluster Indexes, Primary and Secondary Indexes. B-Tree - B+Tree index, Transaction Processing – Introduction- Need for Concurrency control- Desirable properties of Transaction- Schedule and Recoverability- Serializability and Schedules – Concurrency Control – Types of Locks- Two Phases locking- Deadlock- Time stamp based concurrency control. |
(30hrs) |
| DISCRETE MATHS |
MATHEMATICAL LOGIC, SETS, RELATIONS & FUNCTIONS, COMBINATIONS, GRAPH THEORY. |
(30hrs) |
| COMPUTER NETWORKS |
Requirements of IP addresses, Subnetting, Supernetting , Assigning Private IP, NAT( static NAT, Dynamic NAT, Port NAT), Classless addressing, Special Ip address, Calculating forwarding table of router, How different questions asked in different competitive Exams about Routing |
(35hrs) |
| DIGITAL LOGIC |
|
(30hrs) |
| OPERATING SYSTEMS |
|
(30hrs) |
| Programming and Data Structures |
|
(30 Hrs) |
