**Sophomore Year / Third Semester**

**Nature of Course:** Theory (3 Hrs)

**Text Books:**

1. Y Langsam, MJ Augenstein and A.M, Tanenbaum Data Structures using C and C++, Prentice Hall India, Second Edition 2015

**Reference Books: **

1. Leen Ammeral, Programmes and Data Structures in C, Wiley Professional Computing

2. G.W Rowe, Introduction to Data Structure and Algroithms with C and C++, Prentice Hall India

3. R.L Kruse, B.P. Leung, C.L. Tondo, Data Structure and Program Design in C Prentice-Hall India

**Course Synopsis:
**This course includes the basic foundations in of data structures and algorithms. This course covers concepts of various data structures like stack, queue, list, tree and graph. Additionally, the course includes idea of sorting and searching.

**Goals:**

- To introduce data abstraction and data representation in memory
- To describe, design and use of elementary data structures such as stack, queue, linked list, tree and graph
- To discuss decomposition of complex programming problems into manageable sub-problems
- To introduce algorithms and their complexity

**Course Contents:**

**Unit 1: Introduction to Data Structures & Algorithms (4 Hrs.)**

- Data types, Data structure and Abstract date type
- Dynamic memory allocation in C
- Introduction to Algorithms
- Asymptotic notations and common functions

**Unit 2: Stack (4 Hrs.)**

- Basic Concept of Stack, Stack as an ADT, Stack Operations, Stack Applications
- Conversion from infix to postfix/prefix expression, Evaluation of postfix/ prefix expressions

**Unit 3: Queue (4 Hrs.)**

- Basic Concept of Queue, Queue as an ADT, Primitive Operations in Queue
- Linear Queue, Circular Queue, Priority Queue, Queue Applications

**Unit 4: Recursion (3 Hrs.)**

- Principle of Recursion, Comparison between Recursion and Iteration, Tail Recursion
- Factorial, Fibonacci Sequence, GCD, Tower of Hanoi(TOH)
- Applications and Efficiency of Recursion

**Unit 5: Lists (8 Hrs.)**

- Basic Concept, List and ADT, Array Implementation of Lists, Linked List
- Types of Linked List: Singly Linked List, Doubly Linked List, Circular Linked List.
- Basic operations in Linked List: Node Creation, Node Insertion and Deletion from Beginning, End and Specified Position
- Stack and Queue as Linked List

**Unit 6: Sorting (8 Hrs.)**

- Introduction and Types of sorting: Internal and External sort
- Comparison Sorting Algorithms: Bubble, Selection and Insertion Sort, Shell Sort
- Divide and Conquer Sorting: Merge, Quick and Heap Sort
- Efficiency of Sorting Algorithms

**Unit 7: Searching and Hashing (6 Hrs.)**

- Introduction to Searching, Search Algorithms: Sequential Search, Binary Search
- Efficiency of Search Algorithms
- Hashing : Hash Function and Hash Tables, Collision Resolution Techniques

**Unit 8: Trees and Graphs (8 Hrs.)**

- Concept and Definitions, Basic Operations in Binary Tree, Tree Height, Level and Depth
- Binary Search Tree, Insertion, Deletion, Traversals, Search in BST
- AVL tree and Balancing algorithm, Applications of Trees
- Definition and Representation of Graphs, Graph Traversal, Minimum Spanning Trees: Kruskal and Prims Algorithm
- Shortest Path Algorithms: Dijksrtra Algorithm

**Laboratory Works:
**The laboratory work consists of implementing the algorithms and data structures studied in the course. Student should implement at least following concepts;

- Dynamic memory allocation and deallocation strategies
- Stack operations and Queue operations
- Array and Linked List implementation of List
- Linked List implementation of Stack and Queues
- Sorting, Searching and Hashing algorithms
- Binary Search Trees and AVL Tress
- Graph Representation, Spanning Tree and Shortest Path Algorithms

**Nature of Course:** Theory (3 Hrs)+ Lab (3 Hrs)

**Text Books:**

- M. Morris Mano, “Computer System Architecture”, Prentice-Hall of India, Pvt. Ltd., Third edition, 2007

**Reference:**

- William Stallings, “Computer Organization and Architecture”, Prentice-Hall of India, Pvt. Ltd., Seventh edition, 2005.
- Vincent P. Heuring and Harry F. Jordan, “Computer System Design and Architecture”, Prentice-Hall of India, Pvt. Ltd., Second edition, 2003.

**Course Synopsis:
**This course includes concepts of instruction set architecture, organization or micro-architecture, and system architecture. The instruction set architecture includes programmer’s abstraction of computer. The micro-architecture consist internal representation of computers at register and functional unit level. The system architecture includes organization of computers at the cache and bus level.

**Goal:**

The main objective of the course is to provide the knowledge of numerical method techniques for mathematical modeling.

**Course Contents:**

**Unit 1: Solution of Nonlinear Equations (8 Hrs.)**

- Errors in Numerical Calculations, Sources of Errors, Propagation of Errors, Review of Taylor’s Theorem
- Solving Non-linear Equations by Trial and Error method, Half-Interval method and Convergence, Newton’s method and Convergence, Secant method and Convergence, Fixed point iteration and its convergence, Newton’s method for calculating multiple roots, Horner’s method

**Unit 2: Interpolation and Regression (8 Hrs.)**

- Interpolation vs Extrapolation, Lagrange’s Interpolation, Newton’s Interpolation using divided differences, forward differences and backward differences, Cubic spline interpolation
- Introduction of Regression, Regression vs Interpolation, Least squares method, Linear Regression, Non-linear Regression by fitting Exponential and Polynomial

**Unit 3: Numerical Differentiation and Integration (8 Hrs.)**

