COMPUTER SCIENCE AND ENGINEERING

SEMESTER -4
COMPUTER SCIENCE AND ENGINEERING

SEMESTER IV

COURSE
SLOT COURSES L-T-P HOURS CREDIT
NO.

A MAT 206 GRAPH THEORY 3-1-0 4 4

C O M P U T E R
B CST 202 O R G A N I S A T I O N A N D 3-1-0 4 4
ARCHITECTURE

DATABASE MANAGEMENT
C CST 204 3-1-0 4 4
SYSTEMS

D CST 206 OPERATING SYSTEMS 3-1-0 4 4

E EST 200 DESIGN & ENGINEERING 2-0-0 2 2

(1/2) HUT 200 PROFESSIONAL ETHICS 2-0-0 2 2

F MNC 202 CONSTITUTION OF INDIA 2-0-0 2 --

S CSL 202 DIGITAL LAB 0-0-3 3 2

T CSL204 OPERATING SYSTEMS LAB 0-0-3 3 2

R/M/
VAC Remedial/Minor/Honors course 3-1-0 4 4
H

TOTAL 26* 22/26

* Excluding Hours to be engaged for Remedial/Minor/Honors course.

NOTE:

1. Design & Engineering and Professional Ethics shall be offered in both S3 and S4.
Institutions can advise students belonging to about 50% of the number of branches in
the Institution to opt for Design & Engineering in S3 and Professional Ethics in S4 &
vice versa.

2. *All Institutions should keep 4 hours exclusively for Remedial class/Minor course
(Thursdays from 3 to 5 PM and Fridays from 2 to 4 PM). If a student does not opt for
minor programme, he/she can be given remedial class.

153
COMPUTER SCIENCE AND ENGINEERING

CODE COURSE NAME CATEGORY L T P CREDIT

MAT 206 GRAPH THEORY BSC 3 1 0 4

Preamble: This course introduces fundamental concepts in Graph Theory, including

properties and characterisation of graph/trees and graph theoretic algorithms, which are
widely used in Mathematical modelling and has got applications across Computer Science
and other branches in Engineering.

Prerequisite: The topics covered under the course Discrete Mathematical Structures (MAT
203 )

Course Outcomes: After the completion of the course the student will be able to

Explain vertices and their properties, types of paths, classification of graphs and
CO 1
trees & their properties. (Cognitive Knowledge Level: Understand)
Demonstrate the fundamental theorems on Eulerian and Hamiltonian graphs.
CO 2
(Cognitive Knowledge Level: Understand)

Illustrate the working of Prim’s and Kruskal’s algorithms for finding minimum cost
CO 3 spanning tree and Dijkstra’s and Floyd-Warshall algorithms for finding shortest
paths. (Cognitive Knowledge Level: Apply)
Explain planar graphs, their properties and an application for planar graphs.
CO 4
(Cognitive Knowledge Level: Apply)

Illustrate how one can represent a graph in a computer. (Cognitive Knowledge

CO 5
Level: Apply)

Explain the Vertex Color problem in graphs and illustrate an example application
CO 6
for vertex coloring. (Cognitive Knowledge Level: Apply)
COMPUTER SCIENCE AND ENGINEERING
Mapping of course outcomes with program outcomes

PO PO PO PO PO
PO 2 PO 3 PO 4 PO 7 PO 10 PO 11 PO 12
1 5 6 8 9

CO 1 √ √ √ √ √

CO 2 √ √ √ √ √ √

CO 3 √ √ √ √ √ √

CO 4 √ √ √ √ √ √

CO 5 √ √ √ √ √

CO 6 √ √ √ √ √ √

Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics

PO3 Design/Development of solutions PO9 Individual and team work

Conduct investigations of complex
PO4 PO10 Communication
problems
PO5 Modern tool usage PO11 Project Management and Finance
PO6 The Engineer and Society PO12 Life long learning

Assessment Pattern

Continuous Assessment Tests (%) End Semester

Bloom’s Category
Examination (%)
1 2
Remember 30 30 30

Understand 30 30 30
Apply 40 40 40

Analyse
Evaluate

Create
COMPUTER SCIENCE AND ENGINEERING

Mark Distribution

Total Marks CIE Marks ESE Marks ESE Duration

150 50 100 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 10 marks

Continuous Assessment Tests : 25 marks

Continuous Assessment Assignment : 15 marks

Internal Examination Pattern:

Each of the two internal examinations has to be conducted out of 50 marks

First Internal Examination shall be preferably conducted after completing the first half of the
syllabus and the Second Internal Examination shall be preferably conducted after completing
remaining part of the syllabus.

There will be two parts: Part A and Part B. Part A contains 5 questions (preferably, 2
questions each from the completed modules and 1 question from the partly covered module),
having 3 marks for each question adding up to 15 marks for part A. Students should answer
all questions from Part A. Part B contains 7 questions (preferably, 3 questions each from the
completed modules and 1 question from the partly covered module), each with 7 marks. Out
of the 7 questions in Part B, a student should answer any 5.

End Semester Examination Pattern: There will be two parts; Part A and Part B. Part A
contain 10 questions with 2 questions from each module, having 3 marks for each question.
Students should answer all questions. Part B contains 2 questions from each module of which
student should answer anyone. Each question can have maximum 2 sub-divisions and carries
14 marks.
COMPUTER SCIENCE AND ENGINEERING

Syllabus

Module 1

Introduction to Graphs : Introduction- Basic definition – Application of graphs – finite,

infinite and bipartite graphs – Incidence and Degree – Isolated vertex, pendant
vertex and Null graph. Paths and circuits – Isomorphism, sub graphs, walks, paths
and circuits, connected graphs, disconnected graphs and components.

Module 2

Eulerian and Hamiltonian graphs : Euler graphs, Operations on graphs, Hamiltonian paths
and circuits, Travelling salesman problem. Directed graphs – types of digraphs, Digraphs and
binary relation, Directed paths, Fleury’s algorithm.

Module 3

Trees and Graph Algorithms : Trees – properties, pendant vertex, Distance and centres in a
tree - Rooted and binary trees, counting trees, spanning trees, Prim’s algorithm and Kruskal’s
algorithm, Dijkstra’s shortest path algorithm, Floyd-Warshall shortest path algorithm.

Module 4

Connectivity and Planar Graphs : Vertex Connectivity, Edge Connectivity, Cut set and Cut
Vertices, Fundamental circuits, Planar graphs, Kuratowski’s theorem (proof not required),
Different representations of planar graphs, Euler's theorem, Geometric dual.

Module 5

Graph Representations and Vertex Colouring : Matrix representation of graphs-

Adjacency matrix, Incidence Matrix, Circuit Matrix, Path Matrix. Coloring- Chromatic
number, Chromatic polynomial, Matchings, Coverings, Four color problem and Five color
problem. Greedy colouring algorithm.

Text book:

1. Narsingh Deo, Graph theory, PHI,1979

Reference Books:

1. R. Diestel, Graph Theory, free online edition, 2016: diestel-graph-theory.com/

basic.html.
2. Douglas B. West, Introduction to Graph Theory, Prentice Hall India Ltd.,2001
3. Robin J. Wilson, Introduction to Graph Theory, Longman Group Ltd.,2010
4. J.A. Bondy and U.S.R. Murty. Graph theory with Applications
COMPUTER SCIENCE AND ENGINEERING

Sample Course Level Assessment Questions.

Course Outcome 1 (CO1):

1. Differentiate a walk, path and circuit in a graph.

2. Is it possible to construct a graph with 12 vertices such that two of the vertices have
degree 3 and the remaining vertices have degree 4? Justify

3. Prove that a simple graph with n vertices must be connected, if it has more than
(n − 1)(n − 2)
edges.
2
4. Prove the statement: If a graph (connected or disconnected) has exactly two odd degree,
then there must be a path joining these two vertices.

Course Outcome 2 (CO2):

1. Define Hamiltonian circuit and Euler graph. Give one example for each.

2. Define directed graphs. Differentiate between symmetric digraphs and asymmetric

digraphs.

3. Prove that a connected graph G is an Euler graph if all vertices of G are of even degree.

4. Prove that a graph G of n vertices always has a Hamiltonian path if the sum of the degrees
of every pair of vertices Vi, Vj in G satisfies the condition d(Vi) + d(Vj) = n −1
Course Outcome 3 (CO3):

1. Discuss the centre of a tree with suitable example.

(n + 1)
2. Define binary tree. Then prove that number of pendant vertices in a binary tree is
2
3. Prove that a tree with n vertices has n − 1 edges.

4. Explain Floyd Warshall algorithm.

5. Run Dijkstra’s algorithm on the following directed graph, starting at vertex S.

COMPUTER SCIENCE AND ENGINEERING

Course Outcome 4 (CO4):

1. Define edge connectivity, vertex connectivity and separable graphs. Give an example for
each.

2. Prove that a connected graph with n vertices and e edges has e − n + 2 edges.

3. Prove the statement: Every cut set in a connected graph G must also contain at least one
branch of every spanning tree of G.

4. Draw the geometrical dual (G*) of the graph given below, also check whether G and G*
are self-duals or not, substantiate your answer clearly.

Course Outcome 5 (CO5):

1. Show that if A(G) is an incidence matrix of a connected graph G with n vertices, then
rank of A(G) is n−1.

2. Show that if B is a cycle matrix of a connected graph G with n vertices and m edges, then
rank B = m−n+1.

3. Derive the relations between the reduced incidence matrix, the fundamental cycle matrix,
and the fundamental cut-set matrix of a graph G.

4. Characterize simple, self-dual graphs in terms of their cycle and cut-set matrices.

Course Outcome 6 (CO6):

1. Show that an n vertex graph is a tree iff its chromatic polynomial is P n (λ) = λ(λ − 1)n −1

2. Prove the statement: “A covering g of a graph is minimal if g contains no path of length

three or more.”

3. Find the chromatic polynomial of the graph

COMPUTER SCIENCE AND ENGINEERING
Model Question paper

QP
Code : Total Pages: 4

Reg No.:_______________ Name:__________________________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

IV SEMESTER B.TECH DEGREE EXAMINATION, MONTH and YEAR
Course Code: MAT 206
Course Name: GRAPH THEORY
Max. Marks: 100 Duration: 3 Hours
PART A
Answer all questions, each carries3 marks. Mark
s

1 Construct a simple graph of 12 vertices with two of them having degree 1, (3)
three having degree 3 and the remaining seven having degree 10.
2 What is the largest number of vertices in a graph with 35 edges, if all (3)
vertices are of degree at least 3 ?
3 Define a Euler graph. Give an example of Eulerian graph which is not (3)
Hamiltonian
4 Give an example of a strongly connected simple digraph without a directed (3)
Hamiltonian path.
5 What is the sum of the degrees of any tree of n vertices? (3)
6 How many spanning trees are there for the following graph (3)
COMPUTER SCIENCE AND ENGINEERING
7 Show that in a simple connected planar graph G having V-vertices, E-edges, (3)
and no triangles E <= 3V - 6.
8 Let G be the following disconnected planar graph. Draw its dual G*, and the (3)
dual of the dual (G*)*.

9 Consider the circuit matrix B and incidence matrix A of a simple connected (3)
graph whose columns are arranged using the same order of edges. Prove that
every row of B is orthogonal to every row of A?
10 A graph is critical if the removal of any one of its vertices (and the edges (3)
adjacent to that vertex) results in a graph with a lower chromatic number.
Show that Kn is critical for all n > 1.
PART B
Answer any one Question from each module. Each question carries 14 Marks
11 a) Prove that for any simple graph with at least two vertices has two vertices of (6)
the same degree.
b) Prove that in a complete graph with n vertices there are (n-1)/2 edge disjoint (8)
Hamiltonian circuits and n >= 3
OR
COMPUTER SCIENCE AND ENGINEERING
12 a) Determine whether the following graphs G1 = (V1, E1) and G2 = (V2, E2) are (6)
isomorphic or not. Give justification.

b) Prove that a simple graph with n vertices and k components can have at (8)
most (n-k) (n-k+1)/2 edges
13 a) Let S be a set of 5 elements. Construct a graph G whose vertices are subsets (8)
of S of size 2 and two such subsets are adjacent in G if they are disjoint.
i. Draw the graph G.
ii. How many edges must be added to G in order for G to have a
Hamiltonian cycle?
b) Let G be a graph with exactly two connected components, both being (6)
Eulerian. What is the minimum number of edges that need to be added to G
to obtain an Eulerian graph?

OR
14 a) Show that a k-connected graph with no hamiltonian cycle has an (8)
independent set of size k + 1.
b) i. Let G be a graph that has exactly two connected components, both
being Hamiltonian graphs. Find the minimum number of edges that
one needs to add to G to obtain a Hamiltonian graph. (6)
ii. For which values of n the graph Qn (hyper-cube on n vertices) is
Eulerian.
15 a) A tree T has at least one vertex v of degree 4, and at least one vertex w of (5)
degree 3. Prove that T has at least 5 leaves.
COMPUTER SCIENCE AND ENGINEERING
b) Write Dijkstra’s shortest path algorithm. (9)
Consider the following weighted directed graph G.

Find the shortest path between a and every other vertices in G using
Dijkstra’s shortest path algorithm.
OR
16 a) Define pendent vertices in a binary tree? Prove that the number of pendent (5)
vertices in a binary tree with n vertices is (n+1)/2.
b) (9)
Write Prim’s algorithm for finding minimum spanning tree.
Find a minimum spanning tree in the following weighted graph, using
Prim's algorithm.

Determine the number of minimum spanning trees for the given graph.
COMPUTER SCIENCE AND ENGINEERING
17 a) i. State and prove Euler's Theorem relating the number of faces, edges and (9)
vertices for a planar graph.
ii. If G is a 5-regular simple graph and |V| = 10, prove that G is non-planar.
b) Let G be a connected graph and e an edge of G. Show that e is a cut-edge if (5)
and only if e belongs to every spanning tree.
OR
18 a) State Kuratowski's theorem, and use it to show that the graph G below is not (9)
planar. Draw G on the plane without edges crossing. Your drawing should
use the labelling of the vertices given.

b) Let G be a connected graph and e an edge of G. Show that e belongs to a (5)

loop if and only if e belongs to no spanning tree.
19 a) Define the circuit matrix B(G) of a connected graph G with n vertices and e (7)
edges with an example. Prove that the rank of B(G) is e-n+1
b) Give the definition of the chromatic polynomial PG(k). Directly from the (7)
definition, prove that the chromatic polynomials of Wn and Cn satisfy the
identity PWn(k) = k PCn-1 (k – 1).

OR
20 a) Define the incidence matrix of a graph G with an example. Prove that the (4)
rank of an incidence matrix of a connected graph with n vertices is n-1.
COMPUTER SCIENCE AND ENGINEERING
b) i. A graph G has chromatic polynomial PG(k) = k4-4k3+5k2-2k. How
many vertices and edges does G have? Is G bipartite? Justify your
answers.
ii. Find a maximum matching in the graph below and use Hall's theorem
to show that it is indeed maximum.

(10)

****

Assignments

Assignment must include applications of the above theory in Computer Science.

COMPUTER SCIENCE AND ENGINEERING
Teaching Plan

No. of
No Topic
Lectures

1 Module-I (Introduction to Graphs) (8)

1. Introduction- Basic definition – Application of graphs – finite and 1

infinite graphs, bipartite graphs,

2. Incidence and Degree – Isolated vertex, pendent vertex and Null graph 1

3. Paths and circuits 1

4. Isomorphism 1

5. Sub graphs, walks 1

6. Paths and circuits 1

7. Connected graphs. 1

8. Disconnected graphs and components 1

2 Module-II (Eulerian and Hamiltonian graphs) (8)

1. Euler graphs 1

2. Operations on graphs 1

3. Hamiltonian paths and circuits 1

4. Hamiltonian paths circuits 1

5. Travelling salesman problem 1

6. Directed graphs – types of digraphs, 1

7. Digraphs and binary relation, Directed paths 1

8. Fleury’s algorithm 1

3 Module-III (Trees and Graph Algorithms) (11)

1. Trees – properties 1

2. Trees – properties 1

3. Trees – properties, pendent vertex 1

4. Distance and centres in a tree 1

COMPUTER SCIENCE AND ENGINEERING
5. Rooted and binary tree 1

6. Counting trees 1

7. Spanning trees, Fundamental circuits 1

8. Prim’s algorithm 1

9. Kruskal’s algorithm 1

10. Dijkstra’s shortest path algorithm 1

11. Floyd-Warshall shortest path algorithm 1

4 Module-IV (Connectivity and Planar Graphs) (9)

1. Vertex Connectivity, Edge Connectivity 1

2. Cut set and Cut Vertices 1

3. Fundamental circuits 1

4. Fundamental circuits 1

5. Planar graphs 1

6. Kuratowski’s theorem 1

7. Different representations of planar graphs 1

8. Euler's theorem 1

9. Geometric dual 1

5 Module-V (Graph Representations and Vertex Colouring) (9)

1. Matrix representation of graphs- Adjacency matrix, Incidence Matrix 1

2. Circuit Matrix, Path Matrix 1

3. Colouring- chromatic number, 1

4. Chromatic polynomial 1

5. Matching 1

6. Covering 1

7. Four colour problem and five colour problem 1

COMPUTER SCIENCE AND ENGINEERING
8. Four colour problem and five colour problem 1

9. Greedy colouring algorithm. 1

COMPUTER SCIENCE AND ENGINEERING

Computer YEAR OF
CATEGORY L T P CREDIT
CST 202 Organization INTRODUCTION
and Architecture PCC 3 1 0 4 2019

Preamble:

The course is prepared with the view of enabling the learners capable of understanding the
fundamental architecture of a digital computer. Study of Computer Organization and
Architecture is essential to understand the hardware behind the code and its execution at
physical level by interacting with existing memory and I/O structure. It helps the learners
to understand the fundamentals about computer system design so that they can extend the
features of computer organization to detect and solve problems occurring in computer
architecture.

Prerequisite : Topics covered under the course Logic System Design (CST 203)

Course Outcomes: After the completion of the course the student will be able to

CO# CO

Recognize and express the relevance of basic components, I/O organization and
CO1
pipelining schemes in a digital computer (Cognitive knowledge: Understand)

Explain the types of memory systems and mapping functions used in memory systems
CO2
(Cognitive Knowledge Level: Understand)
Demonstrate the control signals required for the execution of a given instruction
CO3
(Cognitive Knowledge Level: Apply) )

Illustrate the design of Arithmetic Logic Unit and explain the usage of registers in it
CO4
(Cognitive Knowledge Level: Apply)

Explain the implementation aspects of arithmetic algorithms in a digital computer

CO5
(Cognitive Knowledge Level:Apply)
Develop the control logic for a given arithmetic problem (Cognitive Knowledge
CO6
Level: Apply)
COMPUTER SCIENCE AND ENGINEERING

Mapping of course outcomes with program outcomes

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12

CO1

CO2

CO3

CO4

CO5

CO6

Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics
PO3 Design/Development of solutions PO9 Individual and team work

Conduct investigations of complex

PO4 PO10 Communication
problems
PO5 Modern tool usage PO11 Project Management and Finance
PO6 The Engineer and Society PO12 Life long learning

Assessment Pattern

Continuous Assessment Tests End Semester

Bloom’s Category
Test1 (%) Test2 (%) Examination Marks (%)

Remember 20 20 30

Understand 40 40 30
Apply 40 40 40

Analyze
COMPUTER SCIENCE AND ENGINEERING

Evaluate
Create

Mark Distribution

Total Marks CIE Marks ESE Marks ESE Duration

150 50 100 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 10 marks

Continuous Assessment Tests : 25 marks

Continuous Assessment Assignment : 15 marks

Internal Examination Pattern:

Each of the two internal examinations has to be conducted out of 50 marks

First Internal Examination shall be preferably conducted after completing the first half of the
syllabus and the Second Internal Examination shall be preferably conducted after completing
remaining part of the syllabus.

There will be two parts: Part A and Part B. Part A contains 5 questions (preferably, 2 questions
each from the completed modules and 1 question from the partly covered module), having 3
marks for each question adding up to 15 marks for part A. Students should answer all questions
from Part A. Part B contains 7 questions (preferably, 3 questions each from the completed
modules and 1 question from the partly covered module), each with 7 marks. Out of the 7
questions in Part B, a student should answer any 5.
COMPUTER SCIENCE AND ENGINEERING

End Semester Examination Pattern:

There will be two parts; Part A and Part B. Part A contains 10 questions with 2 questions from
each module, having 3 marks for each question. Students should answer all questions. Part B
contains 2 questions from each module of which a student should answer any one. Each question
can have maximum 2 sub-divisions and carries 14 marks.

Syllabus

Module 1

Basic Structure of computers – functional units - basic operational concepts - bus structures.
Memory locations and addresses - memory operations,Instructions and instruction sequencing ,
addressing modes.

Basic processing unit – fundamental concepts – instruction cycle – execution of a complete

instruction - single bus and multiple bus organization

Module 2

Register transfer logic: inter register transfer – arithmetic, logic and shift micro operations.
Processor logic design: - processor organization – Arithmetic logic unit - design of
arithmetic circuit - design of logic circuit - Design of arithmetic logic unit - status register –
design of shifter - processor unit – design of accumulator.
Module 3

Arithmetic algorithms: Algorithms for multiplication and division (restoring method) of binary
numbers. Array multiplier , Booth’s multiplication algorithm.
Pipelining: Basic principles, classification of pipeline processors, instruction and arithmetic
pipelines (Design examples not required), hazard detection and resolution.

Module 4
Control Logic Design: Control organization – Hard_wired control-microprogram control –
control of processor unit - Microprogram sequencer,micro programmed CPU organization -
horizontal and vertical micro instructions.

Module 5

I/O organization: accessing of I/O devices – interrupts, interrupt hardware -Direct memory
access.
COMPUTER SCIENCE AND ENGINEERING

Memory system: basic concepts – semiconductor RAMs. memory system considerations –

ROMs, Content addressable memory, cache memories - mapping functions.

Text Books

1. Hamacher C., Z. Vranesic and S. Zaky, Computer Organization ,5/e, McGraw Hill, 2011

2. Mano M. M., Digital Logic & Computer Design, PHI, 2004

3. KaiHwang, Faye Alye Briggs, Computer architecture and parallel processing McGraw-
Hill, 1984

Reference Books

1. Mano M. M., Digital Logic & Computer Design, 3/e, Pearson Education, 2013.

2. Patterson D.A. and J. L. Hennessy, Computer Organization and Design, 5/e, Morgan
Kaufmann Publishers, 2013.

3. William Stallings, Computer Organization and Architecture: Designing for Performance,

Pearson, 9/e, 2013.

4. Chaudhuri P., Computer Organization and Design, 2/e, Prentice Hall, 2008.

5. Rajaraman V. and T. Radhakrishnan, Computer Organization and Architecture, Prentice

Hall, 2011

Sample Course Level Assessment Questions

Course Outcome1(CO1): Which are the registers involved in a memory access

operation and how are they involved in it?

Course Outcome 2(CO2): Explain the steps taken by the system to handle a write miss
condition inside the cache memory.

Course Outcome 3(CO3): Generate the sequence of control signals required for the
execution of the instruction MOV [R1],R2 in a threebus organization.

Course Outcome 4(CO4): Design a 4-bit combinational logic shifter with 2 control
signals H0 and H1 that perform the following operations :
COMPUTER SCIENCE AND ENGINEERING

H1 H0 Operation

0 0 Transfer 1's to all output line

0 1 No shift operation

1 0 Shift left
1 1 Shift right

Course Outcome 5(CO5): Explain the restoring algorithm for binary division. Also
trace the algorithm to divide (1001)2 by (11)2

Course Outcome 6(CO6): Design a software control logic based on microprogramed

control to perform the addition of 2 signed numbers represented in sign magnitude form.
COMPUTER SCIENCE AND ENGINEERING

Model Question Paper

QP CODE: PAGES:2

Reg No:_______________

Name:_________________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

THIRD SEMESTER B.TECH DEGREE EXAMINATION, MONTH & YEAR

Course Code: CST 202

Course Name: Computer organization and architecture

Max.Marks:100 Duration: 3 Hours

PART A

Answer all Questions. Each question carries 3 Marks

1. Give the significance of instruction cycle.

2. Distinguish between big endian and little endian notations. Also give the significance of
these notations.

3. Compare I/O mapped I/O and memory mapped I/O.

4. Give the importance of interrupts in I/O interconnection.

5. Justify the significance of status register.

6. How does the arithmetic circuitry perform logical operations in an ALU.

7. Illustrate divide overflow with an example.

8. Write notes on arithmetic pipeline.

9. Briefly explain the role of micro program sequence.

10. Differentiate between horizontal and vertical micro instructions.

Part B

Answer any one Question from each module. Each question carries 14 Marks
COMPUTER SCIENCE AND ENGINEERING

11.

11.(a) What is the significance of addressing modes in computer architecture.

(4)

11.(b) Write the control sequence for the instruction DIV R1,[R2] in a three bus structure.
(10)

OR

12. Explain the concept of a single bus organization with help of a diagram. Write the control
sequence for the instruction ADD [R1],[R2].

(14)

13. Explain various register transfer logics.

(14)

OR

14.
14.(a) Design a 4 bit combinational logic shifter with 2 control signals H1 and H2 that
perform the following operations (bit values given in parenthesis are the values of
control variable H1 and H2 respectively.) : Transfer of 0’s to S (00), shift right (01),
shift left (10), no shift (11).
(5)
14.(b) Design an ALU unit which will perform arithmetic and logic operation with a given
binary adder.
(9)

15.
15.(a) Give the logic used behind Booth’s multiplication algorithm.

(4)

15.(b) Identify the appropriate algorithm available inside the system to perform the
multiplication between -14 and -9. Also trace the algorithm for the above input.
(10)
OR

16.

16.(a) List and explain the different pipeline hazards and their possible solutions

(10)
COMPUTER SCIENCE AND ENGINEERING

16.(b) Design a combinational circuit for 3x2 multiplication.

(4)
17. Design a hardwared control unit used to perform addition/subtraction of 2 numbers
represented in sign magnitude form.

(14)

OR

18. Give the structure of the micro program sequencer and its role in sequencing the micro
instructions.

(14)

19.

19.(a) Explain the different ways in which interrupt priority schemes can be implemented
(10)

19.(b) Give the structure of SRAM cell.

(4)

OR

20.

20.(a) Explain the various mapping functions available in cache memory.

(9)

20.(b) Briefly explain content addressable memory.

(5)
COMPUTER SCIENCE AND ENGINEERING

TEACHING PLAN
No of
No Contents Lecture
Hrs
Module 1 : (Basic Structure of computers) (9 hours)
Functional units,basic operational concepts,bus structures
1.1 1
(introduction)
1.2 Memory locations and addresses , memory operations 1

1.3 Instructions and instruction sequencing 1

1.4 Addressing modes 1

1.5 Fundamental concepts of instruction execution, instruction cycle 1

1.6 Execution of a complete instruction - single bus organization (Lecture 1) 1

1.7 Execution of a complete instruction - single bus organization (Lecture 2) 1

1.8 Execution of a complete instruction - multiple bus organization (Lecture 1) 1

1.9 Execution of a complete instruction - multiple bus organization (Lecture 2) 1

Module 2 :(Register transfer logic and Processor logic design) (10 hours)

2.1 Inter register transfer – arithmetic micro operations 1

2.2 Inter register transfer – logic and shift micro operations 1

2.3 Processor organization 1

2.4 Design of arithmetic circuit 1

2.5 Design of logic circuit 1

2.6 Design of arithmetic logic unit 1

2.7 Design of status register 1

2.8 Design of shifter - processor unit 1
COMPUTER SCIENCE AND ENGINEERING

2.9 Design of accumulator (Lecture 1) 1

2.10 Design of accumulator (Lecture 2) 1

Module 3 : (Arithmetic algorithms and Pipelining) (9 hours)

3.1 Algorithm for multiplication of binary numbers 1

3.2 Algorithm for division (restoring method) of binary numbers 1

3.3 Array multiplier 1

3.4 Booth’s multiplication algorithm 1
3.5 Pipelining: Basic principles 1
3.6 Classification of pipeline processors (Lecture 1) 1
3.7 Classification of pipeline processors (Lecture 2) 1
3.8 Instruction and arithmetic pipelines (Design examples not required) 1
3.9 Hazard detection and resolution 1
Module 4 :( Control Logic Design) (9 hours)

4.1 Control organization –design of hardwired control logic (Lecture 1) 1

4.2 Control organization –design of hardwired control logic (Lecture 2) 1
4.3 Control organization –design of hardwired control logic (Lecture 3) 1
4.4 Design of microprogram control logic–control of processor unit (Lecture1) 1
4.5 Design of microprogram control logic–control of processor unit (Lecture2) 1
4.6 Design of microprogram control logic–control of processor unit (Lecture3) 1
4.7 Microprogram sequencer 1
4.8 Micro programmed CPU organization 1
4.9 Microinstructions –horizontal and vertical micro instructions 1
Module 5 : (Basic processing units, I/O and memory) (8 hours)

5.1 Accessing of I/O devices –interrupts 1

5.2 Interrupt hardware 1
COMPUTER SCIENCE AND ENGINEERING

5.3 Direct memory access 1

5.4 Memory system: basic concepts –semiconductor RAMs 1
5.5 Memory system considerations – ROMs 1
5.6 Content addressable memory 1
5.7 Cache memories -mapping functions (Lecture 1) 1
5.8 Cache memories -mapping functions (Lecture 2) 1
COMPUTER SCIENCE AND ENGINEERING

YEAR OF
CST Database Management CATEGORY L T P CREDIT
INTRODUCTION
204 Systems
PCC 3 1 0 4 2019

Preamble: This course provides a clear understanding of fundamental principles of Database

Management Systems (DBMS) with special focus on relational databases to the learners. The
topics covered in this course are basic concepts of DBMS, Entity Relationship (ER) model,
Relational Database principles, Relational Algebra, Structured Query Language (SQL), Physical
Data Organization, Normalization and Transaction Processing Concepts. The course also gives a
glimpse of the alternative data management model, NoSQL. This course helps the learners to
manage data efficiently by identifying suitable structures to maintain data assets of
organizations and to develop applications that utilize database technologies.

Prerequisite: Topics covered under the course Data Structures (CST 201), Exposure to a High
Level Language like C/python.

Course Outcomes: After the completion of the course the student will be able to

Summarize and exemplify fundamental nature and characteristics of database systems

CO1
(Cognitive Knowledge Level: Understand)
Model real word scenarios given as informal descriptions, using Entity Relationship
CO2
diagrams. (Cognitive Knowledge Level: Apply)

Model and design solutions for efficiently representing and querying data using
CO3
relational model (Cognitive Knowledge Level: Analyze)

Demonstrate the features of indexing and hashing in database applications (Cognitive

CO4
Knowledge Level: Apply)
Discuss and compare the aspects of Concurrency Control and Recovery in Database
CO5
systems (Cognitive Knowledge Level: Apply)

Explain various types of NoSQL databases (Cognitive Knowledge Level:

CO6
Understand)
COMPUTER SCIENCE AND ENGINEERING

Mapping of course outcomes with program outcomes

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12

CO1

CO2

CO3

CO4

CO5

CO6

Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics
PO3 Design/Development of solutions PO9 Individual and team work
Conduct investigations of complex
PO4 PO10 Communication
problems
PO5 Modern tool usage PO11 Project Management and Finance
PO6 The Engineer and Society PO12 Life long learning

Assessment Pattern

Continuous Assessment Tests End Semester

Bloom’s Category Examination Marks
Test1 (%) Test2 (%)
(%)
Remember 30 30 30
Understand 40 40 40
Apply 30 30 30
COMPUTER SCIENCE AND ENGINEERING

Analyze
Evaluate

Create

Mark Distribution

Total Marks CIE Marks ESE Marks ESE Duration

150 50 100 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 10 marks

Continuous Assessment Tests : 25 marks

Continuous Assessment Assignment : 15 marks

Internal Examination Pattern:

Each of the two internal examinations has to be conducted out of 50 marks

First Internal Examination shall be preferably conducted after completing the first half of the
syllabus and the Second Internal Examination shall be preferably conducted after completing
remaining part of the syllabus.

