# BSc.CSIT Third Semester Syllabus | TU Syllabus

0
943 ## BSc.CSIT Third Semester Syllabus Overview

Syllabus of BSc.CSIT Third Semester comprises five compulsory courses that include Data Structures and Algorithm, Numerical Method, Computer Architecture, Computer Graphics, and Statistics II. They are a total of 15 credit hours with a total of 500 full marks.

BSc.CSIT Third Semester course code is shown below in table:

### Course Title 1: Data Structures and Algorithm

Full Marks: 60 + 20 + 20

Course No: CSC206

Pass Marks: 24 + 8 + 8

Nature of the Course: Theory + Lab

Credit Hrs

Semester: III

Course Description: 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.

Course Objectives:

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

Course Contents:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Concept and Definitions, Basic Operations in Binary Tree, Tree Height, Level and Depth
1. Binary Search Tree, Insertion, Deletion, Traversals, Search in BST
1. AVL tree and Balancing algorithm, Applications of Trees
1. Definition and Representation of Graphs, Graph Traversal, Minimum Spanning Trees: Kruskal and Prims Algorithm
1. 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;

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

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       Computting
1. G.W Rowe, Introduction to Data Structure and Algroithms with C and C++ , prentice Hall  India
1. R.L Kruse, B.P. Leung, C.L. Tondo, Data Structure and Program Design in C PrenticeHall India

### Course Title 2: Numerical Method

Full Marks: 60 + 20 + 20

Course No.: CSC207

Pass Marks: 24 + 8 + 8

Nature of the Course: Theory + Lab

Credit Hrs: 3

Semester: III

Course Description: This course contains the concepts of numerical method techniques for solving linear and nonlinear equations, interpolation and regression, differentiation and integration, and partial differential equations.

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

Course Content:

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

1.1Errors in Numerical Calculations, Sources of Errors, Propagation of Errors, Review of Taylor’s Theorem

1.2Solving 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.)

2.1Interpolation vs Extrapolation, Lagrange’s Interpolation, Newton’s Interpolation using divided differences, forward differences and backward differences, Cubic spline interpolation

2.2Introduction 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.)

3.1Differentiating Continuous Functions (Two-Point and Three-Point Formula), Differentiating Tabulated Functions by using Newton’s Differences, Maxima and minima of Tabulated Functions

3.2Newton-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, MultiSegment Simpson’s 3/8 rule, Gaussian integration algorithm, Romberg integration

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

4.1Review of the existence of solutions and properties of matrices, Gaussian elimination method, pivoting, Gauss-Jordan method, Inverse of matrix using Gauss-Jordan  method

4.2Matrix factorization and Solving System of Linear Equations by using Dolittle and Cholesky’s algorithm

4.3Iterative Solutions of System of Linear Equations, Jacobi Iteration Method, Gauss-Seidal Method

4.4Eigen values and eigen vectors problems, Solving eigen value problems using power method.

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

5.1Review of differential equations, Initial value problem, Taylor series method, Picard’s method, Euler’s method and its accuracy, Heun’s method, Runge-Kutta methods

5.2Solving 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.)

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

Text Books:

1. W. Chency and D. Kincaid, “Numerical Mathematics and Computing“, 7thEdition, Brooks/Cole Publishing Co, 2012
1. C.F. Gerald and P.O. Wheatley, “Applied Numerical Analysis“, 9thEdition, Addison Wesley Publishing Company, New York, 2011

#### Reference Books:

1. E. Balagurusamy, “Numerical Methods”, Tata McGraw-Hill Publishing Company Ltd., New Delhi, 1999
1. W.H. Press, B.P. Flannery et al., “Numerical Recipes: Art of Scientific Computing“, 3rd  Edition, Cambridge Press, 2007.
1. J. M. Mathews and K. Fink, “Numerical Methods using MATLAB “, 4rd Edition, Prentice Hall Publication, 2004

### Course Title 3: Computer Architecture

Full Marks: 60 + 20 + 20

Course No: CSC208

Pass Marks: 24 + 8 + 8

Nature of the Course: Theory + Lab

Credit Hrs

Semester: III

Course Description: 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.

.

Course Objectives:

1. Discuss representation of data and algorithms used to perform operations on data
1. Demonstrate different operations in terms of Micro-operations
1. Explain architecture of basic computer and micro-programmed control unit
1. Understand and memory and I/O organization of a typical computer system
2. Demonstrate the benefits of pipelined systems     Course Contents: Unit 1: Data Representation (4 Hrs.)
1. Data Representation: Binary Representation, BCD, Alphanumeric Representation, Complements, Fixed Point representation, Representing Negative Numbers, Floating Point Representation, Arithmetic with Complements, Overflow, Detecting Overflow
1. Other Binary Codes: Gray Code, self Complementing Code, Weighted Code, Excess-3 Code, EBCDIC
1. Error Detection Codes: Parity Bit, Odd Parity, Even parity, Parity Generator & Checker

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