- Differentiating Continuous Functions (Two-Point and Three-Point Formula), Differentiating Tabulated Functions by using Newton’s Differences, Maxima and minima of Tabulated Functions
- Newton-Cote’s Quadrature Formulas, Trapezoidal rule, Multi-Segment Trapezoidal rule, Simpson’s 1/3 rule, Multi-Segment Simpson’s 1/3 rule, Simpson’s 3/8 rule, Multi-Segment Simpson’s 3/8 rule, Gaussian integration algorithm, Romberg integration

**Unit 4: Solving System of Linear Equations (8 Hrs.)**

- Review of the existence of solutions and properties of matrices, Gaussian elimination method, pivoting, Gauss-Jordan method, Inverse of matrix using Gauss-Jordan method
- Matrix factorization and Solving System of Linear Equations by using Dolittle and Cholesky’s algorithm
- Iterative Solutions of System of Linear Equations, Jacobi Iteration Method, Gauss-Seidal Method
- Eigen values and eigen vectors problems, Solving eigen value problems using power method.

**Unit 5: Solution of Ordinary Differential Equations (8 Hrs.)**

- Review of differential equations, Initial value problem, Taylor series method, Picard’s method, Euler’s method and its accuracy, Heun’s method, Runge-Kutta methods
- Solving System of ordinary differential equations, Solution of the higher order equations, Boundary value problems, Shooting method and its algorithm

**Unit 6: Solution of Partial Differential Equations (5 Hrs.)**

- Review of partial differential equations, Classification of partial differential equation, Deriving difference equations, Laplacian equation and Poisson’s equation, engineering examples

**Laboratory Works:
**The laboratory exercise should consist program development and testing of non-linear equations, system of linear equations, interpolation, numerical integration and differentation, linear algebraic equations, ordinary and partial differential equations.Numerical solutions using C or Matlab

**Nature of Course:** Theory (3 Hrs)+ Lab (3 Hrs)

**Text books:**

- M. Morris Mano, “Computer System Architecture”, Prentice-Hall of India, Pvt. Ltd., Third edition, 2007

**References: **

- William Stallings, “Computer Organization and Architecture”, Prentice-Hall of India, Pvt. Ltd., Seventh edition, 2005
- Vincent P. Heuring and Harry F. Jordan, “Computer System Design and Architecture”, Prentice-Hall of India, Pvt. Ltd., Second edition, 2003.

**Course of Synopsis:
**This course includes concepts of instruction set architecture, organization or micro-architecture, and system architecture. The instruction set architecture includes programmer’s abstraction of computer. The micro-architecture consist internal representation of computers at register and functional unit level. The system architecture includes organization of computers at the cache and bus level.

**Goal:**

- Discuss representation of data and algorithms used to perform operations on data
- Demonstrate different operations in terms of Micro-operations
- Explain architecture of basic computer and micro-programmed control unit
- Understand and memory and I/O organization of a typical computer system
- Demonstrate benefits of pipelined systems

**Course Contents:**

**Unit 1: Data Representation (4 Hrs.)**

- Data Representation: Binary Representation, BCD, Alphanumeric Representation, Complements, Fixed Point representation, Representing Negative Numbers, Floating Point Representation, Arithmetic with Complements, Overflow, Detecting Overflow
- Other Binary Codes: Gray Code, self Complementing Code, Weighted Code, Excess-3 Code, EBCDIC
- Error Detection Codes: Parity Bit, Odd Parity, Even parity, Parity Generator & Checker

**Unit 2: Register Transfer and Microoperations (5 Hrs.)**

- Microoperation, Register Transfer Language, Register Transfer, Control Function
- Arithmetic Microoperations: Binary Adder, Binary Adder-subtractor, Binary Incrementer, Arithmetic Circuit
- Logic Microoperations, Hardware Implementation, Applications of Logic Microoperations.
- Shift Microoperations: Logical Shift, Circular shift, Arithmetic Shift, Hardware Implementation of Shifter.

**Unit 3: Basic Computer Organization and Design (8 Hrs.)**

- Instruction Code, Operation Code, Stored Program Concept
- Registers and memory of Basic Computer, Common Bus System for Basic Computer.
- Instruction Format, Instruction Set Completeness, Control Unit of Basic Computer, Control Timing Signals
- Instruction Cycle of Basic computer, Determining Type of Instruction, Memory Reference Instructions, Input-Output Instructions, Program Interrupt & Interrupt Cycle.
- Synopsis and Flowchart of Basic Computer

**Unit 4: Microprogrammed Control (4 Hrs.)**

- Control Word, Microprogram, Control Memory, Control Address Register, Sequencer
- Address Sequencing, Conditional Branch, Mapping of Instructions, Subroutines, Microinstruction Format, Symbolic Microinstructions
- Design of Control Unit

**Unit 5: Central Processing Unit (4 Hrs.)**

- Major Components of CPU, CPU Organization
- Instruction Formats, Addressing Modes, Data Transfer and manipulation, Program Control, Subroutine Call and Return, Types of Interrupt
- RISC vs CISC, Pros and Cons of RISC and CISC, Overlapped Register Windows

**Unit 6: Pipelining (6 Hrs.)**

- Parallel Processing, Multiple Functional Units, Flynn’s Classification
- Pipelining: Concept and Demonstration with Example, Speedup Equation, Floating Point addition and Subtraction with PipeliningInstruction Level Pipelining: Instruction Cycle, Three & Four-Segment Instruction Pipeline, Pipeline Conflicts and Solutions
- Vector Processing, Applications, Vector Operations, Matrix Multiplication

**Unit 7: Computer Arithmetic (6 Hrs.)**

- Addition and Subtraction with Signed Magnitude Data, Addition and Subtraction with Signed 2’s Complement Data
- Multiplication of Signed Magnitude Data, Booth Multiplication, Division of Signed magnitude Data, Divide Overflow

**Unit 8: Input Output Organization (4 Hrs.)**

