SYLLABUS

18 SCHEME  4TH SEMESTER SYLLABUS 

COMPLEX ANALYSIS, PROBABILITY AND STATISTICAL METHODS (18MAT41)

Module-1

Calculus of complex functions: Review of function of a complex variable, limits, continuity, and

differentiability. Analytic functions: Cauchy-Riemann equations in Cartesian and polar forms and

consequences.

Construction of analytic functions: Milne-Thomson method-Problems.

Module-2

Conformal transformations: Introduction. Discussion of transformations .Bilinear transformations- Problems.Complex integration: Line integral of a complex function-Cauchy’s theorem and Cauchy’s integral formula and problems.

Module-3

Probability Distributions: Review of basic probability theory. Random variables (discrete and continuous), probability mass/density functions. Binomial, Poisson, exponential and normal distributions- problems (No derivation for mean and standard deviation)-Illustrative examples.

Module-4

Statistical Methods: Correlation and regression-Karl Pearson’s coefficient of correlation and rank correlation -problems. Regression analysis- lines of regression –problems.

Curve Fitting: Curve fitting by the method of least squares- fitting the curves of the form-

Module-5

Joint probability distribution: Joint Probability distribution for two discrete random variables, expectation and covariance. Sampling Theory: Introduction to sampling distributions, standard error, Type-I and Type-II errors. Test of hypothesis for means, student’s t-distribution, Chi-square distribution as a test of goodness of fit.

_________________________________________________________________________________

DESIGN AND ANALYSIS OF ALGORITHMS (18CS42)

Module 1 

Introduction: What is an Algorithm? (T2:1.1), Algorithm Specification (T2:1.2), Analysis

Framework (T1:2.1), Performance Analysis: Space complexity, Time complexity (T2:1.3).

Asymptotic Notations: Big-Oh notation (O), Omega notation (Ω), Theta notation (Θ), and

Little-oh notation (o), Mathematical analysis of Non-Recursive and recursive Algorithms

with Examples (T1:2.2, 2.3, 2.4). Important Problem Types: Sorting, Searching, String

processing, Graph Problems, Combinatorial Problems. Fundamental Data Structures:

Stacks, Queues, Graphs, Trees, Sets and Dictionaries. (T1:1.3,1.4). RBT: L1, L2, L3

Module 2

Divide and Conquer: General method, Binary search, Recurrence equation for divide and

conquer, Finding the maximum and minimum (T2:3.1, 3.3, 3.4), Merge sort, Quick sort

(T1:4.1, 4.2), Strassen’s matrix multiplication (T2:3.8), Advantages and Disadvantages of

divide and conquer. Decrease and Conquer Approach: Topological Sort. (T1:5.3).

RBT: L1, L2, L3

Module 3

Greedy Method: General method, Coin Change Problem, Knapsack Problem, Job

sequencing with deadlines (T2:4.1, 4.3, 4.5). Minimum cost spanning trees: Prim’s

Algorithm, Kruskal’s Algorithm (T1:9.1, 9.2). Single source shortest paths: Dijkstra's

Algorithm (T1:9.3). Optimal Tree problem: Huffman Trees and Codes (T1:9.4).

Transform and Conquer Approach: Heaps and Heap Sort (T1:6.4). RBT: L1, L2, L3

Module 4

Dynamic Programming: General method with Examples, Multistage Graphs (T2:5.1, 5.2).

Transitive Closure: Warshall’s Algorithm, All Pairs Shortest Paths: Floyd's Algorithm,

