**Download Soft Copies of Syllabus in PDF format –**

ENGINEERING MATHEMATICS – 4 Syllabus

**Check VTU 4th Semester Results**

### ENGINEERING MATHEMATICS – IV

Subject Code : 10MAT41

IA Marks : 25

Hours/Week : 04 Exam Hours : 03

Total Hours : 52 Exam Marks : 100

**PART-A**

Unit-I: NUMERICAL METHODS – 1 [6 hours]

Numerical solution of ordinary differential equations of first order and first degree; Picard’s method, Taylor’s series method, modified Euler’s method, Runge-kutta method of fourth-order. Milne’s and Adams – Bashforthpredictor and corrector methods (No derivations of formulae).

Unit-II: NUMERICAL METHODS – 2 [6 hours]

Numerical solution of simultaneous first order ordinary differential equations: Picard’s method, Runge-Kutta method of fourthorder.

Numerical solution of second order ordinary differential equations: Picard’s method, Runge-Kutta method and Milne’s method.

Unit-III: Complex variables – 1 [7 hours]

Function of a complex variable, Analytic functions-Cauchy-Riemann equations in cartesian and polar forms. Properties of analytic functions. Application to flow problems- complex potential, velocity potential, quipotential lines, stream functions, stream lines.

Unit-IV: Complex variables – 2 [7 hours]

Conformal Transformations: Bilinear Transformations. Discussion of Transformations: w z2, w = ez , w z (a2 / z) . Complex line integrals- Cauchy’s theorem and Cauchy’s integral formula.

**PART – B**

Unit-V: SPECIAL FUNCTIONS [7 hours]

Solution of Laplace equation in cylindrical and spherical systems leading Bessel’s and Legendre’s differential equations, Series solution of Bessel’s differential equation leading to Bessel function of first kind. Orthogonal property of Bessel functions. Series solution of Legendre’s differential equation leading to Legendrepolynomials, Rodrigue’s formula.

Unit-VI: PROBABILITY THEORY – 1 [6 hours]

Probability of an event, empherical and axiomatic definition, probability associated with set theory, addition law, conditional probability, multiplication law, Baye’s theorem.

Unit-VII: PROBABILITY THEORY- 2 [7 hours]

Random variables (discrete and continuous), probability density function, cumulative density function. Probability distributions – Binomial and Poisson distributions; Exponential and normal distributions.

Unit-VIII: SAMPLING THEORY [6 hours]

Sampling, Sampling distributions, standard error, test of hypothesis for means, confidence limits for means, student’s tdistribution. Chi –Square distribution as a test of goodness of fit

**Text Books:**

1. B.S. Grewal, Higher Engineering Mathematics, Latest edition, Khanna Publishers

2. Erwin Kreyszig, Advanced Engineering Mathematics, Latest edition, Wiley Publications.

**Reference Book:**

1. B.V. Ramana, Higher Engineering Mathematics, Latest edition, Tata Mc. Graw Hill Publications.

2. Peter V. O’Neil, Engineering Mathematics, CENGAGE Learning India Pvt Ltd. Publishers

### COMPUTER ORGANIZATION

Subject Code : 10CS46

(Common to CSE & ISE)

IA Marks : 25

Hours/Week : 04 Exam Hours : 03

Total Hours : 52 Exam Marks : 100

**PART – A**

UNIT – 1 6 Hours

Basic Structure of Computers: Computer Types, Functional Units, Basic Operational Concepts, Bus Structures, Performance – Processor Clock, Basic Performance Equation, Clock Rate, Performance Measurement, Historical Perspective.

Machine Instructions and Programs: Numbers, Arithmetic Operations and Characters, Memory Location and Addresses,

Memory Operations, Instructions and Instruction Sequencing.

UNIT – 2 7 Hours

Machine Instructions and Programs contd.: Addressing Modes, Assembly Language, Basic Input and Output Operations, Stacks

and Queues, Subroutines, Additional Instructions, Encoding of Machine Instructions

UNIT – 3 6 Hours

Input/output Organization: Accessing I/O Devices, Interrupts – Interrupt Hardware, Enabling and Disabling Interrupts, Handling

Multiple Devices, Controlling Device Requests, Exceptions, Direct Memory Access, Buses

UNIT – 4 7 Hours

Input/output Organization contd.: Interface Circuits, Standard I/O Interfaces – PCI Bus, SCSI Bus, USB

**PART – B**

UNIT – 5 7 Hours