- Input-Output Interface: I/O Bus and Interface Modules, I/O vs. Memory Bus, Isolated vs. Memory-Mapped I/O
- Asynchronous Data Transfer: Strobe, Handshaking
- Modes of Transfer: Programmed I/O, Interrupt-Initiated I/O, Direct memory Access
- Priority Interrupt: Polling, Daisy-Chaining, Parallel Priority Interrupt
- Direct Memory Access, Input-Output Processor, DMA vs. IOP

**Unit 9: Memory Organization (4 Hrs.)**

- Memory Hierarchy, Main Memory, RAM and ROM Chips, Memory address Map, Memory Connection to CPU, Auxiliary Memory (magnetic Disk, Magnetic Tape)
- Associative Memory: Hardware Organization, Match Logic, Read Operation, Write Operation
- Cache Memory: Locality of Reference, Hit & Miss Ratio, Mapping, Write Policies

**Laboratory Works:
**The laboratory work includes implementing and simulating the algorithms, studied in the course, by using high level languages like C or VHDL. The laboratory works should include at least following concepts;

- Simulate features like overflow, data representation by using VHDL
- Simulate design of different units by using VHDL
- Simulate pipelining by using VHDL
- Implement algorithms for computer arithmetic using high level language like C or C++

**Nature of Course:** Theory (3 Hrs)+ Lab (3 Hrs)

**Text Books:**

- Donald Hearne and M. Pauline Baker, “Computer Graphics, C Versions.” Prentice Hall

**Reference Books:**

- J.D. Foley, S.K. Feiner and J.F. Hughes, “Computer Graphics – Principles and Practises” (Second Edition in C)
- R.K. Maurya, “Computer Graphics with Virtual Reality”, Wiley India
- F.S. Hill, Stephen M.Kelley, “Computer Graphics using Open GL” Prentice Hall

**Course Synopsis:**

The course covers concepts of graphics hardware, software, and applications, data structures for representing 2D and 3D geometric objects, drawing algorithms for graphical objects, techniques for representing and manipulating geometric objects, illumination and lighting models, and concept of virtual reality.

**Goal: **

The objective of this course is to understand the theoretical foundation as well as the practical applications of 2D and 3D graphics.

**Course Contents:**

**Unit 1: Introduction to Computer Graphics (3 Hrs.)**

- A Brief Overview of Computer Graphics, Areas of Applications.
- Graphics Hardware: Display Technology, Architecture of Raster-Scan Displays, Vector Displays, Display Processors, Hard copy device. Input Devices
**.** - Graphics Software: Software standards, Need of machine independent graphics language

**Unit 2: Scan Conversion Algorithm (6 Hrs.)**

- Scan Converting a Point and a straight Line: DDA Line Algorithm, Bresenham’s Line Algorithm
- Scan Converting Circle and Ellipse: Mid-Point Circle and Ellipse Algorithm
- Area Filling: Scan Line Polygon fill Algorithm, Inside-outside Test, Scan-line fill of Curved Boundary area, Boundary-fill and Flood-fill algorithm

**Unit 3: Two-Dimensional Geometric Transformations (5 Hrs.)**

- Two-Dimensional translation, Rotation, Scaling, Reflection and Shearing
- Homogeneous Coordinate and 2D Composite Transformations. Transformation between Co-ordinate Systems.
- Two Dimensional Viewing: Viewing pipeline, Window to viewport coordinate transformation
- Clipping: Point, Lines(Cohen Sutherland line clipping, Liang-Barsky Line Clipping), Polygon Clipping(Sutherland Hodgeman polygon clipping)

**Unit 4: Three-Dimensional Geometric Transformation (5 Hrs.)**

- Three-Dimensional translation, Rotation, Scaling, Reflection and Shearing
- Three-Dimensional Composite Transformations
- Three-Dimensional Viewing: Viewing pipeline, world to screen viewing transformation, Projection concepts(Orthographic, parallel, perspective projections)

**Unit 5: 3D Objects Representation (7 Hrs.)**

- Representing Surfaces: Boundary and Space partitioning
- Polygon Surface: Polygon tables , Surface normal and Spatial orientation of surfaces, Plane equations, Polygon meshes
- Wireframe Representation
- Blobby Objects

- Representing Curves: Parametric Cubic Curves, Spline Representation, Cubic spline interpolation, Hermite Curves, Bezier and B-spline Curve and surface
- Quadric Surface: Sphere and Ellipsoid

**Unit 6: Solid Modeling (4 Hrs.)**

- Sweep,Boundary and Spatial-Partitioning Representation
- Binary Space Partition Trees (BSP)
- Octree Representation

**Unit 7: Visible Surface Detections (5 Hrs.)**

- Image Space and Object Space Techniques
- Back Face Detection, Depth Buffer (Z-buffer), A-Buffer and Scan-Line Algorithms.
- Depth Sorting Method (Painter’s Algorithm)
- BSP tree Method, Octree and Ray Tracing

**Unit 8: Illumination Models and Surface Rendering Techniques (5 Hrs.)**

- Basic Illumination Models: Ambient light, Diffuse reflection, Specular reflection and Phong model
- Intensity attenuation and Color consideration, Transparency, Shadows
- Polygon Rendering Methods: Constant intensity shading, Gouraud shading, Phong Shading and Fast Phong Shading

**Unit 9: Introduction to Virtual Reality (2 Hrs.)**

- Concept of Virtual reality
- Virtual Reality Components of VR System, Types of VR System, 3D Position Trackers, Navigation and Manipulation Interfaces
- Application of VR

**Unit 10: Introduction to OpenGL (3 Hrs.)**

- Introduction, Callback functions, Color commands, Drawings pixels, lines, polygons using OpenGL, Viewing and Lighting

**Laboratory Works:
**The laboratory course consists of implementing following algorithms using high-level languages and OpenGL.

- DDA Line Algorithm
- Bresenham’s line drawing algorithm
- Mid-Point Circle Algorithm
- Mid-Point Ellipse Algorithm
- Basic transformation on 2D including Translation, Rotation and Scaling
- Simple 3D Object with basic transformations including Translation, Rotation and Scaling
- Clipping
- Hidden surface removal
- Basic Drawing Techniques in OpenGL