Optimal Binary Search Trees, Knapsack problem ((T1:8.2, 8.3, 8.4), Bellman-Ford

Algorithm (T2:5.4), Travelling Sales Person problem (T2:5.9), Reliability design (T2:5.8).

RBT: L1, L2, L3

Module 5

Backtracking: General method (T2:7.1), N-Queens problem (T1:12.1), Sum of subsets

problem (T1:12.1), Graph coloring (T2:7.4), Hamiltonian cycles (T2:7.5). Programme and

Bound: Assignment Problem, Travelling Sales Person problem (T1:12.2), 0/1 Knapsack

problem (T2:8.2, T1:12.2): LC Programme and Bound solution (T2:8.2), FIFO Programme

and Bound solution (T2:8.2). NP-Complete and NP-Hard problems: Basic concepts, non-

deterministic algorithms, P, NP, NP-Complete, and NP-Hard classes (T2:11.1). RBT: L1, L2, L3

_________________________________________________________________________________

OPERATING SYSTEMS(18CS43)

Module 1

Introduction to operating systems, System structures: What operating systems do;

Computer System organization; Computer System architecture; Operating System structure;

Operating System operations; Process management; Memory management; Storage

management; Protection and Security; Distributed system; Special-purpose systems;

Computing environments. Operating System Services; User - Operating System interface;

System calls; Types of system calls; System programs; Operating system design and

implementation; Operating System structure; Virtual machines; Operating System

generation; System boot. Process Management Process concept; Process scheduling;

Operations on processes; Inter process communication

Text book 1: Chapter 1, 2.1, 2.3, 2.4, 2.5, 2.6, 2.8, 2.9, 2.10, 3.1, 3.2, 3.3, 3.4 RBT: L1, L2, L3

Module 2

Multi-threaded Programming: Overview; Multithreading models; Thread Libraries;

Threading issues. Process Scheduling: Basic concepts; Scheduling Criteria; Scheduling

Algorithms; Multiple-processor scheduling; Thread scheduling. Process Synchronization:

Synchronization: The critical section problem; Peterson’s solution; Synchronization

hardware; Semaphores; Classical problems of synchronization; Monitors.

Text book 1: Chapter 4.1, 4.2, 4.3, 4.4, 5.1, 5.2, 5.3, 5.4, 5.5, 6.2, 6.3, 6.4, 6.5, 6.6, 6.7

RBT: L1, L2, L3

Module 3

Deadlocks : Deadlocks; System model; Deadlock characterization; Methods for handling

deadlocks; Deadlock prevention; Deadlock avoidance; Deadlock detection and recovery from

deadlock. Memory Management: Memory management strategies: Background; Swapping;

Contiguous memory allocation; Paging; Structure of page table; Segmentation.

Text book 1: Chapter 7, 8.1 to 8.6 RBT: L1, L2, L3

Module 4

Virtual Memory Management: Background; Demand paging; Copy-on-write; Page

replacement; Allocation of frames; Thrashing. File System, Implementation of File

System: File system: File concept; Access methods; Directory structure; File system

mounting; File sharing; Protection: Implementing File system: File system structure; File

system implementation; Directory implementation; Allocation methods; Free space

management.

Text book 1: Chapter 91. To 9.6, 10.1 to 10.5 RBT: L1, L2, L3

Module 5

Secondary Storage Structures, Protection: Mass storage structures; Disk structure; Disk

attachment; Disk scheduling; Disk management; Swap space management. Protection: Goals

of protection, Principles of protection, Domain of protection, Access matrix, Implementation

of access matrix, Access control, Revocation of access rights, Capability- Based systems.

Case Study: The Linux Operating System: Linux history; Design principles; Kernel

modules; Process management; Scheduling; Memory Management; File systems, Input and

output; Inter-process communication.

Text book 1: Chapter 12.1 to 12.6, 21.1 to 21.9 RBT: L1, L2, L3

_________________________________________________________________________________

MICROCONTROLLER AND EMBEDDED SYSTEMS(18CS44)

Module 1 

Microprocessors versus Microcontrollers, ARM Embedded Systems: The RISC design

philosophy, The ARM Design Philosophy, Embedded System Hardware, Embedded System

Software.

ARM Processor Fundamentals: Registers, Current Program Status Register, Pipeline,

Exceptions, Interrupts, and the Vector Table , Core Extensions

Text book 1: Chapter 1 - 1.1 to 1.4, Chapter 2 - 2.1 to 2.5 RBT: L1, L2

Module 2

Introduction to the ARM Instruction Set : Data Processing Instructions , Programme

Instructions, Software Interrupt Instructions, Program Status Register Instructions,

Coprocessor Instructions, Loading Constants

ARM programming using Assembly language: Writing Assembly code, Profiling and

cycle counting, instruction scheduling, Register Allocation, Conditional Execution, Looping

Constructs : Text book 1: Chapter 3:Sections 3.1 to 3.6 ( Excluding 3.5.2), Chapter 6(Sections 6.1 to

6.6) RBT: L1, L2

Module 3

Embedded System Components: Embedded Vs General computing system, History of

embedded systems, Classification of Embedded systems, Major applications areas of

embedded systems, purpose of embedded systems

Core of an Embedded System including all types of processor/controller, Memory, Sensors,

Actuators, LED, 7 segment LED display, stepper motor, Keyboard, Push button switch,

Communication Interface (onboard and external types), Embedded firmware, Other system

components. : Text book 2:Chapter 1(Sections 1.2 to 1.6),Chapter 2(Sections 2.1 to 2.6)

RBT: L1, L2

Module 4

Embedded System Design Concepts: Characteristics and Quality Attributes of Embedded

Systems, Operational quality attributes ,non-operational quality attributes, Embedded

Systems-Application and Domain specific, Hardware Software Co-Design and Program

Modelling, embedded firmware design and development : Text book 2: Chapter-3, Chapter-4, Chapter-7 (Sections 7.1, 7.2 only), Chapter-9 (Sections 9.1, 9.2, 9.3.1, 9.3.2 only) RBT: L1, L2

Module 5

RTOS and IDE for Embedded System Design: Operating System basics, Types of

operating systems, Task, process and threads (Only POSIX Threads with an example

program), Thread preemption, Multiprocessing and Multitasking, Task Communication

(without any program), Task synchronization issues – Racing and Deadlock, Concept of

Binary and counting semaphores (Mutex example without any program), How to choose an

RTOS, Integration and testing of Embedded hardware and firmware, Embedded system

Development Environment – Block diagram (excluding Keil), Disassembler/decompiler,

simulator, emulator and debugging techniques, target hardware debugging, boundary scan.

Text book 2: Chapter-10 (Sections 10.1, 10.2, 10.3, 10.4 , 10.7, 10.8.1.1, 10.8.1.2, 10.8.2.2,

10.10 only), Chapter 12, Chapter-13 ( block diagram before 13.1, 13.3, 13.4, 13.5, 13.6

only) RBT: L1, L2

_________________________________________________________________________________

OBJECT ORIENTED CONCEPTS (18CS45)

Module 1

Introduction to Object Oriented Concepts: A Review of structures, Procedure–Oriented Programming system, Object Oriented. Programming System, Comparison of Object Oriented Language with C, Console I/O, variables and reference variables, Function Prototyping, Function Overloading. Class and Objects: Introduction, member functions and data, objects and functions.

Text book 1: Ch 1: 1.1 to 1.9 Ch 2: 2.1 to 2.3 RBT: L1, L2

Module 2

Class and Objects (contd):

Objects and arrays, Namespaces, Nested classes, Constructors, Destructors. Introduction to Java: Java’s magic: the Byte code; Java Development Kit (JDK); the Java Buzzwords, Object-oriented programming; Simple Java programs. Data types, variables and arrays, Operators, Control Statements. Text book 1:Ch 2: 2.4 to 2.6Ch 4: 4.1 to 4.2 Text book 2: Ch:1 Ch: 2 Ch:3 Ch:4 Ch:5

RBT: L1, L2

Module 3

Classes, Inheritance,Exception Handling: Classes: Classes fundamentals; Declaring

objects; Constructors, this keyword, garbage collection. Inheritance: inheritance basics,

using super, creating multi level hierarchy, method overriding. Exception handling:

Exception handling in Java. Text book 2: Ch:6 Ch: 8 Ch:10 RBT: L1, L2, L3

Module 4

Packages and Interfaces:Packages, Access Protection,Importing Packages.Interfaces.

Multi Threaded Programming:Multi Threaded Programming: What are threads? How to

make the classes threadable ; Extending threads; Implementing runnable; Synchronization;

Changing state of the thread; Bounded buffer problems, producer consumer problems.

Text book 2: CH: 9 Ch 11: RBT: L1, L2, L3

Module 5

Event Handling: Two event handling mechanisms; The delegation event model; Event

classes; Sources of events; Event listener interfaces; Using the delegation event model;

Adapter classes; Inner classes. Swings: Swings: The origins of Swing; Two key Swing features; Components and Containers; The Swing Packages; A simple Swing Application; Create a Swing Applet; Jlabel and ImageIcon; JTextField;The Swing Buttons; JTabbedpane; JScrollPane; JList;

JComboBox; JTable. Text book 2: Ch 22: Ch: 29 Ch: 30 RBT: L1, L2, L3

_________________________________________________________________________________

DATA COMMUNICATION (18CS46)

Module 1
Introduction: Data Communications, Networks, Network Types, Internet History, Standards
and Administration, Networks Models: Protocol Layering, TCP/IP Protocol suite, The OSI
model, Introduction to Physical Layer-1: Data and Signals, Digital Signals, Transmission
Impairment, Data Rate limits, Performance. Textbook1: Ch 1.1 to 1.5, 2.1 to 2.3, 3.1, 3.3 to 3.6
RBT: L1, L2

Module 2
Digital Transmission: Digital to digital conversion (Only Line coding: Polar, Bipolar and
Manchester coding). Physical Layer-2: Analog to digital conversion (only PCM), Transmission Modes, Analog Transmission: Digital to analog conversion. Textbook1: Ch 4.1 to 4.3, 5.1
RBT: L1, L2

Module 3
Bandwidth Utilization: Multiplexing and Spread Spectrum, Switching: Introduction, Circuit Switched Networks and Packet switching. Error Detection and Correction: Introduction, Block coding, Cyclic codes, Checksum, Textbook1: Ch 6.1, 6.2, 8.1 to 8.3, 10.1 to 10.4 RBT: L1, L2

Module 4
Data link control: DLC services, Data link layer protocols, Point to Point protocol (Framing,
Transition phases only). Media Access control: Random Access, Controlled Access and Channelization, Introduction to Data-Link Layer: Introduction, Link-Layer Addressing, ARP
IPv4 Addressing and subnetting: Classful and CIDR addressing, DHCP, NAT
Textbook1: Ch 9.1, 9.2, 11.1, 11.2 11.4, 12.1 to 12.3, 18.4 RBT: L1, L2

Module 5
Wired LANs Ethernet: Ethernet Protocol, Standard Ethernet, Fast Ethernet, Gigabit
Ethernet and 10 Gigabit Ethernet, Wireless LANs: Introduction, IEEE 802.11 Project and Bluetooth.
Other wireless Networks: Cellular Telephony Textbook1: Ch 13.1 to 13.5, 15.1 to 15.3, 16.2

RBT: L1, L2

_________________________________________________________________________________

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (18CSL47)

Programs List:

1

.a. Create a Java class called Student with the following details as variables within it.

(i) USN

(ii) Name

(iii) Programme

(iv) Phone

Write a Java program to create nStudent objects and print the USN, Name, Programme, and

Phoneof these objects with suitable headings.

b. Write a Java program to implement the Stack using arrays. Write Push(), Pop(), and

Display() methods to demonstrate its working.

2.

a. Design a superclass called Staff with details as StaffId, Name, Phone, Salary. Extend this

class by writing three subclasses namely Teaching (domain, publications), Technical

(skills), and Contract (period). Write a Java program to read and display at least 3 staff

objects of all three categories.

b. Write a Java class called Customer to store their name and date_of_birth. The date_of_birth

format should be dd/mm/yyyy. Write methods to read customer data as <name,

dd/mm/yyyy> and display as <name, dd, mm, yyyy> using StringTokenizer class

considering the delimiter character as “/”.

3.

a. Write a Java program to read two integers a andb. Compute a/b and print, when b is not zero.

Raise an exception when b is equal to zero.

b. Write a Java program that implements a multi-thread application that has three threads. First

thread generates a random integer for every 1 second; second thread computes the square of

the number andprints; third thread will print the value of cube of the number.

4. Sort a given set of n integer elements using Quick Sort method and compute its time

complexity. Run the program for varied values of n> 5000 and record the time taken to sort.

Plot a graph of the time taken versus non graph sheet. The elements can be read from a file

or can be generated using the random number generator. Demonstrate using Java how the

divide-and-conquer method works along with its time complexity analysis: worst case,

average case and best case.

5. Sort a given set of n integer elements using Merge Sort method and compute its time

complexity. Run the program for varied values of n> 5000, and record the time taken to

sort. Plot a graph of the time taken versus non graph sheet. The elements can be read from a

file or can be generated using the random number generator. Demonstrate using Java how

the divide-and-conquer method works along with its time complexity analysis: worst case,

average case and best case.

6. Implement in Java, the 0/1 Knapsack problem using (a) Dynamic Programming method (b)

Greedy method.

7. From a given vertex in a weighted connected graph, find shortest paths to other vertices

using Dijkstra's algorithm. Write the program in Java.

8. Find Minimum Cost Spanning Tree of a given connected undirected graph using

Kruskal'salgorithm. Use Union-Find algorithms in your program

9. Find Minimum Cost Spanning Tree of a given connected undirected graph using

Prim's algorithm.

10. Write Java programs to

(a) Implement All-Pairs Shortest Paths problem using Floyd's algorithm.

(b) Implement Travelling Sales Person problem using Dynamic programming.

11. Design and implement in Java to 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}. Display a suitable message, if

