## 3rd semester syllabus: CS

**DIGITAL LOGIC DESIGN (NEC-309)**

** **Unit-I

Digital Design and Binary Numbers: Binary Arithmetic, Negative Numbers and their Arithmetic, Floating point representation, Binary Codes, Cyclic Codes, Error Detecting and Correcting Codes, Hamming Codes. Minterm and Maxterm Realization of Boolean Functions, Gate-level minimization: The map method up to four variable, don’t care conditions, SOP and POS simplification, NAND and NOR implementation, Quine Mc- Cluskey Method (Tabular method).

Unit-II

Combinational Logic: Combinational Circuits, Analysis Procedure, Design Procedure, Binary Adder-Subtractor, Code Converters, Parity Generators and Checkers, Decimal Adder, Binary Multiplier, Magnitude Comparator, Decoders, Encoders, Multiplexers, Hazards and Threshold Logic

Unit-III

Memory and Programmable Logic Devices: Semiconductor Memories, RAM, ROM, PLA, PAL, Memory System design.

Unit-IV

Synchronous Sequential Logic: Sequential Circuits, Storage Elements: Latches, Flip Flops, Analysis of Clocked Sequential circuits, state reduction and assignments, design procedure.

Registers and Counters: Shift Registers, Ripple Counter, Synchronous Counter, Other Counters.

Unit-V

Asynchronous Sequential Logic: Analysis procedure, circuit with latches, design procedure, reduction of state and flow table, race free state assignment, hazards.

* *

**DATA STRUCTURES USING – C (NCS-301)**

** **Unit – I

Introduction: Basic Terminology, Elementary Data Organization, Algorithm, Efficiency of an Algorithm, Time and Space Complexity, Asymptotic notations: Big-Oh, Time-Space trade-off.

Abstract Data Types (ADT) Arrays: Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major Order, and Column Major Order, Application of arrays, Sparse Matrices and their representations. Linked lists: Array Implementation and Dynamic Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation and Addition, Generalized Linked List .

Unit – II

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, Recursion, Tower of Hanoi Problem, Simulating Recursion, Principles of recursion, Tail recursion, Removal of 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.

Unit – III

Trees: Basic terminology, Binary Trees, Binary Tree Representation: Array Representation and Dynamic Representation, Complete Binary Tree, Algebraic Expressions, Extended Binary Trees, Array and Linked Representation of Binary trees, Tree Traversal algorithms: Inorder, Preorder and Postorder, Threaded Binary trees, Traversing Threaded Binary trees, Huffman algorithm.

Unit – IV

Graphs: Terminology, Sequential and linked Representations of Graphs: Adjacency Matrices, Adjacency List, Adjacency Multi list, Graph Traversal : Depth First Search and Breadth First Search, Connected Component, Spanning Trees, Minimum Cost Spanning Trees: Prims and Kruskal algorithm. Transistive Closure and Shortest Path algorithm: Warshal Algorithm and Dijikstra Algorithm, Introduction to Activity Networks

Unit – V

Searching : Sequential search, Binary Search, Comparison and Analysis Internal Sorting: Insertion Sort, Selection, Bubble Sort, Quick Sort, Two Way Merge Sort, Heap Sort, Radix Sort, Practical consideration for Internal Sorting.

Search Trees: Binary Search Trees(BST), Insertion and Deletion in BST, Complexity of Search Algorithm, AVL trees, Introduction to m-way Search Trees, B Trees & B+ Trees .

Hashing: Hash Function, Collision Resolution Strategies Storage Management: Garbage Collection and Compaction.

**DISCRETE STRUCTURES AND GRAPH THEORY (NCS-302)**

** Unit-I**

Set Theory: Introduction, Combination of sets, Multisets, Ordered pairs,Set Identities.

Relations: Definition, Operations on relations, Properties of relations, Composite Relations, Equality of relations, Order of relations. Functions: Definition, Classification of functions,Operations on functions, Recursively defined functions.Natural Numbers: Introduction, Mathematical Induction, Variants of Induction, Induction with Nonzero Base cases.

**Unit-II**

Algebraic Structures: Definition, Groups, Subgroupsand order, Cyclic Groups, Cosets, Lagrange’s theorem, Normal Subgroups, Permutation and Symmetric groups, Group Homomorphisms, Definition and elementary properties of Rings and Fields, Integers Modulo n.

**Unit-III**

Partial order sets: Definition, Partial order sets,Combination of partial order sets, Hasse diagram.

Lattices: Definition, Properties of lattices – Bounded, Complemented, Modular and Complete

Lattice,Morphisms of lattices.

Boolean Algebra: Introduction, Axioms and Theorems of Boolean algebra, Algebraic manipulation of Boolean expressions. Simplificationof Boolean Functions, Karnaugh maps, Logic gates, Digital circuits and Boolean algebra. Combinational and sequential Circuits.

**Unit-IV**

Propositional Logic: Proposition, well formed formula, Truth tables, Tautology, Satisfiability,

Contradiction, Algebra of proposition, Theory of Inference ,Natural Deduction. Predicate Logic: First order predicate, well formedformula of predicate, quantifiers, Inference theory of predicate logic.

**Unit-V**

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

** Computer Based Numerical and Statistical Techniques (NCS-303)**

** Unit –I :**

**Computer Arithmetic and Errors: **Floating Point Arithmetic, Machine epsilon, Round off Error, Chopping Error, Truncation Error, Associative and Distributive Law in Floating Point arithmetic, Inherent Error, Error propagation, Numerical Instability

**Roots of Equation: **Secant Method, Newton Raphson Method and Fixed point Iteration Methods for Simple roots and derivation of their rate of convergence, Aitken Acceleration of Convergence, Modified Newton Raphson Method for Multiple roots, Birge-Vieta Method for Polynomials, Bairstrow Method for quadratic factors, Computer Algorithms of these methods.

** Unit –II**

**Interpolation: **Algorithms and Error Analysis of Lagrange and Newton divided difference interpolations, Relationship in various difference operators, Piecewise Linear Interpolation, Cubic Spline Interpolation, Natural Spline, Chebshev Polynomial Approximations, Lanczos Economization of Power Series

**Curve fitting: **Linear and Non Linear Least Squares Approximation, ill Conditioning in Least Squares Methods, Gram-Schmidt Process of Orthogonalization. Computer Algorithms of Least Square Curve Fitting

**Unit – III**

**Differentiation: **Methods based on Interpolation and Finite Differences, Richrdson Extrapolation **Integration: **Error Analysis of Trepezoidal and Simpson Methods, Newton Cotes Integration Methods, Guassian Integration Methods: Guass Legendre Method, Lobatto ntegration Method and Radau Integration Method, Error Terms in Integration Methods

**Unit – IV**

**Solution of Simultaneous Linear Algebraic Equations: **Guass Elimination Method, ill Conditioned Systems, Condition Number, Successive Over Relaxation Method, Rate of Convergence

**Solution of Ordinary Differential equations: **Single Step Methods-Runge-Kutta Second Order, Third Order and Fourth Order Methods, Multi Step Method-Predictor- Corrector Method

**Statistical Techniques**: Statistical Hypotheses, Test of Hypotheses, Type-I and Type-II Errors, Level of Significance, Test involving Normal Distribution