There will be two parts: Part A and Part B. Part A contains 5 questions (preferably, 2 questions
each from the completed modules and 1 question from the partly covered module), having 3
marks for each question adding up to 15 marks for part A. Students should answer all questions
from Part A. Part B contains 7 questions (preferably, 3 questions each from the completed
modules and 1 question from the partly covered module), each with 7 marks. Out of the 7
questions in Part B, a student should answer any 5.
COMPUTER SCIENCE AND ENGINEERING

End Semester Examination Pattern:

There will be two parts; Part A and Part B. Part A contains 10 questions with 2 questions from
each module, having 3 marks for each question. Students should answer all questions. Part B
contains 2 questions from each module of which a student should answer any one. Each question
can have maximum 2 sub-divisions and carries 14 marks.

Syllabus

Module 1: Introduction & Entity Relationship (ER) Model

Concept & Overview of Database Management Systems (DBMS) - Characteristics of Database

system, Database Users, structured, semi-structured and unstructured data. Data Models and
Schema - Three Schema architecture. Database Languages, Database architectures and
classification.

ER model - Basic concepts, entity set & attributes, notations, Relationships and constraints,
cardinality, participation, notations, weak entities, relationships of degree 3.

Module 2: Relational Model

Structure of Relational Databases - Integrity Constraints, Synthesizing ER diagram to relational

schema

Introduction to Relational Algebra - select, project, cartesian product operations, join - Equi-join,
natural join. query examples, introduction to Structured Query Language (SQL), Data Definition
Language (DDL), Table definitions and operations – CREATE, DROP, ALTER, INSERT,
DELETE, UPDATE.

Module 3: SQL DML (Data Manipulation Language), Physical Data Organization

SQL DML (Data Manipulation Language) - SQL queries on single and multiple tables, Nested
queries (correlated and non-correlated), Aggregation and grouping, Views, assertions, Triggers,
SQL data types.

Physical Data Organization - Review of terms: physical and logical records, blocking factor,
pinned and unpinned organization. Heap files, Indexing, Singe level indices, numerical examples,
Multi-level-indices, numerical examples, B-Trees & B+-Trees (structure only, algorithms not
required), Extendible Hashing, Indexing on multiple keys – grid files.
COMPUTER SCIENCE AND ENGINEERING

Module 4: Normalization
Different anomalies in designing a database, The idea of normalization, Functional dependency,
Armstrong’s Axioms (proofs not required), Closures and their computation, Equivalence of
Functional Dependencies (FD), Minimal Cover (proofs not required). First Normal Form (1NF),
Second Normal Form (2NF), Third Normal Form (3NF), Boyce Codd Normal Form (BCNF),
Lossless join and dependency preserving decomposition, Algorithms for checking Lossless Join
(LJ) and Dependency Preserving (DP) properties.

Module 5: Transactions, Concurrency and Recovery, Recent Topics

Transaction Processing Concepts - overview of concurrency control, Transaction Model,

Significance of concurrency Control & Recovery, Transaction States, System Log, Desirable
Properties of transactions.
Serial schedules, Concurrent and Serializable Schedules, Conflict equivalence and conflict
serializability, Recoverable and cascade-less schedules, Locking, Two-phase locking and its
variations. Log-based recovery, Deferred database modification, check-pointing.

Introduction to NoSQL Databases, Main characteristics of Key-value DB (examples from:

Redis), Document DB (examples from: MongoDB)

Main characteristics of Column - Family DB (examples from: Cassandra) and Graph DB

(examples from : ArangoDB)

Text Books

1. Elmasri R. and S. Navathe, Database Systems: Models, Languages, Design and

Application Programming, Pearson Education, 2013.

2. Sliberschatz A., H. F. Korth and S. Sudarshan, Database System Concepts, 6/e, McGraw
Hill, 2011.

Reference Books:
1. Adam Fowler, NoSQL for Dummies, John Wiley & Sons, 2015
2. NoSQL Data Models: Trends and Challenges (Computer Engineering: Databases and Big
Data), Wiley, 2018
3. Web Resource: https://www.w3resource.com/redis/
4. web Resource: https://www.w3schools.in/category/mongodb/
5. Web Resource: https://www.tutorialspoint.com/cassandra/cassandra_introduction.htm
6. Web Resource : https://www.tutorialspoint.com/arangodb/index.htm
COMPUTER SCIENCE AND ENGINEERING

Sample Course Level Assessment Questions

Course Outcome1 (CO1):

1. List out any three salient features of database systems, which distinguish it from a file
system.
2. Give one example each for logical and physical data independence.

Course Outcome 2(CO2):

1. What facts about the relationships between entities EMPLOYEE and PROJECT are
conveyed by the following ER diagram?

1. Design an ER diagram for the following scenario:

There is a set of teams, each team has an ID (unique identifier), name, main stadium, and to
which city this team belongs. Each team has many players, and each player belongs to one
team. Each player has a number (unique identifier), name, DoB, start year, and shirt
number that he uses. Teams play matches, in each match there is a host team and a guest
team.

Course Outcome 3(CO3):

1. For the SQL query, SELECT A, B FROM R WHERE B=’apple’ AND C = ‘orange’ on the
table R(A, B, C, D), where A is a key, write any three equivalent relational algebra
expressions.
2. Given the FDs P→Q, P→R, QR→S, Q→T, QR→U, PR→U, write the sequence of
Armstrong’s Axioms needed to arrive at the following FDs: (a) P → T (b) PR → S (c)
QR → SU
3. Consider a relation PLAYER (PLAYER-NO, PLAYER-NAME, PLAYER-POSN,
TEAM, TEAM-COLOR, COACH-NO, COACH-NAME, TEAM-CAPTAIN). Assume
that PLAYER-NO is the only key of the relation and that the following dependencies
hold:
TEAM→{TEAM-COLOR, COACH-NO, TEAM-CAPTAIN}
COACH-NO→COACH-NAME.
i. Is the relation in 2NF? If not, decompose to 2NF.
ii. Is the relation in 3NF? If not, decompose to 3NF.
COMPUTER SCIENCE AND ENGINEERING

4. In the following tables foreign keys have the same name as primary keys except
DIRECTED-BY, which refers to the primary key ARTIST-ID. Consider only single-
director movies.
MOVIES(MOVIE-ID, MNAME, GENRE, LENGTH, DIRECTED-BY)
ARTIST(ARTIST-ID, ANAME)
ACTING(ARTIST-ID, MOVIE-ID)
Write SQL expressions for the following queries:
(a) Name(s) and director name(s) of movie(s) acted by ‘Jenny’.
(b) Names of actors who have never acted with ‘Rony’
(c) Count of movies genre-wise.
(d) Name(s) of movies with maximum length.

Course Outcome 4(CO4):

1. Consider an EMPLOYEE file with 10000 records where each record is of size 80 bytes.
The file is sorted on employee number (15 bytes long), which is the primary key.
Assuming un-spanned organization, block size of 512 bytes and block pointer size of 5
bytes. Compute the number of block accesses needed for retrieving an employee record
based on employee number if (i) No index is used (ii) Multi-level primary index is used.

Course Outcome 5(CO5):

1. Determine if the following schedule is recoverable. Is the schedule cascade-less? Justify
your answer. r1(X), r2(Z), r1(Z), r3(X), r3(Y), w1(X), c1, w3(Y), c3, r2(Y), w2(Z), w2(Y),
c2. (Note: ri(X)/wi(X) means transaction Ti issues read/write on item X; ci means
transaction Ti commits.)
2. Two-phase locking protocol ensures serializability. Justify.

Course Outcome 6(CO6):

1. List out any three salient features of NoSQL databases. Give example of a document in
MongoDB.
COMPUTER SCIENCE AND ENGINEERING

Model Question paper

QPCODE
Reg No:__________________
Name:___________________
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

FOURTH SEMESTER B.TECH DEGREE EXAMINATION, MONTH & YEAR

Course Code: CST 204
Course Name: Database Management Systems
Max.Marks:100 Duration: 3 Hours
PART A
Answer all Questions. Each question carries 3 Marks
1 List out any three salient features of a database systems.
2 When is multi-valued composite attribute used in ER modelling?
3 For the SQL query, SELECT A, B FROM R WHERE B=’apple’ AND C = ‘orange’
on the table R(A, B, C, D), where A is a key, write any two equivalent relational
algebra expressions.
4 Outline the concept of theta-join.
5 How is the purpose of where clause is different from that of having clause?
6 What is the use of a trigger?
7 When do you say that a relation is not in 1NF?
8 Given the FDs P→Q, P→R, QR→S, Q→T, QR→U, PR→U, write the sequence of
Armstrong’s Axioms needed to arrive at a. P → T b. PR → S
9 What is meant by the lost update problem?
10 What is meant by check pointing?

PART B
COMPUTER SCIENCE AND ENGINEERING

Answer any one Question from each module. Each question carries 14 Marks
11 a. Design an ER diagram for the following scenario: There is a set of teams, each (14)
team has an ID (unique identifier), name, main stadium, and to which city this
team belongs. Each team has many players, and each player belongs to one
team. Each player has a number (unique identifier), name, DoB, start year, and
shirt number that he uses. Teams play matches, in each match there is a host
team and a guest team. The match takes place in the stadium of the host team.
For each match we need to keep track of the following: The date on which the
game is played The final result of the match. The players participated in the
match. For each player, how many goals he scored, whether or not he took
yellow card, and whether or not he took red card. During the match, one player
may substitute another player. We want to capture this substitution and the time
at which it took place. Each match has exactly three referees. For each referee
we have an ID (unique identifier), name, DoB, years of experience. One referee
is the main referee and the other two are assistant referee.
OR
12 a. Interpret the the following ER diagram.
(8)

"

b. Distinguish between physical data independence and logical data independence (6)
with suitable examples.
COMPUTER SCIENCE AND ENGINEERING

13 EMPLOYEE(ENO, NAME, ADDRESS, DOB, AGE, GENDER, SALARY, (14)

DNUM, SUPERENO)
DEPARTMENT(DNO, DNAME, DLOCATION, DPHONE, MGRENO)
PROJECT(PNO, PNAME, PLOCATION, PCOST, CDNO)

DNUM is a foreign key that identifies the department to which an employee

belongs. MGRENO is a foreign key identifying the employee who manages the
department. CDNO is a foreign key identifying the department that controls the
project. SUPERENO is a foreign key identifying the supervisor of each employee.

Write relational algebra expressions for the following queries:-

(a) Names of female employees whose salary is more than 20000.

(b) Salaries of employee from ‘Accounts’ department
(c) Names of employees along with his/her superviser’s name
(d) For each employee return name of the employee along with his department
name and the names of projects in which he/she works
(e) Names of employees working in all the departments

OR
14 a.Write SQL DDL statements for the the following (Assume suitable domain (10)
types):
i. Create the tables STUDENT(ROLLNO, NAME, CLASS, SEM,
ADVISER), FACULTY(FID, NAME, SALARY, DEPT). Assume that
ADVISER is a foreign key referring FACUTY table.
ii. Delete department with name ‘CS’ and all employees of the
department.
iii. Increment salary of every faculty by 10%.
b.Illustrate foreign key constraint with a typical example. (4)
COMPUTER SCIENCE AND ENGINEERING

15 For the relation schema below, give an expression in SQL for each of the queries (14)
that follows:

employee(employee-name, street, city)

works(employee-name, company-name, salary)
company(company-name, city)
manages(employee-name, manager-name)

a) Find the names, street address, and cities of residence for all employees
who work for the Company ‘RIL Inc.' and earn more than $10,000.
b) Find the names of all employees who live in the same cities as the
companies for which they work.
c) Find the names of all employees who do not work for ‘KYS Inc.’. Assume
that all people work for exactly one company.
d) Find the names of all employees who earn more than every employee of
‘SB Corporation'. Assume that all people work for at most one company.
e) List out number of employees company-wise in the decreasing order of
number of employees.

OR
16 a. Consider an EMPLOYEE file with 10000 records where each record is of (9)
size 80 bytes. The file is sorted on employee number (15 bytes long), which
is the primary key. Assuming un-spanned organization and block size of
512 bytes compute the number of block accesses needed for selecting
records based on employee number if,
i. No index is used
ii. Single level primary index is used
iii. Multi-level primary index is used
Assume a block pointer size of 6 bytes.
b. Illustrate correlated and non-correlated nested queries with real examples. (5)

17 a. Illstrate3NF and BCNF with suitable real examples. (6)

b. Given a relation R(A1,A2,A3,A4,A5) with functional dependencies (8)

A1→A2A4 and A4→A5, check if the decomposition R1(A1,A2,A3),
R2(A1,A4), R3(A2,A4,A5) is lossless.
OR
18 a. Consider the un-normalized relation R(A, B, C, D, E, F, G) with the FDs (7)
A→B , AC→G, AD→EF, EF→G, CDE→AB. Trace the normalization
process to reach 3NF relations.
COMPUTER SCIENCE AND ENGINEERING

b. Illustrate Lossless Join Decomposition and Dependency Preserving (7)

Decomposition with typical examples.
19 a. Discuss the four ACID properties and their importance. (7)

b. Determine if the following schedule is conflict serializable. Is the schedule (7)

recoverable? Is the schedule cascade-less? Justify your answers.
r1(X), r2(Z), r1(Z), r3(X), r3(Y ), w1(X), c1, w3(Y), c3, r2(Y), w2(Z),
w2(Y), c2

(Note: ri(X)/wi(X) means transaction Ti issues read/write on item X; ci

means transaction Ti commits.)
OR
20 a. Discuss the main characteristics of Key-value DB and Graph DB. (7)

b. Illustrate two-phase locking with a schedule containing three transactions. (7)

Argue that 2PL ensures serializability. Also argue that 2Pl can lead to
deadlock.
COMPUTER SCIENCE AND ENGINEERING

Teaching Plan

Hours
Course Name
(48)
Module 1: Introduction & ER Model 8
Concept & Overview of DBMS, Characteristics of DB system,
1.1 1
Database Users.
Structured, semi-structured and unstructured data. Data Models and
1.2 1
Schema

1.3 Three-Schema-architecture. Database Languages 1

1.4 Database architectures and classification 1

1.5 ER model: basic concepts, entity set & attributes, notations 1

1.6 Relationships and constraints – cardinality, participation, notations 1
1.7 Weak entities, relationships of degree 3 1
1.8 ER diagram – exercises 1
Module 2: Relational Model 7
2.1 Structure of relational Databases, Integrity Constraints 1
Synthesizing ER diagram to relational schema, Introduction to
2.2 1
relational algebra.
2.3 Relational algebra: select, project, Cartesian product operations 1
2.4 Relational Algebra: join - Equi-join, Natural join 1
2.5 Query examples 1
2.6 Introduction to SQL, important data types 1
DDL, Table definitions and operations – CREATE, DROP, ALTER,
2.7 1
INSERT, DELETE, UPDATE
Module 3: SQL DML, Physical Data Organization 11
3.1 SQL DML, SQL queries on single and multiple tables 1
3.2 Nested queries (correlated and non-correlated) 1
3.3 Aggregation and grouping 1
COMPUTER SCIENCE AND ENGINEERING

Hours
Course Name
(48)
3.4 Views, assertions (with examples) 1
3.5 Triggers (with examples), SQL data types 1
Review of terms: physical and logical records, blocking factor,
3.6 1
pinned and unpinned organization. Heap files, Indexing
3.7 Singe level indices, numerical examples 1

3.8 Multi-level-indices, numerical examples 1

3.9 B-Trees and B+Trees (structure only, algorithms not required) 1

3.10 Extendible Hashing 1

3.11 Indexing on multiple keys – grid files 1
Module 4: Normalization 8
Different anomalies in designing a database, The idea of
4.1 1
normalization
4.2 Functional dependency, Armstrong’s Axioms (proofs not required) 1
Closures and their computation, Equivalence of FDs, minimal
4.3 1
Cover (proofs not required).
4.4 1NF, 2NF 1
4.5 3NF, BCNF 1
4.6 Lossless join and dependency preserving decomposition 1
Algorithms for checking Lossless Join and Dependency preserving
4.7 1
properties (Lecture 1)
Algorithms for checking Lossless Join and Dependency preserving
4.8 1
properties (Lecture 2)
Module 5: Transactions, Concurrency and Recovery, Recent
14
Topics
5.1 Transaction Processing Concepts: Transaction Model 1
Overview of concurrency control, Significance of concurrency
5.2 1
Control & Recovery
5.3 Transaction States, System Log 1
COMPUTER SCIENCE AND ENGINEERING

Hours
Course Name
(48)
5.4 Desirable Properties of transactions, Serial schedules 1
5.5 Concurrent and Serializable Schedules 1
5.6 Conflict equivalence and conflict serializability 1
5.7 Recoverable and cascade-less schedules 1

5.8 Locking, Two-phase locking, strict 2PL. 1

5.9 Log-based recovery 1

5.10 Deferred database modification (serial schedule), example 1
Deferred database modification (concurrent schedule) example,
5.11 1
check-pointing
5.12 Introduction to NoSQL Databases 1
Main characteristics of Key-value DB (examples from: Redis),
5.13 Document DB (examples from: MongoDB) [detailed study not 1
expected]

Main characteristics of Column-Family DB (examples from:

5.14 Cassandra) and Graph DB (examples from : ArangoDB) [detailed 1
study not expected]
COMPUTER SCIENCE AND ENGINEERING
Year of
CST OPERATING Category L T P Credit
Introduction
206 SYSTEMS
PCC 3 1 0 4 2019

Preamble: Study of operating system is an essential to understand the overall working of

computer system, tradeoffs between performance and functionality and the division of jobs
between hardware and software. This course introduces the concepts of memory management,
device management, process management, file management and security & protection
mechanisms available in an operating system. The course helps the learner to understand the
fundamentals about any operating system design so that they can extend the features of operating
system to detect and solve many problems occurring in operating system and to manage the
computer resources appropriately.

Prerequisite: Topics covered in the courses are Data Structures (CST 201) and Programming
in C (EST 102)

Course Outcomes: After the completion of the course the student will be able to

Explain the relevance, structure and functions of Operating Systems in computing

CO1
devices. (Cognitive knowledge: Understand)

Illustrate the concepts of process management and process scheduling mechanisms

CO2
employed in Operating Systems. (Cognitive knowledge: Understand)
Explain process synchronization in Operating Systems and illustrate process
CO3 synchronization mechanisms using Mutex Locks, Semaphores and Monitors
(Cognitive knowledge: Understand)
Explain any one method for detection, prevention, avoidance and recovery for
CO4
managing deadlocks in Operating Systems. (Cognitive knowledge: Understand)

Explain the memory management algorithms in Operating Systems. (Cognitive

CO5
knowledge: Understand)
Explain the security aspects and algorithms for file and storage management in
CO6
Operating Systems. (Cognitive knowledge: Understand)
COMPUTER SCIENCE AND ENGINEERING
Mapping of course outcomes with program outcomes

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12

CO1

CO2

CO3

CO4

CO5

CO6

Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics

PO3 Design/Development of solutions PO9 Individual and team work

Conduct investigations of complex

PO4 PO10 Communication
problems

PO5 Modern tool usage PO11 Project Management and Finance

PO6 The Engineer and Society PO12 Life long learning

Assessment Pattern

Test 1 (Marks Test 2 (Marks End Semester Examination

Bloom’s Category
in percentage) in percentage) (Marks in percentage)
Remember 30 30 30

Understand 30 30 30
Apply 40 40 40

Analyse
Evaluate

Create
COMPUTER SCIENCE AND ENGINEERING
Mark Distribution

Total Marks CIE Marks ESE Marks ESE Duration

150 50 100 3

Continuous Internal Evaluation Pattern:

Attendance : 10 marks
Continuous Assessment Test : 25 marks
Continuous Assessment Assignment : 15 marks

Internal Examination Pattern:

Each of the two internal examinations has to be conducted out of 50 marks. First series test shall
be preferably conducted after completing the first half of the syllabus and the second series test
shall be preferably conducted after completing remaining part of the syllabus. There will be two
parts: Part A and Part B. Part A contains 5 questions (preferably, 2 questions each from the
completed modules and 1 question from the partly completed module), having 3 marks for each
question adding up to 15 marks for part A. Students should answer all questions from Part A.
Part B contains 7 questions (preferably, 3 questions each from the completed modules and 1
question from the partly completed module), each with 7 marks. Out of the 7 questions, a student
should answer any 5.

End Semester Examination Pattern:

There will be two parts; Part A and Part B. Part A contains 10 questions with 2 questions from
each module, having 3 marks for each question. Students should answer all questions. Part B
contains 2 questions from each module of which a student should answer any one. Each question
can have maximum 2 sub-divisions and carries 14 marks.

Syllabus

Module I

Introduction: Operating system overview – Operations, Functions, Service – System calls,

Types – Operating System structure - Simple structure, Layered approach, Microkernel, Modules
– System boot process.

Module II

Processes - Process states, Process control block, threads, scheduling, Operations on processes -
process creation and termination – Inter-process communication - shared memory systems,
Message passing systems.
Process Scheduling – Basic concepts- Scheduling COMPUTER SCIENCE
criteria -scheduling AND ENGINEERING
algorithms- First come
First Served, Shortest Job Firs, Priority scheduling, Round robin scheduling

Module III

Process synchronization- Race conditions – Critical section problem – Peterson’s solution,

Synchronization hardware, Mutex Locks, Semaphores, Monitors – Synchronization problems -
Producer Consumer, Dining Philosophers and Readers-Writers.

Deadlocks: Necessary conditions, Resource allocation graphs, Deadlock prevention, Deadlock

avoidance – Banker’s algorithms, Deadlock detection, Recovery from deadlock.

Module IV

Memory Management: Concept of address spaces, Swapping, Contiguous memory allocation,

fixed and variable partitions, Segmentation, Paging. Virtual memory, Demand paging, Page
replacement algorithms.

Module V

File System: File concept - Attributes, Operations, types, structure – Access methods, Protection.
File-system implementation, Directory implementation. Allocation methods.
Storage Management: Magnetic disks, Solid-state disks, Disk Structure, Disk scheduling,
Disk formatting.

Text Book

Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, ' Operating System Concepts' 9th
Edition, Wiley India 2015.

Reference Books:

1. Andrew S Tanenbaum, “Modern Operating Systems” , 4th Edition, Prentice Hall, 2015.
2. William Stallings, “Operating systems”, 6th Edition, Pearson, Global Edition, 2015.
3. Garry Nutt, Nabendu Chaki, Sarmistha Neogy, “Operating Systems”, 3rd Edition, Pearson
Education.
4. D.M.Dhamdhere, “Operating Systems”, 2nd Edition, Tata McGraw Hill, 2011.
5. Sibsankar Haldar, Alex A Aravind, “Operating Systems”, Pearson Education.
Sample Course Level Assessment Questions COMPUTER SCIENCE AND ENGINEERING

Course Outcome1 (CO1): What is the main advantage of the micro kernel approach to system
design? How do user program and system program interact in a microkernel architecture?

Course Outcome 2 (CO2): Define process. With the help of a neat diagram explain different
states of process.
Course Outcome 3 (CO3): What do you mean by binary semaphore and counting semaphore?
With C, explain implementation of wait () and signal().

Course Outcome 4 (CO4): Describe resource allocation graph for the following. a) with a
deadlock b) with a cycle but no deadlock.

Course Outcome 5 (CO5): Consider the following page reference string 1, 2, 3, 4, 2, 1, 5, 6, 2,

1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. Find out the number of page faults if there are 4 page frames, using
the following page replacement algorithms. i) LRU ii) FIFO iii) Optimal

Course Outcome 6 (CO6): Explain the different file allocation methods with advantages and
disadvantages.

Model Question Paper

QP CODE: PAGES: ___

Reg No:_______________
Name:_________________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

FOURTH SEMESTER B.TECH DEGREE EXAMINATION, MONTH & YEAR

Course Code: CST 206

Course name : OPERATING SYSTEMS

Max Marks: 100 Duration: 3 Hours

PART-A

(Answer All Questions. Each question carries 3 marks)

1. How does hardware find the Operating System kernel after system switch-on?

2. What is the purpose of system call in operating system?

3. Why is context switching considered as an overhead to the system?

COMPUTER
4. How is inter process communication implement SCIENCE
using shared memory? AND ENGINEERING

5. Describe resource allocation graph for the following.

a) with a deadlock b)with a cycle but no deadlock.

6. What is critical section? What requirement should be satisfied by a solution to the critical
section problem?

7. Consider the reference string 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. How

many page faults occur while using FCFS for the following cases.

a) frame=2 b)frame=3

8. Differentiate between internal and external fragmentations.

9. Compare sequential access and direct access methods of storage devices.

10. Define the terms (i) Disk bandwidth (ii) Seek time.

PART-B(Answer any one question from each module)

11. a) Explain the following structures of operating system (i) Monolithic systems
(ii) Layered Systems (iii) Micro Kernel (iv) Modular approach. (12)

b) Under what circumstances would a user be better of using a time sharing system than a
PC or a single user workstation? (2)

OR

12. a) What is the main advantage of the micro kernel approach to system design? How do user
program and system program interact in a microkernel architecture? (8)

b) Describe the differences between symmetric and asymmetric multiprocessing? What are
the advantages and disadvantages of multiprocessor systems? (6)

13. a) Define process. With the help of a neat diagram explain different states of process. (8)
b) Explain how a new process can be created in Unix using fork system call. (6)
OR

14 a) Find the average waiting time and average turnaround time for the processes given in the
table below using:- i) SRT scheduling algorithm ii) Priority scheduling algorithm (9)
Process Arrival Time (ms)COMPUTER SCIENCE
CPU Burst Time (ms) AND ENGINEERING
Priority
P1 0 5 3
P2 2 4 1
P3 3 1 2
P4 5 2 4
b) What is a Process Control Block? Explain the fields used in a Process Control Block. (5)

15. Consider a system with five processes P0 through P4 and three resources of type A, B, C.
Resource type A has 10 instances, B has 5 instances and C has 7 instances. Suppose at time
t0 following snapshot of the system has been taken:

i) What will be the content of the Need matrix? Is the system in a safe state? If Yes, then what is
the safe sequence? (8)
iii)What will happen if process P1 requests one additional instance of resource type A and two
instances of resource type C? (6)

OR

16. a) State dining philosopher’s problem and give a solution using semaphores. (7)

b) What do you mean by binary semaphore and counting semaphore? With C struct, explain
implementation of wait () and signal() (7)
COMPUTER
17. a) Consider the following page reference string SCIENCE
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2,AND
3, 7, 6,ENGINEERING
3, 2, 1, 2,
3, 6. Find out the number of page faults if there are 4 page frames, using the following
page replacement algorithms i) LRU ii) FIFO iii) Optimal (9)

b) Explain the steps involved in handling a page fault. (5)

OR

18. a) With a diagram, explain how paging is done with TLB. (5)

b) Memory partitions of sizes 100 kb, 500 kb, 200 kb, 300 kb, 600 kb are available, how
would best ,worst and first fit algorithms place processes of size 212 kb, 417 kb, 112 kb,
426 kb in order. Rank the algorithms in terms of how efficiently they uses memory. (9)

19. a) Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. the drive currently
services a request at cylinder 143, and the previous request was at cylinder 125. the queue
of pending request in FIFO order is 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130.
Starting from the current position, what is the total distance (in cylinders) that the disk arm
moves to satisfy all pending requests for each of the following algorithms

i) FCFS ii) SSFT iii) SCAN iv) LOOK v) C-SCAN (10)

b) What is the use of access matrix in protection mechanism? (4)

OR

20. a) Explain the different file allocation operations with advantages and disadvantages. (8)
b) Explain the following i) file types ii) file operation iii) file attributes (6)

Teaching Plan

Module 1 - Introduction 5 Hours

1.1 Introduction to Operating System 1

1.2 Operating System operations, functions, service 1

1.3 System calls, Types 1

1.4 Operating System Structure: Simple, Layered, Microkernel, Modules 1

1.5 System Boot Process 1

Module 2 – Processes and Process Scheduling 9 Hours

2.1 Processes, Process states 1

2.2 Process Control Block, Threads 1

COMPUTER SCIENCE AND ENGINEERING
2.3 Scheduling 1

2.4 Operations on processes: process creation and termination 1

2.5 Inter-process communication: Shared memory systems, Message Passing 1

2.6 Process Scheduling – Basic concepts, Scheduling Criteria 1

2.7 Scheduling algorithms - Basics 1

2.8 First come First Served, Shortest Job First 1

2.9 Priority scheduling, Round Robin Scheduling 1

Module 3 - Process synchronization and Dead locks 13 Hours

3.1 Process synchronization, Race conditions 1

3.2 Critical Section problem, Peterson’s solution 1

3.3 Synchronization hardware, Mutex Locks 1

3.4 Semaphores 1
3.5 Monitors 1

3.6 Synchronization problem examples (Lecture 1) 1

3.7 Synchronization problem examples (Lecture 2) 1

3.8 Deadlocks: Necessary conditions, Resource Allocation Graphs 1

3.9 Deadlock prevention 1

3.10 Deadlock avoidance 1

3.11 Banker’s algorithm 1

3.12 Deadlock detection 1

3.13 Deadlock recovery 1

Module 4 - Memory Management 9 Hours

4.1 Memory Management: Concept of Address spaces 1

4.2 Swapping 1
4.3 Contiguous memory allocation, fixed and variable partitions 1

4.4 Segmentation. 1
4.5 Paging (Lecture 1) 1

4.6 Paging (Lecture 2) 1

4.7 Virtual memory, Demand Paging 1
COMPUTER SCIENCE AND ENGINEERING
4.8 Page replacement algorithms (Lecture 1) 1

4.9 Page replacement algorithms (Lecture 2) 1

Module 5 - File and Disk management 9 Hours

5.1 File concept, Attributes, Operations, types, structure 1

5.2 Access methods 1

5.3 Protection 1
5.4 File-System implementation 1

5.5 Directory implementation 1

5.6 Allocation methods 1

5.7 Magnetic disks, Solid-state disks, Disk structure 1

5.8 Disk scheduling 1

5.9 Disk formatting 1

HUMANITIES
CODE COURSE NAME CATEGORY L T P CREDIT
2 0 0 2
EST 200 DESIGN AND ENGINEERING

Preamble:
The purpose of this course is to
i) introduce the undergraduate engineering studentsthe fundamental principles of
design engineering,
ii) make them understand the steps involved in the design process and
iii) familiarize them with the basic tools used and approaches in design.
Students are expected to apply design thinking in learning as well as while practicing
engineering, which is very important and relevant for today. Case studies from various
practical situations will help the students realize that design is not only concerned about the
function but also many other factors like customer requirements, economics, reliability, etc.
along with a variety of life cycle issues.

The course will help students to consider aesthetics, ergonomics and sustainability factors in
designs and also to practice professional ethics while designing.

Prerequisite:

Nil.The course will be generic to all engineering disciplines and will not require specialized
preparation or prerequisites in any of the individual engineering disciplines.

Course Outcomes:

After the completion of the course the student will be able to

CO 1 Explain the different concepts and principles involved in design engineering.

CO 2 Apply design thinking while learning and practicing engineering.
CO 3 Develop innovative, reliable, sustainable and economically viable designs
incorporating knowledge in engineering.

Mapping of course outcomes with program outcomes

PO 1 PO 2 PO 3 PO 4 PO 5 PO 6 PO 7 PO 8 PO 9 PO PO PO
10 11 12
CO 1 2 1 1 1
CO 2 2 1 1 2
CO 3 2 1 1 2 2 1
HUMANITIES
Assessment Pattern

Continuous Internal Evaluation (CIE) Pattern:

Attendance : 10 marks
Continuous Assessment Test (2 numbers) : 25 marks
Assignment/Quiz/Course project : 15 marks

End Semester Examination (ESE) Pattern: There will be two parts; Part A and Part B.
Part A : 30 marks
part B : 70 marks
Part A contains 10 questions with 2 questions from each module, having 3 marks for each question.
Students should answer all questions.
Part B contains 2 case study questions from each module of which student should answer any one.
Each question carry 14 marks and can have maximum 2 sub questions.

Mark distribution

Total Marks CIE ESE ESE Duration

150 50 100 3 hours

Bloom’s Category Continuous Assessment Tests End Semester

1 2 Examination
Remember 5 5 10
Understand 10 10 20
Apply 35 35 70
Analyse - - -
Evaluate - - -
Create - - -
HUMANITIES
Course Level Assessment Questions

