**University Syllabus of CSE 4TH SEMESTER of MAKAUT**

**M(CS)401 : NUMERICAL METHODS :**

Approximation in numerical computation: Truncation and rounding errors, Fixed and floating-point arithmetic, Propagation of errors. (4)

Interpolation: Newton forward/backward interpolation, Lagrange’s and Newton’s divided difference Interpolation. (5)

Numerical integration: Trapezoidal rule, Simpson’s 1/3 rule, Expression for corresponding error terms. (3)

Numerical solution of a system of linear equations: Gauss elimination method, Matrix inversion, LU Factorization method, Gauss-Seidel iterative method. (6) Numerical solution of Algebraic equation: Bisection method, Regula-Falsi method, Newton-Raphson method. (4)

Numerical solution of ordinary differential equation: Euler’s method, Runge-Kutta methods, Predictor-Corrector methods and Finite Difference method. (6)

**M 401 : MATHEMATICS – 3:**

**Note 1: The whole syllabus has been divided into five modules. **

**Note 2: Structure of the question paper**

There will be three groups in the question paper. In Group A, there will be one set of multiple choice type questions spreading the entire syllabus from which 10 questions (each carrying one mark) are to be answered. From Group B, three questions (each carrying 5 marks) are to be answered out of a set of questions covering all the five modules. Three questions (each carrying 15 marks) are to be answered from Group C. Each question of Group C will have two or three parts covering not more than two modules. Sufficient questions should to be set covering the whole syllabus for alternatives.

**Module I**

Theory of Probability: Axiomatic definition of probability. Conditional probability. Independent events and related

problems. Bayes theorem (Statement only) & its application. One dimensional random variable. Probability

distributions-discrete and continuous. Expectation. Binomial, Poisson, Uniform, Exponential, Normal distributions and related problems. t, χ2 and F-distribution (Definition only). Transformation of random variables. Central Limit

Theorem, Law of large numbers (statement only) and their applications. Tchebychev inequalities (statement only) and

its application. (14L)

**Module II**

Sampling theory: Random sampling. Parameter, Statistic and its Sampling distribution. Standard error of statistic.

Sampling distribution of sample mean and variance in random sampling from a normal distribution (statement only) and

related problems.

Estimation of parameters: Unbiased and consistent estimators. Point estimation. Interval estimation. Maximum

likelihood estimation of parameters (Binomial, Poisson and Normal). Confidence intervals and related problems. (7L)

**Module III**

Testing of Hypothesis: Simple and Composite hypothesis. Critical region. Level of significance. Type I and Type II errors. One sample and two sample tests for means and proportions. χ2 – test for goodness of fit. (5L)

**Module IV **

Advanced Graph Theory: Planar and Dual Graphs. Kuratowski’s graphs. Homeomorphic graphs. Eulers formula ( n – e

+ r = 2) for connected planar graph and its generalisation for graphs with connected components. Detection of planarity.

Graph colouring. Chromatic numbers of Cn, Kn , Km,n and other simple graphs. Simple applications of chromatic

numbers. Upper bounds of chromatic numbers (Statements only). Chromatic polynomial. Statement of four and five

colour theorems. ( 10L )

**Module V **

Algebraic Structures: Group, Subgroup, Cyclic group, Permutation group, Symmetric group ( S3), Coset, Normal

subgroup, Quotient group, Homomorphism & Isomorphism

( Elementary properties only).

Definition of Ring, Field, Integral Domain and simple related problems. ( 12L)

**CS 401 : Communication Engineering & Coding Theory :**

**Module – 1**