Memory System: Basic Concepts, Semiconductor RAM Memories, Read Only Memories, Speed, Size, and Cost, Cache

Memories–Mapping Functions, Replacement Algorithms, Performance Considerations, Virtual Memories, Secondary Storage

UNIT – 6 7 Hours

Arithmetic: Addition and Subtraction of Signed Numbers, Design of Fast Adders, Multiplication of Positive Numbers, Signed Operand Multiplication, Fast Multiplication, Integer Division, Floating-point Numbers and Operations

UNIT – 7 6 Hours

Basic Processing Unit: Some Fundamental Concepts, Execution of a Complete Instruction, Multiple Bus Organization, Hard-wired

Control and Micro programmed Control

UNIT – 8 6 Hours

Multicores, Multiprocessors, and Clusters: Performance, The Power Wall, The Switch from Uniprocessors to Multiprocessors, Amdahl’s Law, Shared Memory Multiprocessors, Clusters and other Message Passing, Multiprocessors, Hardware Multithreading, SISD, IMD, SIMD, SPMD, and Vector.

**Text Books:**

1. Carl Hamacher, Zvonko Vranesic, Safwat Zaky: Computer Organization, 5th Edition, Tata McGraw Hill, 2002. (Listed topics only from Chapters 1, 2, 4, 5, 6, 7)

2. David A. Patterson, John L. Hennessy: Computer Organization and Design – The Hardware / Software Interface ARM Edition, 4th Edition, Elsevier, 2009. (Listed topics only)

**Reference Books:**

1. William Stallings: Computer Organization & Architecture, 7th Edition, PHI, 2006.

2. Vincent P. Heuring & Harry F. Jordan: Computer Systems Design and Architecture, 2nd Edition, Pearson Education, 2004.

### DESIGN AND ANALYSIS OF ALGORITHMS

Subject Code : 10CS43

(Common to CSE & ISE)

IA Marks : 25

Hours/Week : 04 Exam Hours : 03

Total Hours : 52 Exam Marks : 100

**PART – A**

UNIT – 1 7 Hours

INTRODUCTION: Notion of Algorithm, Review of Asymptotic Notations, Mathematical Analysis of Non-Recursive and Recursive Algorithms Brute Force Approaches: Introduction, Selection Sort and Bubble Sort, Sequential Search and Brute Force String Matching.

UNIT – 2 6 Hours

DIVIDE AND CONQUER: Divide and Conquer: General Method, Defective Chess Board, Binary Search, Merge Sort, Quick Sort and its performance.

UNIT – 3 7 Hours

THE GREEDY METHOD: The General Method, Knapsack Problem, Job Sequencing with Deadlines, Minimum-Cost Spanning Trees:

Prim’s Algorithm, Kruskal’s Algorithm; Single Source Shortest Paths.

UNIT – 4 6 Hours

DYNAMIC PROGRAMMING: The General Method, Warshall’s Algorithm, Floyd’s Algorithm for the All-Pairs Shortest Paths

Problem, Single-Source Shortest Paths: General Weights, 0/1 Knapsack, The Traveling Salesperson problem.

**PART – B**

UNIT – 5 7 Hours

DECREASE-AND-CONQUER APPROACHES, SPACE-TIME TRADEOFFS: Decrease-and-Conquer Approaches: Introduction, Insertion

Sort, Depth First Search and Breadth First Search, Topological Sorting Space-Time Tradeoffs: Introduction, Sorting by Counting, Input Enhancement in String Matching.

UNIT – 6 7 Hours

LIMITATIONS OF ALGORITHMIC POWER AND COPING WITH THEM: Lower-Bound Arguments, Decision Trees, P, NP, and NPComplete

Problems, Challenges of Numerical Algorithms.

UNIT – 7 6 Hours

COPING WITH LIMITATIONS OF ALGORITHMIC POWER:

Backtracking: n – Queens problem, Hamiltonian Circuit Problem, Subset – Sum Problem. Branch-and-Bound: Assignment

Problem, Knapsack Problem, Traveling Salesperson Problem. Approximation Algorithms for NP-Hard Problems – Traveling

Salesperson Problem, Knapsack Problem

UNIT – 8 6 Hours

PRAM ALGORITHMS: Introduction, Computational Model, Parallel Algorithms for Prefix Computation, List Ranking, and Graph Problems

**Text Books:**

1. Anany Levitin: Introduction to The Design & Analysis of Algorithms, 2nd Edition, Pearson Education, 2007.