Course Outcome 1 (CO1): Appreciate the different concepts and principles involved in design
engineering.

1. State how engineering design is different from other kinds of design

2. List the different stages in a design process.

3. Describedesign thinking.

4. State the function of prototyping and proofing in engineering design.

5. Write notes on the following concepts in connection with design engineering 1) Modular Design,
2) Life Cycle Design , 3) Value Engineering, 4) Concurrent Engineering, and 5) Reverse Engineering

6. State design rights.

Course Outcome 2 (CO2) Apply design thinking while learning and practicing engineering.

1. Construct the iterative process for design thinking in developing simple products like a pen,
umbrella, bag, etc.

2. Show with an example how divergent-convergent thinking helps in generating alternative designs
and then how to narrow down to the best design.

3. Describe how a problem-based learning helps in creating better design engineering solutions.

4. Discuss as an engineer, how ethics play a decisive role in your designs

Course Outcome 3(CO3): Develop innovative, reliable, sustainable and economically viable designs
incorporating different segments of knowledge in engineering.

1. Illustratethe development of any simple product by passing through the different stages of design
process

2. Show thegraphical design communication with the help of detailed 2D or 3D drawings for any
simple product.

3. Describe how to develop new designs for simple products through bio-mimicry.
HUMANITIES
Model Question paper

Page 1 of 2
Reg No.:_______________ Name:__________________________
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
THIRD/FOURTH SEMESTER B.TECH DEGREE EXAMINATION
Course Code: EST 200
Course Name: DESIGN AND ENGINEERING
Max. Marks: 100Duration: 3 Hours
PART A
Answer all questions, each question carries 3 marks
Use only hand sketches

(1)Write aboutthe basic design process.

(2) Describe how to finalize the design objectives.
(3) State the role of divergent-convergent questioning in design thinking.
(4) Discuss how to perform design thinking in a team managing the conflicts.
(5) Show how engineering sketches and drawings convey designs.
(6)Explain the role of mathematics and physics in design engineering process.
(7) Distinguish between project-based learning and problem-based learning in design
engineering.
(8) Describe how concepts like value engineering , concurrent engineering and reverse
engineering influence engineering designs?
(9) Show how designs are varied based on the aspects of production methods, life span,
reliability and environment?
(10) Explain how economics influence the engineering designs?
(10x3 marks =30 marks)

Part B
Answer any ONE question from each module. Each question carry 14 marks

Module 1
(11) Show the designing of a wrist watch going through the various stages of the design
process. Use hand sketches to illustrate the processes.
or
(12)Find the customer requirements for designing a new car showroom. Show how the
design objectives were finalized considering the design constraints?
HUMANITIES
Module 2
(13)Illustrate the design thinking approach for designing a bag for college students within a
limited budget. Describe each stage of the process and the iterative procedure
involved. Use hand sketches to support your arguments.
or
(14)Construct a number of possible designs and then refine them to narrow down to the
best design for a drug trolley used in hospitals. Show how the divergent-convergent
thinking helps in the process. Provide your rationale for each step by using hand
sketches only.

Module 3
(15) Graphically communicate the design of a thermo flask used to keep hot coffee. Draw
the detailed 2D drawings of the same with design detailing, material selection, scale
drawings, dimensions, tolerances, etc. Use only hand sketches.
or
(16)Describe the role of mathematical modelling in design engineering. Show how
mathematics and physics play a role in designing a lifting mechanism to raise 100 kg of
weight to a floor at a height of 10 meters in a construction site.

Module 4
(17) Show the development of a nature inspired design for a solar poweredbus waiting shed
beside a highway. Relate between natural and man-made designs. Use hand sketches
to support your arguments.
or
(18)Show the design of a simple sofa and then depict how the design changes when
considering 1) aesthetics and 2) ergonomics into consideration. Give hand sketches and
explanations to justify the changes in designs.

Module 5
(19)Examine the changes in the design of a foot wear with constraints of 1) production
methods, 2) life span requirement, 3) reliability issues and 4) environmental factors.
Use hand sketches and give proper rationalization for the changes in design.
or
(20)Describe the how to estimate the cost of a particular design using ANY of the following:
i) a website, ii) the layout of a plant, iii) the elevation of a building, iv) anelectrical or
electronic system or device and v) a car.
Show how economics will influence the engineering designs. Use hand sketches to support
your arguments.

(5x14 marks =70 marks)

Page 2 of 2
HUMANITIES
Syllabus

Module 1
Design Process:- Introduction to Design and Engineering Design, Defining a Design
Process-:Detailing Customer Requirements, Setting Design Objectives, Identifying
Constraints, Establishing Functions, Generating Design Alternatives and Choosing a
Design.

Module 2
Design Thinking Approach:-Introduction to Design Thinking, Iterative Design
Thinking Process Stages: Empathize, Define, Ideate, Prototype and Test. Design
Thinking as Divergent-Convergent Questioning. Design Thinking in a Team
Environment.

Module 3
Design Communication (Languages of Engineering Design):-Communicating
Designs Graphically, Communicating Designs Orally and in Writing. Mathematical
Modeling In Design, Prototyping and Proofing the Design.

Module 4
Design Engineering Concepts:-Project-based Learning and Problem-based Learning
in Design.Modular Design and Life Cycle Design Approaches. Application of Bio-
mimicry,Aesthetics and Ergonomics in Design. Value Engineering, Concurrent
Engineering, and Reverse Engineering in Design.

Module 5
Expediency, Economics and Environment in Design Engineering:-Design for
Production, Use, and Sustainability. Engineering Economics in Design. Design
Rights. Ethics in Design

Text Books
1) YousefHaik, SangarappillaiSivaloganathan, Tamer M. Shahin, Engineering Design Process,
Cengage Learning 2003, Third Edition, ISBN-10: 9781305253285,

2) Voland, G., Engineering by Design, Pearson India 2014, Second Edition, ISBN 9332535051

Reference Books
1.Philip Kosky, Robert Balmer, William Keat, George Wise, Exploring Engineering, Fourth
Edition: An Introduction to Engineering and Design, Academic Press 2015, 4th Edition,
ISBN: 9780128012420.
2. Clive L. Dym, Engineering Design: A Project-Based Introduction, John Wiley & Sons,
New York 2009, Fourth Edition, ISBN: 978-1-118-32458-5
3. Nigel Cross, Design Thinking: Understanding How Designers Think and Work, Berg
Publishers 2011, First Edition, ISBN: 978-1847886361
4. Pahl, G., Beitz, W., Feldhusen, J., Grote, K.-H., Engineering Design: A Systematic
Approach, Springer 2007, Third Edition, ISBN 978-1-84628-319-2
HUMANITIES
Course Contents and Lecture Schedule
No Topic No. of Lectures
1 Module 1: Design Process
1.1 Introduction to Design and Engineering Design.
What does it mean to design something? How Is
engineering design different from other kinds of design? 1
Where and when do engineers design? What are the basic
vocabularyin engineering design? How to learn and do
engineering design.
1.2 Defining a Design Process-: Detailing Customer
Requirements.
How to do engineering design? Illustrate the process with 1
an example. How to identify the customer requirements of
design?
1.3 Defining a Design Process-: Setting Design Objectives,
Identifying Constraints, Establishing Functions.
How to finalize the design objectives? How to identify the 1
design constraints? How to express the functions a design
in engineering terms?
1.4 Defining a Design Process-: Generating Design
Alternatives and Choosing a Design.
1
How to generate or create feasible design alternatives?
How to identify the "best possible design”?
1.5 Case Studies:- Stages of Design Process.
Conduct exercises for designing simple products going 1
through the different stages of design process.
2 Module 2: Design Thinking Approach
2.1 Introduction to Design Thinking
How does the design thinking approach help engineers in 1
creating innovative and efficient designs?
2.2 Iterative Design Thinking Process Stages: Empathize,
Define, Ideate, Prototype and Test.
How can the engineers arrive at better designs utilizing 1
the iterative design thinking process (in which knowledge
acquired in the later stages can be applied back to the
earlier stages)?
2.3 Design Thinking as Divergent-Convergent Questioning.
Describe how to create a number of possible designs and 1
then how to refine and narrow down to the 'best design'.
2.4 Design Thinking in a Team Environment.
How to perform design thinking as a team managing the 1
conflicts ?
2.5 Case Studies: Design Thinking Approach.
1
Conduct exercises using the design thinking approach for
HUMANITIES
designing any simple products within a limited time and
budget
3 Module 3: Design Communication (Languages of Engineering Design)
3.1 Communicating Designs Graphically.
1
How do engineering sketches and drawings convey designs?
3.2 Communicating Designs Orally and in Writing.
How can a design be communicated through oral 1
presentation or technical reports efficiently?
First Series Examination
3.3 Mathematical Modelling in Design.
How do mathematics and physics become a part of the 1
design process?
3.4 Prototyping and Proofing the Design.
1
How to predict whether the design will function well or not?
3.5 Case Studies: Communicating Designs Graphically.
Conduct exercises for design communication through
detailed 2D or 3D drawings of simple products with 1
design detailing, material selection, scale drawings,
dimensions, tolerances, etc.
4 Module 4: Design Engineering Concepts
4.1 Project-based Learning and Problem-based Learning in 1
Design.
How engineering students can learn design engineering
through projects?
How students can take up problems to learn design
engineering?
4.2 Modular Design and Life Cycle Design Approaches. 1
What is modular approach in design engineering? How it
helps?
How the life cycle design approach influences design
decisions?
4.3 Application of Bio-mimicry, Aesthetics and Ergonomics 1
in Design.
How do aesthetics and ergonomics change engineering
designs?
How do the intelligence in nature inspire engineering
designs? What are the common examples of bio-mimicry
in engineering?
4.4 Value Engineering, Concurrent Engineering, and Reverse 1
Engineering in Design.
How do concepts like value engineering , concurrent
engineering and reverse engineering influence
engineering designs?
4.5 Case Studies: Bio-mimicry based Designs. 1
Conduct exercises to develop new designs for simple
HUMANITIES
products using bio-mimicry and train students to bring out
new nature inspired designs.
5 Module 5: Expediency, Economics and Environment in Design
Engineering
5.1 Design for Production, Use, and Sustainability. 1
How designs are finalized based on the aspects of
production methods, life span, reliability and
environment?
5.2 Engineering Economics in Design. 1
How to estimate the cost of a particular design and how
will economics influence the engineering designs?
5.3 Design Rights. 1
What are design rights and how can an engineer put it
into practice?
5.4 Ethics in Design. 1
How do ethics play a decisive role in engineering design?
5.5 Case Studies: Design for Production, Use, and 1
Sustainability.
Conduct exercises using simple products to show how designs
change with constraints of production methods, life span
requirement, reliability issues and environmental factors.
Second Series Examination
HUMANITIES

Code. Course Name L T P Hrs Credit

HUT 200 Professional Ethics 2 0 0 2 2

Preamble:To enable students to create awareness on ethics and human values.

Prerequisite: Nil

Course Outcomes: After the completion of the course the student will be able to

CO 1 Understand the core values that shape the ethical behaviour of a professional.
CO 2 Adopt a good character and follow an ethical life.
Explain the role and responsibility in technological development by keeping personal ethics
CO 3
and legal ethics.
Solve moral and ethical problems through exploration and assessment by established
CO 4
experiments.
Apply the knowledge of human values and social values to contemporary ethical values and
CO 5
global issues.

Mapping of course outcomes with program outcomes

PO PO 2 PO 3 PO 4 PO 5 PO 6 PO 7 PO 8 PO 9 PO1 PO1 PO1

1 0 1 2
CO 1 2 2
CO 2 2 2
CO 3 3 2
CO 4 3 2
CO 5 3 2

Assessment Pattern
Continuous Assessment Tests
Bloom’s category End Semester Exam
1 2
Remember 15 15 30
Understood 20 20 40
Apply 15 15 30
Mark distribution
Total
CIE ESE ESE Duration
Marks

150 50 100 3 hours

HUMANITIES
Continuous Internal Evaluation Pattern:
Attendance : 10 marks
Continuous Assessment Tests (2 Nos) : 25 marks
Assignments/Quiz : 15 marks

End Semester Examination Pattern: There will be two parts; Part A and Part B. Part A contains 10 questions
with 2 questions from each module, having 3 marks for each question. Students should answer all questions.
Part B contains 2 questions from each module of which student should answer any one. Each question can have
maximum 2 sub-divisions and carry 14 marks.

Course Level Assessment Questions

Course Outcome 1 (CO1):

1. Define integrity and point out ethical values.
2. Describe the qualities required to live a peaceful life.
3. Explain the role of engineers in modern society.

Course Outcome 2 (CO2)

1. Derive the codes of ethics.
2. Differentiate consensus and controversy.
3. Discuss in detail about character and confidence.

Course Outcome 3(CO3):

1. Explain the role of professional’s ethics in technological development.
2. Distinguish between self interest and conflicts of interest.
3. Review on industrial standards and legal ethics.

Course Outcome 4 (CO4):

1. Illustrate the role of engineers as experimenters.
2. Interpret the terms safety and risk.
3. Show how the occupational crimes are resolved by keeping the rights of employees.

Course Outcome 5 (CO5):

1. Exemplify the engineers as managers.
2. Investigate the causes and effects of acid rain with a case study.
3. Explorate the need of environmental ethics in technological development.
HUMANITIES
Model Question paper
QP CODE: Reg No:______________

PAGES:3 Name :______________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY THIRD/FOURTH SEMESTER

B.TECH DEGREE EXAMINATION, MONTH & YEAR

Course Code: HUT 200

Course Name: PROFESSIONAL ETHICS
Max. Marks: 100 Duration: 3 Hours
(2019-Scheme)

PART A

(Answer all questions, each question carries 3 marks)

1. Define empathy and honesty.

2. Briefly explain about morals, values and ethics.

3. Interpret the two forms of self-respect.

4. List out the models of professional roles.

5. Indicate the advantages of using standards.

6. Point out the conditions required to define a valid consent?

7. Identify the conflicts of interests with an example?

8. Recall confidentiality.

9. Conclude the features of biometric ethics.

10. Name any three professional societies and their role relevant to engineers.

(10x3 = 30 marks)

PART B

(Answer one full question from each module, each question carries 14 marks)

MODULE I

11. a) Classify the relationship between ethical values and law?

b) Compare between caring and sharing. (10+4 = 14 marks)

Or

12. a) Exemplify a comprehensive review about integrity and respect for others.
HUMANITIES
b) Discuss about co-operation and commitment. (8+6 = 14 marks)

MODULE II

13.a) Explain the three main levels of moral developments, deviced by Kohlberg.

b) Differentiate moral codes and optimal codes. (10+4 = 14 marks)

Or

14. a) Extrapolate the duty ethics and right ethics.

b) Discuss in detail the three types of inquiries in engineering ethics (8+6 = 14 marks)

MODULE III

15.a) Summarize the following features of morally responsible engineers.

(i) Moral autonomy (ii) Accountability

b)Explain the rights of employees (8+6 = 14 marks)

Or

16. a) Explain the reasons for Chernobyl mishap ?

b) Describe the methods to improve collegiality and loyalty. (8+6 = 14 marks)

MODULE IV

17.a) Execute collegiality with respect to commitment, respect and connectedness.

b) Identify conflicts of interests with an example. (8+6 = 14 marks)

Or

18. a) Explain in detail about professional rights and employee rights.

b) Exemplify engineers as managers.
MODULE V

19.a) Evaluate the technology transfer and appropriate technology.

b) Explain about computer and internet ethics. (8+6 = 14 marks)
Or

20. a) Investigate the causes and effects of acid rain with a case study.
b) Conclude the features of ecocentric and biocentric ethics. (8+6 = 14 marks)
HUMANITIES
Syllabus

Module 1 – Human Values.

Morals, values and Ethics – Integrity- Academic integrity-Work Ethics- Service Learning- Civic Virtue-
Respect for others- Living peacefully- Caring and Sharing- Honestly- courage-Cooperation commitment-
Empathy-Self Confidence -Social Expectations.

Module 2 - Engineering Ethics & Professionalism.

Senses of Engineering Ethics - Variety of moral issues- Types of inquiry- Moral dilemmas –Moral Autonomy –
Kohlberg’s theory- Gilligan’s theory- Consensus and Controversy-Profession and Professionalism- Models of
professional roles-Theories about right action –Self interest-Customs and Religion- Uses of Ethical Theories.

Module 3- Engineering as social Experimentation.

Engineering as Experimentation – Engineers as responsible Experimenters- Codes of Ethics- Plagiarism-

A balanced outlook on law - Challenges case study- Bhopal gas tragedy.

Module 4- Responsibilities and Rights.

Collegiality and loyalty – Managing conflict- Respect for authority- Collective bargaining- Confidentiality-
Role of confidentiality in moral integrity-Conflicts of interest- Occupational crime- Professional rights-
Employee right- IPR Discrimination.

Module 5- Global Ethical Issues.

Multinational Corporations- Environmental Ethics- Business Ethics- Computer Ethics -Role in Technological
Development-Engineers as Managers- Consulting Engineers- Engineers as Expert witnesses and advisors-Moral
leadership.

Text Book

1. M Govindarajan, S Natarajan and V S Senthil Kumar, Engineering Ethics, PHI Learning

Private Ltd, New Delhi,2012.

2. R S Naagarazan, A text book on professional ethics and human values, New age international
(P) limited ,New Delhi,2006.

Reference Books

1. Mike W Martin and Roland Schinzinger, Ethics in Engineering,4th edition, Tata McGraw Hill
Publishing Company Pvt Ltd, New Delhi,2014.
2. Charles D Fleddermann, Engineering Ethics, Pearson Education/ Prentice Hall of India, New
Jersey,2004.
3. Charles E Harris, Michael S Protchard and Michael J Rabins, Engineering Ethics- Concepts and
cases, Wadsworth Thompson Learning, United states,2005.
4. http://www.slideword.org/slidestag.aspx/human-values-and-Professional-ethics.
HUMANITIES

Course Contents and Lecture Schedule

SL.N Topic No. of Lectures

o 25
1 Module 1 – Human Values.

1.1 Morals, values and Ethics, Integrity, Academic Integrity,Work Ethics 1

1.2 Service Learning, Civic Virtue, Respect for others, Living peacefully 1
1.3 Caring and Sharing, Honesty, Courage, Co-operation commitment 2
1.4 Empathy, Self Confidence, Social Expectations 1
2 Module 2- Engineering Ethics & Professionalism.

2.1 Senses of Engineering Ethics, Variety of moral issues, Types of inquiry 1

2.2 Moral dilemmas, Moral Autonomy, Kohlberg’s theory 1
Gilligan’s theory, Consensus and Controversy,Profession&
2.3 2
Professionalism, Models of professional roles, Theories about right action
2.4 Self interest-Customs and Religion, Uses of Ethical Theories 1
3 Module 3- Engineering as social Experimentation.

3.1 Engineering as Experimentation, Engineers as responsible Experimenters 1

3.2 Codes of Ethics,Plagiarism, A balanced outlook on law 2
3.3 Challenger case study, Bhopal gas tragedy 2
4 Module 4- Responsibilities and Rights.

4.1 Collegiality and loyalty, Managing conflict, Respect for authority 1

Collective bargaining, Confidentiality, Role of confidentiality in moral
4.2 2
integrity, Conflicts of interest
Occupational crime, Professional rights, Employee right, IPR
4.3 2
Discrimination
5 Module 5- Global Ethical Issues.

Multinational Corporations, Environmental Ethics, Business Ethics,

5.1 2
Computer Ethics
5.2 Role in Technological Development, Moral leadership 1
Engineers as Managers, Consulting Engineers, Engineers as Expert
5.3 2
witnesses and advisors
HUMANITIES
CODE COURSE NAME CATEGORY L T P CREDIT
MCN202 CONSTITUTION OF INDIA 2 0 0 NIL

Preamble:

The study of their own country constitution and studying the importance environment as
well as understanding their own human rights help the students to concentrate on their day
to day discipline. It also gives the knowledge and strength to face the society and people.

Prerequisite: Nil

Course Outcomes: After the completion of the course the student will be able to

CO 1 Explain the background of the present constitution of India and features.

CO 2 Utilize the fundamental rights and duties.

CO 3 Understand the working of the union executive, parliament and judiciary.

CO 4 Understand the working of the state executive, legislature and judiciary.

CO 5 Utilize the special provisions and statutory institutions.

CO 6 Show national and patriotic spirit as responsible citizens of the country

Mapping of course outcomes with program outcomes

PO 1 PO 2 PO 3 PO 4 PO 5 PO 6 PO 7 PO 8 PO 9 PO PO PO
10 11 12
CO 1 2 2 2 2
CO 2 3 3 3 3
CO 3 3 2 3 3
CO 4 3 2 3 3
CO 5 3 2 3 3
CO 6 3 3 3 2

Assessment Pattern

Bloom’s Category Continuous Assessment End Semester Examination

Tests
1 2
Remember 20 20 40
Understand 20 20 40
Apply 10 10 20
Analyse
HUMANITIES
Evaluate
Create

Mark distribution

Total CIE ESE ESE Duration

Marks

150 50 100 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 10 marks
Continuous Assessment Test (2 numbers) : 25 marks
Assignment/Quiz/Course project : 15 marks

End Semester Examination Pattern: There will be two parts; Part A and Part B. Part A
contain 10 questions with 2 questions from each module, having 3 marks for each question.
Students should answer all questions. Part B contains 2 questions from each module of
which student should answer any one. Each question can have maximum 2 sub-divisions
and carry 14 marks.
Course Level Assessment Questions

Course Outcome 1 (CO1):

1 Discuss the historical background of the Indian constitution.

2 Explain the salient features of the Indian constitution.

3 Discuss the importance of preamble in the implementation of constitution.

Course Outcome 2 (CO2)

1 What are fundamental rights ? Examine each of them.

2 Examine the scope of freedom of speech and expression underlying the constitution.

3 The thumb impression of an accused is taken by the police against his will. He contends

that this is a violation of his rights under Art 20(3) of the constitution. Decide.

Course Outcome 3(CO3):

1 Explain the powers of the President to suspend the fundamental rights during emergency.
HUMANITIES
2 Explain the salient features of appeal by special leave.

3. List the constitutional powers of President.

Course Outcome 4 (CO4):

1 Discuss the constitutional powers of Governor.

2 Examine the writ jurisdiction of High court.

3 Discuss the qualification and disqualification of membership of state legislature.

Course Outcome 5 (CO5):

1 Discuss the duties and powers of comptroller of auditor general.

2 Discuss the proclamation of emergency.

3 A state levies tax on motor vehicles used in the state, for the purpose of maintaining roads

in the state. X challenges the levy of the tax on the ground that it violates the freedom of

interstate commerce guaranteed under Art 301. Decide.

Course Outcome 6 (CO6):

1 Explain the advantages of citizenship.

2 List the important principles contained in the directive principles of state policy.

3 Discuss the various aspects contained in the preamble of the constitution

Model Question paper

PART A

(Answer all questions. Each question carries 3 marks)

1 Define and explain the term constitution.

2 Explain the need and importance of Preamble.

3 What is directive principle of state policy?

4 Define the State.

5 List the functions of Attorney general of India.

HUMANITIES
6 Explain the review power of Supreme court.

7 List the qualifications of Governor.

8 Explain the term and removal of Judges in High court.

9 Explain the powers of public service commission.

10 List three types of emergency under Indian constitution.

(10X3=30marks)

PART B

(Answer on question from each module. Each question carries 14 marks)

Module 1

11 Discuss the various methods of acquiring Indian citizenship.

12 Examine the salient features of the Indian constitution.

Module 2

13 A high court passes a judgement against X. X desires to file a writ petition in the supreme

court under Art32, on the ground that the judgement violates his fundamental rights.

Advise him whether he can do so.

14 What is meant by directive principles of State policy? List the directives.

Module3

15 Describe the procedure of election and removal of the President of India.

16 Supreme court may in its discretion grant special leave to appeal. Examine the situation.

Module 4

17 Discuss the powers of Governor.

18 X filed a writ petition under Art 226 which was dismissed. Subsequently, he filed a writ

petition under Art 32 of the constitution, seeking the same remedy. The Government

argued that the writ petition should be dismissed, on the ground of res judicata. Decide.

Module 5
HUMANITIES
19 Examine the scope of the financial relations between the union and the states.

20 Discuss the effects of proclamation of emergency.

(14X5=70marks)

Syllabus

Module 1 Definition, historical back ground, features, preamble, territory, citizenship.

Module 2 State, fundamental rights, directive principles, duties.

Module 3 The machinery of the union government.

Module 4 Government machinery in the states

Module 5 The federal system, Statutory Institutions, miscellaneous provisions.

Text Books

1 D D Basu, Introduction to the constitution of India, Lexis Nexis, New Delhi, 24e, 2019

2 PM Bhakshi, The constitution of India, Universal Law, 14e, 2017

Reference Books

1 Ministry of law and justice, The constitution of India, Govt of India, New Delhi, 2019.

2 JN Pandey, The constitutional law of India, Central Law agency, Allahabad, 51e, 2019

3 MV Pylee, India’s Constitution, S Chand and company, New Delhi, 16e, 2016

Course Contents and Lecture Schedule

No Topic No. of Lectures
1 Module 1
1.1 Definition of constitution, historical back ground, salient features 1
of the constitution.
1.2 Preamble of the constitution, union and its territory. 1
1.3 Meaning of citizenship, types, termination of citizenship. 2
2 Module 2
2.1 Definition of state, fundamental rights, general nature, 2
classification, right to equality ,right to freedom , right against
exploitation
HUMANITIES
2.2 Right to freedom of religion, cultural and educational rights, right 2
to constitutional remedies. Protection in respect of conviction for
offences.
2.3 Directive principles of state policy, classification of directives, 2
fundamental duties.
3 Module 3
3.1 The Union executive, the President, the vice President, the 2
council of ministers, the Prime minister, Attorney-General,
functions.
3.2 The parliament, composition, Rajya sabha, Lok sabha, 2
qualification and disqualification of membership, functions of
parliament.

3.3 Union judiciary, the supreme court, jurisdiction, appeal by special 1

leave.
4 Module 4
4.1 The State executive, the Governor, the council of ministers, the 2
Chief minister, advocate general, union Territories.
4.2 The State Legislature, composition, qualification and 2
disqualification of membership, functions.
4.3 The state judiciary, the high court, jurisdiction, writs jurisdiction. 1
5 Module 5
5.1 Relations between the Union and the States, legislative relation, 1
administrative relation, financial Relations, Inter State council,
finance commission.
5.2 Emergency provision, freedom of trade commerce and inter 2
course, comptroller and auditor general of India, public Services,
public service commission, administrative Tribunals.
5.3 Official language, elections, special provisions relating to certain 2
classes, amendment of the Constitution.
COMPUTER SCIENCE AND ENGINEERING
CATEGORY L T P CREDIT
CSL 202 DIGITAL LAB
PCC 0 0 3 2

Preamble: This course helps the learners to get familiarized with (i) Digital Logic Design
through the implementation of Logic Circuits using ICs of basic logic gates & flip-
flops and (ii) Hardware Description Language based Digital Design. This course helps the
learners to design and implement hardware systems in areas such as games, music, digital
filters, wireless communications and graphical displays.

Prerequisite:Topics covered under the course Logic System Design (CST 203)

Course Outcomes: After the completion of the course the student will be able to

Design and implement combinational logic circuits using Logic Gates (Cognitive
CO 1
Knowledge Level: Apply)

Design and implement sequential logic circuits using Integrated Circuits

CO 2
(Cognitive Knowledge Level: Apply)
Simulate functioning of digital circuits using programs written in a Hardware
CO 3
Description Language (Cognitive Knowledge Level: Apply)

Function effectively as an individual and in a team to accomplish a given task of

CO 4
designing and implementing digital circuits (Cognitive Knowledge Level: Apply)

Mapping of course outcomes with program outcomes

PO 1 PO 2 PO 3 PO 4 PO 5 PO 6 PO 7 PO 8 PO 9 PO10 PO11 PO12

CO 1

CO 2

CO 3

CO 4
COMPUTER SCIENCE AND ENGINEERING
Assessment Pattern

Continuous Assessment
End Semester
Bloom’s Category Test (Internal Exam)
Examination (Percentage)
(Percentage)

Remember 20 20
Understand 20 20

Apply 60 60
Analyse

Evaluate
Create

Mark Distribution

Total Marks CIE Marks ESE Marks ESE Duration

150 75 75 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 15 marks

Continuous Evaluation in Lab : 30 marks

Continuous Assessment Test : 15 marks

Viva-voce : 15 marks

Internal Examination Pattern: The marks will be distributed as Design/Algorithm 30

marks, Implementation/Program 20 marks, Output 20 marks and Viva 30 marks. Total 100
marks which will be converted out of 15 while calculating Internal Evaluation marks.

End Semester Examination Pattern:The marks will be distributed as Design/Algorithm 30

marks, Implementation/Program 20 marks, Output 20 marks and Viva 30 marks. Total 100
marks will be converted out of 75 for End Semester Examination.
COMPUTER SCIENCE AND ENGINEERING
Fair Lab Record:
All Students attending the Digital Lab should have a Fair Record. The fair record should be
produced in the University Lab Examination. Every experiment conducted in the lab should
be noted in the fair record. For every experiment in the fair record, the right hand page should
contain Experiment Heading, Experiment Number, Date of Experiment, and Aim of
Experiment. The left hand page should contain components used, circuit design or a print out
of the code used for the experiment and sample output obtained.

SYLLABUS

Conduct a minimum of 8 experiments from Part A and a minimum of 4 experiments from

Part B. The starred experiments in Part A are mandatory. The lab work should be conducted
in groups (maximum group size being 4). The performance of a student in the group should
be assessed based on teamwork, integrity and cooperation.
Part A (Any 8 Experiments)

• A 2 hour session should be spent to make the students comfortable with the use of
trainer kit/breadboard and ICs.
• The following experiments can be conducted on breadboard or trainer kits.
• Out of the 15 experiments listed below, a minimum of 8 experiments should be
completed by a student, including the mandatory experiments (5).

1. Realization of functions using basic and universal gates (SOP and POS forms).
2. Design and realization of half adder, full adder, half subtractor and full subtractor using:
a) basic gates (b) universal gates. *
3. Code converters: Design and implement BCD to Excess 3 and Binary to Gray code
converters.
4. Design and implement 4 bit adder/subtractor circuit and BCD adder using IC7483.
5. Implementation of Flip Flops: SR, D, T, JK and Master Slave JK Flip Flops using basic
gates.*
6. Asynchronous Counter: Design and implement 3 bit up/down counter.
7. Asynchronous Counter: Realization of Mod N counters (At least one up counter and one
down counter to be implemented). *
8. Synchronous Counter: Realization of 4-bit up/down counter.
9. Synchronous Counter: Realization of Mod-N counters and sequence generators. (At least
one mod N counter and one sequence generator to be implemented) *
10. Realization of Shift Register (Serial input left/right shift register), Ring counter and
Johnson Counter using flipflops. *
11. Realization of counters using IC’s (7490, 7492, 7493).
12. Design and implement BCD to Seven Segment Decoder.
13. Realization of Multiplexers and De-multiplexers using gates.
14. Realization of combinational circuits using MUX & DEMUX ICs (74150, 74154).
15. To design and set up a 2-bit magnitude comparator using basic gates.
COMPUTER SCIENCE AND ENGINEERING
PART B (Any 4 Experiments)

• The following experiments aim at training the students in digital circuit design with
Verilog. The experiments will lay a foundation for digital design with Hardware
Description Languages.
• A 3 hour introductory session shall be spent to make the students aware of the
fundamentals of development using Verilog
• Out of the 8 experiments listed below, a minimum of 4 experiments should be
completed by a student
Experiment 1. Realization of Logic Gates and Familiarization of Verilog
(a) Familiarization of the basic syntax of Verilog
(b) Development of Verilog modules for basic gates and to verify truth tables.
(c) Design and simulate the HDL code to realize three and four variable Boolean
functions

Experiment 2: Half adder and full adder

(a) Development of Verilog modules for half adder in 3 modeling styles (dataflow/
structural/behavioural).
(b) Development of Verilog modules for full adder in structural modeling using half
adder.

Experiment 3: Design of code converters

Design and simulate the HDL code for

(a) 4- bit binary to gray code converter