**Nature of Course:** Theory (3 Hrs) + Lab (3Hrs)

**Text Books:**

- Ronald E. Walpole, Raymond H. Myers, Sharon L. Myers, & Keying Ye(2012). Probability & Statistics for Engineers & Scientists. 9
^{th}Ed., Printice Hall - Michael Baron (2013). Probability and Statistics for Computer Scientists. 2
^{nd}Ed., CRC Press, Taylor & Francis Group, A Chapman & Hall Book

**References:
**

- Douglas C. Montgomery & George C. Runger (2003). Applied Statistics and Probability for Engineers. 3
^{rd}Ed., John Willey and Sons, Inc. - Sidney Siegel, & N. John Castellan, Jr. Nonparametric Statistics for the Behavioral Sciences, 2
^{nd}Ed., McGraw Hill International Editions.

**Course Synopsis:
**The course consists of concepts of sampling, testing hypothesis, parametric and non-parametric tests, correlation and regression, experimental designs and stochastic processes.

**Goals:
**The main objective of the course is to acquire the theoretical as well as practical knowledge of estimation, testing of hypothesis, application of parametric and non-parametric statistical tests, design of experiments, multiple regression analysis, and basic concept of stochastic process with special focus on data/problems related to computer science and information technology

**Course Contents:**

**Unit 1: Sampling Distribution and Estimation (6 Hrs.)
**Sampling distribution; sampling distribution of mean and proportion; Central Limit Theorem; Concept of inferential Statistics; Estimation; Methods of estimation; Properties of good estimator; Determination of sample size; Relationship of sample size with desired level of error

Problems and illustrative examples related to Computer Science and IT

**Unit 2: Testing of hypothesis (8 Hrs.)
**Types of statistical hypotheses; Power of the test, concept of p-value and use of p -value in decision making, steps used in testing of hypothesis, one sample tests for mean of normal population (for known and unknown variance), test for single proportion, test for difference between two means and two proportions, paired sample t-test; Linkage between confidence interval and testing of hypothesis

Problems and illustrative examples related to computer Science and IT

**Unit 3: Non-parametric test (8 Hrs.)
**Parametric vs. non-parametric test; Needs of applying non-parametric tests; One-sample test: Run test, Binomial test

**,**Kolmogorov–Smirnov test; Two independent sample test: Median test, Kolmogorov-Smirnov test, Wilcoxon Mann Whitney test, Chi-square test; Paired-sample test: Wilcoxon signed rank test; Cochran’s Q test; Friedman two way analysis of variance test; Kruskal Wallis test

Problems and illustrative examples related to Computer Science and IT

**Unit 4: Multiple correlation and regression (6 Hrs.)
**Multiple and partial correlations; Introduction of multiple linear regression; Hypothesis testing of multiple regression; Test of significance of regression; Test of individual regression coefficient; Model adequacy tests

Problems and illustrative examples related to computer Science and IT

**Unit 5**:** Design of experiment (10 Hrs.)
**Experimental design; Basic principles of experimental designs; Completely Randomized Design (CRD); Randomized Block Design (RBD); ANOVA table, Efficiency of RBD relative to CRD, Estimations of missing value (one observation only), Advantages and disadvantages; Latin Square Design (LSD): Statistical analysis of m × m LSD for one observation per experimental unit, ANOVA table, Estimation of missing value in LSD (one observation only), Efficiency of LSD relative to RBD, Advantage and disadvantages.

Problems and illustrative examples related to computer Science and IT

**Unit 6: Stochastic Process (7 Hrs.)
**Definition and classification; Markov Process: Markov chain, Matrix approach, Steady- State distribution; Counting process: Binomial process, Poisson process; Simulation of stochastic process; Queuing system: Main component of queuing system, Little’s law; Bernoulli single server queuing process: system with limited capacity; M/M/1 system: Evaluating the system performance.

**Laboratory Works:
**The laboratory work includes implementing concepts of statistics using statistical software tools such as SPSS, STATA etc.

S. No |
Practical Problems |
No. of practical problems |

1 | Sampling distribution, random number generation, and computation of sample size | 1 |

2 | Methods of estimation (including interval estimation) | 1 |

3 | Parametric tests (covering most of the tests) | 3 |

4 | Non-parametric test(covering most of the tests) | 3 |

5 | Partial correlation | 1 |

6 | Multiple regression | 1 |

7 | Design of Experiments | 3 |

8 | Stochastic process | 2 |

Total number of practical problems |
15 |

**Sophomore Year/Fourth semester**

**Nature of Course:** Theory (3 Hrs) + Lab (3 Hrs)

**Text Books:**

1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3^{rd} Edition, Pearson – Addison-Wesley.

**Reference Books:**

- Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, 2
^{nd}Edition, Prentice Hall. - Michael Sipser, Introduction to the Theory of Computation, 3
^{rd}Edition, Thomson Course Technology - Efim Kinber, Carl Smith, Theory of Computing: A Gentle Introduction, Prentice- Hall.
- John Martin
*,*Introduction to Languages and the Theory of Computation, 3^{rd}Edition, Tata McGraw Hill.

**Course Synopsis:
**This course presents a study of Finite State Machines and their languages. It covers the details of finite state automata, regular expressions, context-free grammars. More, the course includes design of the Push-down automata and Turing Machines. The course also includes basics of undecidabilty and intractability.

**Goals:
**The main objective of the course is to introduce concepts of the models of computation and formal language approach to computation. The general objectives of this course are to, introduce concepts in automata theory and theory of computation, design different finite state machines and grammars and recognizers for different formal languages, identify different formal language classes and their relationships, determine the decidability and intractability of computational problems

**Course Contents:**

**Unit 1: Basic Foundations (3 Hrs.)**