(Listed topics only from the Chapters 1, 2, 3, 5, 7, 8, 10, 11).

2. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran: Fundamentals of Computer Algorithms, 2nd Edition, Universities Press, 2007. (Listed topics only from the Chapters 3, 4, 5, 13)

**Reference Books:**

1. Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, Clifford Stein: Introduction to Algorithms, 3rd Edition, PHI, 2010.

2. R.C.T. Lee, S.S. Tseng, R.C. Chang & Y.T.Tsai: Introduction to the Design and Analysis of Algorithms A Strategic Approach, Tata McGraw Hill, 2005.

### UNIX AND SHELL PROGRAMMING

Subject Code : 10CS44

(Common to CSE & ISE)

I.A. Marks : 25

Hours/Week : 04 Exam Hours : 03

Total Hours : 52 Exam Marks : 100

**PART – A**

UNIT – 1 6 Hours

The Unix Operating System, The UNIX architecture and Command Usage, The File System

UNIT – 2 6 Hours

Basic File Attributes, the vi Editor

UNIT – 3 7 Hours

The Shell, The Process, Customizing the environment

UNIT – 4 7 Hours

More file attributes, Simple filters

**PART – B**

UNIT – 5 6 Hours

Filters using regular expressions,

UNIT – 6 6 Hours

Essential Shell Programming

UNIT – 7 7 Hours

awk – An Advanced Filter

UNIT – 8 7 Hours

perl – The Master Manipulator

**Text Book:**

1. Sumitabha Das: UNIX – Concepts and Applications, 4th Edition, Tata McGraw Hill, 2006.

(Chapters 1.2, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 18, 19)

**Reference Books:**

1. Behrouz A. Forouzan and Richard F. Gilberg: UNIX and Shell Programming, Cengage Learning, 2005.

2. M.G. Venkateshmurthy: UNIX & Shell Programming, Pearson Education, 2005

### MICROPROCESSORS

Subject Code : 10CS45

(Common to CSE & ISE)

IA Marks : 25

Hours/Week : 04 Exam Hours : 03

Total Hours : 52 Exam Marks : 100

**PART A**

UNIT – 1 7 Hours

Introduction, Microprocessor Architecture – 1: A Historical Background, The Microprocessor-Based Personal Computer

Systems. The Microprocessor and its Architecture: Internal Microprocessor Architecture, Real Mode Memory Addressing.

UNIT – 2 7 Hours

Microprocessor Architecture – 2, Addressing Modes: Introduction to

Protected Mode Memory Addressing, Memory Paging, Flat Mode Memory Addressing Modes: Data Addressing Modes, Program

Memory Addressing Modes, Stack Memory Addressing Modes

UNIT – 3 6 Hours

Programming – 1: Data Movement Instructions: MOV Revisited, PUSH/POP, Load-Effective Address, String Data Transfers,

Miscellaneous Data Transfer Instructions, Segment Override Prefix, Assembler Details.

Arithmetic and Logic Instructions: Addition, Subtraction and Comparison, Multiplication and Division.

UNIT – 4 6 Hours

Programming – 2: Arithmetic and Logic Instructions (continued): BCD and ASCII Arithmetic, Basic Logic Instructions, Shift and Rotate, String Comparisons. Program Control Instructions: The Jump Group, Controlling the Flow of the Program, Procedures and Introduction to Interrupts Machine Control and Miscellaneous Instructions.

**PART B**

UNIT – 5 6 Hours

Programming – 3: Combining Assembly Language with C/C++: Using Assembly Language with C/C++ for 16-Bit DOS Applications

and 32-Bit Applications Modular Programming, Using the Keyboard and Video Display, Data Conversions, Example Programs

UNIT – 6 7 Hours

Hardware Specifications, Memory Interface – 1: Pin-Outs and the Pin Functions, Clock Generator, Bus Buffering and Latching, Bus Timings, Ready and Wait State, Minimum versus Maximum Mode. Memory Interfacing: Memory Devices

UNIT – 7 6 Hours

Memory Interface – 2, I/O Interface – 1: Memory Interfacing (continued): Address Decoding, 8088 Memory Interface, 8086

Memory Interface. Basic I/O Interface: Introduction to I/O Interface, I/O Port Address Decoding.

UNIT – 8 7 Hours

I/O Interface – 2, Interrupts, and DMA: I/O Interface (continued): The Programmable Peripheral Interface 82C55,