1. Microoperation, Register Transfer Language, Register Transfer, Control Function
1. Logic Microoperations, Hardware Implementation, Applications of Logic Microoperations.
1. Shift Microoperations: Logical Shift, Circular shift, Arithmetic Shift, Hardware Implementation of Shifter.

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

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

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

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

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

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

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

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

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

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

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

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

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

9.1Memory Hierarchy, Main Memory, RAM and ROM Chips, Memory address Map, Memory Connection to CPU, Auxiliary Memory (magnetic Disk, Magnetic Tape)

9.1Associative Memory: Hardware Organization, Match Logic, Read Operation, Write Operation

9.1Cache 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;

1. Simulate features like overflow, data representation by using VHDL
1. Simulate design of different units by using VHDL
1. Simulate pipelining by using VHDL

Implement algorithms for computer arithmetic using a high-level languages like C or C++
Text Books:

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

References Books:

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

### Course Title 4: Computer Graphics

Full Marks: 60 + 20 + 20

Course no: CSC209

Pass Marks: 24 + 8 + 8

Nature of the Course: Theory + Lab

Credit Hrs: 3

Semester: III

Course Description: 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.

Course Objectives: 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 of Computer Graphics (3 Hrs.)

1.1A Brief Overview of Computer Graphics, Areas of Applications.

1.2Graphics Hardware: Display Technology, Architecture of Raster-Scan

Displays, Vector Displays, Display Processors, Hard copy device.  Input Devices.

1.3Graphics Software: Software standards, Need of machine independent graphics language.

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

2.1Scan Converting a Point and a straight Line: DDA Line Algorithm, Bresenham’s Line Algorithm

2.2Scan Converting Circle and Ellipse :Mid Point Circle and Ellipse Algorithm

2.3Area 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.)

3.1 Two-Dimensional  translation, Rotation, Scaling, Reflection and Shearing

3.2 Homogeneous Coordinate and 2D Composite Transformations. Transformation between Co-ordinate Systems.

3.3Two Dimensional Viewing: Viewing pipeline, Window to viewport coordinate transformation

3.4Clipping: Point, Lines(Cohen Sutherland line clipping, Liang-Barsky Line Clipping) , Polygon Clipping(Sutherland Hodgeman polygon clipping)

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

4.1Three-Dimensional  translation, Rotation, Scaling, Reflection and Shearing

4.2Three-Dimensional  Composite Transformations

4.3Three-Dimensional Viewing:  Viewing pipeline, world to screen viewing transformation, Projection concepts(Orthographic, parallel, perspective projections)

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

5.1Representing Surfaces: Boundary and Space partitioning

5.1.1Polygon Surface:  Polygon tables , Surface normal and Spatial orientation of surfaces, Plane equations, Polygon meshes

5.1.2Wireframe Representation

5.1.3Blobby Objects

5.2Representing Curves: Parametric Cubic Curves,  Spline Representation, Cubic spline interpolation, Hermite Curves, Bezier and B-spline Curve and surface

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

6.1Sweep ,Boundary and Spatial-Partitioning  Representation

6.2Binary Space Partition Trees (BSP)

6.3Octree Representation

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

7.1Image Space and Object Space Techniques

7.2Back Face Detection, Depth Buffer (Z-buffer), A-Buffer and Scan-Line Algorithms.

7.3Depth Sorting Method (Painter’s Algorithm)

7.4BSP tree Method, Octree and Ray Tracing

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

8.1Basic Illumination Models: Ambient light, Diffuse reflection, Specular reflection and Phong model

8.2Intensity attenuation  and Color consideration ,Transparency, Shadows

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

9.1Concept of Virtual reality

9.2Virtual Reality Components of VR System, Types of VR System, 3D Position Trackers, Navigation and Manipulation Interfaces

9.3Application of VR

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

1.1Introduction, 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.

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

Text Books:

1.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)
1. R.K. Maurya, “Computer Graphics with Virtual Reality”, Wiley India
1. F.S. Hill, Stephen M.Kelley, “Computer Graphics using Open GL” Prentice Hall

### Course Title: Statistics II

Full Marks: 60 + 20 + 20

Course No: STA210

Pass Marks: 24 + 8 + 8

Nature of Course: Theory + Lab

Credit Hrs: 3

Semester: III

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

Course Objectives: 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 nonparametric statistical tests, design of experiments, multiple regression analysis, and basic concept of stochastic process with special focus to data/problems related with 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 correlation; 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.

Text Books:

1. Ronald E. Walpole, Raymond H. Myers, Sharon L. Myers, & Keying Ye(2012).

Probability & Statistics for Engineers & Scientists. 9th  Ed.,  Printice Hall

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