- Review of Set Theory, Logic, Functions, Proofs
- Automata, Computability and Complexity: Complexity Theory, Computability Theory, Automata Theory
- Basic concepts of Automata Theory: Alphabets, Power of Alphabet, Kleen Closure Alphabet, Positive Closure of Alphabet, Strings, Empty String, Substring of a string, Concatenation of strings, Languages, Empty Language

**Unit 2: Introduction to Finite Automata (8 Hrs.)**

- Introduction to Finite Automata, Introduction of Finite State Machine
- Deterministic Finite Automata (DFA), Notations for DFA, Language of DFA, Extended Transition Function of DFA Non-Deterministic Finite Automaton (NFA), Notations for NFA, Language of NFA, Extended Transition
- Equivalence of DFA and NFA, Subset-Construction
- Method for reduction of NFA to DFA, Theorems for equivalence of Language accepted by DFA and NFA
- Finite Automaton with Epsilon Transition (ε – NFA), Notations for ε – NFA, Epsilon Closure of a State, Extended Transition Function of ε – NFA, Removing Epsilon Transition using the concept of Epsilon Closure, Equivalence of NFA and ε –NFA, Equivalence of DFA and ε – NFA
- Finite State Machines with output: Moore machine and Mealy Machines

**Unit 3: Regular Expressions (6 Hrs.)**

- Regular Expressions, Regular Operators, Regular Languages and their applications, Algebraic Rules for Regular Expressions
- Equivalence of Regular Expression and Finite Automata, Reduction of Regular Expression to ε – NFA, Conversion of DFA to Regular Expression
- Properties of Regular Languages, Pumping Lemma, Application of Pumping Lemma, Closure Properties of Regular Languages over (Union, Intersection, Complement) Minimization of Finite State Machines: Table Filling Algorithm

**Unit IV: Context Free Grammar (9 Hrs.)**

- Introduction to Context Free Grammar (CFG), Components of CFG, Use of CFG, Context Free Language (CFL)
- Types of derivations: Bottomup and Topdown approach, Leftmost and Rightmost, Language of a grammar
- Parse tree and its construction, Ambiguous grammar, Use of parse tree to show ambiguity in grammar
- Regular Grammars: Right Linear and Left Linear, Equivalence of regular grammar and finite automata
- Simplification of CFG: Removal of Useless symbols, Nullable Symbols, and Unit Productions, Chomsky Normal Form (CNF), Greibach Normal Form (GNF), Backus-Naur Form (BNF)
- Context Sensitive Grammar, Chomsky Hierarchy Pumping Lemma for CFL, Application of Pumping Lemma, Closure Properties of CFL

**Unit 5: Push Down Automata (7 Hrs.)**

- Introduction to Push Down Automata (PDA), Representation of PDA, Operations of PDA, Move of a PDA, Instantaneous Synopsis for PDA
- Deterministic PDA, Non Deterministic PDA, Acceptance of strings by PDA, Language of PDA
- Construction of PDA by Final State , Construction of PDA by Empty Stack,
- Conversion of PDA by Final State to PDA accepting by Empty Stack and vice-versa, Conversion of CFG to PDA, Conversion of PDA to CFG

**Unit 6: Turing Machines (10 Hrs.)**

- Introduction to Turing Machines (TM), Notations of Turing Machine, Language of a Turing Machine, Instantaneous Synopsis for Turing Machine, Acceptance of a string by a Turing Machines
- Turing Machine as a Language Recognizer, Turing Machine as a Computing Function, Turing Machine with Storage in its State, Turing Machine as a enumerator of stings of a language, Turing Machine as Subroutine
- Turing Machine with Multiple Tracks, Turing Machine with Multiple Tapes, Equivalence of Multitape-TM and Multitrack-TM, Non-Deterministic Turing Machines, Restricted Turing Machines: With Semi-infinite Tape, Multistack Machines, Counter Machines
- Curch Turing Thesis, Universal Turing Machine, Turing Machine and Computers, Encoding of Turing Machine, Enumerating Binary Strings, Codes of Turing Machine, Universal Turing Machine for encoding of Turing Machine

**Unit 7: Undecidability and Intractability (5 Hrs.)**

- Computational Complexity, Time and Space complexity of A Turing Machine, Intractability
- Complexity Classes, Problem and its types: Absract, Decision, Optimization
- Reducibility, Turing Reducible, Circuit Satisfiability, Cook’s Theorem,
- Undecidability, Undecidable Problems: Post’s Correspondence Problem, Halting
- Problem and its proof, Undecidable Problem about Turing Machines

**Laboratory Works:
**The laboratory work consists of design and implementation of finite state machines like DFA, NFA, PDA, and Turing Machine. Students are highly recommended to construct Tokenizers/ Lexers over/for some language. Students are advised to use regex and Perl (for using regular expressions), or any other higher level language for the laboratory works.

**Nature of Course:** Theory (3 Hrs)+ Lab (3 Hrs)

**Text Books:**

- Data Communications and Networking, 4
^{th}Edition, Behrouz A Forouzan. McGraw-Hill - Computer Networking; A Top-Down Approach Featuring The Internet, 2nd Edition, Kurose James F., Ross W. Keith PEARSON EDUCATION ASIA

**Course Synopsis:
**This course introduces concept of computer networking and discuss the different layers of networking model.

**Goal:
**The main objective of this course is to introduce the understanding of the concept of computer networking with its layers, topologies, protocols & standards, IPv4/IPv6 addressing, Routing and Latest Networking Standards

**Course Contents:**

**Unit 1: Introduction to Computer Network (6Hrs.)**

- Definitions, Uses, Benefits
- Overview of Network Topologies (Star, Tree, Bus,…)
- Overview of Network Types (PAN, LAN, CAN, MAN,…)
- Networking Types (Client/Server, P2P)
- Overview of Protocols and Standards
- OSI Reference Model
- TCP/IP Models and its comparison with OSI.
- Connection and Connection-Oriented Network Services
- Internet, ISPs, Backbone Network Overview

