Similary as a B Tech CSE First year syllabus, Second year syllabus is also similar for all college and universities because of AICTE is handling the syllabus for all universities and colleges.
In Second year there are some core subjects like Data structure, Database Management System, Computer Organization and
Architecture, Discrete Structures & Theory
of Logic, Operating Systems, Theory of Automata and
Formal Languages, which is very important to understand the Core of Computer Science as well as the perspective of Gate Exam.
List of second year Computer Science Subjects
| Subjects | Topics |
|---|---|
| DATA STRUCTURE |
|
| Computer Organization and Architecture |
|
| Discrete Structures & Theory of Logic |
|
| Operating systems |
|
| Theory of Automata and Formal Languages |
|
| Microprocessor |
|
Syllabus of Second Year Computer Science
DATA STRUCTURE
Unit/Module 1 : Introduction to Data Structure
Basic Terminology, Elementary Data Organization, Built in Data Types in C.
Algorithm, Efficiency of an Algorithm, Time and Space Complexity,
Asymptotic notations: Big Oh, Big Theta and Big Omega, Time-Space trade-off. Abstract Data Types (ADT)
Unit/Module 2 : Arrays and Linked List
Array: Definition, Single and Multidimensional Arrays,
Representation of Arrays: Row Major Order, and Column Major Order, Derivation of Index Formulae for 1-D,2-D,3-D and n-D Array, Application of arrays, Sparse Matrices and their representations.
Linked lists: Array Implementation and Pointer Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation and Addition Subtraction & Multiplications of Single variable & Two variables Polynomial.
Unit/Module 3 : Searching And Sorting
Searching: Concept of Searching, Sequential search, Index Sequential Search, Binary Search.
Concept of Hashing & Collision resolution Techniques used in Hashing.
Sorting: Insertion Sort, Selection, Bubble Sort, Quick Sort, Merge Sort, Heap Sort and Radix Sort.
Unit/Module 4: Graphs and Trees
Graphs: Terminology used with Graph, Data Structure for Graph Representations: Adjacency Matrices, Adjacency List, Adjacency.
Graph Traversal: Depth First Search and Breadth First
Search, Connected Component, Spanning Trees,
Minimum Cost Spanning Trees: Prim’s and Kruskal algorithm. Transitive Closure and Shortest Path algorithm: Warshal Algorithm and Dijikstra Algorithm.
Unit/Module 5 : Stacks and Queue
Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array and Linked Implementation of Stack in C,
Application of stack: Prefix and Postfix Expressions, Evaluation of postfix expression, Iteration and Recursion- Principles of recursion, Tail recursion, Removal of recursion Problem solving using iteration and recursion with examples such as binary search, Fibonacci numbers, and Hanoi towers. Tradeoffs between iteration and recursion.
Queues: Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and linked implementation of queues in C, Dequeue and Priority Queue.
Computer Organization and Architecture
Unit/Module 1 : Introduction To COA
Introduction Functional units of digital system and their interconnections, buses, bus architecture, types of buses and bus arbitration. Register, bus and memory transfer. Processor organization, general registers organization, stack organization and addressing modes.
Unit/Module 2 : Arithmetic and logic unit:
Look ahead carries adders. Multiplication: Signed operand
multiplication, Booths algorithm and array multiplier. Division and logic operations. Floating point
arithmetic operation, Arithmetic & logic unit design. IEEE Standard for Floating Point Numbers
Unit/Module 3 : Control Unit
Instruction types, formats, instruction cycles and sub cycles (fetch and execute etc),
micro operations, execution of a complete instruction. Program Control, Reduced Instruction Set
Computer, Pipelining. Hardwire and micro programmed control: micro programme sequencing,
concept of horizontal and vertical microprogramming.
Unit/Module 4 : Memory and Virtual Memory
Memory: Basic concept and hierarchy, semiconductor RAM memories, 2D & 2 1/2D memory
organization. ROM memories. Cache memories: concept and design issues & performance, address
mapping and replacement Auxiliary memories: magnetic disk, magnetic tape and optical disks
Virtual memory: concept implementation.
Unit/Module 5 : Input/Output
Input / Output: Peripheral devices, I/O interface, I/O ports, Interrupts: interrupt hardware, types of
interrupts and exceptions. Modes of Data Transfer: Programmed I/O, interrupt initiated I/O and
Direct Memory Access., I/O channels and processors. Serial Communication: Synchronous &
asynchronous communication, standard communication interfaces.
Discrete Structures & Theory of Logic
Unit/Module 1 : Set Theory, Functions and Natural Numbers
Set Theory: Introduction, Combination of sets, Multisets, Ordered pairs. Proofs of some general
identities on sets. Relations: Definition, Operations on relations, Properties of relations, Composite
Relations, Equality of relations, Recursive definition of relation, Order of relations.
Functions: Definition, Classification of functions, Operations on functions, Recursively defined
functions. Growth of Functions.
Natural Numbers: Introduction, Mathematical Induction, Variants of Induction, Induction with
Nonzero Base cases. Proof Methods, Proof by counter – example, Proof by contradiction.
Unit/Module 2 : Algebraic Structures
Algebraic Structures: Definition, Groups, Subgroups and order, Cyclic Groups, Cosets,
Lagrange’s theorem, Normal Subgroups, Permutation and Symmetric groups, Group
Homomorphisms, Definition and elementary properties of Rings and Fields.
Unit/Module 3 : Lattices, Boolean Algebra
Lattices: Definition, Properties of lattices – Bounded, Complemented, Modular and Complete
lattice. Boolean Algebra: Introduction, Axioms and Theorems of Boolean algebra, Algebraic
manipulation of Boolean expressions. Simplification of Boolean Functions, Karnaugh maps, Logic
gates, Digital circuits and Boolean algebra.
Unit/Module 4 : Propositional And Predicate Logic Propositional Logic: Proposition, well formed formula, Truth tables, Tautology, Satisfiability,
Contradiction, Algebra of proposition, Theory of Inference.
Predicate Logic: First order predicate, well formed formula of predicate, quantifiers, Inference
theory of predicate logic.
Unit/Module 5 : Trees and Graphs
Trees: Definition, Binary tree, Binary tree traversal, Binary search tree.
Graphs: Definition and terminology, Representation of graphs, Multigraphs, Bipartite graphs,
Planar graphs, Isomorphism and Homeomorphism of graphs, Euler and Hamiltonian paths, Graph
coloring, Recurrence Relation & Generating function: Recursive definition of functions, Recursive
algorithms, Method of solving recurrences.
Combinatorics: Introduction, Counting Techniques, Pigeonhole Principle
Operating systems
Unit/Module 1 : Introduction to Operating System Introduction : Operating system and functions, Classification of Operating systems- Batch,
Interactive, Time sharing, Real Time System, Multiprocessor Systems, Multiuser Systems,
Multiprocess Systems, Multithreaded Systems, Operating System Structure- Layered structure,
System Components, Operating System services, Reentrant Kernels, Monolithic and Microkernel
Systems.
Unit/Module 2 : Concurrent Processes
Concurrent Processes: Process Concept, Principle of Concurrency, Producer / Consumer Problem,
Mutual Exclusion, Critical Section Problem, Dekker’s solution, Peterson’s solution, Semaphores,
Test and Set operation; Classical Problem in Concurrency- Dining Philosopher Problem, Sleeping
Barber Problem; Inter Process Communication models and Schemes, Process generation.
Unit/Module 3 : CPU Scheduling and Deadlock
CPU Scheduling: Scheduling Concepts, Performance Criteria, Process States, Process Transition
Diagram, Schedulers, Process Control Block (PCB), Process address space, Process identification
information, Threads and their management, Scheduling Algorithms, Multiprocessor Scheduling.
Deadlock: System model, Deadlock characterization, Prevention, Avoidance and detection,
Recovery from deadlock.
Unit/Module 4 : Memory Management
Memory Management: Basic bare machine, Resident monitor, Multiprogramming with fixed
partitions, Multiprogramming with variable partitions, Protection schemes, Paging, Segmentation,
Paged segmentation, Virtual memory concepts, Demand paging, Performance of demand paging,
Page replacement algorithms, Thrashing, Cache memory organization, Locality of reference.
Unit/Module 5 : I/O Management and Disk Scheduling
I/O Management and Disk Scheduling, I/O devices, and I/O subsystems, I/O buffering, Disk
storage and disk scheduling, RAID. File System: File concept, File organization and access
mechanism, File directories, and File sharing, File system implementation issues, File system
protection and security.
Theory of Automata and Formal Languages
Unit/Module 1 :Basic Concepts and Automata Theory
Introduction to Theory of Computation- Automata,
Computability and Complexity, Alphabet, Symbol, String, Formal Languages, Deterministic Finite
Automaton (DFA)- Definition, Representation, Acceptability of a String and Language, Non
Deterministic Finite Automaton (NFA), Equivalence of DFA and NFA, NFA with ε-Transition,
Equivalence of NFA’s with and without ε-Transition, Finite Automata with output- Moore
Machine, Mealy Machine, Equivalence of Moore and Mealy Machine, Minimization of Finite
Automata, Myhill-Nerode Theorem, Simulation of DFA and NFA
Unit/Module 2 : Regular Expressions and Languages
Regular Expressions, Transition Graph, Kleen’s Theorem,
Finite Automata and Regular Expression- Arden’s theorem, Algebraic Method Using Arden’s
Theorem, Regular and Non-Regular Languages- Closure properties of Regular Languages,
Pigeonhole Principle, Pumping Lemma, Application of Pumping Lemma, Decidability- Decision
properties, Finite Automata and Regular Languages, Regular Languages and Computers,
Simulation of Transition Graph and Regular language.
Unit/Module 3 : Regular and Non-Regular Grammars
Context Free Grammar(CFG)-Definition, Derivations,
Languages, Derivation Trees and Ambiguity, Regular Grammars-Right Linear and Left Linear
grammars, Conversion of FA into CFG and Regular grammar into FA, Simplification of CFG,
Normal Forms- Chomsky Normal Form(CNF), Greibach Normal Form (GNF), Chomsky
Hierarchy, Programming problems based on the properties of CFGs.
Unit/Module 4 : Push Down Automata and Properties of Context Free Languages
Nondeterministic Pushdown
Automata (NPDA)- Definition, Moves, A Language Accepted by NPDA, Deterministic Pushdown
Automata(DPDA) and Deterministic Context free Languages(DCFL), Pushdown Automata for
Context Free Languages, Context Free grammars for Pushdown Automata, Two stack Pushdown
Automata, Pumping Lemma for CFL, Closure properties of CFL, Decision Problems of CFL,
Programming problems based on the properties of CFLs.
Unit/Module 5: Turing Machines and Recursive Function Theory
Basic Turing Machine Model,
Representation of Turing Machines, Language Acceptability of Turing Machines, Techniques for
Turing Machine Construction, Modifications of Turing Machine, Turing Machine as Computer of
Integer Functions, Universal Turing machine, Linear Bounded Automata, Church’s Thesis,
Recursive and Recursively Enumerable language, Halting Problem, Post’s Correspondance
Problem, Introduction to Recursive Function Theory.
Microprocessor
Unit/Module 1 : Introduction to Microprocessor
Microprocessor evolution and types, microprocessor architecture and operation of its components,
addressing modes, interrupts, data transfer schemes, instruction and data flow, timer and timing
diagram, Interfacing devices.
Unit/Module 2 : Architecture of 8085 microprocessor
Pin diagram and internal architecture of 8085 microprocessor, registers, ALU, Control & status,
interrupt and machine cycle. Instruction sets. Addressing modes. Instruction formats Instruction
Classification: data transfer, arithmetic operations, logical operations, branching operations,
machine control and assembler directives.
Unit/Module 3 : Architecture of 8086 microprocessor
Architecture of 8086 microprocessor: register organization, bus interface unit, execution unit,
memory addressing, and memory segmentation. Operating modes. Instruction sets, instruction
format, Types of instructions. Interrupts: hardware and software interrupts.
Unit/Module 4 : Assembly language programming based on intel 8085/8086
Assembly language programming based on intel 8085/8086. Instructions, data transfer, arithmetic,
logic, branch operations, looping, counting, indexing, programming techniques, counters and time
delays, stacks and subroutines, conditional call and return instructions
Unit/Module 5 : Peripheral Devices
Peripheral Devices: 8237 DMA Controller, 8255 programmable peripheral interface,
8253/8254programmable timer/counter, 8259 programmable interrupt controller, 8251 USART and
RS232C.
Syllabus Source: https://tinyurl.com/y7erzyzb