VTU B.E 4th Semester Computer Science Syllabus

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.

7 Responses

Leave a reply