**Unit 2: Physical Layer and Network Media (4Hrs.)**

- Network Devices: Repeater, Hub, Switch, Bridge, Router
- Different types of transmission medias (wired: twisted pair, coaxial, fiber optic, Wireless: Radio waves, micro waves, infrared)
- Ethernet Cable Standards (UTP & Fiber cable standards)
- Circuit, Message & Packet Switching
- ISDN: Interface and Standards

**Unit 3: Data Link Layer (8Hrs.)**

- Function of Data Link Layer (DLL)
- Overview of Logical Link Control (LLC) and Media Access Control (MAC)
- Framing and Flow Control Mechanisms
- Error Detection and Correction techniques
- Channel Allocation Techniques (ALOHA, Slotted ALOHA)
- Ethernet Standards (802.3 CSMA/CD, 802.4 Token Bus, 802.5 Token Ring)
- Wireless LAN: Spread Spectrum, Bluetooth, Wi-Fi
- Overview Virtual Circuit Switching, Frame Relay& ATM
- DLL Protocol: HDLC, PPP

**Unit 4: Network Layer (10Hrs.)**

- Introduction and Functions
- IPv4 Addressing & Sub-netting
- Class-full and Classless Addressing
- IPv6 Addressing and its Features
- IPv4 and IPv6 Datagram Formats
- Comparison of IPv4 and IPv6 Addressing
- Example Addresses: Unicast, Multicast and Broadcast
- Routing
- Introduction and Definition
- Types of Routing (Static vs Dynamic, Unicast vs Multicast, Link State vs Distance Vector, Interior vs Exterior)
- Path Computation Algorithms: Bellman Ford, Dijkstra’s
- Routing Protocols: RIP, OSPF & BGP

- Overview of IPv4 to IPv6 Transition Mechanisms
- Overview of ICMP/ICMPv6&NATing
- Overview of Network Traffic Analysis
- Security Concepts: Firewall & Router Access Control

**Unit 5: Transport Layer (6Hrs.)**

- Introduction, Functions and Services
- Transport Protocols: TCP, UDP and Their Comparisons
- Connection Oriented and Connectionless Services
- Congestion Control: Open Loop & Closed Loop, TCP Congestion Control
- Traffic Shaping Algorithms: Leaky Bucket & Token Bucket
- Queuing Techniques for Scheduling
- Introduction to Ports and Sockets, Socket Programming

**Unit 6: Application Layer (7Hrs.)**

- Introduction and Functions
- Web &HTTP
- DNS and the Query Types
- File Transfer and Email Protocols: FTP, SFTP, SMTP, IMAP, POP3
- Overview of Application Server Concepts: Proxy, Web, Mail
- Network Management: SNMP

**Unit 7: Multimedia &Future Networking (4Hrs.)**

- Overview Multimedia Streaming Protocols: SCTP
- Overview of SDN and its Features, Data and Control Plane
- Overview of NFV
- Overview of NGN

**Laboratory Works:
**The lab activities under this subject should accommodate at least the following;

- Understanding of Network equipment, wiring in details
- OS (Ubuntu/CentOS/Windows) installation, practice on basic Networking commands (ifconfig/ipconfig, tcpdump, netstat, dnsip, hostname, route…)
- Overview of IP Addressing and sub-netting, static ip setting on Linux/windows machine, testing
- Introduction to Packet Tracer, creating of a LAN and connectivity test in the LAN, creation of VLAN and VLAN trunking.
- Basic Router Configuration, Static Routing Implementation
- Implementation of Dynamic/interior/exterior routing (RIP, OSPF, BGP)
- Firewall Implementation, Router Access Control List (ACL)
- Packet capture and header analysis by wire-shark (TCP,UDP,IP)
- DNS, Web, FTP server configuration (shall use packet tracer, GNS3)
- Case Study: Network Operation Center Visit (ISP, Telecom, University Network)
- LAB Exam, Report and VIVA

**Nature of Course:** Theory (3 Hrs) + Lab (3 Hrs)

Text Book**s:**

- Modern Operating Systems: Andrew S. Tanenbaum, PH1 Publication, Third edition, 2008

**Reference ****Books:**

- Abraham Silberschatz, Peter Baer Galvin and Greg Gagne, “Operating System Concepts”, John Wiley & Sons (ASIA) Pvt. Ltd, Seventh edition, 2005.
- Harvey M. Deitel, Paul J. Deitel, and David R. Choffnes, “Operating Systems, Prentice Hall, Third edition, 2003.

**Course Synopsis:
**This course includes the basic concepts of operating system components. It consists of process management, deadlocks and process synchronization, memory management techniques, File system implementation, and I/O device management principles. It also includes case study on Linux operating system.

**Goals:**

- Describe need and role of operating system.
- Understand OS components such a scheduler, memory manager, file system handlers and I/O device managers.
- Analyze and criticize techniques used in OS components
- Demonstrate and simulate algorithms used in OS components
- Identify algorithms and techniques used in different components of Linux

**Course Contents****:**

**Unit 1: Operating System Overview (4 ****Hrs.****)**

- Definition, Two views of operating system, Evolution of operating system, Types of OS.
- System Call, Handling System Calls, System Programs, Operating System Structures, The Shell, Open Source Operating Systems

**Unit 2: Process Management (10 ****Hrs.****)**

- Process vs Program, Multiprogramming, Process Model, Process States, Process Control Block.
- Threads, Thread vs Process, User and Kernel Space Threads.
- Inter Process Communication, Race Condition, Critical Section
- Implementing Mutual Exclusion: Mutual Exclusion with Busy Waiting (Disabling Interrupts, Lock Variables, Strict Alteration, Peterson’s Solution, Test and Set Lock), Sleep and Wakeup, Semaphore, Monitors, Message Passing,
- Classical IPC problems: Producer Consumer, Sleeping Barber, Dining Philosopher Problem
- Process Scheduling: Goals, Batch System Scheduling (First-Come First-Served, Shortest Job First, Shortest Remaining Time Next), Interactive System Scheduling (Round-Robin Scheduling, Priority Scheduling, Multiple Queues), Overview of Real Time System Scheduling

