- Academics
- B.Sc.CSIT
- New Course
- Freshman Year
- Sophomore Year
- Junior Year
- Senior Year

- Old Course
- Freshman Year
- Sophomore Year
- Junior Year
- Senior Year

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.

Goal:

- 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 Treesm,
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:

1. W. Chency and D. Kincaid, "Numerical Mathematics and Computing", 7th Edition, Brooks/Cole Publishing Co, 2012

2. C.F. Gerald and P.O. Wheatley, "Applied Numerical Analysis", 9th Edition, Addison Wesley Publishing Company, New York, 2011

Reference Books:

1. E. Balagurusamy, “Numerical Methods”, Tata McGraw-Hill Publishing Company Ltd., New Delhi, 1999

2. W.H. Press, B.P. Flannery et al., "Numerical Recipes: Art of Scientific Computing", 3rd Edition, Cambridge Press, 2007.

3. J. M. Mathews and K. Fink, “Numerical Methods using MATLAB “, 4rd Edition, Prentice
Hall Publication, 2004

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:

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

Reference Books:
1. William Stallings, “Computer Organization and Architecture”, Prentice-Hall of India, Pvt. Ltd., Seventh edition, 2005.

2. 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:

- 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, Micro instruction 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:
1. J.D. Foley, S.K. Feiner and J.F. Hughes, “Computer Graphics – Principles and Practises” (Second Edition in C)

2. R.K. Maurya, “Computer Graphics with Virtual Reality”, Wiley India

3. 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 (3 Hrs)

Text Books:

1. Ronald E. Walpole, Raymond H. Myers, Sharon L. Myers, & Keying Ye(2012). Probability & Statistics for Engineers & Scientists. 9th Ed., Printice Hall

2. Michael Baron (2013). Probability and Statistics for Computer Scientists. 2nd Ed., CRC Press, Taylor & Francis Group, A Chapman & Hall Book

Reference Books:
1.Douglas C. Montgomery & George C. Runger (2003). Applied Statistics and Probability for Engineers. 3rd Ed., John Willey and Sons, Inc.

2.Sidney Siegel, & N. John Castellan, Jr. Nonparametric Statistics for the Behavioral Sciences, 2nd 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.

Goal: 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.

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, 3rd Edition, Pearson – Addison-Wesley.

Reference Books:
1. Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, 2nd Edition, Prentice Hall.

2. Michael Sipser, Introduction to the Theory of Computation, 3rd Edition, Thomson Course Technology

3. Efim Kinber, Carl Smith, Theory of Computing: A Gentle Introduction, Prentice- Hall.

4. John Martin, Introduction to Languages and the Theory of Computation, 3rd 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.

Goal: 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 4: 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, 4th 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: Sampling Distribution and Estimation (6 Hrs.)

- 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 6: Application Layer (7Hrs.)

- 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 Books:

- 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.

Goal:

- 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 Works:

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

Reference Books:

- 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:

- 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.

Goal: 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.