Programmable Interval Timer 8254. Interrupts: Basic Interrupt Processing, Hardware Interrupts: INTR and INTA/; Direct Memory Access: Basic DMA Operation and Definition.

**Text Book:**

1. Barry B Brey: The Intel Microprocessors, 8th Edition, Pearson Education, 2009.

(Listed topics only from the Chapters 1 to 13)

**Reference Books:**

1. Douglas V. Hall: Microprocessors and Interfacing, Revised 2nd Edition, TMH, 2006.

2. K. Udaya Kumar & B. S. Umashankar : Advanced Microprocessors & IBM-PC Assembly Language Programming, TMH 2003.

3. James L. Antonakos: The Intel Microprocessor Family: Hardware and Software Principles and Applications, Cengage

Learning, 2007.

### GRAPH THEORY AND COMBINATORICS

Subject Code : 10CS42

(Common to CSE & ISE)

IA Marks : 25

Hours/Week : 04 Exam Hours : 03

Total Hours : 52 Exam Marks : 100

**PART – A**

UNIT – 1 7 Hours

Introduction to Graph Theory: Definitions and Examples, Subgraphs, Complements, and Graph somorphism, Vertex Degree,

Euler Trails and Circuits

UNIT – 2 6 Hours

Introduction to Graph Theory contd.: Planar Graphs, Hamilton Paths and Cycles, Graph Colouring, and Chromatic Polynomials

UNIT – 3 6 Hours

Trees: Definitions, Properties, and Examples, Routed Trees, Trees and Sorting, Weighted Trees and Prefix Codes

UNIT – 4 7 Hours

Optimization and Matching: Dijkstra’s Shortest Path Algorithm, Minimal Spanning Trees – The algorithms of Kruskal and Prim,Transport Networks – Max-flow, Min-cut Theorem, Matching Theory

**PART – B**

UNIT – 5 6 Hours

Fundamental Principles of Counting: The Rules of Sum and Product, Permutations, Combinations – The Binomial Theorem,

Combinations with Repetition, The Catalon Numbers

UNIT – 6 6 Hours

The Principle of Inclusion and Exclusion: The Principle of Inclusion and Exclusion, Generalizations of the Principle,

Derangements – Nothing is in its Right Place, Rook Polynomials

UNIT – 7 7 Hours

Generating Functions: Introductory Examples, Definition and Examples – Calculational Techniques, Partitions of Integers, the Exponential Generating Function, the Summation Operator

UNIT – 8 7 Hours

Recurrence Relations: First Order Linear Recurrence Relation, The Second Order Linear Homogeneous Recurrence Relation with Constant Coefficients, The Non-homogeneous Recurrence Relation, The Method of Generating Functions

**Text Book:**

1. Ralph P. Grimaldi: Discrete and Combinatorial Mathematics, 5th Edition, Pearson Education, 2004.

(Chapter 11, Chapter 12.1 to 12.4, Chapter 13, Chapter 1, Chapter 8.1 to 8.4, Chapter 9 Chapter 10.1 to 10.4).

**Reference Books:**

1. D.S. Chandrasekharaiah: Graph Theory and Combinatorics, Prism, 2005.

2. Chartrand Zhang: Introduction to Graph Theory, TMH, 2006.

3. Richard A. Brualdi: Introductory Combinatorics, 4th Edition, Pearson Education, 2004.

4. Geir Agnarsson & Raymond Geenlaw: Graph Theory, Pearson Education, 2007.

### DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY

Subject Code : 10CSL47

(Common to CSE & ISE)

IA Marks : 25

Hours/Week : 03 Exam Hours : 03

Total Hours : 42 Exam Marks : 50

Design, develop and implement the specified algorithms for the following problems using C/C++ Language in LINUX/Windows environment.

1. Sort a given set of elements using the Quicksort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.

2. Using OpenMP, implement a parallelized Merge Sort algorithm to sort a given set of elements and determine the time

required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.

3. a. Obtain the Topological ordering of vertices in a given digraph. b. Compute the transitive closure of a given directed graph using Warshall’s algorithm.

4. Implement 0/1 Knapsack problem using Dynamic Programming.

5. From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra’s algorithm.

6. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal’s algorithm.

7. a. Print all the nodes reachable from a given starting node in a digraph using BFS method.

b. Check whether a given graph is connected or not using DFS method.