(b) 4- bit gray to binary code converter

Experiment 4: Mux and Demux in Verilog

(a) Development of Verilog modules for a 4x1 MUX.
(b) Development of Verilog modules for a 1x4 DEMUX.

Experiment 5: Adder/Subtractor
(a) Write the Verilog modules for a 4-bit adder/subtractor
(b) Development of Verilog modules for a BCD adder

Experiment 6: Magnitude Comparator

Development of Verilog modules for a 4 bit magnitude comparator

Experiment 7: Flipflops and shiftregisters

(a) Development of Verilog modules for SR, JK, T and D flip flops.
(b) Development of Verilog modules for a Johnson/Ring counter

Experiment 8: Counters
(a) Development of Verilog modules for an asynchronous decade counter.
(b) Development of Verilog modules for a 3 bit synchronous up-down counter.
COMPUTER SCIENCE AND ENGINEERING
Practice Questions

PART A
1. Design a two bit parallel adder using gates and implement it using ICs of basic gates
2. A combinatorial circuit has 4 inputs and one output. The output is equal to 1 when (a)
all inputs are 1, (b) none of the inputs are 1, (c) an odd number of inputs are equal to
1. Obtain the truth table and output function for this circuit and implement the same.
3. Design and implement a parallel subtractor.
4. Design and implement a digital circuit that converts Gray code to Binary.
5. Design a combinational logic circuit that will output the 1’s compliment of a 4-bit
input number.

∑
6. Implement and test the logic function f! (A, B, C ) = m(0,1,3,6) using an 8:1 MUX
IC
7. Design a circuit that will work as a ring counter or a Johnson counter based on a mode
bit, M.
8. Design a 4-bit synchronous down counter.
9. Design a Counter to generate the binary sequence 0,1,3,7,6,4
10. Design an asynchronous mod 10 down counter
11. Design and implement a synchronous counter using JK flip flop ICs to generate the
sequence: 0 - 1 -3 - 5 - 7 - 0.

PART B
1. Develop Verilog modules for a full subtractor in structural modeling using half
subtractors.
2. Design a 4 bit parallel adder using Verilog.
3. Develop Verilog modules for a 4 bit synchronous down counter.
4. Write Verilog code for implementing a 8:1 multiplexer.
5. Develop Verilog modules for a circuit that converts Excess 3 code to binary.
6. Write the Verilog code for a JK Flip flop, and its test-bench. Use all possible
combinations of inputs to test its working
7. Write the hardware description in Verilog of a 8-bit register with shift left and shift
right modes of operations and test its functioning.
8. Write the hardware description in Verilog of a mod-N (N > 9) counter and test it.
COMPUTER SCIENCE AND ENGINEERING

YEAR OF
OPERATING CATEGORY L T P CREDIT
CST 206 INTRODUCTION
SYSTEMS LAB
PCC 0 0 3 2 2019

Preamble: The course aims to offer students a hands-on experience on Operating System
concepts using a constructivist approach and problem-oriented learning. Operating systems are
the fundamental part of every computing device to run any type of software.

Prerequisite: Topics covered in the courses are Data Structures (CST 201) and Programming
in C (EST 102)

Course Outcomes:

At the end of the course, the student should be able to

Illustrate the use of systems calls in Operating Systems. (Cognitive knowledge:

CO1
Understand)

Implement Process Creation and Inter Process Communication in Operating

CO2
Systems. (Cognitive knowledge: Apply)
Implement Fist Come First Served, Shortest Job First, Round Robin and Priority-
CO3
based CPU Scheduling Algorithms. (Cognitive knowledge: Apply)

Illustrate the performance of First In First Out, Least Recently Used and Least
CO4
Frequently Used Page Replacement Algorithms. (Cognitive knowledge: Apply)
Implement modules for Deadlock Detection and Deadlock Avoidance in Operating
CO5
Systems. (Cognitive knowledge: Apply)
Implement modules for Storage Management and Disk Scheduling in Operating
CO6
Systems. (Cognitive knowledge: Apply)
COMPUTER SCIENCE AND ENGINEERING

Mapping of course outcomes with program outcomes

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12

CO1

CO2

CO3

CO4

CO5

CO6

Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics

PO3 Design/Development of solutions PO9 Individual and team work

Conduct investigations of complex

PO4 PO10 Communication
problems

PO5 Modern tool usage PO11 Project Management and Finance

PO6 The Engineer and Society PO12 Life long learning

Assessment Pattern:

Continuous Assessment Test

End Semester Examination
Bloom’s Category (Internal Exam) Marks in
Marks in percentage
percentage
Remember 20 20
Understand 20 20
Apply 60 60
Analyse

Evaluate
Create
COMPUTER SCIENCE AND ENGINEERING

Mark Distribution

ESE
Total Marks CIE Marks ESE Duration
Marks
150 75 75 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 15 marks

Continuous Evaluation in Lab : 30 marks

Continuous Assessment Test : 15 marks

Viva Voce : 15 marks

Internal Examination Pattern: The marks will be distributed as Algorithm 30 marks,

Program 20 marks, Output 20 marks and Viva 30 marks. Total 100 marks which will be
converted out of 15 while calculating Internal Evaluation marks.

End Semester Examination Pattern: The percentage of marks will be distributed as

Algorithm 30 marks, Program 20 marks, Output 20 marks and Viva 30 marks. Total 75 marks.

Operating System to Use in Lab : Linux

Compiler/Software to Use in Lab : gcc

Progamming Language to Use in Lab : Ansi C

Fair Lab Record:

All Students attending the Operating System Lab should have a Fair Record. The fair record
should be produced in the University Lab Examination. Every experiment conducted in the
lab should be noted in the fair record. For every experiment in the fair record, the right hand
page should contain Experiment Heading, Experiment Number, Date of experiment, Aim of
the Experiment and the operations performed on them, Details of experiment including
algorithm and result of Experiment. The left hand page should contain a print out of the code
used for experiment and sample output obtained for a set of input.
COMPUTER SCIENCE AND ENGINEERING

SYLLABUS
OPERATING SYSTEMS LAB
* mandatory

1. Basic Linux commands

2. Shell programming
-Command syntax
-Write simple functions with basic tests, loops, patterns
3. System calls of Linux operating system:*
fork, exec, getpid, exit, wait, close, stat, opendir, readdir
4. Write programs using the I/O system calls of Linux operating system (open, read, write)
5. Implement programs for Inter Process Communication using Shared Memory *
6. Implement Semaphores*
7. Implementation of CPU scheduling algorithms. a) Round Robin b) SJF c) FCFS d)
Priority *
8. Implementation of the Memory Allocation Methods for fixed partition*
a) First Fit b) Worst Fit c) Best Fit
9. Implement l page replacement algorithms a) FIFO b) LRU c) LFU*
10. Implement the banker’s algorithm for deadlock avoidance. *
11. Implementation of Deadlock detection algorithm
12. Simulate file allocation strategies.
b) Sequential b) Indexed c) Linked
13. Simulate disk scheduling algorithms. *
c) FCFS b)SCAN c) C-SCAN

OPERATING SYSTEMS LAB - PRACTICE QUESTIONS

1. Write a program to create a process in linux.

2. Write programs using the following system calls of Linux operating system:
fork, exec, getpid, exit, wait, close, stat, opendir, readdir
3. Write programs using the I/O system calls of Linux operating system (open, read, write)
COMPUTER SCIENCE AND ENGINEERING

4. Given the list of processes, their CPU burst times and arrival times, display/print the
Gantt chart for FCFS and SJF. For each of the scheduling policies, compute and print the
average waiting time and average turnaround time
5. Write a C program to simulate following non-preemptive CPU scheduling algorithms to
find turnaround time and waiting time.
a)FCFS b) SJF c) Round Robin (pre-emptive) d) Priority
6. Write a C program to simulate following contiguous memory allocation techniques
a) Worst-fit b) Best-fit c) First-fit
7. Write a C program to simulate paging technique of memory management.
8. Write a C program to simulate Bankers algorithm for the purpose of deadlock avoidance.
9. Write a C program to simulate disk scheduling algorithms a) FCFS b) SCAN c) C-SCAN
10. Write a C program to simulate page replacement algorithms a) FIFO b) LRU c) LFU
11. Write a C program to simulate producer-consumer problem using semaphores.
12. Write a program for file manipulation for display a file and directory in memory.
13. Write a program to simulate algorithm for deadlock prevention.
14. Write a C program to simulate following file allocation strategies.
a)Sequential b) Indexed c) Linked
COMPUTER SCIENCE AND ENGINEERING

SEMESTER -4
MINOR
COMPUTER SCIENCE AND ENGINEERING

CST Programming Category L T P CREDIT YEAR OF INTRODUCTION

28 Methodologies MINOR 3 1 0 4 2019

Preamble: This is the second course for awarding B.Tech Minor in Computer Science and
Engineering with specialization in Software Engineering. The course provides the learners a
clear understanding of the main constructs of contemporary programming languages and the
various systems of ideas that have been used to guide the design of programming languages.
This course covers the concepts of Names, Bindings & Scope, Statement-Level Control
Structures, Sub Programs, support for Object Oriented Programming, Exception Handling, Event
Handling, Concurrency Control, Functional Programming and Logic Programming. This course
helps the learners to equip with the knowledge necessary for the critical evaluation of existing
and upcoming programming languages. It also enables the learner to choose the most appropriate
language for a given programming task, apply that language's approach to structure or organize
the code and classify programming languages based on their features.
Prerequisite:

1. Topics covered under the course Programming in C (EST 102)

2. Object Oriented Programming (CST 251)

Course Outcomes: After the completion of the course the student will be able to

Explain the criteria for evaluating programming languages and compare Imperative,
CO1 Functional and Logic programming languages (Cognitive Knowledge Level:
Understand)

Explain the characteristics of data types and variables (Cognitive Knowledge Level:
CO2
Understand)
Illustrate how control flow structures and subprograms help in developing the
CO3 structure of a program to solve a computational problem (Cognitive Knowledge Level:
Apply)
Explain the characteristics of Object Oriented Programming Languages (Cognitive
CO4
Knowledge Level: Understand)
Compare concurrency constructs in different programming languages (Cognitive
CO5
Knowledge Level: Understand)

1
COMPUTER SCIENCE AND ENGINEERING

Mapping of course outcomes with program outcomes

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12

CO1

CO2

CO3

CO4

CO5

Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics

PO3 Design/Development of solutions PO9 Individual and team work

Conduct investigations of complex

PO4 PO10 Communication
problems
PO5 Modern tool usage PO11 Project Management and Finance

PO6 The Engineer and Society PO12 Life long learning

Assessment Pattern

Continuous Assessment Tests End Semester Examination

Bloom’s Category
Test 1 (Marks%) Test 2 (Marks%) (Marks%)

Remember 30 30 30
Understand 50 50 50
Apply 20 20 20
Analyze
Evaluate
Create

2
COMPUTER SCIENCE AND ENGINEERING

Mark Distribution

Total Marks CIE Marks ESE Marks ESE Duration

150 50 100 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 10 marks
Continuous Assessment Test : 25 marks
Continuous Assessment Assignment : 15 marks

Internal Examination Pattern:

Each of the two internal examinations has to be conducted out of 50 marks. First series test shall
be preferably conducted after completing the first half of the syllabus and the second series test
shall be preferably conducted after completing remaining part of the syllabus. There will be two
parts: Part A and Part B. Part A contains 5 questions (preferably, 2 questions each from the
completed modules and 1 question from the partly completed module), having 3 marks for each
question adding up to 15 marks for part A. Students should answer all questions from Part A.
Part B contains 7 questions (preferably, 3 questions each from the completed modules and 1
question from the partly completed module), each with 7 marks. Out of the 7 questions, a student
should answer any 5.

End Semester Examination Pattern:

There will be two parts; Part A and Part B. Part A contains 10 questions with 2 questions from
each module, having 3 marks for each question. Students should answer all questions. Part B
contains 2 questions from each module of which a student should answer any one. Each question
can have maximum 2 sub-divisions and carries 14 marks.

3
COMPUTER SCIENCE AND ENGINEERING

SYLLABUS

Module 1

Introduction – Role of Programming Languages, Programming Domains, Language Evaluation

Criteria, Influence on Language Design, Language Design Trade-offs, Implementation Methods.
Names, Bindings & Scope – Names, Variables, Concept of Binding, Scope and Lifetime,
Referencing Environments.
Module 2

Data Types – Primitive Data Types, Character String Types, User-Defined Ordinal Types, Array
Types, Record Types, List Types, Pointer & Reference Types, Type Checking, Strong Typing,
Type Equivalence. Expressions – Arithmetic Expressions, Overloaded Operators, Type
Conversions, Relational and Boolean Expressions, Short-Circuit Evaluation. Assignment -
Assignment Statements, Mixed-mode Assignment.

Module 3

Statement-Level Control Structures – Selection Statements, Iterative Statements,

Unconditional Branching, Guarded Commands. Subprograms – Design Issues of Subprograms,
Local Referencing Environments, Parameter Passing Methods, Subprograms as Parameters,
Overloaded Subprograms, Closures, Co-routines.

Module 4

Support for Object Oriented Programming – Inheritance, Dynamic Binding, Design Issues for Object
Oriented Languages, Support for Object Oriented Programming in C++, Implementation of Object-
Oriented Constructs. Exception Handling – Basic Concepts, Design Issues. Event Handling - Introduction
to Event Handling.

Module 5

Concurrency – Subprogram Level Concurrency, Semaphores, Monitors, Message Passing.

Functional Programming Languages – Introduction to LISP and Scheme, Comparison of
Functional and Imperative Languages. Logic Programming Languages – Basic Elements of
Prolog, Applications of Logic Programming.

Text Books

1. Robert W. Sebesta, Concepts of Programming Languages, 10th Edition, Pearson.

2. Scott M. L., Programming Language Pragmatics, 3rd Edn., Morgan Kaufmann Publishers.

4
COMPUTER SCIENCE AND ENGINEERING

Reference Books:

1. Kenneth C. Louden, Programming Languages: Principles and Practice, 2nd Edn., Cengage
Learning.

2. Tucker A. B. and R. E. Noonan, Programming Languages: Principles and Paradigms, 2nd

Edn. –TMH.

3. Ravi Sethi, Programming Languages: Concepts & Constructs, 2nd Edn., Pearson
Education.

4. David A. Watt, Programming Language Design Concepts, Wiley Dreamtech

Sample Course Level Assessment Questions

Course Outcome 1 (CO1): Compare any three programming languages based on the language
evaluation criteria. Prepare a list of characteristics that affect the language evaluation criteria.
Identify the advantages and disadvantages of imperative, functional and logic programming
languages.
Course Outcome 2 (CO2): Two most important design issues that are specific to character
string types are (1) whether a string is simply a special kind of character array or a primitive type
(2) whether strings have static or dynamic length. Justify your answer.
Course Outcome 3 (CO3):
1. Describe three situations where a combined counting and logical looping statement is
needed.
2. Describe the ways that aliases can occur with pass-by-reference parameters.
3. Identify the two fundamental design considerations for parameter-passing methods.
Course Outcome 4 (CO4):
1. Describe the role of a virtual method table in implementing dynamic method binding.
2. Identify one disadvantage of inheritance.
Course Outcome 5 (CO5): Evaluate the use of semaphores and monitors for providing
competition synchronization and cooperation synchronization.

5
COMPUTER SCIENCE AND ENGINEERING

Model Question paper

QP CODE: PAGES:3

Reg No:______________ Name :______________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

FOURTH SEMESTER B.TECH (MINOR) DEGREE EXAMINATION, MONTH &

YEAR Course Code: CST 282

Course Name: Programming Methodologies

Max.Marks:100 Duration: 3 Hours

PART A

Answer all Questions. Each question carries 3 Marks

1. Differentiate between readability and writability.

2. Define binding and binding time
3. What are the advantages of user-defined enumeration types?
4. Define narrowing and widening conversions.
5. Why for statement in C language is more flexible than that of older languages?
6. What are the advantages and disadvantages of dynamic local variables in subprograms?
7. Explain the concept of dynamic method binding with an example.
8. Is it mandatory to use constructors in object oriented languages? Justify your answer.
9. What are the applications of logical programming languages?
10. Explain the working of let and let-rec constructs in Scheme.

Part B

Answer any one Question from each module. Each question carries 14 Marks

11.
(a) Explain different criteria used for evaluating languages.
(7 marks)
(b) Explain the major methods of implementing programming languages.
(7 marks)

OR

12.
(a) Explain the meanings, purposes, advantages and disadvantages of four categories of
scalar variables according to their storage bindings.
(7 marks)

6
COMPUTER SCIENCE AND ENGINEERING

(b) What is referencing environment of a statement? Show the referencing

environment at the indicated program points (1), (2), (3) & (4) for the following
program segment. Assume that the programming language used is statically scoped.

program example;
var a, b : integer;
procedure sub1;
var x, y: integer;
begin { sub1 }
……….. (1)
end { sub1 }
procedure sub2;
var x : integer;
……..
procedure sub3;
var x: integer;
begin { sub3 }
……….. (2)
end { sub3 }
begin { sub2 }
……….. (3)
end { sub2}
begin {example}
……….. (4)
end {example } (7 Marks)

13.
(a) Explain any two problems associated with the pointer data types and also indicate
how dangling pointer problem can be solved.
(7 marks)
(b) Describe the lazy and eager approaches for reclaiming garbage.
(7 marks)
OR

14.
(a) What is meant by side effect and illustrate the advantages of referential
transparency?
(8 marks)
(b) Explain the terms: compound assignment operator, coercion and short circuit
evaluation. (6 marks)

7
COMPUTER SCIENCE AND ENGINEERING

15.
(a) Explain different categories of iteration control statements.
(8 marks)
(b) Explain techniques used for identifying correct referencing environment for a
subprogram that was sent as a parameter.
(6 marks)
OR
16.
(a) Describe the implementation models of Parameter passing.
(10 Marks)
(b) Differentiate coroutines from conventional subprograms.
(4 marks)
17.
(a) What is an exception handler? Explain how exceptions are handled in object
oriented language?
(7 Marks)
(b) What are the design issues in object oriented languages? (7 Marks)

OR

18. Explain the following object oriented features:

(i) Encapsulation
(ii) Inheritance
(iii) Constructors and Destructors
(iv) Operator Overloading
(v) Polymorphism
(14 Marks)
19.
(a) Compare functional and imperative programming languages.
(7 Marks)
(b) Explain the role of monitors in concurrency.
(7 Marks)
OR
20.
(a) Explain the searching strategies used in Prolog. Why backward chaining is preferred
over forward chaining in Prolog?
(10 Marks)
(b) How does a binary semaphore differ from an ordinary semaphore?
(4 Marks)

8
COMPUTER SCIENCE AND ENGINEERING

Teaching Plan

Module 1 (Introduction) 9 Hours

Introduction : Reasons for studying Concepts of programming

1.1 1 Hour
languages, Programming Domains
1.2 Language Evaluation Criteria (Lecture 1) 1 Hour

1.3 Language Evaluation Criteria (Lecture 2) 1 Hour

1.4 Influence on Language Design, Language Design Trade-offs 1 Hour

1.5 Implementation Methods 1 Hour

1.6 Names, Variables 1 Hour

1.7 Concept of Binding 1 Hour

1.8 Scope and Lifetime 1 Hour

1.9 Referencing Environments 1 Hour

Module 2 (Data Types, Expressions and Assignment Statements) 8 Hours

2.1 Primitive Data Types, Character String Types 1 Hour

2.2 User-Defined Ordinal Types, Array Types 1 Hour

2.3 Record Types, List Types, Pointer and Reference Types 1 Hour

Implementation of pointer and reference types, Type Checking,

2.4 1 Hour
Strong Typing, Type Equivalence
Expressions and Assignment Statements, Arithmetic
2.5 1 Hour
Expressions
2.6 Overloaded Operators, Type Conversions 1 Hour

2.7 Relational and Boolean Expressions, Short-Circuit Evaluation 1 Hour

2.8 Assignment Statements, Mixed-mode Assignment 1 Hour

Module 3 (Statement Level Control Structures, Subprograms) 8 Hours

3.1 Selection Statements, Iterative Statements 1 Hour

3.2 Unconditional Branching 1 Hour

9
COMPUTER SCIENCE AND ENGINEERING

3.3 Guarded Commands 1 Hour

3.4 Subprograms: Design Issues of Subprograms 1 Hour

3.5 Local Referencing Environments 1 Hour

3.6 Parameter Passing Methods 1 Hour

3.7 Subprograms as Parameters, Overloaded Subprograms 1 Hour

3.8 Closures, Co-routines 1 Hour

Module 4 (Support for Object Oriented Programming, Exception

10 Hours
Handling, Event handling)
4.1 Inheritance 1 Hour

4.2 Dynamic Binding 1 Hour

4.3 Design Issues for Object Oriented Languages 1 Hour

4.4 Support for Object Oriented Programming in C++ 1 Hour

4.5 Implementation of Object-Oriented Constructs (Lecture 1) 1 Hour

4.6 Implementation of Object-Oriented Constructs (Lecture 2) 1 Hour

4.7 Implementation of Object-Oriented Constructs (Lecture 3) 1 Hour

4.8 Basic Concepts 1 Hour

4.9 Exception Handling - Design Issues 1 Hour

4.10 Introduction to Event Handling 1 Hour

Module 5 (Concurrency, Functional Programming Languages, Logic

10 Hours
Programming languages)
5.1 Subprogram Level Concurrency 1 Hour

5.2 Semaphores 1 Hour

5.3 Monitors 1 Hour

5.4 Message Passing 1 Hour

5.5 Introduction to LISP and Scheme (Lecture 1) 1 Hour

5.6 Introduction to LISP and Scheme (Lecture 2) 1 Hour

5.7 Comparison of Functional and Imperative Languages 1 Hour

5.8 Basic Elements of Prolog (Lecture 1) 1 Hour

10
COMPUTER SCIENCE AND ENGINEERING

5.9 Basic Elements of Prolog (Lecture 2) 1 Hour

5.10 Applications of Logic Programming 1 Hour

11
COMPUTER SCIENCE AND ENGINEERING
CODE Mathematics for Machine CATEGORY L T P CREDIT
CST 284 Learning MINOR 3 1 0 4

Preamble: This is a foundational course for awarding B. Tech. Minor in Computer Science
and Engineering with specialization in Machine Learning. The purpose of this course is to
introduce mathematical foundations of basic Machine Learning concepts among learners, on which
Machine Learning systems are built. This course covers Linear Algebra, Vector Calculus, Probability
and Distributions, Optimization and Machine Learning problems. Concepts in this course help the
learners to understand the mathematical principles in Machine Learning and aid in the creation of new
Machine Learning solutions, understand & debug existing ones, and learn about the inherent
assumptions & limitations of the current methodologies.
Prerequisite:
1. A sound background in higher secondary school Mathematics.
2. Python for Machine Learning (CST 253)
Course Outcomes: After the completion of the course the student will be able to
Make use of the concepts, rules and results about linear equations, matrix algebra,
CO 1 vector spaces, eigenvalues & eigenvectors and orthogonality & diagonalization to
solve computational problems (Cognitive Knowledge Level: Apply)
Perform calculus operations on functions of several variables and matrices,
CO 2
including partial derivatives and gradients (Cognitive Knowledge Level: Apply)

Utilize the concepts, rules and results about probability, random variables, additive
& multiplicative rules, conditional probability, probability distributions and Bayes’
CO 3
theorem to find solutions of computational problems (Cognitive Knowledge Level:
Apply)
Train Machine Learning Models using unconstrained and constrained optimization
CO 4
methods (Cognitive Knowledge Level: Apply)
Illustrate how the mathematical objects - linear algebra, probability, and calculus
CO 5 can be used to design machine learning algorithms (Cognitive Knowledge Level:
Understand)

Mapping of course outcomes with program outcomes

PO 1 PO 2 PO 3 PO 4 PO 5 PO 6 PO 7 PO 8 PO 9 PO 10 PO 11 PO 12
CO 1 √ √ √ √ √
CO 2 √ √ √ √
CO 3 √ √ √ √ √
CO 4 √ √ √ √ √ √

CO 5 √ √ √ √ √ √ √ √
COMPUTER SCIENCE AND ENGINEERING
Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics
PO3 Design/Development of solutions PO9 Individual and team work

Conduct investigations of complex

PO4 PO10 Communication
problems
PO5 Modern tool usage PO11 Project Management and Finance
PO6 The Engineer and Society PO12 Life long learning

Assessment Pattern

Continuous Assessment Tests End Semester

Bloom’s Category
1 2 Examination

Remember 20% 20% 20%

Understand 40% 40% 40%

Apply 40% 40% 40%

Analyse
Evaluate

Create

Mark Distribution

Total Marks CIE Marks ESE Marks ESE Duration

150 50 100 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 10 marks

Continuous Assessment Tests : 25 marks

Continuous Assessment Assignment : 15 marks

COMPUTER SCIENCE AND ENGINEERING
Internal Examination Pattern:

Each of the two internal examinations has to be conducted out of 50 marks

First Internal Examination shall be preferably conducted after completing the first half of the
syllabus and the Second Internal Examination shall be preferably conducted after completing
remaining part of the syllabus.

There will be two parts: Part A and Part B. Part A contains 5 questions (preferably, 2
questions each from the completed modules and 1 question from the partly covered module),
having 3 marks for each question adding up to 15 marks for part A. Students should answer
all questions from Part A. Part B contains 7 questions (preferably, 3 questions each from the
completed modules and 1 question from the partly covered module), each with 7 marks. Out
of the 7 questions in Part B, a student should answer any 5.

End Semester Examination Pattern: There will be two parts; Part A and Part B. Part A
contains 10 questions with 2 questions from each module, having 3 marks for each question.
Students should answer all questions. Part B contains 2 questions from each module of which
student should answer anyone. Each question can have maximum 2 sub-divisions and carries
14 marks. 

COMPUTER SCIENCE AND ENGINEERING
Syllabus

Module 1

LINEAR ALGEBRA : Systems of Linear Equations – Matrices, Solving Systems of Linear

Equations. Vector Spaces - Linear Independence, Basis and Rank, Linear Mappings, Norms,
- Inner Products - Lengths and Distances - Angles and Orthogonality - Orthonormal Basis -
Orthogonal Complement - Orthogonal Projections. Matrix Decompositions - Determinant
and Trace, Eigenvalues and Eigenvectors, Cholesky Decomposition, Eigen decomposition
and Diagonalization, Singular Value Decomposition, Matrix Approximation.

Module 2

VECTOR CALCULUS : Differentiation of Univariate Functions - Partial Differentiation

and Gradients, Gradients of Vector Valued Functions, Gradients of Matrices, Useful
Identities for Computing Gradients. Back propagation and Automatic Differentiation - Higher
Order Derivatives- Linearization and Multivariate Taylor Series.

Module 3

Probability and Distributions : Construction of a Probability Space - Discrete and

Continuous Probabilities, Sum Rule, Product Rule, and Bayes’ Theorem. Summary Statistics
and Independence – Important Probability distributions - Conjugacy and the Exponential
Family - Change of Variables/Inverse Transform.

Module 4

Optimization : Optimization Using Gradient Descent - Gradient Descent With Momentum,

Stochastic Gradient Descent. Constrained Optimization and Lagrange Multipliers - Convex
Optimization - Linear Programming - Quadratic Programming.

Module 5

CENTRAL MACHINE LEARNING PROBLEMS : Data and Learning Model-

Empirical Risk Minimization - Parameter Estimation - Directed Graphical Models.

Linear Regression - Bayesian Linear Regression - Maximum Likelihood as Orthogonal

Projection.

Dimensionality Reduction with Principal Component Analysis - Maximum Variance

Perspective, Projection Perspective. Eigenvector Computation and Low Rank
Approximations.
COMPUTER SCIENCE AND ENGINEERING
Density Estimation with Gaussian Mixture Models - Gaussian Mixture Model, Parameter
Learning via Maximum Likelihood, EM Algorithm.

Classification with Support Vector Machines - Separating Hyperplanes, Primal Support

Vector Machine, Dual Support Vector Machine, Kernels.

Text book:

1.Mathematics for Machine Learning by Marc Peter Deisenroth, A. Aldo Faisal, and
Cheng Soon Ong published by Cambridge University Press (freely available at https://
mml - book.github.io)

Reference books:

1. Linear Algebra and Its Applications, 4th Edition by Gilbert Strang

2. Linear Algebra Done Right by Axler, Sheldon, 2015 published by Springer

3. Introduction to Applied Linear Algebra by Stephen Boyd and Lieven Vandenberghe,

2018 published by Cambridge University Press

4. Convex Optimization by Stephen Boyd and Lieven Vandenberghe, 2004 published by

Cambridge University Press

5. Pattern Recognition and Machine Learning by Christopher M Bishop, 2006, published

by Springer

6. Learning with Kernels – Support Vector Machines, Regularization, Optimization, and

Beyond by Bernhard Scholkopf and Smola, Alexander J Smola, 2002, bublished by
MIT Press

7. Information Theory, Inference, and Learning Algorithms by David J. C MacKay, 2003

published by Cambridge University Press

8. Machine Learning: A Probabilistic Perspective by Kevin P Murphy, 2012 published by

MIT Press.

9. The Nature of Statistical Learning Theory by Vladimir N Vapnik, 2000, published by

Springer
COMPUTER SCIENCE AND ENGINEERING
Sample
Sample Course
Course LevelLevel Assessment
Assessment Questions.
Questions.
Sample
Sample
Sample Course
Course
Course Level Level
Level Assessment
Assessment
Assessment Questions.
Questions.
Questions.
Course
Course Outcome
Outcome 1 (CO1):
1 (CO1):
Course
Course
Course Outcome
Outcome
Outcome 1 (CO1):
1 (CO1):
1 (CO1):
1. Find the set S of all solutions in x of the following inhomogeneous linear systems Ax = b
1. Find the set S of all solutions in x of the following inhomogeneous linear systems Ax
1.
1. 1. Find
FindFind theASset
the the
whereset set
ofSSall
and of
bof all
all solutions
solutions
solutions
are defined in
inofxxthe
inasxfollows: of following
of the following
the following inhomogeneous
inhomogeneous
inhomogeneous linear
linear
linear systems
systems
systems Ax
b == bb
Ax =Ax
=where
b,
where Awhere
where AAand
and Aare
bandand b are
bbdefined
are
are defined
defined
defined as follows:
asfollows:
as follows:
as follows:

2. Determine the inverses of the following matrix if possible

2. Determine the inverses of the following matrix if possible
2.
2. 2. Determine
Determine
Determine theinverses
the inverses
the inverses offollowing
of
of the thefollowing
the following matrix
matrix
matrix ififpossible
possible
if possible

3. Are the following sets of vectors linearly independent?

3.
3. 3.3.
Are Are
Are
the
Are the
the following
following
following
the sets
following sets
sets
of
sets of
of vectors
vectors
vectors
of linearly
linearly
linearly
vectors independent?
independent?
independent?
linearly independent?

