## Subject Code: CS

### Course Structure

Sections/Units Topics
Section A Engineering Mathematics
Unit 1 Discrete Mathematics
Unit 2 Linear Algebra
Unit 3 Calculus
Unit 4 Probability
Section B Digital Logic
Section C Computer Organization and Architecture
Section D Programming and Data Structures
Section E Algorithms
Section F Theory of Computation
Section G Compiler Design
Section H Operating System
Section I Databases
Section J Computer Networks

### Course Syllabus

Section A: Engineering Mathematics

Unit 1: Discrete Mathematics

• Propositional and first order logic
• Sets
• Relations
• Functions
• Partial orders
• Lattices
• Groups
• Graphs −
• Connectivity
• Matching
• Coloring
• Combinatorics −
• Counting
• Recurrence relations
• Generating functions

Unit 2: Linear Algebra

• Matrices
• Determinants
• System of linear equations
• Eigenvalues and eigenvectors
• LU decomposition

Unit 3: Calculus

• Limits, continuity and differentiability
• Maxima and minima
• Mean value theorem
• Integration

Unit 4: Probability

• Random variables
• Uniform, normal, exponential, poisson and binomial distributions
• Mean, median, mode and standard deviation
• Conditional probability
• Bayes theorem

Section B: Digital Logic

• Boolean algebra
• Combinational and sequential circuits
• Minimization. Number
• representations and computer arithmetic (fixed and floating point)

Section C: Computer Organization and Architecture

• Machine instructions and addressing modes
• ALU, data-path and control unit
• Instruction pipelining
• Memory hierarchy −
• Cache
• Main memory and secondary storage
• I/O interface (interrupt and DMA mode)

Section D: Programming and Data Structures

• Programming in C

• Recursion

• Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs

Section E: Algorithms

• Searching, sorting, hashing
• Asymptotic worst case time and space complexity
• Algorithm design techniques −
• Greedy
• Dynamic programming
• Divide-and-conquer
• Graph search, minimum spanning trees, shortest paths

Section F: Theory of Computation

• Regular expressions and finite automata
• Context-free grammars and push-down automata
• Regular and contex-free languages, pumping lemma
• Turing machines and undecidability

Section G: Compiler Design

• Lexical analysis, parsing, syntax-directed translation
• Runtime environments
• Intermediate code generation

Section H: Operating System

• Processes, threads, inter-process communication, concurrency and synchronization

• CPU scheduling

• Memory management and virtual memory

• File systems

Section I: Databases

• ER-model
• Relational model −
• Relational algebra
• Tuple calculus
• SQL
• Integrity constraints, normal forms
• File organization, indexing (e.g., B and B+ trees)
• Transactions and concurrency control

Section J: Computer Networks

• Concept of layering
• LAN technologies (Ethernet)
• Flow and error control techniques, switching
• IPv4/IPv6, routers and routing algorithms (distance vector, link state)
• TCP/UDP and sockets, congestion control
• Application layer protocols (DNS, SMTP, POP, FTP, HTTP)
• Basics of Wi-Fi
• Network security −
• Authentication
• Basics of public key and private key cryptography
• Digital signatures and certificates
• Firewalls