8. Find a subset of a given set S = {sl, s2,…..,sn} of n positive integers whose sum is equal to a given positive integer d. For example, if S= {1, 2, 5, 6, 8} and d = 9 there are two solutions {1,2,6}and{1,8}.A suitable message is to be displayed if the given problem instance doesn’t have a solution.

9. Implement any scheme to find the optimal solution for the Traveling Salesperson problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation.

10. Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.

11. Implement All-Pairs Shortest Paths Problem using Floyd’s algorithm. Parallelize this algorithm, implement it using OpenMP and determine the speed-up achieved.

12. Implement N Queen’s problem using Back Tracking.

**Note**: In the examination each student picks one question from the lot of all 12 questions.

### MICROPROCESSORS LABORATORY

Subject Code : 10CSL48

(Common to CSE & ISE)

IA Marks : 25

Hours/Week : 03 Exam Hours : 03

Total Hours : 42 Exam Marks : 50

Note:

- Develop and execute the following programs using 8086 Assembly Language. Any suitable assembler like MASM, TASM
- etc may be used.
- Program should have suitable comments.
- The board layout and the circuit diagram of the interface are to be provided to the student during the examination.

1. a) Search a key element in a list of ‘n’ 16-bit numbers using the Binary search algorithm.

b) Read the status of eight input bits from the Logic Controller Interface and display ‘FF’ if it is the parity of the input

read is even; otherwise display 00.

2. a) Write two ALP modules stored in two different files; one module is to read a character from the keyboard and the

other one is to display a character. Use the above two modules to read a string of characters from the keyboard

terminated by the carriage return and print the string on the display in the next line.

b) Implement a BCD Up-Down Counter on the Logic Controller Interface.

3. a) Sort a given set of ‘n’ numbers in ascending order using the Bubble Sort algorithm.

b) Read the status of two 8-bit inputs (X & Y) from the Logic Controller Interface and display X*Y.

4. a) Read an alphanumeric character and display its equivalent ASCII code at the canter of the screen.

b) Display messages FIRE and HELP alternately with flickering effects on a 7-segment display interface for a suitable period of time. Ensure a flashing rate that makes it easy to read both the messages (Examiner does not specify these delay values nor is it necessary for the student to compute these values).

5. a) Reverse a given string and check whether it is a palindrome or not.

b) Assume any suitable message of 12 characters length and display it in the rolling fashion on a 7-segment display

interface for a suitable period of time. Ensure a flashing rate that makes it easy to read both the messages. (Examiner does not specify these delay values nor is it necessary for the student to compute these values).

6. a) Read two strings, store them in locations STR1 and STR2. Check whether they are equal or not and display appropriate

messages. Also display the length of the stored strings.

b) Convert a 16-bit binary value (assumed to be an unsigned integer) to BCD and display it from left to right and right to left for specified number of times on a 7-segment display interface.

7. a) Read your name from the keyboard and display it at a specified location on the screen after the message “What is your name?” You must clear the entire screen before display.

b) Scan a 8 x 3 keypad for key closure and to store the code of the key pressed in a memory location or display on screen. Also display row and column numbers of the key pressed.

8. a) Compute nCr using recursive procedure. Assume that ‘n’ and ‘r’ are non-negative integers.

b) Drive a Stepper Motor interface to rotate the motor in specified direction (clockwise or counter-clockwise) by N steps (Direction and N are specified by the examiner). Introduce suitable delay between successive steps. (Any arbitrary value for the delay may be assumed by the student).

9. a) Read the current time from the system and display it in the standard format on the screen.

b) Generate the Sine Wave using DAC interface (The output of the DAC is to be displayed on the CRO).

10. a) Write a program to simulate a Decimal Up-counter to display 00-

b) Generate a Half Rectified Sine wave form using the DAC interface. (The output of the DAC is to be displayed on the CRO).

11. a) Read a pair of input co-ordinates in BCD and move the cursor to the specified location on the screen.

b) Generate a Fully Rectified Sine waveform using the DAC interface.

(The output of the DAC is to be displayed on the CRO).

12. a) Write a program to create a file (input file) and to delete an existing file.

b) Drive an elevator interface in the following way:

i. Initially the elevator should be in the ground floor, with all requests in OFF state.

ii. When a request is made from a floor, the elevator should move to that floor, wait there for a couple of seconds

(approximately), and then come down to ground floor and stop. If some requests occur during going up or coming

down they should be ignored.

**Note**: In the examination each student picks one question from the lot of all 12 questions.

[…] >> Refer Syllabus HerE << […]