4. 4.A set
A set
of of n linearly
n linearly independent
independent vectors
vectors in R inn R n
formsforms a basis.
a basis. Does
Does thethe
set set of vectors
of vectors (2, (2, 4,−3) ,
n
4. 4.4.
A setA set
A(0,
set1,
of of n linearly
noflinearly
1)n, linearly independent
independent
independent
(0, 1,−1) vectors
vectors
vectors
form a basis 3 in R forms a basis. Does the set of vectors (2, 4,−3) ,
n n
forinRR?inExplain
R3 forms
forms a basis.
a your
basis. DoesDoes
reasons. the of
the set setvectors
of vectors (2, 4,−3)
(2, 4,−3) , ,
4,−3) , (0, 1, 1) , (0, 1,−1) form a basis for R ? Explain your reasons.
(0, 1, (0,
(0,1)1,1, 1),1,−1)
, 1)
(0, ,(0,
(0,1,−1)
1,−1) form
formform aabasis
a basisbasis
for R for
3
for?R R33??Explain
ExplainExplainyouryour your reasons.
reasons.
reasons.
5. 5.Consider the transformation T (x, y) = (x +
Consider the transformation T (x, y) = (x + y, x + 2y, 2x y, x + 2y, 2x + 3y). Obtain
+ 3y). kerker
Obtain T and useuse this to
T and
5. 5.5. this
Consider
Consider
Consider the
the
to calculate
calculate transformation
the transformation
thetransformation
the nullity.
nullity. Also (x,TTy)
TAlso
find (x,
(x,=y)
find
the y)
(x ==+(x
the (x
y, +x+ y,+y, x2y,
transformation
transformation x ++2x2y,+2x
2y,
matrix 2x
3y).+ 3y).
+for
matrix 3y). Obtain
Obtain
T. Tker
T. ker ker
forObtain TT and
and and use
use use this
this this to
to to
calculate
calculate
calculate thenullity.
nullity.
the nullity.
the Also
AlsoAlso find
findfind thetransformation
transformation
the transformation
the matrix matrix
for T.
matrix forT.
for T.

6. 6.Find
Find
the the characteristic
characteristic equation,
equation, eigenvalues,
eigenvalues, and eigenspaces
and eigenspaces corresponding
corresponding to each to each
6. 6.6. Find
Find Find the
the the
eigenvalue characteristic
characteristic equation,
equation,
characteristic eigenvalues,
eigenvalues,
equation,
of the following matrix and
and and
eigenvalues, eigenspaces
eigenspaces corresponding
corresponding
eigenspaces to each
to each
corresponding to each
eigenvalue of the following matrix
eigenvalue
eigenvalue offollowing
of the
eigenvalue of thefollowing
the following matrix
matrix
matrix

"
7. Diagonalize the following matrix, if possible
7. 7.7. Diagonalize
Diagonalize thefollowing
following
the following
Diagonalize the matrix,
matrix, ififpossible
possible
if possible
matrix,
COMPUTER SCIENCE AND ENGINEERING
7. Diagonalize the following matrix, if possible

8. Find the singular value decomposition (SVD) of the following matrix

8. 8.Find the singular

Find the value
singular value decomposition
decomposition (SVD) (SVD)
of the of the following
following matrixmatrix

"

Course Outcome 2 (CO2):

Course
Course Outcome
Outcome 2 (CO2):
2 (CO2):

1. 1. For
Fora scalar
a scalar function
function f(x,f(x, x2 +3y
y, zy,) z=) x=2 +3y
2
2 +2z+2z
2
, find
2, find the the gradient
gradient andand its magnitude
its magnitude at at the
1.thepoint
For
(1, 2, -1).
a scalar
point function f(x, y, z ) = x2 +3y2 +2z2, find the gradient and its magnitude at the
(1, 2, -1).
pointthe
2. 2. Find
Find (1, maximum
2, -1). andminimum
minimumvalues
values of
of the
the function f(x, y) 2 2
the maximum and y) == 4x
4x++4y4y- x- x-2 y- ysubject
2 to
2 2
the
Findcondition
2.subject to the
the x + y and
<=
condition
maximum x2 2.
+ y2 <= 2. values of the function f(x, y) = 4x + 4y - x 2 - y2 subject to
minimum
2 2
the condition
3. 3. Suppose x +trying
y <= 2. f(x, y) y)
= x2=+ x
2y2 + 2y2. Along
Supposeyou
youwere to to
were trying minimize
minimize f(x, + 2y + 2y2. what vector
Along what vector
3.should you
should
Suppose
travel
you from (5,(5,
travel
you werefrom
12)?
trying 12)?
to minimize f(x, y) = x2+ 2y + 2y2. Along what vector
4. should you travel from (5, 12)?
4. Find thethe
second order Taylor series expansion forfor
f(x, y) y)
= (x + y)
+ y)about (0 (0
, 0).
2 2
Find second order Taylor series expansion f(x, = (x about , 0).
5.
4.Find thethe
critical points
orderofTaylor
f(x, y)series
= x expansion
3xy+5x-2y+6y +8.y) = (x + y)2 about (0 , 0).
2– 2
Find second for f(x,
5. Find the critical points of f(x, y) = x2 – 3xy+5x-2y+6y2+8.
6. Compute the gradient of the Rectified Linear Unit (ReLU) function ReLU(z) =
5. Find the critical points of f(x, y) = x2 – 3xy+5x-2y+6y2+8.
6. Compute the gradient of the Rectified Linear Unit (ReLU) function ReLU(z) = max(0 , z).
max(0 , z).
7. 6.LetCompute
LL ==||Ax
the gradient of the Rectified Linear Unit (ReLU) function ReLU(z) = max(0 , z).
||Ax- b||
- b||2,22where
, whereAAisisa amatrix
matrixand
andx xand
andb bare
arevectors.
vectors.Derive
DerivedL
dLininterms
termsofof dx.
2
7. Let
7.dx.Let L = ||Ax - b||22, where A is a matrix and x and b are vectors. Derive dL in terms of dx.
Course Outcome 3 (CO3):
Course Outcome 3 (CO3):
1. Let J and T be independent events, where P(J)=0.4 and P(T)=0.7.
i. Find P(J∩T)
1. Let J and T be independent events, where P(J)=0.4 and P(T)=0.7.
ii. Find P(J∪T)
i. Find P(J∩T)
iii. Find P(J∩T′)
ii. Find P(J∪T)
iii. Find P(J∩T′)
COMPUTER SCIENCE AND ENGINEERING
Course Outcome 3 (CO3):

1. Let J and T be independent events, where P(J)=0.4 and P(T)=0.7.

i. Find P(J∩T)

ii. Find P(J∪T)

iii. Find P(J∩T′)

2. Let A and B be events such that P(A)=0.45 , P(B)=0.35 and P(A∪B)=0.5. Find
P(A∣B).
2. Let A and B be events such that P(A)=0.45 , P(B)=0.35 and P(A∪B)=0.5. Find P(A∣B).
3. A random variable R has the probability distribution as shown in the following table:
3. A random variable R has the probability distribution as shown in the following table:

i.
i. Given that E(R)=2.85, find a and b.
i. Given
ii. that E(R)=2.85,
Find P(R>2). find a and b.
ii. Find P(R>2).
4. A biased coin (with probability of obtaining a head equal to p > 0) is tossed repeatedly and
4. A biasedindependently
coin (with probability
until the of obtaining
first head isaobserved.
head equalCompute
to p > 0)the
is tossed repeatedly
probability that the first head
and independently
appears at anuntil
eventhenumbered
first headtoss.
is observed. Compute the probability that the
first head appears at an even numbered toss.
5. Two players A and B are competing at a trivia quiz game involving a series of questions. On
5. Two players A and B question,
are competing at a triviathat
quiz game involving a series of are p and q
any individual the probabilities A and B give the correct answer
questions. On any individual
respectively, question,with
for all questions, the outcomes
probabilities
for that A andquestions
different B give the correct
being independent. The
answer gameare p finishes
and q respectively,
when a player for wins
all questions, with outcomes
by answering a questionforcorrectly.
differentCompute the
questions being independent.
probability that A winsThe if game finishes when a player wins by answering a
i. A answers
question correctly. Compute thethe
first question, that A wins if
probability
ii. B answers the first question.
i. A answers the first question,
6. A coin for which P(heads) = p is tossed until two successive tails are obtained. Find the
ii. Bprobability
answers the first
that thequestion.
experiment is completed on the nth toss.
6. A coin for which P(heads) = p is tossed until two successive tails are obtained. Find
7. You roll a fair dice twice. Let the random variable X be the product of the outcomes of the
the probability that the experiment is completed on the nth toss.
two rolls. What is the probability mass function of X? What are the expected value and the
7. You rollstandard
a fair dice twice. Let the random variable X be the product of the outcomes of
deviation of X?
the two rolls. What is the probability mass function of X? What are the expected value
and 8. While watching
the standard deviationaofgameX? of Cricket, you observe someone who is clearly supporting
Mumbai Indians. What is the probability that they were actually born within 25KM of
Mumbai? Assume that:
• the probability that a randomly selected person is born within 25KM of Mumbai is
1/20;
• the chance that a person born within 25KMs of Mumbai actually supports MI is
7/10 ;
• the probability that a person not born within 25KM of Mumbai supports MI with
probability 1/10.

9. What is an exponential family? Why are exponential families useful?

COMPUTER SCIENCE AND ENGINEERING
8. While watching a game of Cricket, you observe someone who is clearly supporting
Mumbai Indians. What is the probability that they were actually born within 25KM of
Mumbai? Assume that:
• the probability that a randomly selected person is born within 25KM of
Mumbai is 1/20;
• the chance that a person born within 25KMs of Mumbai actually supports MI
is 7/10 ;
• the probability that a person not born within 25KM of Mumbai supports MI
with probability 1/10.
9. What is an exponential family? Why are exponential families useful?
10. Let Z1 and Z2 be independent random variables each having the standard normal
distribution. Define the random variables X and Y by X = Z1 + 3Z2 and Y = Z1 + Z2.
Argue that the joint distribution of (X, Y) is a bivariate normal distribution. What are
the parameters of this distribution?
11. Given a continuous random variable x, with cumulative distribution function Fx(x),
show that the random variable y = Fx(x) is uniformly distributed.
12. Explain Normal distribution, Binomial distribution and Poisson distribution in the
exponential family form.

Course Outcome 4(CO4):

1. Find the extrema of f(x, y) = x subject to g(x, y) = x2 + 2y2 = 3.

2. Maximize the function f(x, y, z) = xy + yz + xz on the unit sphere g(x, y, z) = x2 + y2 +
z2 = 1.
3. Provide necessary and suffcient conditions under which a quadratic optimization
problem be written as a linear least squares problem.
4. Consider the univariate function f(x) = x3 + 6x2 - 3x - 5. Find its stationary points and
indicate whether they are maximum, minimum, or saddle points.
5. Consider the update equation for stochastic gradient descent. Write down the update
when we use a mini-batch size of one.
indicate whether
indicate whether they
they are
are maximum,
maximum, minimum,
minimum, or
or saddle
saddle points.
points.

5. Consider
5. Consider the
the update
update equation
equation for
for stochastic
stochastic gradient
gradient descent.
descent. Write
Write down
down the
the update
update when
when
we use
we use aa mini-batch
mini-batch size
size of
of one.
one.
COMPUTER SCIENCE AND ENGINEERING
6. Consider
6.
6. Consider the
Consider the function
the function
function

"

i. Is f(x) a convex function? Justify your answer.

i.i. Is f(x)
Is f(x) aa convex
convex function?
function? Justify
Justify your
your answer.
answer.
ii.
ii. Is (1
Is (1 ,, -1)
-1) aa local/global
local/global minimum?
minimum? Justify
Justify your
your answer.
answer.
2 2
7. Is the
7. Is the function
function f(x,
f(x, y)
y) == 2x
2x22++yy22++6xy
6xy--xx++3y
3y- -77convex,
convex,concave,
concave,ororneither?
neither?Justify
Justify your
your
answer.answer.
8.
8. Consider
Consider the
the following
following convex
convex optimization
optimization problem
problem

"

Subject to the constraint x + y >= 4, x, y >= 1.

Subject to the constraint x + y >= 4, x, y >= 1.
Derive an
Derive an explicit
explicit form
form of
of the
the Lagrangian
Lagrangian dual
dual problem.
problem.

9. 9.
Solve the following
Solve LP problem
the following withwith
LP problem the simplex method.
the simplex method.
9. Solve the following LP problem with the simplex method.

"
subject
subject to toto constraints
the the constraints
subject the constraints

Course
Course Outcome
Outcome 5 (CO5):
5 (CO5):
Course Outcome 5 (CO5):
1. What is a loss function? Give examples.
1. What is a loss function? Give examples.
2.1. What is
area loss
training/validation/test sets? What is cross-validation? Name one or two
function? Give examples.
2. What areoftraining/validation/test
examples sets? What is cross-validation? Name one or two examples
cross-validation methods.
2. What are training/validation/test sets? What is cross-validation? Name one or two examples
of cross-validation methods.
3. of cross-validation
Explain methods.
generalization, overfitting, model selection, kernel trick, Bayesian learning
3. Explain generalization, overfitting, model selection, kernel trick, Bayesian learning
3. Explain generalization, overfitting, model selection, kernel trick, Bayesian learning
4. Distinguish between Maximum Likelihood Estimation (MLE) and Maximum A Posteriori
4. Distinguish between Maximum Likelihood Estimation (MLE) and Maximum A Posteriori
Estimation (MAP)?
Estimation (MAP)?
5. What is the link between structural risk minimization and regularization?
5. What is the link between structural risk minimization and regularization?
6. What is a kernel? What is a dot product? Give examples of kernels that are valid dot
6. What is a kernel? What is a dot product? Give examples of kernels that are valid dot
products.
products.
Course Outcome 5 (CO5):

1. What is a loss function? Give examples.COMPUTER SCIENCE AND ENGINEERING

4.2. Distinguish
What are training/validation/test
between Maximum sets? What isEstimation
Likelihood cross-validation?
(MLE) Name one or two A
and Maximum examples
of cross-validation
Posteriori Estimationmethods.
(MAP)?
5.3. What
Explain generalization,
is the link between overfitting, model
structural risk selection, and
minimization kernel trick, Bayesian learning
regularization?
6.4. What
Distinguish between
is a kernel? WhatMaximum Likelihood
is a dot product? GiveEstimation
examples (MLE) andthat
of kernels Maximum
are validAdot
Posteriori
Estimation (MAP)?
products.
7.5. What
Whatisisridge
the link between How
regression? structural risktrain
can one minimization and regularization?
a ridge regression linear model?
8.6. What
What isis Principal
a kernel?Component
What is a Analysis
dot product?
(PCA)?GiveWhich
examples
eigenof value
kernels that arethevalid dot
indicates
products.of largest variance? In what sense is the representation obtained from a
direction
7. projection
What is ridge ontoregression?
the eigenHow can onecorresponding
directions train a ridge regression
the the linear
largestmodel?
eigen values
optimal for data reconstruction?
8. What is Principal Component Analysis (PCA)? Which eigen value indicates the direction of
largest variance?
9. Suppose that you In what
have sense is
a linear the representation
support vector machine obtained
(SVM) from a projection
binary classifier.onto the
eigen directions
Consider a pointcorresponding the the
that is currently largest eigen
classified valuesand
correctly, optimal
is farforaway
data reconstruction?
from the
9. decision
Supposeboundary. If you
that you have remove
a linear the point
support vectorfrom the training
machine (SVM) set, andclassifier.
binary re-train the
Consider a
classifier, will the decision boundary change or stay the same? Explain your answer
point that is currently classified correctly, and is far away from the decision boundary. If you
inremove
one sentence.
the point from the training set, and re-train the classifier, will the decision boundary
change or stay the same? Explain your answer in one sentence.
10. Suppose you have n independent and identically distributed (i.i.d) sample data points
10. xSuppose
1, ... , xnyou havedata
. These n independent
points come andfrom
identically distributed
a distribution (i.i.d)
where thesample of a x1, ... ,
data points
probability
xn. These
given data points
datapoint x is come from a distribution where the probability of a given datapoint x is

"

Prove that the MLE estimate of parameter is the sample mean.

11. Suppose the data set y1,...,yn is a drawn from a random sample consisting of i.i.d.
discrete uniform distributions with range 1 to N. Find the maximum likelihood
estimate of N.
12. Ram has two coins: one fair coin and one biased coin which lands heads with
probability 3/4. He picks one coin at random (50-50) and flips it repeatedly until he
gets a tails. Given that he observes 3 heads before the first tails, find the posterior
probability that he picked each coin.

i. What are the prior and posterior odds for the fair coin?

ii. What are the prior and posterior predictive probabilities of heads on the next
flip? Here prior predictive means prior to considering the data of the first four
flips.
uniform distributions with range 1 to N. Find the maximum likelihood estimate of N.
12. Ram has two coins: one fair coin and one biased coin which lands heads with probability
3/4. He picks one coin at random (50-50) and flips it repeatedly until he gets a tails. Given
that he observes 3 heads before the first tails, find the posterior probability that he picked
COMPUTER SCIENCE AND ENGINEERING
each coin.
i. What are the prior and posterior odds for the fair coin?
ii. What are the prior and posterior predictive probabilities of heads on the next flip?
Here prior predictiveModel
means Question paper the data of the first four flips.
prior to considering
QP Code : Total Pages: 4
Reg No.:_______________ Name:__________________________
Model Question paper
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
IV SEMESTER
QP Code : B.TECH (MINOR) DEGREE EXAMINATION, MONTH andPages:
Total YEAR4
Reg No.:_______________ Name:__________________________
Course Code: CST 284
APJ
Course ABDUL
Name: KALAM TECHNOLOGICAL
MATHEMATICS FOR MACHINE UNIVERSITY
LEARNING
IV SEMESTER B.TECH (HONOURS) DEGREE EXAMINATION, MONTH and YEAR
Max. Marks: 100 Duration: 3 Hours
Course Code: CST 274
Course Name: COMPUTATIONAL FUNDAMENTALS PART A FOR MACHINE LEARNING
Max. Marks: 100 Answer all questions, each carries 3 marks. Marks
Duration: 3 Hours
PART A
1 Show that withAnswer
the usual operation each
all questions, of scalar multiplication
carries 3 marks. but with Marks
1 Show that on
addition with the given
reals usual by
operation
x # y = of
2(xscalar
+ y) ismultiplication but with addition on
not a vector space.
reals given by x # y = 2(x + y) is not a vector space.
2 Find the eigenvalues of the following matrix in terms of k. Can you find
2 Find the eigenvalues of the following matrix in terms of k. Can you find an
an eigenvector corresponding to each of the eigenvalues?
eigenvector corresponding to each of the eigenvalues?

3 Let f(x, y, z) = xyer, where r = x2+z2-5. Calculate the gradient of f at the

3 Let f(x, y, z) = xyer, where r = x2+z2-5. Calculate the gradient of f at the point
(1,point
3, -2).(1, 3, -2).
4 Compute the Taylor polynomials Tn, n = 0 , ... , 5 of f(x) = sin(x) + cos(x) at
4 x0 Compute
= 0. the Taylor polynomials Tn, n = 0 , ... , 5 of f(x) = sin(x) + cos(x)
5 LetatXxbe a continuous random variable with probability density function on
0 = 0.
0 <= x <= 1 defined by f(x) = 3x2. Find the pdf of Y = X2.
65 Let that
Show X beifatwocontinuous
events A random variable
and B are with probability
independent, then A anddensity function
B' are independent.
7 Explain the principle of the gradient descent algorithm.
on 0 <= x <= 1 defined by f(x) = 3x2. Find the pdf of Y = X2.
6 Show that if two events A and B are independent, then A and B' are
independent.
7 Explain the principle of the gradient descent algorithm.
COMPUTER SCIENCE AND ENGINEERING
8 Briey explain the difference between (batch) gradient descent and
stochastic gradient descent. Give an example of when you might prefer

8
one over the other.
Briey explain the difference between (batch) gradient descent and stochastic
8 Briey explain the difference between (batch) gradient descent and stochastic
9 What isdescent.
gradient the empirical
Give an risk? What of
example is “empirical risk minimization”?
when you might prefer one over the other.
910gradient descent.
What Give
is thethe an
empirical example
risk? of
Whatwhen you might
is “empirical prefer
risk one over the other.
minimization”?
9 What is Explain
the empirical concept
risk? of ais
What Kernel function
“empirical risk in Support
minimization”? Vector Machines.
10 Explain the concept of a Kernel function in Support Vector Machines. Why are
10 Explain Why
the concept of aso
are kernels Kernel
useful?function in Supporta Vector
What properties kernel Machines. Why
should posses to are
be
kernels so useful? What properties a kernel should posses to be used in an SVM?
kernels so
useduseful?
in an What
SVM?properties a kernel should posses to be used in an SVM?
PART B
PART
Answer any one Question from each B module. Each question carries 14 Marks
11 a)Answer i. any one
Find allQuestion
solutionsfrom PART
to theeach B linear
module.
system of Each question carries 14 Marks
equations (6)
11 a) i. Answer
Find all any
solutions to the system of linear equations
one Question from each module. Each question carries 14 Marks (6)

11 a) i. Find all solutions to the system of linear equations (6)

ii. Prove that" all

ii. Prove that all
ii.vectors
Prove orthogonal −3, 1]T forms
to [2,orthogonal
that all vectors to a −3,
[2, subspace
1] T forms
3
W ofaRsubspace
. What is dim
T 3
vectors(W)
orthogonal
and why?
to [2, −3, 1] forms a subspace W of R . What is dim
W of R3. What is dim (W) and why?
(W) and why?
b) Use Usethethe
Gramm-Schmidt
Gramm-Schmidt process to find
process an orthogonal
to find basis for
an orthogonal the for
basis column
the space
(8) (8)
b) Use theofGramm-Schmidt
the following process
matrix to find an orthogonal basis for the column space (8)
column space of the following matrix
of the following matrix

"
OR
12 a) i. Let L be the line through the OR 2
ORorigin in R that is parallel to the vector (6)
12 a) i. Let L be 4]Tline
[3,the . Find the standard
through matrix
the origin in Rof
2 the orthogonal projection onto L. Also
that is parallel to the vector (6)
T
[3, 4] find
. Find
thethe standard
point matrixisofclosest
on L which the orthogonal projection
to the point onto
(7 , 1) and findL.the
Also
point on
find theL point
whichonis Lclosest
whichtoisthe
closest
pointto(-3
the, 5).
point (7 , 1) and find the point on
ii. Find
L which the rank-1
is closest approximation
to the point (-3 , 5).of
ii. Find the rank-1 approximation of

b) i. Find an orthonormal basis of R3 consisting of eigenvectors for the (8)

b) i. Find an orthonormal basis of R3 consisting of eigenvectors for the (8)
COMPUTER SCIENCE AND ENGINEERING
12 a) i. Let L be the line through the origin in R2 that is parallel to the (6)
vector OR
12 a) i. Let L be the line through the origin in R2 that is parallel to the vector (6)
[3,4]4]T.T.Find
[3, Findthe
thestandard
standardmatrix
matrixofofthe
theorthogonal
orthogonalprojection
projectiononto
ontoL. Also
L. Also
find find the
the point on Lpoint
whichonisL closest
which is
to closest to (7
the point the, 1)
point
and(7find
, 1)the
and
point on
Lfind
which
theispoint
closest to which
on L the point (-3 , 5).to the point (-3 , 5).
is closest
ii. Find the rank-1 approximation of
ii. Find the rank-1 approximation of

"

b) i. Find an orthonormal basis of R3 consisting of eigenvectors for the (8)

following matrix
b) following
i. Find matrix
an orthonormal basis of R3 consisting of eigenvectors for the (8)

ii. Find a 3 × 3 orthogonal "

ii. Find
matrix S anda a33××33orthogonal matrix
diagonal matrix D Ssuch
andthat
a 3A×=3SDS
diagonal
T
. matrix D
such that A = SDST .
13 a) A skier is on a mountain with equation z = 100 – 0.4x2 – 0.3y2, where z denotes (8)
13 height.
a) A skier is on a mountain with equation z = 100 – 0.4x2 – 0.3y2, where z (8)
denotes height.
i. The skier is located at the point with xy-coordinates (1 , 1), and wants to
skii.downhill along
The skier is the steepest
located at thepossible path. xy-coordinates
point with In which direction(1 ,(indicated
1), and
by a vector (a , b) in the xy-plane) should the skier begin
wants to ski downhill along the steepest possible path. In whichskiing.
direction (indicated by a vector (a , b) in the xy-plane) should the
ii. The skier begins skiing in the direction given by the xy-vector (a , b) you
found skier begin
in part (i), skiing.
so the skier heads in a direction in space given by the
vector (a , b , c). Find the value of c.
ii. The skier begins skiing in the direction given by the xy-vector (a ,
b) b) linear
Find the you found in part (i),tosothe
approximation thefunction
skier heads
f(x,y)in=a2direction
- sin(-x -in3y)space
at the (6)
given
point (0 , π),by
andthethen
vector
use (a , b answer
your , c). Find
to the value f(0.001
estimate of c. , π).
b) Find the linear approximation to the function f(x,y) = 2 - sin(-x - (6)
3y) at the point (0 , π),OR
and then use your answer to estimate
14 a) Let g be the function given by (8)
f(0.001 , π).

OR
OR
14 a) Let g be the function given by (8)

COMPUTER SCIENCE AND ENGINEERING

14 a) Let g be the function given by (8)

"
i. Calculate the partial derivatives of g at (0 , 0).
i. Calculate the partial derivatives of g at (0 , 0).
ii.
ii. Show
Showthatthatggisisnot
notdifferentiable
differentiableatat(0
(0,,0).
0).
b) Find the second order Taylor series expansion for f(x,y) = e-(x2+y2) cos(xy) about (0 , (6)
b) Find the second order Taylor series expansion for f(x,y) = e-(x2+y2) cos(xy) (6)
0).
aboutare
15 a) There (0 ,two
0). bags. The first bag contains four mangos and two apples; the second (6)
15 a) There
bag are twofour
contains bags. The first
mangos andbag
fourcontains
apples. four mangos
We also haveand two apples;
a biased (6)
coin, which
the second
shows bagwith
“heads” contains four mangos
probability 0.6 andand fourwith
“tails” apples. We also0.4.
probability haveIf athe coin
biased coin, which shows “heads” with probability 0.6 and “tails” with
probability 0.4. If the coin shows “heads”. we pick a fruit at

showsrandom
“heads”.from bag 1;
we pick otherwise
a fruit at we pick a fruit at random from bag 2. Your
random fromflips
friend bag the
1; otherwise
coin (youwe pick see
cannot a fruit
theatresult),
random froma bag
picks fruit2.atYour friend
random
flips the coin (you cannot see the result), picks a fruit at random from the
from the corresponding bag, and presents you a mango.
corresponding bag, and presents you a mango.
What What
is the is the probability
probability that
that the the mango
mango was picked
was picked from2?bag 2?
from bag
b) b)
Suppose that one
Suppose thathasone
written
has awritten
computer program that
a computer sometimes
program compiles and (8)(8)
that sometimes
sometimes notand
compiles (code does not
sometimes change).
not (code doesYou decide toYou
not change). model
decidethe apparent
to model
stochasticity (success vs. no success) x of the compiler using a Bernoulli
the apparent stochasticity (success vs. no success) x of the compiler using
distribution with parameter μ:
a Bernoulli distribution with parameter μ:

"
Choose a conjugate prior for the Bernoulli likelihood and compute the posterior
Choose a conjugate prior for the Bernoulli likelihood and compute the
distribution p( μ | x1 , ... , xN).
posterior distribution p( μ | x1 , ... OR
, xN).

OR
16 a) Consider a mixture of two Gaussian distributions (8)

i. Compute the marginal distributions for each dimension.

ii. Compute the mean, mode and median for each marginal distribution.
iii. Compute the mean and mode for the two-dimensional distribution.

b) Express the Binomial distribution as an exponential family distribution. Also (6)

express the Beta distribution is an exponential family distribution. Show that the
Choose a conjugate
distribution prior μ:
with parameter for the Bernoulli likelihood and compute the posterior
distribution p( μ | x1 , ... , xN).
OR
COMPUTER SCIENCE AND ENGINEERING
Choose a conjugate prior for the Bernoulli likelihood and compute the posterior
16 a) Consider a mixture of two Gaussian distributions (8)
16 a) Consider a mixture of two Gaussian distributions (8)
distribution p( μ | x1 , ... , xN).
OR

16 a) Consider a mixture of two Gaussian distributions (8)

"

i. i.Compute
Compute the the marginal
marginal distributions
distributions for for
eacheach dimension.
dimension.
ii. ii.
Compute
Compute the mean, mode and
the mean, modemedian
andformedian
each marginal
for eachdistribution.
marginal
iii. Compute the mean and mode for the two-dimensional distribution.
distribution.
i. Compute
b) Express the marginal distributions for each dimension.
iii.the Binomial
Compute the distribution
mean and mode as an
for exponential family distribution.
the two-dimensional distribution. Also (6)
ii. Compute the mean, mode and median for each marginal distribution.
express the Betathedistribution
iii. Compute mean and mode is an for
exponential family distribution.
the two-dimensional Show that the
distribution.
product of the Beta and the Binomial distribution is also a member of the
b) b)Express
Express the Binomial
the Binomial distribution
distribution as anas exponential
an exponential family
family distribution.
distribution. Also (6)(6)
exponential family.
FindAlso
17 a) express the express
theextrema thef(x,y,z)
of Beta distribution
Beta distribution =isxan is an exponential
- yexponential
+ z subject family =family
x2 + y2 distribution.
distribution.
to g(x,y,z) +Show that the
z2 = 2. (8)
b) product
Let Show of that
the the
Betaproduct
and theof the Beta and
Binomial the Binomial
distribution distribution
is also a member is also
of athe (6)

exponential
memberfamily.
of the exponential family.
17 a) Find the extrema of f(x,y,z) = x - y + z subject to g(x,y,z) = x2 + y2 + z2 = 2. (8)
17b) a)Let Find the extrema of f(x,y,z) = x - y + z subject to g(x,y,z) = x2 + y2 + z2 = (8)(6)
2.
b) Let

Show
" that x* = (1 , 1/2 , -1) is optimal for the optimization problem
Show that x* = (1 , 1/2 , -1) is optimal for the optimization problem

(6)
OR
18 a) Derive the gradient descent trainingOR
rule assuming that the target function (8)
18 a) Derive the gradient descent training rule assuming that the target function is (8)
is represented as od = w0 + w1x1 + ... + wnxn. Define explicitly the cost/
represented as od = w0 + w1x1 + ... + wnxn. Define explicitly the cost/error function
error function E, assuming that a set of training examples D is provided,
E, assuming that a set of training examples D is provided, where each training
where each training example d ∈ D is associated with the target output td.
example d ∈ D is associated with the target output td.

b) Find the maximum value of f(x,y,z) = xyz given that g(x,y,z) = x + y + z = 3 and (6)
x,y,z >= 0.
19 a) Consider the following probability distribution (7)
18 a) Derive the gradient
represented as od = wdescent
0 + w1x1 training
+ ... + wnrule assuming
xn. Define that the
explicitly target function
the cost/error is (8)
function
represented od =a wset
E, assumingasthat 0 +of
w1training
x1 + ... +examples
wnxn. Define
D isexplicitly
provided,thewhere
cost/error
each function
training
E, assuming
example d ∈ that
D is aassociated
set of training examples
with the D is tprovided,
target output d. where each training
COMPUTER
example d ∈ D is associated with the target output td. SCIENCE AND ENGINEERING
b) Find the maximum value of f(x,y,z) = xyz given that g(x,y,z) = x + y + z = 3 and (6)
b) Find the maximum value of f(x,y,z) = xyz given that g(x,y,z) = x + y + z = (6)
b) Find
x,y,z the maximum value of f(x,y,z) = xyz given that g(x,y,z) = x + y + z = 3 and (6)
>= 0.
19 a) x,y,z 3
Considerand x,y,z >= 0.
>= 0.the following probability distribution (7)
19 19
a) a)Consider the following
Consider probability
the following distribution
probability distribution (7) (7)

where θ is a parameter and x is a positive real number. Suppose you get m i.i.d.
where
where
samples is a parameter
θ isxi aθdrawn
parameter and
andthis
from xaispositive
a positive
x isdistribution. real
real number.
number.
Compute Suppose
Suppose
the you
maximumyou getmmi.i.d.
get
likelihood
samples
i.i.d.xfor
estimator drawn
isamples xfrom
θ based thisfrom
drawn
i on these distribution. ComputeCompute
this distribution.
samples. the maximum likelihood
the maximum
estimator for θ based
likelihood on these
estimator for θsamples.
based on these samples.
b) b)Consider the following
Consider Bayesian
the following network
Bayesian with with
network boolean variables.
boolean variables. (7) (7)
b) Consider the following Bayesian network with boolean variables. (7)

i. List variable(s) conditionally independent of X33 given X11 and X12

ii. List variable(s) conditionally independent of X33 and X22
iii. Write the joint probability P(X11, X12, X13, X21, X22, X31, X32, X33)
factored according to the Bayes net. How many parameters are
necessary to define the conditional probability distributions for
this Bayesian network?
iv. Write an expression for P(X13 = 0,X22 = 1,X33 = 0) in terms of the
conditional probability distributions given in your answer to part
(iii). Justify your answer.

OR
Justify your answer.