the given problem instance doesn't have a solution.

12. Design and implement in Java to find all Hamiltonian Cycles in a connected undirected

Graph G of n vertices using backtracking principle.

_________________________________________________________________________________

MICROCONTROLLER AND EMBEDDED SYSTEMS LABORATORY (18CSL48)

Programs List:

PART A Conduct the following experiments by writing program using ARM7TDMI/LPC2148 using and evaluation board/simulator and the required software tool.

1. Write a program to multiply two 16 bit binary numbers.

2. Write a program to find the sum of first 10 integer numbers.

3. Write a program to find factorial of a number.

4. Write a program to add an array of 16 bit numbers and store the 32 bit result in internal RAM

5. Write a program to find the square of a number (1 to 10) using look-up table.

6. Write a program to find the largest/smallest number in an array of 32 numbers .

7. Write a program to arrange a series of 32 bit numbers in ascending/descending order.

8. Write a program to count the number of ones and zeros in two consecutive memory locations.

PART –B Conduct the following experiments on an ARM7TDMI/LPC2148 evaluation board using evaluation version of Embedded 'C' & Keil Uvision-4 tool/compiler.

9. Display “Hello World” message using Internal UART.

10. Interface and Control a DC Motor.

11. Interface a Stepper motor and rotate it in clockwise and anti-clockwise direction.

12. Determine Digital output for a given Analog input using Internal ADC of ARM controller.

13. Interface a DAC and generate Triangular and Square waveforms.

14. Interface a 4x4 keyboard and display the key code on an LCD.

15. Demonstrate the use of an external interrupt to toggle an LED On/Off.

16. Display the Hex digits 0 to F on a 7-segment LED interface, with an appropriate delay in between

_________________________________________________________________________________

--------------------------------------------------------------------------------------------------------------------------