Elements of Communication system, Analog Modulation & Demodulation, Noise, SNR Analog-toDigital Conversion. (Basic ideas in brief) [8] [Details: Introduction to Base Band transmission & Modulation (basic concept) (1L); Elements of Communication systems (mention of transmitter, receiver and channel); origin of noise and its effect, Importance of SNR in system design (1L); Basic principles of Linear Modulation (Amplitude Modulation) (1L); Basic principles of Non-linear modulation (Angle Modulation – FM, PM) (1L); Sampling theorem, Sampling rate, Impulse sampling, Reconstruction from samples, Aliasing (1L); Analog Pulse Modulation – PAM (Natural & flat topped sampling), PWM, PPM (1L); Basic concept of Pulse Code Modulation, Block diagram of PCM (1L); Multiplexing – TDM, FDM (1L);

**Module – 2**

Digital Transmission: [8] [Details: Concept of Quantisation & Quantisation error, Uniform Quantiser (1L); Non-uniform Quantiser, A-law & law companding (mention only) (1L); Encoding, Coding efficiency (1L); Line coding & properties, NRZ & RZ, AMI, Manchester coding PCM, DPCM (1L); Baseband Pulse Transmission, Matched filter (mention of its importance and basic concept only), Error rate due to noise (2L); ISI, Raised cosine function, Nyquist criterion for distortion-less base-band binary transmission, Eye pattern, Signal power in binary digital signals (2L);

**Module – 3**

Digital Carrier Modulation & Demodulation Techniques: [8] [Details: Bit rate, Baud rate (1L); Information capacity, Shanon’s limit (1L); M-ary encoding, Introduction to the different digital modulation techniques – ASK, FSK, PSK, BPSK, QPSK, mention of 8 BPSK, 16 BPSK (2L); Introduction to QAM, mention of 8QAM, 16 QAM without elaboration (1L); Delta modulation, Adaptive delta modulation (basic concept and importance only, no details (1L); introduction to the concept of DPCM, Delta Modulation, Adaptive Delta modulation and their relevance (1L); Spread Spectrum Modulation – concept only. (1L).

**Module – 4**

Information Theory & Coding: [8] [Details: Introduction, News value & Information content (1L);, Entropy (1L);, Mutual information (1L);, Information rate (1L);, Shanon-Fano algorithm for encoding (1L);, Shannon’s Theorem – Source Coding Theorem (1L);, Channel Coding Theorem, Information Capacity Theorem (basic understanding only) (1L);; Error Control & Coding – basic principle only. (1L);

**CS 402 : Formal Language & Automata Theory :**

**Module-1**

[13 L] Fundamentals: Basic definition of sequential circuit, block diagram, mathematical representation, concept of transition table and transition diagram (Relating of Automata concept to sequential circuit concept) Design of sequence detector, Introduction to finite state model [ 2L] Finite state machine: Definitions, capability & state equivalent, kth- equivalent concept [ 1L] Merger graph, Merger table, Compatibility graph [ 1L] Finite memory definiteness, testing table & testing graph. [1L] Deterministic finite automaton and non deterministic finite automaton. [1L] Transition diagrams and Language recognizers. [1L] Finite Automata: NFA with Î transitions – Significance, acceptance of languages. [1L] Conversions and Equivalence: Equivalence between NFA with and without Î transitions. NFA to DFA conversion. [2L] Minimization of FSM, Equivalence between two FSM’s , Limitations of FSM [1L] Application of finite automata, Finite Automata with output- Moore & Melay machine. [2L]

**Learning outcome of Finite Automata**: The student will be able to define a system and recognize the behavior of a system. They will be able to minimize a system and compare different systems.

**Module-2: [8 L] **

Regular Languages : Regular sets. [1L] Regular expressions, identity rules. Arden’s theorem state and prove [1L] Constructing finite Automata for a given regular expressions, Regular string accepted by NFA/DFA [1L] Pumping lemma of regular sets. Closure properties of regular sets (proofs not required). [1L] Grammar Formalism: Regular grammars-right linear and left linear grammars. [1L] Equivalence between regular linear grammar and FA. [1L] Inter conversion, Context free grammar. [1L] Derivation trees, sentential forms. Right most and leftmost derivation of strings. (Concept only) [1L]

**Learning outcome of Regular Languages and Grammar**: Student will convert Finite Automata to regular expression. Students will be able to check equivalence between regular linear grammar and FA.

**Module-3: [9L] **

Context Free Grammars, Ambiguity in context free grammars. [1L] Minimization of Context Free Grammars. [1L] Chomsky normal form and Greibach normal form. [1L] Pumping Lemma for Context Free Languages. [1L] Enumeration of properties of CFL (proofs omitted). Closure property of CFL, Ogden’s lemma & its applications [1L] Push Down Automata: Push down automata, definition. [1L] Acceptance of CFL, Acceptance by final state and acceptance by empty state and its equivalence. [1L] Equivalence of CFL and PDA, interconversion. (Proofs not required). [1L] Introduction to DCFL and DPDA. [1L]

**Learning outcome of PDA and context free grammar**: Students will be able to minimize context free grammar. Student will be able to check equivalence of CFL and PDA. They will be able to design Turing Machine.

**Module-4: [6L] **

Turing Machine : Turing Machine, definition, model [1L] Design of TM, Computable functions [1L] Church’s hypothesis, counter machine [1L] Types of Turing machines (proofs not required) [1 L] Universal Turing Machine, Halting problem [2L]

**Learning outcome of Turing Machine** : Students will be able to design Turing machine.

**CS 403 : Computer Architecture :**

**Module – 1: [12 L] **

Introduction: Review of basic computer architecture (Revisited), Quantitative techniques in computer design, measuring and reporting performance. (3L) Pipelining: Basic concepts, instruction and arithmetic pipeline, data hazards, control hazards and structural hazards, techniques for handling hazards. Exception handling. Pipeline optimization techniques; Compiler techniques for improving performance. (9L)

**Module – 2: [8L] **

Hierarchical memory technology: Inclusion, Coherence and locality properties; Cache memory organizations, Techniques for reducing cache misses; Virtual memory organization, mapping and management techniques, memory replacement policies. (8L)

**Module – 3: [6L] **

Instruction-level parallelism: basic concepts, techniques for increasing ILP, superscalar, superpipelined and VLIW processor architectures. Array and vector processors. (6L)

**Module – 4: [12 L] **

Multiprocessor architecture: taxonomy of parallel architectures; Centralized shared- memory architecture: synchronization, memory consistency, interconnection networks. Distributed shared-memory architecture. Cluster computers. (8L)

Non von Neumann architectures: data flow computers, reduction computer architectures, systolic architectures. (4L)

Above syllabus is copied from MAKAUT University website. If there is any mistake kindly comment below and inform us.