OR
20 a) Consider the following one dimensional COMPUTER
training data set,SCIENCE
’x’ denotes AND
negative (6)
ENGINEERING
examples and ’o’ positive examples. The exact data points and their labels are
20 a) Consider the following one dimensional training data set, ’x’ denotes (6)
given in the table below. Suppose a SVM is used to classify this data.
negative examples and ’o’ positive examples. The exact data points and
their labels are given in the table below. Suppose a SVM is used to
classify this data.

"
i. Indicate which arewhich
i. Indicate the support vectors
are the andvectors
support mark theand
decision
mark boundary.
the decision
ii. Give the value of the cost function and the model parameter after training.
b) Supposeboundary.
that we are fitting a Gaussian mixture model for data items (8)
consisting of athe
ii. Give single
valuereal value,
of the costx,function
using K and
= 2 components. We haveafter
the model parameter N=
5 training cases, in which the values of x are as 5, 15, 25, 30, 40. Using the
training.
EM algorithm to find the maximum likeihood estimates for the model
parameters, what are the mixing proportions for the two components, π1
and π2, and the means for the two components, μ1 and μ2. The standard
deviations for the two components are fixed at 10.
COMPUTER SCIENCE AND ENGINEERING
b) Suppose that we are fitting a Gaussian mixture model for data (8)
items consisting of a single real value, x, using K = 2 components.
We have N = 5 training cases, in which the values of x are as 5,
15, 25, 30, 40. Using the EM algorithm to find the maximum
likeihood estimates for the model parameters, what are the mixing
proportions for the two components, π1 and π2, and the means for
the two components, µ1 and µ2. The standard deviations for the
two components are fixed at 10.
Suppose that at some point in the EM algorithm, the E step found
Suppose that at some point in the EM algorithm, the E step found that the
that the responsibilities of the two components for the five data
responsibilities of the two components for the five data items were as
items were as follows:
follows:

"
What values for the parameters π1, π2 , µ1, and µ2 will be found in
What
the nextvalues forofthe
M step algorithm?π1, π2 , μ1, and μ2 will be found in the next
theparameters
M step of the algorithm? ****
****
COMPUTER SCIENCE AND ENGINEERING

Teaching Plan
No. of
Lectures
No Topic
(45)

1 Module-I (LINEAR ALGEBRA) 8

1. Systems of Linear Equations – Matrices, Solving Systems of Linear
1
Equations. Vector Spaces - Linear Independence.
2. Vector Spaces - Basis and Rank 1
3. Linear Mappings 1

4. Norms, Inner Products, Lengths and Distances, Angles and

1
Orthogonality, Orthonormal Basis, Orthogonal Complement
5. Orthogonal Projections, Matrix Decompositions, Determinant and 1
Trace.
6. Eigenvalues and Eigenvectors 1

7. Cholesky Decomposition, Eigen decomposition and Diagonalization 1

8. Singular Value Decomposition - Matrix Approximation 1
Module-II (VECTOR CALCULUS) 6

1 Differentiation of Univariate Functions, Partial Differentiation and 1

Gradients

2 Gradients of Vector Valued Functions, Gradients of Matrices 1

3 Useful Identities for Computing Gradients 1

4 Backpropagation and Automatic Differentiation 1

5 Higher Order Derivatives 1

6 Linearization and Multivariate Taylor Series 1

3 Module-III (Probability and Distributions) 10

1 Construction of a Probability Space - Discrete and Continuous 1
Probabilities (Lecture 1)
COMPUTER SCIENCE AND ENGINEERING
2 Construction of a Probability Space - Discrete and Continuous 1
Probabilities (Lecture 2)
3 Sum Rule, Product Rule 1
4 Bayes’ Theorem 1
5 Summary Statistics and Independence 1
6 Important probability Distributions (Lecture 1) 1
7 Important probability Distributions (Lecture 2) 1
8 Conjugacy and the Exponential Family (Lecture 1) 1
9 Conjugacy and the Exponential Family (Lecture 2) 1
10 Change of Variables/Inverse Transform 1
4 Module-IV (Optimization) 7
1 Optimization Using Gradient Descent. 1
2 Gradient Descent With Momentum, Stochastic Gradient Descent 1
3 Constrained Optimization and Lagrange Multipliers (Lecture 1) 1
4 Constrained Optimization and Lagrange Multipliers (Lecture 2) 1
5 Convex Optimization 1
6. Linear Programming 1

7. Quadratic Programming 1
5 Module-V (CENTRAL MACHINE LEARNING PROBLEMS) 14

1. Data and Learning models - Empirical Risk Minimization, 1

2. Parameter Estimation 1

3. Directed Graphical Models 1

4. Linear Regression 1

5. Bayesian Linear Regression 1

6. Maximum Likelihood as Orthogonal Projection 1

7. Dimensionality Reduction with Principal Component Analysis - 1

Maximum Variance Perspective, Projection Perspective.
8. Eigenvector Computation and Low Rank Approximations 1

9. Density Estimation with Gaussian Mixture Models 1

COMPUTER SCIENCE AND ENGINEERING
10. Parameter Learning via Maximum Likelihood 1
11. EM Algorithm 1

12. Classification with Support Vector Machines - Separating 1

Hyperplanes
13. Primal Support Vector Machines, Dual Support Vector Machines 1

14. Kernels 1

*Assignments may include applications of the above theory. With respect to module V,
programming assignments may be given.
COMPUTER SCIENCE AND ENGINEERING

INTRODUCTION TO Year of
CST Category L T P Credit
COMPUTER Introduction
286
NETWORKS MINOR 3 1 0 4 2019

Preamble: This is the second course for awarding B. Tech. Minor in Computer Science and
Engineering with specialization in Networking. Study of this course provides the learners a
clear understanding of how computer networks from local area networks to the massive and
global Internet are built and how they allow the usage of computers to share information and
communicate with one another. This course covers the layers of OSI Reference models and
inter-networking. This course helps the learners to compare and analyze the existing network
technologies and to choose a suitable network design for a given system.

Prerequisite: Data Communication (CST 255)

Course Outcomes: After the completion of the course the student will be able to

Explain the features of computer networks, protocols and network design

CO 1 models (Cognitive Knowledge : Understand)

Discuss the design issues of data link layer, data link layer protocols, bridges
CO 2 and switches (Cognitive Knowledge : Understand)

Illustrate wired LAN protocols (IEEE 802.3/4/5) and wireless LAN protocols
CO 3 (IEEE 802.11a/b/g/n, 802.15) (Cognitive Knowledge : Understand)

Select appropriate routing algorithms, congestion control techniques and

CO 4 Quality of Service requirements for a network (Cognitive Knowledge :
Apply)

Illustrate the functions and protocols of network layer, transport layer and
CO 5 application layer in inter-networking (Cognitive Knowledge : Understand)
COMPUTER SCIENCE AND ENGINEERING

Mapping of course outcomes with program outcomes

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12

CO1 ! ! ! !

CO2 ! ! ! ! !

CO3 ! ! ! ! !

CO4 ! ! ! !

CO5 ! ! ! ! ! !

Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics

PO3 Design/Development of solutions PO9 Individual and team work

Conduct investigations of complex

PO4 PO10 Communication
problems

PO5 Modern tool usage PO11 Project Management and Finance

PO6 The Engineer and Society PO12 Life long learning

Assessment Pattern
End Semester
Test 1 (Marks Test 2 (Marks
Bloom’s Category Examination (Marks in
in percentage) in percentage)
percentage)
Remember 40 30 30

Understand 60 50 50
Apply 20 20

Analyse
Evaluate

Create
COMPUTER SCIENCE AND ENGINEERING

Mark Distribution
Total Marks CIE Marks ESE Marks ESE Duration
150 50 100 3

Continuous Internal Evaluation Pattern:

Attendance : 10 marks
Continuous Assessment Test : 25 marks
Continuous Assessment Assignment : 15 marks

Internal Examination Pattern:

Each of the two internal examinations has to be conducted out of 50 marks. First series test shall
be preferably conducted after completing the first half of the syllabus and the second series test
shall be preferably conducted after completing remaining part of the syllabus. There will be two
parts: Part A and Part B. Part A contains 5 questions (preferably, 2 questions each from the
completed modules and 1 question from the partly completed module), having 3 marks for each
question adding up to 15 marks for part A. Students should answer all questions from Part A.
Part B contains 7 questions (preferably, 3 questions each from the completed modules and 1
question from the partly completed module), each with 7 marks. Out of the 7 questions, a
student should answer any 5.

End Semester Examination Pattern:

There will be two parts; Part A and Part B. Part A contains 10 questions with 2 questions from
each module, having 3 marks for each question. Students should answer all questions. Part B
contains 2 questions from each module of which a student should answer any one. Each
question can have maximum 2 sub-divisions and carries 14 marks.

Syllabus

Module 1

Introduction – Uses of Computer Networks, Network Hardware, Network Software, Reference

Models – The OSI Reference Model, The TCP/IP Reference Model, Comparison of OSI and
TCP/IP Reference models.
Module 2

The Data Link Layer - Data Link layer Design Issues, Error Detection and Correction,
Elementary Data Link Protocols, Sliding Window Protocols, HDLC (High-Level Data Link
Control) Protocol. The Medium Access Control (MAC) Sub layer – The Channel Allocation
Problem, Multiple Access Protocols, Ethernet, Wireless LANs - 802.11 a/b/g/n, Bridges &
Switches.
Module 3
COMPUTER SCIENCE AND ENGINEERING

Network Layer Design Issues. Routing Algorithms - The Optimality Principle, Shortest path
routing, Flooding, Distance Vector Routing, Link State Routing, Multicast Routing, Routing for
Mobile Hosts. Congestion Control Algorithms, Quality of Service (QoS) - Requirements,
Techniques for Achieving Good QoS.

Module 4

Network Layer in Internet – The IP Protocol, IP Addresses, Internet Control Message Protocol
(ICMP), Address Resolution Protocol (ARP), Reverse Address Resolution Protocol (RARP),
Bootstrap Protocol (BOOTP), Dynamic Host Configuration Protocol (DHCP). Open Shortest
Path First (OSPF) Protocol, Border Gateway Protocol (BGP), Internet Multicasting, IPv6,
ICMPv6.

Module 5

Transport Layer – The Transport Service – Services Provided to the Upper Layers, Transport
Service Primitives. The User Datagram Protocol (UDP), Transmission Control Protocol (TCP) –
Overview of TCP, TCP Segment Header, Connection Establishment & Release, Connection
Management Modeling, TCP Retransmission Policy, TCP Congestion Control.

Application Layer – File Transfer Protocol (FTP), Domain Name System (DNS), Electronic
mail, MIME, Simple Network Management Protocol (SNMP), World Wide Web – Architectural
Overview.

Text Book
Andrew S. Tanenbaum, Computer Networks, 4/e, PHI (Prentice Hall India).
Reference Books
1. Behrouz A Forouzan, Data Communication and Networking, 4/e, Tata McGraw Hill
2. Larry L Peterson and Bruce S Dave, Computer Networks – A Systems Approach, 5/e,
Morgan Kaufmann.
3. Fred Halsall, Computer Networking and the Internet, 5/e.
4. James F. Kurose, Keith W. Ross, Computer Networking: A Top-Down Approach, 6/e.
5. Keshav, An Engineering Approach to Computer Networks, Addison Wesley, 1998.
6. W. Richard Stevens. TCP/IP Illustrated volume 1, Addison-Wesley, 2005.
7. William Stallings, Computer Networking with Internet Protocols, Prentice-Hall, 2004.
8. Request for Comments (RFC) Pages - IETF -https://www.ietf.org/rfc.html

Sample Course Level Assessment Questions

CourseOutcome1 (CO1): Compare TCP/IP Reference model and OSI Reference model.
CourseOutcome2 (CO2): Distinguish between switches and bridges.
COMPUTER SCIENCE AND ENGINEERING

CourseOutcome3 (CO3): Draw and explain the frame format for Ethernet.
CourseOutcome5 (CO4): Discuss remedies for count to infinity problem in routing.
CourseOutcome4 (CO5): Subnet the Class C IP Address 206.16.2.0 so that you have 30
subnets. What is the subnet mask for the maximum number of hosts? How many hosts can
each subnet have?

Model Question Paper

QP CODE: PAGES: ___

Reg No:_______________
Name:_________________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

FOURTH SEMESTER B.TECH DEGREE (MINOR) EXAMINATION, MONTH &
YEAR

Course Code: CST 286

Course name : INTRODUCTION TO COMPUTER NETWORKS

Max Marks: 100 Duration: 3 Hours

PART-A

(Answer All Questions. Each question carries 3 marks)

1. Why Layered Architecture is used in Computer Networks? Define the terms protocol and
interface?
2. What are the different service primitives in Computer Networks?
3. Draw and explain Ethernet frame format.
4. What is the output string when the bit string 0111101111101111110 is subjected to bit
stuffing?
5. Discuss the count to infinity problem in routing.
6. What is flooding? Describe any two situations where flooding is advantageous.
7. What is IP (Internet Protocol) subnetting? Illustrate with example.
8. How many octets does the smallest possible IPv6 (IP version 6) datagram contain?
9. Can TCP (Transmission Control Protocol) be used directly over a network (e.g. an
Ethernet) without using IP? Justify your answer
10. What is the role of SNMP (Simple Network Management Protocol)?
(10x3=30)

Part B
COMPUTER SCIENCE AND ENGINEERING

(Answer any one Question from each module. Each question carries 14 Marks)

Module I

11. (a) With a neat diagram, explain the OSI (Open Systems Interconnection) reference
Model. (8)
(b) Compare OSI Reference model and the TCP/IP model (6)

OR
12. (a) Consider two networks providing reliable connection-oriented service. One of them
offers a reliable byte stream and the other offers a reliable message stream. Are they
identical? Justify your answer. (8)
(b) Compare LAN (Local Area Networks), MAN (Metropolitan Area Networks) and
WAN (Wide Area Networks). (6)

Module II

13. (a) Discuss the different strategies used to avoid collisions in CSMA/CA (Carrier Sense
Multiple Access/Collision Avoidance) . (8)
(b) Briefly explain the working of HDLC (High-Level Data Link Control). (6)

OR

14. (a) Explain the working of IEEE 802.11. (10)

(b) Distinguish between Bridges and Switches. (4)

Module III

15. (a) Illustrate Distance Vector Routing Algorithm with an example. (8)
(b) Explain the characteristics of RIP (Routing Information Protocol). (6)

OR

16. (a) Explain an Interior Gateway protocol that uses a link state algorithm to propagate
routing information. (6)
(b) Explain how routing is performed in a Mobile network. (8)

Module IV
COMPUTER SCIENCE AND ENGINEERING

17. (a) Explain address resolution problem and RARP (Reverse Address Resolution Protocol)
with an example network. (10)
(b) How IGMP (Internet Group Management Protocol) supports internet multicasting?
Explain. (4)

OR
18. (a) Subnet the class C IP address 195.1.1.0 so that you have 10 subnets with a maximum
of 12 hosts in each subnet. (6)
(b) Draw IPv6 Datagram format and explain its features (8)

Module V

19. (a) Distinguish between TCP and UDP (User Datagram Protocol) header formats. (8)
(b) Explain the principal DNS (Domain Name System) resource record types for IPv4. (6)
OR
20. (a) What is the role of SMTP (Simple Mail Transfer Protocol) in E-mail? (6)
(b) With the help of a basic model explain the working of WWW (World Wide Web). (8)

Teaching Plan

Module 1 (8 Hours)

1.1 Introduction – Uses of Computer Networks. 1

1.2 Network Hardware – Local Area Networks (LAN), 1

Metropolitan Area Networks (MAN), Wide Area Networks
(WAN).
1.3 Network Hardware – Wireless Networks, Home Networks, 1
Internetworks

1.4 Network Software –– Protocol Hierarchies. 1

1.5 Network Software –– Design issues for the layers. 1

1.6 Network Software – Connection Oriented and Connectionless 1

Services, Service Primitives, Relationship of Services to
Protocols.
1.7 Reference Models – The OSI Reference Model 1
COMPUTER SCIENCE AND ENGINEERING

1.8 Reference Models – The TCP/IP Reference Model, Comparison 1

of OSI and TCP/IP Reference models
Module 2 (11 Hours)

2.1 Data Link layer Design Issues. 1

2.2 Error Detection and Correction - Error Correcting Codes 1

2.3 Error Detection and Correction - Error Detecting Codes 1

2.4 Elementary Data link Protocols. 1

2.5 Sliding Window Protocols. 1

2.6 HDLC (High-Level Data Link Control) Protocol 1

2.7 The Medium Access Control (MAC) Sub layer – The Channel 1
Allocation Problem, Multiple Access Protocols.
2.8 Ethernet - Ethernet Cabling, Manchester Encoding, The 1
Ethernet MAC Sub layer Protocol, The Binary Exponential
Backoff Algorithm.
2.9 Ethernet - Ethernet Performance, Switched Ethernet, Fast 1
Ethernet, Gigabit Ethernet, IEEE 802.2: Logical Link Control.
2.10 Wireless LANs - 802.11 a/b/g/n. 1

2.11 Bridges & Switches. 1

Module 3 (9 Hours)

3.1 Network Layer Design Issues. 1

3.2 Routing Algorithms - The Optimality Principle, Shortest path 1

routing, Flooding.

3.3 Distance Vector Routing, Link State Routing. 1

3.4 Link State Routing. 1

3.5 Multicast Routing, Routing for Mobile Hosts 1

3.6 Distance Vector Routing, Link State Routing 1

COMPUTER SCIENCE AND ENGINEERING

3.7 Congestion control algorithms - General Principles of 1

Congestion Control, Congestion Prevention Policies,
Congestion Control in Virtual-Circuit Subnets
3.8 Congestion control algorithms - Congestion Control in 1
Datagram Subnets, Load Shedding, Jitter Control
3.9 Quality of Service – Requirements, Techniques for Achieving 1
Good Quality of Service.

Module 4 (9 Hours)

4.1 Network layer in internet, IP Protocol 1

4.2 IP Addresses – Subnets, Classless Inter Domain Routing 1

(CIDR)

4.3 IP Addresses - Network Address Translation (NAT) 1

4.4 Internet Control Message Protocol (ICMP), Address Resolution 1

Protocol (ARP), Reverse Address Resolution Protocol (RARP),
4.5 Bootstrap Protocol (BOOTP), Dynamic Host Configuration 1
Protocol (DHCP)
4.6 Open Shortest Path First (OSPF) Protocol 1

4.7 Border Gateway Protocol (BGP) 1

4.8 Internet Multicasing. 1

4.9 IPv6, Internet Control Message Protocol version 6 (ICMPv6). 1

Module 5 (8 Hours)

5.1 The Transport Service – Services Provided to the Upper Layers, 1

Transport Service Primitives. The User Datagram Protocol
(UDP)

5.2 Transmission Control Protocol (TCP) – Overview of TCP, TCP 1

Segment Header, Connection Establishment & Release,
Connection Management Modeling.

5.3 TCP Retransmission Policy, TCP Congestion Control. 1

5.4 Application Layer – File Transfer Protocol (FTP). 1

5.5 Domain Name System (DNS). 1

COMPUTER SCIENCE AND ENGINEERING

5.6 Electronic Mail. 1

5.7 Simple Network Management Protocol (SNMP) 1

5.8 World Wide Web – Architectural Overview 1

COMPUTER SCIENCE AND ENGINEERING

SEMESTER -4
HONOURS
COMPUTER SCIENCE AND ENGINEERING

Year of
CODE COURSE NAME CATEGORY L T P CREDIT
Introduction

CST 2 2 Number Theory Honours 4 0 0 4 2019

Preamble: This is the foundational course for awarding B. Tech. Honours in Computer Science and
Engineering with specialization in Security in Computing. The purpose of this course is to create
awareness among learners about the important areas of number theory used in computer science. This
course covers Divisibility & Modular Arithmetic, Primes & Congruences, Euler's Function, Quadratic
Residues and Arithmetic Functions, Sum of Squares and Continued fractions. Concepts in Number
Theory help the learner to apply them eventually in practical applications in Computer organization &
Security, Coding & Cryptography, Random number generation, Hash functions and Graphics.

Prerequisite: A sound background in Higher Secondary School Mathematics

Course Outcomes: After the completion of the course the student will be able to

Illustrate modular arithmetic operations, methods and techniques (Cognitive Knowledge

CO1
Level:Understand)
Use the methods - Induction, Contraposition or Contradiction to verify the correctness of
CO2
mathematical assertions (Cognitive Knowledge Level: Apply)
Utilize theorems and results about prime numbers, congruences, quadratic residues and
CO3 integer factorization for ensuring security in computing systems (Cognitive Knowledge
Level: Analyse)
Illustrate uses of Chinese Remainder Theorem & Euclidean algorithm in Cryptography and
CO4
Security (Cognitive Knowledge Level: Apply)
Explain applications of arithmetic functions in Computer Science (Cognitive Knowledge
CO5
Level:Understand)
Implement Number Theoretic Algorithms using a programming language (Cognitive
CO6
Knowledge Level: Apply)
COMPUTER SCIENCE AND ENGINEERING

Mapping of course outcomes with program outcomes

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12

CO1 ! ! ! ! ! !

CO2 ! ! ! ! !

CO3 ! ! ! ! ! !

CO4 ! ! ! ! ! !

CO5 ! ! ! ! ! !

CO6
! ! ! ! ! ! !

Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics

PO3 Design/Development of solutions PO9 Individual and team work

Conduct investigations of complex

PO4 PO10 Communication
problems

PO5 Modern tool usage PO11 Project Management and Finance

PO6 The Engineer and Society PO12 Life long learning

COMPUTER SCIENCE AND ENGINEERING

Assessment Pattern

Continuous Assessment Tests End Semester

Bloom’s Category Examination Marks
Test1 (Percentage) Test2 (Percentage) (Percentage)

Remember 30 30 30

Understand 30 30 30

Apply 40 40 40

Analyse

Evaluate

Create

Mark Distribution

Total Marks CIE Marks ESE Marks ESE Duration

150 50 100 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 10 marks

Continuous Assessment Tests : 25 marks

Continuous Assessment Assignment : 15 marks

COMPUTER SCIENCE AND ENGINEERING

Internal Examination Pattern:

Each of the two internal examinations has to be conducted out of 50 marks

First Internal Examination shall be preferably conducted after completing the first half of the syllabus
and the Second Internal Examination shall be preferably conducted after completing remaining part of
the syllabus.

There will be two parts: Part A and Part B. Part A contains 5 questions (preferably, 2 questions each
from the completed modules and 1 question from the partly covered module), having 3 marks for each
question adding up to 15 marks for part A. Students should answer all questions from Part A. Part B
contains 7 questions (preferably, 3 questions each from the completed modules and 1 question from
the partly covered module), each with 7 marks. Out of the 7 questions in Part B, a student should
answer any 5.

End Semester Examination Pattern:

There will be two parts; Part A and Part B. Part A contains 10 questions with 2 questions from each
module, having 3 marks for each question. Students should answer all questions. Part B contains 2
questions from each module of which a student should answer any one. Each question can have
maximum 2 sub-divisions and carries 14 marks.

SYLLABUS
Module 1

Divisibility and Modular Arithmetic:

Finite Fields – Groups, Rings and Fields.

Divisibility - Divisibility and Division Algorithms, Well ordering Principle,Bezout’s Identity.

Modular Arithmetic- Properties, Euclid's algorithm for the greatest common divisor, Extended Euclid’s
Algorithm, Least Common multiple, Solving Linear Diophantine Equations, Modular Division.

Module 2

Primes and Congruences:

Prime Numbers-Prime Numbers andprime-powerfactorization, Fermat and Mersenne primes.,

Primality testing and factorization.
COMPUTER SCIENCE AND ENGINEERING

Congruences-Linear congruences, Simultaneous linear congruences, Chinese Remainder Theorem,

Fermat’s little theorem, Wilson's theorem.

Module 3

Congruences with a Prime-Power Modulus&Euler's Function:

Congruences with a Prime-Power Modulus-Arithmetic modulo p, Pseudoprimes and Carmichael

numbers, Solving congruences modulo prime powers.

Euler's Function-Euler’s Totient function, Applications of Euler’s Totient function, Traditional

Cryptosystem, Limitations.

The Group of units- The group Un,Primitive roots, Existence of primitive roots, Applications of
primitive roots.

Module 4

Quadratic Residues & Arithmetic Functions :

Quadratic Residues- Quadratic Congruences, The group of Quadratic residues, Legendre symbol,
Jacobi Symbol, Quadratic reciprocity.

Arithmetic Functions- Definition and examples, Perfect numbers, Mobius function and its properties,
Mobius inversion formula, The Dirichlet Products.

Module 5

Sum of Squares and Continued Fractions:

Sum of Squares- Sum of two squares, The Gaussian Integers, Sum of three squares, Sum of four
squares.

Continued Fractions -Finite continued fractions, Infinite continued fractions, Pell's Equation, Solution
of Pell’s equation by continued fractions.

Text Books

1. G.A. Jones & J.M. Jones, Elementary Number Theory, Springer UTM, 2007.

2. Joseph Silverman, A Friendly introduction to Number Theory, Pearson Ed. 2009.

COMPUTER SCIENCE AND ENGINEERING

Reference Books

1. William Stallings, Cryptography and Network Security Principles and Practice, Pearson Ed.
2. Tom M.Apostol, ‘Introduction to Analytic Number Theory’, Narosa Publishing House Pvt. Ltd,
New Delhi, (1996).

3. Neal Koblitz, A course in Number Theory and Cryptography, 2nd Edition, Springer ,2004.

Sample Course Level Assessment Questions

Course Outcome 1 (CO1): Describe the properties of modular arithmetic and modulo operator.

Course Outcome 2 (CO2): Prove that the equation y2 = x3 - 2 has only the integer solution (3, ±5).

Course Outcome 3 (CO3): State the law of reciprocity for Jacobi symbols and use it to determine
whether 888 is a quadratic residue or non residue of the prime 1999.

Course Outcome 4 (CO4): Using Chinese remainder theorem, solve the system of congruence x
≡2(mod 3), x ≡3(mod 5), x ≡2(mod 7)

Course Outcome 5(CO5): State and prove Dirichlet product.

Course Outcome 6 (CO6):Use extended Euclid's algorithm to solve Diophantine equations

efficiently. Given three numbers a>0, b>0, and c, the algorithm should return some x and y such that
a x + b y = c.
COMPUTER SCIENCE AND ENGINEERING

Model Question Paper

QP CODE: PAGES: 03
RegNo : …............................... Name :………..……………

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

FOURTH SEMESTER BTECH (HONOURS) DEGREE EXAMINATION, MONTH &YEAR

Course Code:CST 2 2 Course

Name: Number Theory

Max.Marks:100 Duration: 3 Hours

PART A

Answer all Questions. Each question carries 3 Marks (10x3=30)

1. State and prove well ordering principle.
2. Find gcd d of x=525 and y=231 and express d as ax + by where a and b are integers.
3. Solve the congruence equation 103 x≡ 57 (mod 211).
4. Use Fermat’s Little theorem to show that 91 is not a prime.
5. If m is relatively prime to n , show that Φ(mn) = Φ(m) Φ(n).
6. Explain how public key cryptography can be used for digital signatures.
7. Define Mobius function and prove Mobius function is a multiplicative.
8. State and prove Dirichlet product.
9. Show that every prime of the form 4k+1 canbe represented uniquely as the sum of two
squares.
10. Find the continued fraction representation of the rational number 55/89.

Part B

Answer any one Question from each module.

Each question carries 14 Marks

11. (a) State the Euclidean algorithm and its extension with an example. (7)
(b) Find all the solutions of 24x + 34 y = 6. (7)
OR
12. (a) Describe the properties of modular arithmetic and modulo operator. (7)
(b) Explain Extended Euclidean algorithm. Using the algorithm find the
COMPUTER SCIENCE AND ENGINEERING

multiplicative inverse of 135 mod 61 (7)

13. (a) State and prove Wilson’s theorem . (7)

(b) Explain Fermat’s factorization method and use it to factor 809009 (7)

OR
14. (a) Using Chinese remainder theorem, solve the system of congruences,
x ≡2(mod 3), x ≡3(mod 5), x ≡2(mod 7) (7)
(b) Define Fermat primes. Show that any two distinct Fermat numbers are
Relatively prime. (7)

15. (a) Distinguish between public key and private key encryption techniques.
Also point out the merits and demerits of both. (7)
(b) Define Carmichael number and show that a Carmichael number must
be the product of at least three distinct primes. (7)

OR
16. (a)Define a pseudo prime to a base and find all non trivial bases for which
15 is a pseudo prime. (6)
(b) Find an element of
i) order 5 modulo 11 ii) order 4 modulo 13
iii) order 8 modulo 17 iv) order 6 modulo 19 (8)

17. (a) Determine the quadratic residues and non residues modulo 17. Also
determine whether 219 is a quadratic residue or non residue of the prime 383.
(8)
(b) State the law of quadratic reciprocity. Determine those odd primes p for
which 3 is a quadratic residue and those for which it is a non residue. (6)
OR
18. (a) State and prove properties of Legendre’s symbol. (7)
(b) State the law of reciprocity for Jacobi symbols and using it determine
whether 888 is a quadratic residue or non residue of the prime 1999. (7)

19. (a) Prove that the equation y2 = x3 - 2 has only the integer solution (3 , ±5). (7)
COMPUTER SCIENCE AND ENGINEERING

(b) Define a Gaussian integer. Factorize the Gaussian integer 440 − 55i. (7)
OR
20. (a) If m, and n can be expressed as sum of four squares, then show that mn can
also be expressed the sum of four squares. (7)
(b) Find all the solutions of the Diophantine equation x2 – 6 y 2 =1. (7)

Teaching Plan

Module 1: Divisibility and Euclidean Algorithm 9 hours

1.1 Finite Fields – Groups and Rings. 1 hour

1.2 Finite Fields – Fields. 1 hour

1.3 Divisibility and Division Algorithms, Well ordering Principle. 1 hour

Decimal Expansion of a positive Integer, Greatest Common Divisor,

1.4 1 hour
Bezout’s Theorem.
Modular Arithmetic- Properties of congruences, Modular Arithmetic
1.5 1 hour
Operations, Properties of Modular Arithmetic.
Euclid's algorithm for the greatest common divisor, Extended Euclid’s
1.6 1 hour
Algorithm.

1.7 Solving Linear Diophantine Equations. 1 hour

1.8 Least Common multiple and Modular Division. 1 hour

Implementation of Euclid’s algorithm, Extended Euclid’s Algorithm and

1.9 1 hour
solution of Linear Diophantine Equations.

Module 2: Primes and Congruences 9 hours

2.1 Prime Numbersand prime-powerFactorization. 1 hour

2.2 Fermat and Mersenne primes. 1 hour

2.3 Primality testing and factorization, Miller -Rabin Test for Primality. 1 hour

2.4 Pollard's Rho Method for Factorization, Fermat’s Factorization. 1 hour

COMPUTER SCIENCE AND ENGINEERING

2.5 Linear congruences, Simultaneous linear congruences. 1 hour

2.6 Chinese Remainder Theorem. 1 hour

2.7 Implementation of Chinese Remainder Theorem. 1 hour

2.8 Fermat's little theorem. 1 hour

2.9 Wilson's theorem. 1 hour

Module 3: Congruences with a Prime-Power Modulus &Euler's Function 9 hours

3.1 Congruences with a Prime-Power Modulus, Arithmetic modulo p. 1 hour

3.2 Pseudo-primes and Carmichael numbers. 1 hour

3.3 Solving congruences modulo prime powers. 1 hour

3.4 Definition of Euler Totient function, Examples and properties. 1 hour

3.5 Multiplicativity of Euler's Totient function. 1 hour

3.6 Applications of Euler’s function, Euler’s Theorem. 1 hour

3.7 Traditional Cryptosystem, Limitations, Public Key Cryptography. 1 hour

3.8 The Group of Units, Primitive Roots. 1 hour

3.9 Existence of primitive roots for Primes, Applications of primitive roots. 1 hour

Module 4: Quadratic Residues and Arithmetic Functions 9 hours

4.1 Quadratic congruences, The group of Quadratic Residues. 1 hour

4.2 Legendre symbol, Jacobi Symbol. 1 hour

4.3 Quadratic reciprocity. 1 hour

4.4 Quadratic residues for prime-power moduli. 1 hour

4.5 Arithmetic Functions: Definition and examples. 1 hour