**Unit 3: Process Deadlocks (6 ****Hrs.****)**

- Introduction, Deadlock Characterization, Preemptable and Non-preemptable Resources, Resource – Allocation Graph, Conditions for Deadlock
- Handling Deadlocks: Ostrich Algorithm, Deadlock prevention, Deadlock Avoidance, Deadlock Detection (For Single and Multiple Resource Instances), Recovery From Deadlock (Through Preemption and Rollback)

**Unit 4: Memory Management (8 ****Hrs.****)**

- Introduction, Monoprogramming vs. Multi-programming, Modelling Multiprogramming, Multiprogramming with fixed and variable partitions, Relocation and Protection.
- Memory management (Bitmaps & Linked-list), Memory Allocation Strategies
- Virtual memory: Paging, Page Table, Page Table Structure, Handling Page Faults, TLB’s
- Page Replacement Algorithms: FIFO, Second Chance, LRU, Optimal, LFU, Clock, WS-Clock, Concept of Locality of Reference, Belady’s Anomaly
- Segmentation: Need of Segmentation, its Drawbacks, Segmentation with Paging(MULTICS)

**Unit 5: File Management (6 ****Hrs.****)**

- File Overview: File Naming, File Structure, File Types, File Access, File Attributes, File Operations, Single Level, two Level and Hierarchical Directory Systems, File System Layout.
- Implementing Files: Contiguous allocation, Linked List Allocation, Linked List Allocation using Table in Memory, Inodes.
- Directory Operations, Path Names, Directory Implementation, Shared Files
- Free Space Management: Bitmaps, Linked List

**Unit 6: Device Management (6 ****Hrs.****)**

- Classification of IO devices, Controllers, Memory Mapped IO, DMA Operation, Interrupts
- Goals of IO Software, Handling IO(Programmed IO, Interrupt Driven IO, IO using DMA), IO Software Layers (Interrupt Handlers, Device Drivers)
- Disk Structure, Disk Scheduling (FCFS, SSTF, SCAN, CSCAN, LOOK, CLOOK), Disk Formatting (Cylinder Skew, Interleaving, Error handling), RAID

**Unit 7: Linux Case Study (5 ****Hrs.****)**

- History, Kernel Modules, Process Management, Scheduling, Inter-process Communication, Memory Management, File System Management Approaches, Device Management Approaches.

**Laboratory Work****s:
**The laboratory work includes solving problems in operating system. The lab work should include at least;

- Learn basic Linux Commands
- Create process, threads and implement IPC techniques
- Simulate process Scheduling algorithms and deadlock detection algorithms
- Simulate page replacement algorithms
- Simulate free space management techniques and disk scheduling algorithms.

**Nature of Course:** Theory (3 Hrs) + Lab (3 Hrs)

**Text Books:**

- Fundamentals of Database Systems; Seventh Edition; Ramez Elmasri, Shamkant B. Navathe; Pearson Education
- Database System Concepts; Sixth Edition; Avi Silberschatz, Henry F Korth, S Sudarshan; McGraw-Hill

**References:**

- Database Management Systems; Third Edition; Raghu Ramakrishnan, Johannes Gehrke; McGraw-Hill
- A First Course in Database Systems; Jaffrey D. Ullman, Jennifer Widom; Third Edition; Pearson Education Limited

**Course Synopsis:
**The course covers the basic concepts of databases, database system concepts and architecture, data modeling using ER diagram, relational model, SQL, relational algebra and calculus, normalization, transaction processing, concurrency control, and database recovery.

**Goal:
**The main objective of this course is to introduce the basic concepts of database, data modeling techniques using entity relationship diagram, relational algebra and calculus, basic and advanced features SQL, normalization, transaction processing, concurrency control, and recovery techniques.

**Course Contents:**

**Unit 1: Database and Database Users (2 Hrs.)
**Introduction; Characteristics of the Database Approach; Actors on the Scene; Workers behind the Scene; Advantages of Using the DBMS Approach

**Unit 2: Database System – Concepts and Architecture (3 Hrs.)
**Data Models, Schemas, and Instances; Three-Schema Architecture and Data Independence; Database Languages and Interfaces; the Database System Environment; Centralized and Client/Server Architectures for DBMSs; Classification of Database Management Systems

**Unit 3: Data Modeling Using the Entity-Relational Model (6 Hrs.)
**Using High-Level Conceptual Data Models for Database Design; Entity Types, Entity Sets, Attributes, and Keys; Relationship Types, Relationship Sets, Roles, and Structural Constraints; Weak Entity Types; ER Diagrams, Naming Conventions, and Design Issues; Relationship Types of Degree Higher Than Two; Subclasses, Superclasses, and Inheritance; Specialization and Generalization; Constraints and Characteristics of Specialization and Generalization

**Unit 4: The Relational Data Model and Relational Database Constraints (3 Hrs.)
**Relational Model Concepts; Relational Model Constraints and Relational Database Schemas; Update Operations, Transactions, and Dealing with Constraint Violations

**Unit 5: The Relational Algebra and Relational Calculus (5 Hrs.)
**Unary Relational Operations: SELECT and PROJECT; Relational Algebra Operations from Set Theory; Binary Relational Operations: JOIN and DIVISION; Additional Relational Operations; the Tuple Relational Calculus; the Domain Relational Calculus

**Unit 6: SQL (8 Hrs.)
**Data Definition and Data Types; Specifying Constraints; Basic Retrieval Queries; Complex Retrieval Queries; INSERT, DELETE, and UPDATE Statements; Views