COMPUTER SCIENCE AND ENGINEERING

4.6 Perfect numbers, Definition and proposition. 1 hour

4.7 Mobius inversion formula., application of the Mobius inversion formula. 1 hour

4.8 Mobius function and its properties. 1 hour

4.9 The Dirichlet Product, Definition and proof. 1 hour

Module 5: Sum of Squares and Continued Fractions 9 hours

5.1 Sum of Squares, Sum of two squares. 1 hour

5.2 The Gaussian Integers. 1 hour

5.3 Sum of three squares. 1 hour

5.4 Sum of four squares. 1 hour

5.5 Continued Fractions, Finite continued fractions. 1 hour

5.6 Continued Fractions, Finite continued fractions. 1 hour

5.7 Infinite continued fractions. 1 hour

5.8 Pell's Equation, Definition. 1 hour

5.9 Solution of Pell's equation by continued fractions. 1 hour

COMPUTER SCIENCE AND ENGINEERING
CODE Computational Fundamentals CATEGORY L T P CREDIT
CST 2 4 for Machine Learning HONOURS 3 1 0 4

Preamble: This is the foundational course for awarding B. Tech. Honours in Computer
Science and Engineering with specialization in Machine Learning. The purpose of this course
is to introduce mathematical foundations of basic Machine Learning concepts among learners, on
which Machine Learning systems are built. This course covers Linear Algebra, Vector Calculus,
Probability and Distributions, Optimization and Machine Learning problems. Concepts in this course
help the learners to understand the mathematical principles in Machine Learning and aid in the
creation of new Machine Learning solutions, understand & debug existing ones, and learn about the
inherent assumptions & limitations of the current methodologies.

Prerequisite: A sound background in higher secondary school Mathematics.

Course Outcomes: After the completion of the course the student will be able to

Make use of the concepts, rules and results about linear equations, matrix algebra,
CO 1 vector spaces, eigenvalues & eigenvectors and orthogonality & diagonalization to
solve computational problems (Cognitive Knowledge Level: Apply)

Perform calculus operations on functions of several variables and matrices,

CO 2
including partial derivatives and gradients (Cognitive Knowledge Level: Apply)
Utilize the concepts, rules and results about probability, random variables, additive
& multiplicative rules, conditional probability, probability distributions and Bayes’
CO 3
theorem to find solutions of computational problems (Cognitive Knowledge Level:
Apply)

Train Machine Learning Models using unconstrained and constrained optimization

CO 4
methods (Cognitive Knowledge Level: Apply)
Illustrate how the mathematical objects - linear algebra, probability, and calculus
CO 5 can be used to design machine learning algorithms (Cognitive Knowledge Level:
Understand)

Mapping of course outcomes with program outcomes

PO 1 PO 2 PO 3 PO 4 PO 5 PO 6 PO 7 PO 8 PO 9 PO 10 PO 11 PO 12
CO 1 √ √ √ √ √
CO 2 √ √ √ √
CO 3 √ √ √ √ √
CO 4 √ √ √ √ √ √

CO 5 √ √ √ √ √ √ √ √
COMPUTER SCIENCE AND ENGINEERING

Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics
PO3 Design/Development of solutions PO9 Individual and team work

Conduct investigations of complex

PO4 PO10 Communication
problems
PO5 Modern tool usage PO11 Project Management and Finance
PO6 The Engineer and Society PO12 Life long learning

Assessment Pattern

Continuous Assessment Tests End Semester

Bloom’s Category
1 2 Examination

Remember 20% 20% 20%

Understand 40% 40% 40%

Apply 40% 40% 40%

Analyse
Evaluate

Create

Mark Distribution

Total Marks CIE Marks ESE Marks ESE Duration

150 50 100 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 10 marks

Continuous Assessment Tests : 25 marks

COMPUTER SCIENCE AND ENGINEERING
Continuous Assessment Assignment : 15 marks

Internal Examination Pattern:

Each of the two internal examinations has to be conducted out of 50 marks

First Internal Examination shall be preferably conducted after completing the first half of the
syllabus and the Second Internal Examination shall be preferably conducted after completing
remaining part of the syllabus.

There will be two parts: Part A and Part B. Part A contains 5 questions (preferably, 2
questions each from the completed modules and 1 question from the partly covered module),
having 3 marks for each question adding up to 15 marks for part A. Students should answer
all questions from Part A. Part B contains 7 questions (preferably, 3 questions each from the
completed modules and 1 question from the partly covered module), each with 7 marks. Out
of the 7 questions in Part B, a student should answer any 5.

End Semester Examination Pattern: There will be two parts; Part A and Part B. Part A
contains 10 questions with 2 questions from each module, having 3 marks for each question.
Students should answer all questions. Part B contains 2 questions from each module of which
student should answer anyone. Each question can have maximum 2 sub-divisions and carries
14 marks. 

COMPUTER SCIENCE AND ENGINEERING
Syllabus

Module 1

LINEAR ALGEBRA : Systems of Linear Equations – Matrices, Solving Systems of Linear

Equations. Vector Spaces - Linear Independence, Basis and Rank, Linear Mappings, Norms,
- Inner Products - Lengths and Distances - Angles and Orthogonality - Orthonormal Basis -
Orthogonal Complement - Orthogonal Projections. Matrix Decompositions - Determinant
and Trace, Eigenvalues and Eigenvectors, Cholesky Decomposition, Eigen decomposition
and Diagonalization, Singular Value Decomposition, Matrix Approximation.

Module 2

VECTOR CALCULUS : Differentiation of Univariate Functions - Partial Differentiation

and Gradients, Gradients of Vector Valued Functions, Gradients of Matrices, Useful
Identities for Computing Gradients. Back propagation and Automatic Differentiation - Higher
Order Derivatives- Linearization and Multivariate Taylor Series.

Module 3

Probability and Distributions : Construction of a Probability Space - Discrete and

Continuous Probabilities, Sum Rule, Product Rule, and Bayes’ Theorem. Summary Statistics
and Independence – Important Probability distributions - Conjugacy and the Exponential
Family - Change of Variables/Inverse Transform.

Module 4

Optimization : Optimization Using Gradient Descent - Gradient Descent With Momentum,

Stochastic Gradient Descent. Constrained Optimization and Lagrange Multipliers - Convex
Optimization - Linear Programming - Quadratic Programming.

Module 5

CENTRAL MACHINE LEARNING PROBLEMS : Data and Learning Model-

Empirical Risk Minimization - Parameter Estimation - Directed Graphical Models.

Linear Regression - Bayesian Linear Regression - Maximum Likelihood as Orthogonal

Projection.

Dimensionality Reduction with Principal Component Analysis - Maximum Variance

Perspective, Projection Perspective. Eigenvector Computation and Low Rank
Approximations.
COMPUTER SCIENCE AND ENGINEERING
Density Estimation with Gaussian Mixture Models - Gaussian Mixture Model, Parameter
Learning via Maximum Likelihood, EM Algorithm.

Classification with Support Vector Machines - Separating Hyperplanes, Primal Support

Vector Machine, Dual Support Vector Machine, Kernels.

Text book:

1.Mathematics for Machine Learning by Marc Peter Deisenroth, A. Aldo Faisal, and
Cheng Soon Ong published by Cambridge University Press (freely available at https://
mml - book.github.io)

Reference books:

1. Linear Algebra and Its Applications, 4th Edition by Gilbert Strang

2. Linear Algebra Done Right by Axler, Sheldon, 2015 published by Springer

3. Introduction to Applied Linear Algebra by Stephen Boyd and Lieven Vandenberghe,

2018 published by Cambridge University Press

4. Convex Optimization by Stephen Boyd and Lieven Vandenberghe, 2004 published by

Cambridge University Press

5. Pattern Recognition and Machine Learning by Christopher M Bishop, 2006, published

by Springer

6. Learning with Kernels – Support Vector Machines, Regularization, Optimization, and

Beyond by Bernhard Scholkopf and Smola, Alexander J Smola, 2002, bublished by
MIT Press

7. Information Theory, Inference, and Learning Algorithms by David J. C MacKay, 2003

published by Cambridge University Press

8. Machine Learning: A Probabilistic Perspective by Kevin P Murphy, 2012 published by

MIT Press.

9. The Nature of Statistical Learning Theory by Vladimir N Vapnik, 2000, published by

Springer
COMPUTER SCIENCE AND ENGINEERING
Sample
Sample Course
Course LevelLevel Assessment
Assessment Questions.
Questions.
Sample
Sample
Sample Course
Course
Course Level Level
Level Assessment
Assessment
Assessment Questions.
Questions.
Questions.
Course
Course Outcome
Outcome 1 (CO1):
1 (CO1):
Course
Course
Course Outcome
Outcome
Outcome 1 (CO1):
1 (CO1):
1 (CO1):
1. Find the set S of all solutions in x of the following inhomogeneous linear systems Ax = b
1. Find the set S of all solutions in x of the following inhomogeneous linear systems Ax
1.
1. 1. Find
FindFind theASset
the the
whereset set
ofSSall
and of
bof all
all solutions
solutions
solutions
are defined in
inofxxthe
inasxfollows: of following
of the following
the following inhomogeneous
inhomogeneous
inhomogeneous linear
linear
linear systems
systems
systems Ax
b == bb
Ax =Ax
=where
b,
where Awhere
where AAand
and Aare
bandand b are
bbdefined
are
are defined
defined
defined as follows:
asfollows:
as follows:
as follows:

2. Determine the inverses of the following matrix if possible

2. Determine the inverses of the following matrix if possible
2.
2. 2. Determine
Determine
Determine theinverses
the inverses
the inverses offollowing
of
of the thefollowing
the following matrix
matrix
matrix ififpossible
possible
if possible

3. Are the following sets of vectors linearly independent?

3.
3. 3.3.
Are Are
Are
the
Are the
the following
following
following
the sets
following sets
sets
of
sets of
of vectors
vectors
vectors
of linearly
linearly
linearly
vectors independent?
independent?
independent?
linearly independent?

4. 4.A set
A set
of of n linearly
n linearly independent
independent vectors
vectors in R inn R n
formsforms a basis.
a basis. Does
Does thethe
set set of vectors
of vectors (2, (2, 4,−3) ,
n
4. 4.4.
A setA set
A(0,
set1,
of of n linearly
noflinearly
1)n, linearly independent
independent
independent
(0, 1,−1) vectors
vectors
vectors
form a basis 3 in R forms a basis. Does the set of vectors (2, 4,−3) ,
n n
forinRR?inExplain
R3 forms
forms a basis.
a your
basis. DoesDoes
reasons. the of
the set setvectors
of vectors (2, 4,−3)
(2, 4,−3) , ,
4,−3) , (0, 1, 1) , (0, 1,−1) form a basis for R ? Explain your reasons.
(0, 1, (0,
(0,1)1,1, 1),1,−1)
, 1)
(0, ,(0,
(0,1,−1)
1,−1) form
formform aabasis
a basisbasis
for R for
3
for?R R33??Explain
ExplainExplainyouryour your reasons.
reasons.
reasons.
5. 5.Consider the transformation T (x, y) = (x +
Consider the transformation T (x, y) = (x + y, x + 2y, 2x y, x + 2y, 2x + 3y). Obtain
+ 3y). kerker
Obtain T and useuse this to
T and
5. 5.5. this
Consider
Consider
Consider the
the
to calculate
calculate transformation
the transformation
thetransformation
the nullity.
nullity. Also (x,TTy)
TAlso
find (x,
(x,=y)
find
the y)
(x ==+(x
the (x
y, +x+ y,+y, x2y,
transformation
transformation x ++2x2y,+2x
2y,
matrix 2x
3y).+ 3y).
+for
matrix 3y). Obtain
Obtain
T. Tker
T. ker ker
forObtain TT and
and and use
use use this
this this to
to to
calculate
calculate
calculate thenullity.
nullity.
the nullity.
the Also
AlsoAlso find
findfind thetransformation
transformation
the transformation
the matrix matrix
for T.
matrix forT.
for T.

6. 6.Find
Find
the the characteristic
characteristic equation,
equation, eigenvalues,
eigenvalues, and eigenspaces
and eigenspaces corresponding
corresponding to each to each
6. 6.6. Find
Find Find the
the the
eigenvalue characteristic
characteristic equation,
equation,
characteristic eigenvalues,
eigenvalues,
equation,
of the following matrix and
and and
eigenvalues, eigenspaces
eigenspaces corresponding
corresponding
eigenspaces to each
to each
corresponding to each
eigenvalue of the following matrix
eigenvalue
eigenvalue offollowing
of the
eigenvalue of thefollowing
the following matrix
matrix
matrix

"
7. Diagonalize the following matrix, if possible
7. 7.7. Diagonalize
Diagonalize thefollowing
following
the following
Diagonalize the matrix,
matrix, ififpossible
possible
if possible
matrix,
COMPUTER SCIENCE AND ENGINEERING
7. Diagonalize the following matrix, if possible

8. Find the singular value decomposition (SVD) of the following matrix

8. 8.Find the singular

Find the value
singular value decomposition
decomposition (SVD) (SVD)
of the of the following
following matrixmatrix

"

Course Outcome 2 (CO2):

Course
Course Outcome
Outcome 2 (CO2):
2 (CO2):

1. 1. For
Fora scalar
a scalar function
function f(x,f(x, x2 +3y
y, zy,) z=) x=2 +3y
2
2 +2z+2z
2
, find
2, find the the gradient
gradient andand its magnitude
its magnitude at at the
1.thepoint
For
(1, 2, -1).
a scalar
point function f(x, y, z ) = x2 +3y2 +2z2, find the gradient and its magnitude at the
(1, 2, -1).
pointthe
2. 2. Find
Find (1, maximum
2, -1). andminimum
minimumvalues
values of
of the
the function f(x, y) 2 2
the maximum and y) == 4x
4x++4y4y- x- x-2 y- ysubject
2 to
2 2
the
Findcondition
2.subject to the
the x + y and
<=
condition
maximum x2 2.
+ y2 <= 2. values of the function f(x, y) = 4x + 4y - x 2 - y2 subject to
minimum
2 2
the condition
3. 3. Suppose x +trying
y <= 2. f(x, y) y)
= x2=+ x
2y2 + 2y2. Along
Supposeyou
youwere to to
were trying minimize
minimize f(x, + 2y + 2y2. what vector
Along what vector
3.should you
should
Suppose
travel
you from (5,(5,
travel
you werefrom
12)?
trying 12)?
to minimize f(x, y) = x2+ 2y + 2y2. Along what vector
4. should you travel from (5, 12)?
4. Find thethe
second order Taylor series expansion forfor
f(x, y) y)
= (x + y)
+ y)about (0 (0
, 0).
2 2
Find second order Taylor series expansion f(x, = (x about , 0).
5.
4.Find thethe
critical points
orderofTaylor
f(x, y)series
= x expansion
3xy+5x-2y+6y +8.y) = (x + y)2 about (0 , 0).
2– 2
Find second for f(x,
5. Find the critical points of f(x, y) = x2 – 3xy+5x-2y+6y2+8.
6. Compute the gradient of the Rectified Linear Unit (ReLU) function ReLU(z) =
5. Find the critical points of f(x, y) = x2 – 3xy+5x-2y+6y2+8.
6. Compute the gradient of the Rectified Linear Unit (ReLU) function ReLU(z) = max(0 , z).
max(0 , z).
7. 6.LetCompute
LL ==||Ax
the gradient of the Rectified Linear Unit (ReLU) function ReLU(z) = max(0 , z).
||Ax- b||
- b||2,22where
, whereAAisisa amatrix
matrixand
andx xand
andb bare
arevectors.
vectors.Derive
DerivedL
dLininterms
termsofof dx.
2
7. Let
7.dx.Let L = ||Ax - b||22, where A is a matrix and x and b are vectors. Derive dL in terms of dx.
Course Outcome 3 (CO3):
Course Outcome 3 (CO3):
1. Let J and T be independent events, where P(J)=0.4 and P(T)=0.7.
i. Find P(J∩T)
1. Let J and T be independent events, where P(J)=0.4 and P(T)=0.7.
ii. Find P(J∪T)
i. Find P(J∩T)
iii. Find P(J∩T′)
ii. Find P(J∪T)
iii. Find P(J∩T′)
COMPUTER SCIENCE AND ENGINEERING
Course Outcome 3 (CO3):

1. Let J and T be independent events, where P(J)=0.4 and P(T)=0.7.

i. Find P(J∩T)

ii. Find P(J∪T)

iii. Find P(J∩T′)

2. Let A and B be events such that P(A)=0.45 , P(B)=0.35 and P(A∪B)=0.5. Find
P(A∣B).
2. Let A and B be events such that P(A)=0.45 , P(B)=0.35 and P(A∪B)=0.5. Find P(A∣B).
3. A random variable R has the probability distribution as shown in the following table:
3. A random variable R has the probability distribution as shown in the following table:

i.
i. Given that E(R)=2.85, find a and b.
i. Given
ii. that E(R)=2.85,
Find P(R>2). find a and b.
ii. Find P(R>2).
4. A biased coin (with probability of obtaining a head equal to p > 0) is tossed repeatedly and
4. A biasedindependently
coin (with probability
until the of obtaining
first head isaobserved.
head equalCompute
to p > 0)the
is tossed repeatedly
probability that the first head
and independently
appears at anuntil
eventhenumbered
first headtoss.
is observed. Compute the probability that the
first head appears at an even numbered toss.
5. Two players A and B are competing at a trivia quiz game involving a series of questions. On
5. Two players A and B question,
are competing at a triviathat
quiz game involving a series of are p and q
any individual the probabilities A and B give the correct answer
questions. On any individual
respectively, question,with
for all questions, the outcomes
probabilities
for that A andquestions
different B give the correct
being independent. The
answer gameare p finishes
and q respectively,
when a player for wins
all questions, with outcomes
by answering a questionforcorrectly.
differentCompute the
questions being independent.
probability that A winsThe if game finishes when a player wins by answering a
i. A answers
question correctly. Compute thethe
first question, that A wins if
probability
ii. B answers the first question.
i. A answers the first question,
6. A coin for which P(heads) = p is tossed until two successive tails are obtained. Find the
ii. Bprobability
answers the first
that thequestion.
experiment is completed on the nth toss.
6. A coin for which P(heads) = p is tossed until two successive tails are obtained. Find
7. You roll a fair dice twice. Let the random variable X be the product of the outcomes of the
the probability that the experiment is completed on the nth toss.
two rolls. What is the probability mass function of X? What are the expected value and the
7. You rollstandard
a fair dice twice. Let the random variable X be the product of the outcomes of
deviation of X?
the two rolls. What is the probability mass function of X? What are the expected value
and 8. While watching
the standard deviationaofgameX? of Cricket, you observe someone who is clearly supporting
Mumbai Indians. What is the probability that they were actually born within 25KM of
Mumbai? Assume that:
• the probability that a randomly selected person is born within 25KM of Mumbai is
1/20;
• the chance that a person born within 25KMs of Mumbai actually supports MI is
7/10 ;
• the probability that a person not born within 25KM of Mumbai supports MI with
probability 1/10.

9. What is an exponential family? Why are exponential families useful?

COMPUTER SCIENCE AND ENGINEERING
8. While watching a game of Cricket, you observe someone who is clearly supporting
Mumbai Indians. What is the probability that they were actually born within 25KM of
Mumbai? Assume that:
• the probability that a randomly selected person is born within 25KM of
Mumbai is 1/20;
• the chance that a person born within 25KMs of Mumbai actually supports MI
is 7/10 ;
• the probability that a person not born within 25KM of Mumbai supports MI
with probability 1/10.
9. What is an exponential family? Why are exponential families useful?
10. Let Z1 and Z2 be independent random variables each having the standard normal
distribution. Define the random variables X and Y by X = Z1 + 3Z2 and Y = Z1 + Z2.
Argue that the joint distribution of (X, Y) is a bivariate normal distribution. What are
the parameters of this distribution?
11. Given a continuous random variable x, with cumulative distribution function Fx(x),
show that the random variable y = Fx(x) is uniformly distributed.
12. Explain Normal distribution, Binomial distribution and Poisson distribution in the
exponential family form.

Course Outcome 4(CO4):

1. Find the extrema of f(x, y) = x subject to g(x, y) = x2 + 2y2 = 3.

2. Maximize the function f(x, y, z) = xy + yz + xz on the unit sphere g(x, y, z) = x2 + y2 +
z2 = 1.
3. Provide necessary and suffcient conditions under which a quadratic optimization
problem be written as a linear least squares problem.
4. Consider the univariate function f(x) = x3 + 6x2 - 3x - 5. Find its stationary points and
indicate whether they are maximum, minimum, or saddle points.
5. Consider the update equation for stochastic gradient descent. Write down the update
when we use a mini-batch size of one.
indicate whether
indicate whether they
they are
are maximum,
maximum, minimum,
minimum, or
or saddle
saddle points.
points.

5. Consider
5. Consider the
the update
update equation
equation for
for stochastic
stochastic gradient
gradient descent.
descent. Write
Write down
down the
the update
update when
when
we use
we use aa mini-batch
mini-batch size
size of
of one.
one.
COMPUTER SCIENCE AND ENGINEERING
6. Consider
6.
6. Consider the
Consider the function
the function
function

"

i. Is f(x) a convex function? Justify your answer.

i.i. Is f(x)
Is f(x) aa convex
convex function?
function? Justify
Justify your
your answer.
answer.
ii.
ii. Is (1
Is (1 ,, -1)
-1) aa local/global
local/global minimum?
minimum? Justify
Justify your
your answer.
answer.
2 2
7. Is the
7. Is the function
function f(x,
f(x, y)
y) == 2x
2x22++yy22++6xy
6xy--xx++3y
3y- -77convex,
convex,concave,
concave,ororneither?
neither?Justify
Justify your
your
answer.answer.
8.
8. Consider
Consider the
the following
following convex
convex optimization
optimization problem
problem

"

Subject to the constraint x + y >= 4, x, y >= 1.

Subject to the constraint x + y >= 4, x, y >= 1.
Derive an
Derive an explicit
explicit form
form of
of the
the Lagrangian
Lagrangian dual
dual problem.
problem.

9. 9.
Solve the following
Solve LP problem
the following withwith
LP problem the simplex method.
the simplex method.
9. Solve the following LP problem with the simplex method.

"
subject
subject to toto constraints
the the constraints
subject the constraints

Course
Course Outcome
Outcome 5 (CO5):
5 (CO5):
Course Outcome 5 (CO5):
1. What is a loss function? Give examples.
1. What is a loss function? Give examples.
2.1. What is
area loss
training/validation/test sets? What is cross-validation? Name one or two
function? Give examples.
2. What areoftraining/validation/test
examples sets? What is cross-validation? Name one or two examples
cross-validation methods.
2. What are training/validation/test sets? What is cross-validation? Name one or two examples
of cross-validation methods.
3. of cross-validation
Explain methods.
generalization, overfitting, model selection, kernel trick, Bayesian learning
3. Explain generalization, overfitting, model selection, kernel trick, Bayesian learning
3. Explain generalization, overfitting, model selection, kernel trick, Bayesian learning
4. Distinguish between Maximum Likelihood Estimation (MLE) and Maximum A Posteriori
4. Distinguish between Maximum Likelihood Estimation (MLE) and Maximum A Posteriori
Estimation (MAP)?
Estimation (MAP)?
5. What is the link between structural risk minimization and regularization?
5. What is the link between structural risk minimization and regularization?
6. What is a kernel? What is a dot product? Give examples of kernels that are valid dot
6. What is a kernel? What is a dot product? Give examples of kernels that are valid dot
products.
products.
Course Outcome 5 (CO5):

1. What is a loss function? Give examples.COMPUTER SCIENCE AND ENGINEERING

4.2. Distinguish
What are training/validation/test
between Maximum sets? What isEstimation
Likelihood cross-validation?
(MLE) Name one or two A
and Maximum examples
of cross-validation
Posteriori Estimationmethods.
(MAP)?
5.3. What
Explain generalization,
is the link between overfitting, model
structural risk selection, and
minimization kernel trick, Bayesian learning
regularization?
6.4. What
Distinguish between
is a kernel? WhatMaximum Likelihood
is a dot product? GiveEstimation
examples (MLE) andthat
of kernels Maximum
are validAdot
Posteriori
Estimation (MAP)?
products.
7.5. What
Whatisisridge
the link between How
regression? structural risktrain
can one minimization and regularization?
a ridge regression linear model?
8.6. What
What isis Principal
a kernel?Component
What is a Analysis
dot product?
(PCA)?GiveWhich
examples
eigenof value
kernels that arethevalid dot
indicates
products.of largest variance? In what sense is the representation obtained from a
direction
7. projection
What is ridge ontoregression?
the eigenHow can onecorresponding
directions train a ridge regression
the the linear
largestmodel?
eigen values
optimal for data reconstruction?
8. What is Principal Component Analysis (PCA)? Which eigen value indicates the direction of
largest variance?
9. Suppose that you In what
have sense is
a linear the representation
support vector machine obtained
(SVM) from a projection
binary classifier.onto the
eigen directions
Consider a pointcorresponding the the
that is currently largest eigen
classified valuesand
correctly, optimal
is farforaway
data reconstruction?
from the
9. decision
Supposeboundary. If you
that you have remove
a linear the point
support vectorfrom the training
machine (SVM) set, andclassifier.
binary re-train the
Consider a
classifier, will the decision boundary change or stay the same? Explain your answer
point that is currently classified correctly, and is far away from the decision boundary. If you
inremove
one sentence.
the point from the training set, and re-train the classifier, will the decision boundary
change or stay the same? Explain your answer in one sentence.
10. Suppose you have n independent and identically distributed (i.i.d) sample data points
10. xSuppose
1, ... , xnyou havedata
. These n independent
points come andfrom
identically distributed
a distribution (i.i.d)
where thesample of a x1, ... ,
data points
probability
xn. These
given data points
datapoint x is come from a distribution where the probability of a given datapoint x is

"

Prove that the MLE estimate of parameter is the sample mean.

11. Suppose the data set y1,...,yn is a drawn from a random sample consisting of i.i.d.
discrete uniform distributions with range 1 to N. Find the maximum likelihood
estimate of N.
12. Ram has two coins: one fair coin and one biased coin which lands heads with
probability 3/4. He picks one coin at random (50-50) and flips it repeatedly until he
gets a tails. Given that he observes 3 heads before the first tails, find the posterior
probability that he picked each coin.

i. What are the prior and posterior odds for the fair coin?

ii. What are the prior and posterior predictive probabilities of heads on the next
flip? Here prior predictive means prior to considering the data of the first four
flips.
11. Suppose the data set y1,...,yn is a drawn from a random sample consisting of i.i.d. discrete
uniform distributions with range 1 to N. Find the maximum likelihood estimate of N.
12. Ram has two coins: one fair coin and one biased coin which lands heads with probability
3/4. He picks one coin at random (50-50) and flips it repeatedly until he gets a tails. Given
COMPUTER SCIENCE AND ENGINEERING
that he observes 3 heads before the first tails, find the posterior probability that he picked
each coin.
i. What are the prior and posterior odds for the fair coin?
ii. What are the prior Model Question
and posterior paper
predictive probabilities of heads on the next flip?
Here: prior predictive means prior to considering the data of the first four flips.
QP Code Total Pages: 4
Reg No.:_______________ Name:__________________________
Model
APJ ABDUL KALAM Question paperUNIVERSITY
TECHNOLOGICAL
IV SEMESTER B.TECH (HONOURS) DEGREE EXAMINATION, MONTH and YEAR
QP Code : Total Pages: 4
Course Code: CST 2 4
Reg No.:_______________ Name:__________________________
Course Name: COMPUTATIONAL FUNDAMENTALS FOR MACHINE
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
LEARNING
IV SEMESTER B.TECH (HONOURS) DEGREE EXAMINATION, MONTH and YEAR
Max. Marks: 100 Duration: 3 Hours
Course Code: CST 274
Course Name: COMPUTATIONAL FUNDAMENTALS PART A FOR MACHINE LEARNING
Max. Marks: 100 Answer all questions, each carries 3 marks. Marks
Duration: 3 Hours
PART A
1 Show that withAnswer
the usual operation each
all questions, of scalar multiplication
carries 3 marks. but with Marks
1 Show that on
addition with the given
reals usual by
operation
x # y = of
2(xscalar
+ y) ismultiplication but with addition on
not a vector space.
reals given by x # y = 2(x + y) is not a vector space.
2 Find the eigenvalues of the following matrix in terms of k. Can you find
2 Find the eigenvalues of the following matrix in terms of k. Can you find an
an eigenvector corresponding to each of the eigenvalues?
eigenvector corresponding to each of the eigenvalues?

3 Let f(x, y, z) = xyer, where r = x2+z2-5. Calculate the gradient of f at the

3 Let f(x, y, z) = xyer, where r = x2+z2-5. Calculate the gradient of f at the point
(1,point
3, -2).(1, 3, -2).
4 Compute the Taylor polynomials Tn, n = 0 , ... , 5 of f(x) = sin(x) + cos(x) at
4 x0 Compute
= 0. the Taylor polynomials Tn, n = 0 , ... , 5 of f(x) = sin(x) + cos(x)
5 LetatXxbe a continuous random variable with probability density function on
0 = 0.
0 <= x <= 1 defined by f(x) = 3x2. Find the pdf of Y = X2.
65 Let that
Show X beifatwocontinuous
events A random variable
and B are with probability
independent, then A anddensity function
B' are independent.
7 Explain the principle of the gradient descent algorithm.
on 0 <= x <= 1 defined by f(x) = 3x2. Find the pdf of Y = X2.
6 Show that if two events A and B are independent, then A and B' are
independent.
7 Explain the principle of the gradient descent algorithm.
COMPUTER SCIENCE AND ENGINEERING
8 Briey explain the difference between (batch) gradient descent and
stochastic gradient descent. Give an example of when you might prefer

8
one over the other.
Briey explain the difference between (batch) gradient descent and stochastic
8 Briey explain the difference between (batch) gradient descent and stochastic
9 What isdescent.
gradient the empirical
Give an risk? What of
example is “empirical risk minimization”?
when you might prefer one over the other.
910gradient descent.
What Give
is thethe an
empirical example
risk? of
Whatwhen you might
is “empirical prefer
risk one over the other.
minimization”?
9 What is Explain
the empirical concept
risk? of ais
What Kernel function
“empirical risk in Support
minimization”? Vector Machines.
10 Explain the concept of a Kernel function in Support Vector Machines. Why are
10 Explain Why
the concept of aso
are kernels Kernel
useful?function in Supporta Vector
What properties kernel Machines. Why
should posses to are
be
kernels so useful? What properties a kernel should posses to be used in an SVM?
kernels so
useduseful?
in an What
SVM?properties a kernel should posses to be used in an SVM?
PART B
PART
Answer any one Question from each B module. Each question carries 14 Marks
11 a)Answer i. any one
Find allQuestion
solutionsfrom PART
to theeach B linear
module.
system of Each question carries 14 Marks
equations (6)
11 a) i. Answer
Find all any
solutions to the system of linear equations
one Question from each module. Each question carries 14 Marks (6)

11 a) i. Find all solutions to the system of linear equations (6)

ii. Prove that" all

ii. Prove that all
ii.vectors
Prove orthogonal −3, 1]T forms
to [2,orthogonal
that all vectors to a −3,
[2, subspace
1] T forms
3
W ofaRsubspace
. What is dim
T 3
vectors(W)
orthogonal
and why?
to [2, −3, 1] forms a subspace W of R . What is dim
W of R3. What is dim (W) and why?
(W) and why?
b) Use Usethethe
Gramm-Schmidt
Gramm-Schmidt process to find
process an orthogonal
to find basis for
an orthogonal the for
basis column
the space
(8) (8)
b) Use theofGramm-Schmidt
the following process
matrix to find an orthogonal basis for the column space (8)
column space of the following matrix
of the following matrix

"
OR
12 a) i. Let L be the line through the OR 2
ORorigin in R that is parallel to the vector (6)
12 a) i. Let L be 4]Tline
[3,the . Find the standard
through matrix
the origin in Rof
2 the orthogonal projection onto L. Also
that is parallel to the vector (6)
T
[3, 4] find
. Find
thethe standard
point matrixisofclosest
on L which the orthogonal projection
to the point onto
(7 , 1) and findL.the
Also
point on
find theL point
whichonis Lclosest
whichtoisthe
closest
pointto(-3
the, 5).
point (7 , 1) and find the point on
ii. Find
L which the rank-1
is closest approximation
to the point (-3 , 5).of
ii. Find the rank-1 approximation of

b) i. Find an orthonormal basis of R3 consisting of eigenvectors for the (8)