**Unit 7: Relational Database Design (7 Hrs.)
**Relational Database Design Using ER-to-Relational Mapping; Informal Design Guidelines for Relational Schemas; Functional Dependencies; Normal Forms Based on Primary Keys; General Definitions of Second and Third Normal Forms; Boyce-Codd Normal Form; Multivalued Dependency and Fourth Normal Form; Properties of Relational Decomposition

**Unit 8: Introduction to Transaction Processing Concepts and Theory (4 Hrs.)
**Introduction to Transaction Processing; Transaction and System Concepts; Desirable Properties of Transactions; Characterizing Schedules Based on Recoverability; Characterizing Schedules Based on Serializability

**Unit 9: Concurrency Control Techniques (4 Hrs.)
**Two-Phase Locking Technique; Timestamp Ordering; Multiversion Concurrency Control

**;**Validation (Optimistic) Techniques and Snapshot Isolation Concurrency Control

**Unit 10: Database Recovery Techniques (3 Hrs.)
**Recovery Concepts; NO-UNDO/REDO Recovery Based on Deferred Update; Recovery Technique Based on Immediate Update; Shadow Paging; Database Backup and Recovery from Catastrophic Failures

**Laboratory Works:
**The laboratory work includes writing database programs to create and query databases using basic and advanced features of structured query language (SQL).

**Nature of Course:** Theory (3 Hrs) + Lab (3 Hrs)

**Text Books:**

1. Stuart Russel and Peter Norvig, *Artificial Intelligence A Modern Approach*, Pearson

**Reference Books:**

- E. Rich, K. Knight, Shivashankar B. Nair,
*Artificial Intelligence*, Tata McGraw Hill. - George F. Luger,
*Artificial Intelligence: Structures and Strategies for Complex Problem**Solving*, Benjamin/Cummings Publication - D. W. Patterson,
*Artificial Intelligence and Expert Systems*, Prentice Hall. - P. H. Winston,
*Artificial Intelligence*, Addison Wesley.

**Course Synopsis:
**The course introduces the ideas and techniques underlying the principles and design of artificial intelligent systems. The course covers the basics and applications of AI, including design of intelligent agents, problem-solving, searching, knowledge representation systems, probabilistic reasoning, neural networks, machine learning and natural language processing.

**Goals:
**The main objective of the course is to introduce fundamental concepts of Artificial Intelligence. The general objectives are to learn about computer systems that exhibit intelligent behavior, design intelligent agents, identify AI problems and solve the problems, design knowledge representation and expert systems, design neural networks for solving problems, identify different machine learning paradigms and identify their practical applications.

**Course Contents:**

**Unit 1: Introduction (3 Hrs.)**

- Artificial Intelligence (AI), AI Perspectives: acting and thinking humanly, acting and thinking rationally
- History of AI
- Foundations of AI
- Applications of AI

**Unit 2: Intelligent Agents (4 Hrs.)**

- Introduction of agents, Structure of Intelligent agent, Properties of Intelligent Agents
- Configuration of Agents, PEAS Synopsis of Agents
- Types of Agents: Simple Reflexive, Model-Based, Goal-Based, Utility-Based.
- Environment Types: Deterministic, Stochastic, Static, Dynamic, Observable, Semi-observable, Single Agent, Multi-Agent

**Unit 3: Problem Solving by Searching (9 Hrs.)**

- Definition, Problem as a state space search, Problem formulation, Well-defined problems,
- Solving Problems by Searching, Search Strategies, Performance evaluation of search techniques
- Uninformed Search: Depth First Search, Breadth First Search, Depth-Limited Search, Iterative Deepening Search, Bidirectional Search
- Informed Search: Greedy Best first search, A* search, Hill Climbing, Simulated Annealing
- Game playing, Adversarial search techniques, Mini-max Search, Alpha-Beta Pruning.
- Constraint Satisfaction Problems

**Unit 4: Knowledge Representation (14 Hrs.)**

- Definition and importance of Knowledge, Issues in Knowledge Representation, Knowledge Representation Systems, Properties of Knowledge Representation Systems.
- Types of Knowledge Representation Systems: Semantic Nets, Frames, Conceptual Dependencies, Scripts, Rule-Based Systems, Propositional Logic, Predicate Logic
- Propositional Logic(PL): Syntax, Semantics, Formal logic-connectives, truth tables, tautology, validity, well-formed-formula, Inference using Resolution, Backward Chaining and Forward Chaining
- Predicate Logic: FOPL, Syntax, Semantics, Quantification, Inference with FOPL: By converting into PL (Existential and universal instantiation), Unification and lifting, Inference using resolution
- Handling Uncertain Knowledge, Radom Variables, Prior and Posterior Probability, Inference using Full Joint Distribution, Bayes’ Rule and its use, Bayesian Networks, Reasoning in Belief Networks
- Fuzzy Logic

**Unit 5: Machine Learning (9 Hrs.)**

- Introduction to Machine Learning, Concepts of Learning, Supervised, Unsupervised and Reinforcement Learning
- Statistical-based Learning: Naive Bayes Mode
- Learning by Genetic Algorithm
- Learning with Neural Networks: Introduction, Biological Neural Networks Vs. Artificial Neural Networks (ANN), Mathematical Model of ANN, Types of ANN: Feed-forward, Recurrent, Single Layered, Multi-Layered, Application of Artificial Neural Networks, Learning by Training ANN, Supervised vs. Unsupervised Learning, Hebbian Learning, Perceptron Learning, Back-propagation Learning

**Unit 6: Applications of AI (6 Hrs.)**

- Expert Systems, Development of Expert Systems
- Natural Language Processing: Natural Language Understanding and Natural Language Generation, Steps of Natural Language Processing
- Machine Vision Concepts
- Robotics

**Laboratory Works:
**The laboratory work consists of design and implementation of intelligent agents and expert systems, searching techniques, knowledge representation systems and machine learning techniques. Students are also advised to implement Neural Networks, Genetic Algorithms for solving practical problems of AI. Students are advised to use LISP, PROLOG, or any other high-level language.