b) i. Find an orthonormal basis of R3 consisting of eigenvectors for the (8)
COMPUTER SCIENCE AND ENGINEERING
12 a) i. Let L be the line through the origin in R2 that is parallel to the (6)
vector OR
12 a) i. Let L be the line through the origin in R2 that is parallel to the vector (6)
[3,4]4]T.T.Find
[3, Findthe
thestandard
standardmatrix
matrixofofthe
theorthogonal
orthogonalprojection
projectiononto
ontoL. Also
L. Also
find find the
the point on Lpoint
whichonisL closest
which is
to closest to (7
the point the, 1)
point
and(7find
, 1)the
and
point on
Lfind
which
theispoint
closest to which
on L the point (-3 , 5).to the point (-3 , 5).
is closest
ii. Find the rank-1 approximation of
ii. Find the rank-1 approximation of

"

b) i. Find an orthonormal basis of R3 consisting of eigenvectors for the (8)

following matrix
b) following
i. Find matrix
an orthonormal basis of R3 consisting of eigenvectors for the (8)

ii. Find a 3 × 3 orthogonal "

ii. Find
matrix S anda a33××33orthogonal matrix
diagonal matrix D Ssuch
andthat
a 3A×=3SDS
diagonal
T
. matrix D
such that A = SDST .
13 a) A skier is on a mountain with equation z = 100 – 0.4x2 – 0.3y2, where z denotes (8)
13 height.
a) A skier is on a mountain with equation z = 100 – 0.4x2 – 0.3y2, where z (8)
denotes height.
i. The skier is located at the point with xy-coordinates (1 , 1), and wants to
skii.downhill along
The skier is the steepest
located at thepossible path. xy-coordinates
point with In which direction(1 ,(indicated
1), and
by a vector (a , b) in the xy-plane) should the skier begin
wants to ski downhill along the steepest possible path. In whichskiing.
direction (indicated by a vector (a , b) in the xy-plane) should the
ii. The skier begins skiing in the direction given by the xy-vector (a , b) you
found skier begin
in part (i), skiing.
so the skier heads in a direction in space given by the
vector (a , b , c). Find the value of c.
ii. The skier begins skiing in the direction given by the xy-vector (a ,
b) b) linear
Find the you found in part (i),tosothe
approximation thefunction
skier heads
f(x,y)in=a2direction
- sin(-x -in3y)space
at the (6)
given
point (0 , π),by
andthethen
vector
use (a , b answer
your , c). Find
to the value f(0.001
estimate of c. , π).
b) Find the linear approximation to the function f(x,y) = 2 - sin(-x - (6)
3y) at the point (0 , π),OR
and then use your answer to estimate
14 a) Let g be the function given by (8)
f(0.001 , π).

OR
OR
14 a) Let g be the function given by (8)

COMPUTER SCIENCE AND ENGINEERING

14 a) Let g be the function given by (8)

"
i. Calculate the partial derivatives of g at (0 , 0).
i. Calculate the partial derivatives of g at (0 , 0).
ii.
ii. Show
Showthatthatggisisnot
notdifferentiable
differentiableatat(0
(0,,0).
0).
b) Find the second order Taylor series expansion for f(x,y) = e-(x2+y2) cos(xy) about (0 , (6)
b) Find the second order Taylor series expansion for f(x,y) = e-(x2+y2) cos(xy) (6)
0).
aboutare
15 a) There (0 ,two
0). bags. The first bag contains four mangos and two apples; the second (6)
15 a) There
bag are twofour
contains bags. The first
mangos andbag
fourcontains
apples. four mangos
We also haveand two apples;
a biased (6)
coin, which
the second
shows bagwith
“heads” contains four mangos
probability 0.6 andand fourwith
“tails” apples. We also0.4.
probability haveIf athe coin
biased coin, which shows “heads” with probability 0.6 and “tails” with
probability 0.4. If the coin shows “heads”. we pick a fruit at

showsrandom
“heads”.from bag 1;
we pick otherwise
a fruit at we pick a fruit at random from bag 2. Your
random fromflips
friend bag the
1; otherwise
coin (youwe pick see
cannot a fruit
theatresult),
random froma bag
picks fruit2.atYour friend
random
flips the coin (you cannot see the result), picks a fruit at random from the
from the corresponding bag, and presents you a mango.
corresponding bag, and presents you a mango.
What What
is the is the probability
probability that
that the the mango
mango was picked
was picked from2?bag 2?
from bag
b) b)
Suppose that one
Suppose thathasone
written
has awritten
computer program that
a computer sometimes
program compiles and (8)(8)
that sometimes
sometimes notand
compiles (code does not
sometimes change).
not (code doesYou decide toYou
not change). model
decidethe apparent
to model
stochasticity (success vs. no success) x of the compiler using a Bernoulli
the apparent stochasticity (success vs. no success) x of the compiler using
distribution with parameter μ:
a Bernoulli distribution with parameter μ:

"
Choose a conjugate prior for the Bernoulli likelihood and compute the posterior
Choose a conjugate prior for the Bernoulli likelihood and compute the
distribution p( μ | x1 , ... , xN).
posterior distribution p( μ | x1 , ... OR
, xN).

OR
16 a) Consider a mixture of two Gaussian distributions (8)

i. Compute the marginal distributions for each dimension.

ii. Compute the mean, mode and median for each marginal distribution.
iii. Compute the mean and mode for the two-dimensional distribution.

b) Express the Binomial distribution as an exponential family distribution. Also (6)

express the Beta distribution is an exponential family distribution. Show that the
Choose a conjugate
distribution prior μ:
with parameter for the Bernoulli likelihood and compute the posterior
distribution p( μ | x1 , ... , xN).
OR
COMPUTER SCIENCE AND ENGINEERING
Choose a conjugate prior for the Bernoulli likelihood and compute the posterior
16 a) Consider a mixture of two Gaussian distributions (8)
16 a) Consider a mixture of two Gaussian distributions (8)
distribution p( μ | x1 , ... , xN).
OR

16 a) Consider a mixture of two Gaussian distributions (8)

"

i. i.Compute
Compute the the marginal
marginal distributions
distributions for for
eacheach dimension.
dimension.
ii. ii.
Compute
Compute the mean, mode and
the mean, modemedian
andformedian
each marginal
for eachdistribution.
marginal
iii. Compute the mean and mode for the two-dimensional distribution.
distribution.
i. Compute
b) Express the marginal distributions for each dimension.
iii.the Binomial
Compute the distribution
mean and mode as an
for exponential family distribution.
the two-dimensional distribution. Also (6)
ii. Compute the mean, mode and median for each marginal distribution.
express the Betathedistribution
iii. Compute mean and mode is an for
exponential family distribution.
the two-dimensional Show that the
distribution.
product of the Beta and the Binomial distribution is also a member of the
b) b)Express
Express the Binomial
the Binomial distribution
distribution as anas exponential
an exponential family
family distribution.
distribution. Also (6)(6)
exponential family.
FindAlso
17 a) express the express
theextrema thef(x,y,z)
of Beta distribution
Beta distribution =isxan is an exponential
- yexponential
+ z subject family =family
x2 + y2 distribution.
distribution.
to g(x,y,z) +Show that the
z2 = 2. (8)
b) product
Let Show of that
the the
Betaproduct
and theof the Beta and
Binomial the Binomial
distribution distribution
is also a member is also
of athe (6)

exponential
memberfamily.
of the exponential family.
17 a) Find the extrema of f(x,y,z) = x - y + z subject to g(x,y,z) = x2 + y2 + z2 = 2. (8)
17b) a)Let Find the extrema of f(x,y,z) = x - y + z subject to g(x,y,z) = x2 + y2 + z2 = (8)(6)
2.
b) Let

Show
" that x* = (1 , 1/2 , -1) is optimal for the optimization problem
Show that x* = (1 , 1/2 , -1) is optimal for the optimization problem

(6)
OR
18 a) Derive the gradient descent trainingOR
rule assuming that the target function (8)
18 a) Derive the gradient descent training rule assuming that the target function is (8)
is represented as od = w0 + w1x1 + ... + wnxn. Define explicitly the cost/
represented as od = w0 + w1x1 + ... + wnxn. Define explicitly the cost/error function
error function E, assuming that a set of training examples D is provided,
E, assuming that a set of training examples D is provided, where each training
where each training example d ∈ D is associated with the target output td.
example d ∈ D is associated with the target output td.

b) Find the maximum value of f(x,y,z) = xyz given that g(x,y,z) = x + y + z = 3 and (6)
x,y,z >= 0.
19 a) Consider the following probability distribution (7)
18 a) Derive the gradient
represented as od = wdescent
0 + w1x1 training
+ ... + wnrule assuming
xn. Define that the
explicitly target function
the cost/error is (8)
function
represented od =a wset
E, assumingasthat 0 +of
w1training
x1 + ... +examples
wnxn. Define
D isexplicitly
provided,thewhere
cost/error
each function
training
E, assuming
example d ∈ that
D is aassociated
set of training examples
with the D is tprovided,
target output d. where each training
COMPUTER
example d ∈ D is associated with the target output td. SCIENCE AND ENGINEERING
b) Find the maximum value of f(x,y,z) = xyz given that g(x,y,z) = x + y + z = 3 and (6)
b) Find the maximum value of f(x,y,z) = xyz given that g(x,y,z) = x + y + z = (6)
b) Find
x,y,z the maximum value of f(x,y,z) = xyz given that g(x,y,z) = x + y + z = 3 and (6)
>= 0.
19 a) x,y,z 3
Considerand x,y,z >= 0.
>= 0.the following probability distribution (7)
19 19
a) a)Consider the following
Consider probability
the following distribution
probability distribution (7) (7)

where θ is a parameter and x is a positive real number. Suppose you get m i.i.d.
where
where
samples is a parameter
θ isxi aθdrawn
parameter and
andthis
from xaispositive
a positive
x isdistribution. real
real number.
number.
Compute Suppose
Suppose
the you
maximumyou getmmi.i.d.
get
likelihood
samples
i.i.d.xfor
estimator drawn
isamples xfrom
θ based thisfrom
drawn
i on these distribution. ComputeCompute
this distribution.
samples. the maximum likelihood
the maximum
estimator for θ based
likelihood on these
estimator for θsamples.
based on these samples.
b) b)Consider the following
Consider Bayesian
the following network
Bayesian with with
network boolean variables.
boolean variables. (7) (7)
b) Consider the following Bayesian network with boolean variables. (7)

i. List variable(s) conditionally independent of X33 given X11 and X12

ii. List variable(s) conditionally independent of X33 and X22
iii. Write the joint probability P(X11, X12, X13, X21, X22, X31, X32, X33)
factored according to the Bayes net. How many parameters are
necessary to define the conditional probability distributions for
this Bayesian network?
iv. Write an expression for P(X13 = 0,X22 = 1,X33 = 0) in terms of the
conditional probability distributions given in your answer to part
(iii). Justify your answer.

OR
Justify your answer.

OR
20 a) Consider the following one dimensional COMPUTER
training data set,SCIENCE
’x’ denotes AND
negative (6)
ENGINEERING
examples and ’o’ positive examples. The exact data points and their labels are
20 a) Consider the following one dimensional training data set, ’x’ denotes (6)
given in the table below. Suppose a SVM is used to classify this data.
negative examples and ’o’ positive examples. The exact data points and
their labels are given in the table below. Suppose a SVM is used to
classify this data.

"
i. Indicate which arewhich
i. Indicate the support vectors
are the andvectors
support mark theand
decision
mark boundary.
the decision
ii. Give the value of the cost function and the model parameter after training.
b) Supposeboundary.
that we are fitting a Gaussian mixture model for data items (8)
consisting of athe
ii. Give single
valuereal value,
of the costx,function
using K and
= 2 components. We haveafter
the model parameter N=
5 training cases, in which the values of x are as 5, 15, 25, 30, 40. Using the
training.
EM algorithm to find the maximum likeihood estimates for the model
parameters, what are the mixing proportions for the two components, π1
and π2, and the means for the two components, μ1 and μ2. The standard
deviations for the two components are fixed at 10.
COMPUTER SCIENCE AND ENGINEERING
b) Suppose that we are fitting a Gaussian mixture model for data (8)
items consisting of a single real value, x, using K = 2 components.
We have N = 5 training cases, in which the values of x are as 5,
15, 25, 30, 40. Using the EM algorithm to find the maximum
likeihood estimates for the model parameters, what are the mixing
proportions for the two components, π1 and π2, and the means for
the two components, µ1 and µ2. The standard deviations for the
two components are fixed at 10.
Suppose that at some point in the EM algorithm, the E step found
Suppose that at some point in the EM algorithm, the E step found that the
that the responsibilities of the two components for the five data
responsibilities of the two components for the five data items were as
items were as follows:
follows:

"
What values for the parameters π1, π2 , µ1, and µ2 will be found in
What
the nextvalues forofthe
M step algorithm?π1, π2 , μ1, and μ2 will be found in the next
theparameters
M step of the algorithm? ****
****
COMPUTER SCIENCE AND ENGINEERING

Teaching Plan
No. of
Lectures
No Topic
(45)

1 Module-I (LINEAR ALGEBRA) 8

1. Systems of Linear Equations – Matrices, Solving Systems of Linear
1
Equations. Vector Spaces - Linear Independence.
2. Vector Spaces - Basis and Rank 1
3. Linear Mappings 1

4. Norms, Inner Products, Lengths and Distances, Angles and

1
Orthogonality, Orthonormal Basis, Orthogonal Complement
5. Orthogonal Projections, Matrix Decompositions, Determinant and 1
Trace.
6. Eigenvalues and Eigenvectors 1

7. Cholesky Decomposition, Eigen decomposition and Diagonalization 1

8. Singular Value Decomposition - Matrix Approximation 1
Module-II (VECTOR CALCULUS) 6

1 Differentiation of Univariate Functions, Partial Differentiation and 1

Gradients

2 Gradients of Vector Valued Functions, Gradients of Matrices 1

3 Useful Identities for Computing Gradients 1

4 Backpropagation and Automatic Differentiation 1

5 Higher Order Derivatives 1

6 Linearization and Multivariate Taylor Series 1

3 Module-III (Probability and Distributions) 10

1 Construction of a Probability Space - Discrete and Continuous 1
Probabilities (Lecture 1)
COMPUTER SCIENCE AND ENGINEERING
2 Construction of a Probability Space - Discrete and Continuous 1
Probabilities (Lecture 2)
3 Sum Rule, Product Rule 1
4 Bayes’ Theorem 1
5 Summary Statistics and Independence 1
6 Important probability Distributions (Lecture 1) 1
7 Important probability Distributions (Lecture 2) 1
8 Conjugacy and the Exponential Family (Lecture 1) 1
9 Conjugacy and the Exponential Family (Lecture 2) 1
10 Change of Variables/Inverse Transform 1
4 Module-IV (Optimization) 7
1 Optimization Using Gradient Descent. 1
2 Gradient Descent With Momentum, Stochastic Gradient Descent 1
3 Constrained Optimization and Lagrange Multipliers (Lecture 1) 1
4 Constrained Optimization and Lagrange Multipliers (Lecture 2) 1
5 Convex Optimization 1
6. Linear Programming 1

7. Quadratic Programming 1
5 Module-V (CENTRAL MACHINE LEARNING PROBLEMS) 14

1. Data and Learning models - Empirical Risk Minimization, 1

2. Parameter Estimation 1

3. Directed Graphical Models 1

4. Linear Regression 1

5. Bayesian Linear Regression 1

6. Maximum Likelihood as Orthogonal Projection 1

7. Dimensionality Reduction with Principal Component Analysis - 1

Maximum Variance Perspective, Projection Perspective.
8. Eigenvector Computation and Low Rank Approximations 1

9. Density Estimation with Gaussian Mixture Models 1

COMPUTER SCIENCE AND ENGINEERING
10. Parameter Learning via Maximum Likelihood 1
11. EM Algorithm 1

12. Classification with Support Vector Machines - Separating 1

Hyperplanes
13. Primal Support Vector Machines, Dual Support Vector Machines 1

14. Kernels 1

*Assignments may include applications of the above theory. With respect to module V,
programming assignments may be given.
COMPUTER SCIENCE AND ENGINEERING

YEAR OF
Category L T P CREDIT
CST Principles of Program INTRODUCTION
2 6 Analysis and Verification
HONOURS 3 1 0 4 2019

Preamble: This is the foundational course for awarding B. Tech. Honours in Computer Science
and Engineering with specialization in Formal Methods. Program Analysis and Program
Verification are two important areas of study, discussing Methods, Technologies and Tools to
ensure reliability and correctness of software systems. The syllabus for this course is prepared
with the view of introducing the Foundational Concepts, Methods and Tools in Program Analysis
and Program Verification.

Prerequisite: Topics covered in the course Discrete Mathematical Structures (MAT 203).

Course Outcomes: After the completion of the course the student will be able to

Explain the concepts and results about Lattices, Chains, Fixed Points, Galois
Connections, Monotone and Distributive Frameworks, Hoare Triples, Weakest
CO1
Preconditions, Loop Invariants and Verification Conditions to perform Analysis and
Verification of programs (Cognitive knowledge level: Understand)

Illustrate methods for doing intraprocedural/interprocedural Data flow Analysis for a

CO2
given Program Analysis problem (Cognitive knowledge level: Analyse)
Formulate an Abstract Interpretation framework for a given Data flow Analysis
CO3 problem and perform the analysis using the tool WALA (Cognitive knowledge level:
Analyse)

Use Kildall’s Algorithm to perform Abstract Interpretation of Programs and compare

CO4 the results obtained by the Algorithm on Monotone and Distributive Frameworks
(Cognitive knowledge level: Apply)
Explain the concept of Loop Invariants and use them in Hoare Triple based Weakest
CO5 Precondition analysis to verify the total correctness of a code segment (Cognitive
knowledge level: Apply)

Use the tool VCC to specify and verify the correctness of a C Program with respect to
CO6
a given set of properties (Cognitive knowledge level: Analyse)

1
COMPUTER SCIENCE AND ENGINEERING

Mapping of course outcomes with program outcomes

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12

CO1

CO2

CO3

CO4

CO5

CO6

Abstract POs defined by National Board of Accreditation

PO# Broad PO PO# Broad PO

PO1 Engineering Knowledge PO7 Environment and Sustainability

PO2 Problem Analysis PO8 Ethics

PO3 Design/Development of solutions PO9 Individual and team work

Conduct investigations of complex

PO4 PO10 Communication
problems

PO5 Modern tool usage PO11 Project Management and Finance

PO6 The Engineer and Society PO12 Life long learning

2
COMPUTER SCIENCE AND ENGINEERING

Assessment Pattern:

Continuous Assessment Tests

End Semester
Bloom’s Category Test 1 Test 2 Examination Marks
(Percentage) (Percentage)
Remember 30 30 30

Understand 30 30 30
Apply 40 40 40

Analyze
Evaluate

Create

Mark Distribution

Total Marks CIE Marks ESE Marks ESE Duration

150 50 100 3 hours

Continuous Internal Evaluation Pattern:

Attendance : 10 Marks

Continuous Assessment Tests : 25 Marks

Assignment : 15 Marks

Internal Examination Pattern:

Each of the two internal examinations has to be conducted out of 50 marks

First series test shall be preferably conducted after completing the first half of the syllabus and
the second series test shall be preferably conducted after completing the remaining part of the
syllabus.

3
COMPUTER SCIENCE AND ENGINEERING

There will be two parts: Part A and Part B. Part A contains 5 questions (preferably, 2 questions
each from the completed modules and 1 question from the partly covered module), having 3
marks for each question adding up to 15 marks for part A. Students should answer all questions
from Part A. Part B contains 7 questions (preferably, 3 questions each from the completed
modules and 1 question from the partly covered module), each with 7 marks. Out of the 7
questions in Part B, a student should answer any 5.

End Semester Examination Pattern:

There will be two parts; Part A and Part B. Part A contains 10 questions with 2 questions from
each module, having 3 marks for each question. Students should answer all questions from Part
A. Part B contains 2 questions from each module of which a student should answer any one, each
question carries 14 marks. Each question in part B can have a maximum 2 sub-divisions.

SYLLABUS

Module 1

Mathematical Foundations – Partially Ordered Set, Complete Lattice, Construction of

Complete Lattices, Chains, Fixed Points, Knaster-Tarski Fixed Point Theorem.

Module 2

Introduction to Program Analysis – The WHILE language, Reaching Definition Analysis, Data
Flow Analysis, Abstract Interpretation, Algorithm to find the least solutions for the Data Flow
Analysis problem.

Module 3

Intraprocedural DataFlow Analysis – Available Expressions Analysis, Reaching Definitions

Analysis, Very Busy Expressions Analysis, Live Variable Analysis, Derived Data Flow
Information, Monotone and Distributive Frameworks, Equation Solving - Maximal Fixed Point
(MFP) and Meet Over all Paths (MOP) solutions.

Interprocedural Data Flow Analysis - Structural Operational Semantics, Intraprocedural versus

Interprocedural Analysis, Making Context Explicit, Call Strings as Context, Flow Sensitivity
versus Flow Insensitivity, Implementing Interprocedural Data-flow Analysis using the Tool
WALA.

4
COMPUTER SCIENCE AND ENGINEERING

Module 4

Abstract Interpretation - A Mundane Approach to Correctness, Approximations of Fixed

Points, Galois Connections, Systematic Design of Galois Connections, Induced Operations,
Kildall’s Algorithm for Abstract Interpretation.

Module 5

Program Verification - Why should we Specify and Verify Code, A framework for software
verification - A core programming Language, Hoare Triples, Partial and Total Correctness,
Program Variables and Logical Variables, Proof Calculus for Partial Correctness, Loop
Invariants, Verifying code using the tool VCC (Verifier for Concurrent C).

Text Books

1. Flemming Nielson, Henne Nielson and Chris Kankin, Principles of Program Analysis,
Springer (1998).
2. Michael Hutch and Mark Ryan, Logic in Computer Science - Modeling and Reasoning
about Systems, Cambridge University Press, Second Edition.

References

1. Julian Dolby and Manu Sridharan, Core WALA Tutorial (PLDI 2010), available online at
http://wala.sourceforge.net/files/PLDI_WALA_Tutorial.pdf

2. Ernie & Hillebrand, Mark & Tobies, Stephan (2012), Verifying C Programs: A VCC
Tutorial.

5
COMPUTER SCIENCE AND ENGINEERING

Sample Course Level Assessment Questions

Course Outcome1 (CO1):

1. Find a lattice to represent the data states of a given program and propose a sound abstract
interpretation framework to do a given analysis on the program.
2. When is an abstract interpretation framework said to be sound? Illustrate with an
example.
3. When is an abstract interpretation framework said to be precise? Illustrate with an
example.

Course Outcome2 (CO2):

1. Illustrate how one can do Intraprocedural Available Expression Analysis on a program.

2. Illustrate how one can do Intraprocedural Reaching Definition Analysis on a program.
3. Illustrate how one can do Intraprocedural Live Variable Analysis on a program.

Course Outcome3 (CO3):

1. Illustrate how one can do Interprocedural Data Flow Analysis using the tool WALA.

Course Outcome4 (CO4):

1. Illustrate the working of Kildall’s algorithm to do Intraprocedural Available Expression

Analysis on a program.
2. Compare the results obtained by applying Kildall’s algorithms for Abstract Interpretation
in Monotone and Distributive Frameworks.

Course Outcome5 (CO5):

1. Illustrate the process of obtaining verification conditions (VCs) using weakest

precondition analysis.
2. Explain the concepts of partials and total correctness of programs.
3. Explain the necessity of obtaining loop invariants in verifying the total correctness of a
program.

Course Outcome6 (CO6):

1. Using the tool VCC prove that a given code segment satisfies a given property.

6
COMPUTER SCIENCE AND ENGINEERING

Model Question paper

QP CODE: PAGES:3

Reg No:______________ Name :______________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

4th SEMESTER B.TECH DEGREE (HONOURS) EXAMINATION, MONTH & YEAR

Course Code: CST 2 6

Course Name: Principles of Program Analysis and Verification

Max.Marks:100 Duration: 3 Hours

PART A

Answer all Questions. Each question carries 3 Marks

1. What is a complete lattice? Give an example of a complete lattice.

2. Show that every chain is a lattice.
3. Write a program in while language to find the factorial of a number. Explain the
statements of your program.
4. Consider a program that calculates x! y through repeated multiplications. Draw the flow
graph of the program.
5. What is Available Expression (AE) analysis? Give an application for AE analysis.
6. What is Live variable (LV) analysis? Give an application for LV analysis.
7. Let P be a program analysis problem (like LV, AE etc.) and (A,
! FA, γAC ) and (B,
! FB, γBC )
be two abstract interpretations such that B ! is more abstract than A! . Let α
! and γ! be the
abstraction and concretization functions between A ! and B
! . Then, what are the conditions
required for !α and !γ to form a Galois Connection?
8. When is Kildall’s algorithm for abstract interpretation guaranteed to terminate? Justify
your answer.
9. Is it possible to verify total correctness of a program using Hoare Logic? If yes, how is it
possible?
10. Define loop invariant. Show a simple loop with a loop invariant.

7
COMPUTER SCIENCE AND ENGINEERING

PART B
Answer any one Question from each module. Each question carries 14 Marks

11.
a. What is an infinite ascending chain in a lattice? Show an example lattice with an
infinite ascending chain. Is it possible for a complete lattice to contain an infinite
ascending chain? (7 marks)
b. State and prove Knaster-Tarski fixed point theorem. (7 marks)

OR

12.
a. Consider the lattice (ℕ,! ≤ ) . Let f! : ℕ → ℕ , be a function defined as follows:
when x! < 100 , f! (x) = x + 1 , when x! > 100 , f! (x) = x − 1 , otherwise f! (x) = x .
Then, show the following for f! : (i) the set of all fixpoints, (ii) the set of all pre-
fixpoints and (iii) the set of all post-fixpoints. (7 marks)
b. Let (D,
! ≤ ) be a lattice with a least upper bound for each subset of D ! . Then, prove
that every subset of D! has a greatest lower bound. (7 marks)
13.
a. With a suitable example, explain the equational approach in Data Flow Analysis.
(7 marks)
b. With a suitable example, explain how you obtain the collecting semantics of a
program point. (7 marks)

OR
14.
a. With an example, explain the Constrained Based Approach in Data Flow
Analysis. (7 marks)
b. Discuss the properties of an algorithm to solve the problem of computing the least
solution to the program analysis problems in Data Flow Analysis. (7 marks)
15.
a. Using Intraprocedural Reaching Definition Analysis, find the assignments killed
and generated by each of the blocks in the program
[x:=5]1;
[y:=1]2 ;
while [x>1]3 do
([y:=x*y]4 ; [x:=x-1]5)
(7 marks)
b. Analyse the following program using Intraprocedural Very Busy Expression
analysis

8
COMPUTER SCIENCE AND ENGINEERING

if [a>b]1 then
([x: =b-a]2 ; [y: =a-b]3)
else
([y: =b-a]4; [x: =a-b]5)
(7 marks)

OR
16.
a. Find Maximal Fixed Point (MFP) solution for the program
[x: =a+b]1;
[y: =a*b]2 ;
while [y>a+b]3 do
([a: =a+l]4; [x: =a+b]5)
(7 marks)
b. With examples, explain the difference between flow sensitive and flow insensitive
analysis. (7 marks)
17.
a. Prove that (L,
! α, γ, M ) is an adjunction if and only if (L,
! α, γ, M ) is a Galois
connection. (7 marks)
b. Prove that if α
! : L → M is completely additive then there exists γ! : M → L such
that (L,
! α, γ, M ) is a Galois connection. Similarly, if γ! : M → L is completely
multiplicative then there exists α! : L → M such that (L,! α, γ, M ) is a Galois
connection. (7 marks)

OR
18.
a. Show that if (Li, αi, γi, Mi) are Galois connections and βi : Vi ➝ Li are
representation functions then
((α1 o β1) ↠ (α2 o β2)) (↝) = α2 o ((β1 ↠ β2) (↝)) o γ1
(7 marks)
b. Briefly explain Kildall’s algorithm for abstract interpretation (7 marks)
19.
a. Briefly explain the need of specification and verification of code. (7 marks)
b. Argue that Hoare Logic is sound. When Hoare Logic is complete? Let {A}P{B}
be a Hoare triple such that Hoare Logic is complete for the program P. Then, is it
always possible to check the validity of the Hoare Triple? If not, what is the
difficulty? (7 marks)
OR
20.
a. With suitable examples, show the difference between partial and total correctness.
(7 marks)
b. With a suitable example, show how a basic program segment can be verified
using the tool VCC. (7 marks)

9
COMPUTER SCIENCE AND ENGINEERING

Teaching Plan
Module 1 (Mathematical Foundations) 6 Hours

1.1 Partially Ordered Set 1 Hour

1.2 Complete Lattice, Construction of Complete Lattices 1 Hour

1.3 Chains 1 Hour

1.4 Fixed Points 1 Hour

1.5 Knaster-Tarski Fixed Point Theorem 1 Hour

1.6 Proof of Knaster-Tarski Fixed Point Theorem 1 Hour

Module 2 (Introduction to Program Analysis) 5 Hours

2.1 The WHILE language 1 Hour

2.2 Data Flow Analysis 1 Hour

2.3 Reaching Definition Analysis 1 Hour

2.4 Abstract Interpretation 1 Hour

2.5 Algorithm to find the least solutions for the Data Flow Analysis problem 1 Hour

Module 3 (Data flow Analysis) 15 Hours

3.1 Available Expressions Analysis, Reaching Definitions Analysis 1 Hour

3.2 Very Busy Expressions Analysis 1 Hour

3.3 Live Variable Analysis 1 Hour

3.4 Derived Data Flow Information 1 Hour

3.5 Monotone and Distributive Frameworks 1 Hour

3.6 Equation Solving - MFP Solution 1 Hour

10
COMPUTER SCIENCE AND ENGINEERING

3.7 Equation Solving - MOP Solution 1 Hour

3.8 Structural Operational Semantics (Lecture 1) 1 Hour

3.9 Structural Operational Semantics (Lecture 2) 1 Hour

3.10 Intraprocedural versus Interprocedural Analysis 1 Hour

3.11 Making Context Explicit 1 Hour

3.12 Call Strings as Context 1 Hour

3.13 Flow Sensitivity versus Flow Insensitivity 1 Hour

Implementing Interprocedural Dataflow Analysis using the Tool WALA

3.14 1 Hour
(Lecture 1)
Implementing Interprocedural Dataflow Analysis using the Tool WALA
3.15 1 Hour
(Lecture 2)
Module 4 (Abstract Interpretation) 8 Hours

4.1 A Mundane Approach to Correctness 1 Hour

4.2 Approximations of Fixed Points 1 Hour

4.3 Galois Connections, 1 Hour

4.4 Systematic Design of Galois Connections (Lecture 1) 1 Hour

4.5 Systematic Design of Galois Connections (Lecture 2) 1 Hour

4.6 Induced Operations 1 Hour

4.7 Kildall’s Algorithm for Abstract Interpretation (Lecture 1) 1 Hour

4.8 Kildall’s Algorithm for Abstract Interpretation (Lecture 2) 1 Hour

Module 5 (Program Verification) 11 Hours

5.1 Why should we Specify and Verify Code 1 Hour

5.2 A framework for software verification - A core programming Language 1 Hour

11
COMPUTER SCIENCE AND ENGINEERING

5.3 Hoare Triples (Lecture 1) 1 Hour

5.4 Hoare Triples (Lecture 2) 1 Hour

5.5 Partial and Total Correctness 1 Hour

5.6 Program Variables and Logical Variables 1 Hour

5.7 Proof Calculus for Partial Correctness 1 Hour

5.8 Loop Invariants 1 Hour

5.9 Verifying C programs using the tool VCC (Lecture 1) 1 Hour

5.10 Verifying C programs using the tool VCC (Lecture 2) 1 Hour

5.11 Verifying C programs using the tool VCC (Lecture 3) 1 Hour

12