Computer Science & Eng. • 4th SemesterCore / Standard CurriculumChange Track

Computer Science & Eng. — 4th Semester Syllabus

Computer Science & Engineering

Credits Allocation Table (L-T-P Structure)

Course Title	Code	L	T	P	Credits
Computer Organization and Architecture	105401	3	0	0	3
Formal Language and Automata Theory	105402	3	1	0	4
Design and Analysis of Algorithms	105403	3	0	0	3
Database Management System	105404	3	0	0	3
Effective Technical Communication	105405	3	0	0	3
Computer Networks	105406	3	0	0	3
Computer Organization and Architecture Lab	105401P	0	0	2	1
Design and Analysis of Algorithms Lab	105403P	0	0	2	1
Database Management System Lab	105404P	0	0	2	1
Computer Networks Lab	105406P	0	0	2	1
NPTEL-I (Open Course)	105407	-	-	-	3
TOTAL	-	-	-	-	26

Computer Organization & Architecture

105401

Theory Course • 6 Units

View PYQ Papers

Unit-1.0

Functional blocks of a computer: CPU
Memory
Input-output subsystems
Control unit
Instruction set architecture of a CPU-registers
Instruction execution cycle
RTL interpretation of instructions
Addressing modes
Instruction set
Case study instruction sets of some common CPUs

Unit-2.0

Data representation: Signed number representation
Fixed and floating point representations
Character representation
Computer arithmetic - Integer addition and subtraction
Ripple carry adder
Carry look-ahead adder
Etc. Multiplication shift-and-add
Booth multiplier
Carry save multiplier
Etc. Division restoring and non-restoring techniques
Floating point arithmetic

Unit-3.0

Introduction to x86 architecture
CPU control unit design: Hardwired and micro- programmed design approaches
Case study design of a simple hypothetical CPU
Memory system design: Semiconductor memory technologies
Memory organization

Unit-4.0

Peripheral devices and their characteristics: Input-output subsystems
I/O device interface
I/O transfers-program controlled
Interrupt driven and DMA
Privileged and non- privileged instructions
Software interrupts and exceptions
Programs and processes-role of interrupts in process state transitions
I/O device interfaces SCII
USB

Unit-5.0

Pipelining: Basic concepts of pipelining
Throughput and speedup
Pipeline hazards
Parallel Processors: Introduction to parallel processors
Concurrent access to memory and cache coherency

Unit-6.0

Memory organization: Memory interleaving
Concept of hierarchical memory organization
Cache memory
Cache size vs. Block size
Mapping functions
Replacement algorithms
Write policies

Formal Language and Automata Theory

105402

Theory Course • 6 Units

View PYQ Papers

Unit- 1.0: Introduction

Alphabet
Languages and grammars
Productions and derivation
Chomsky hierarchy of languages

Unit- 2.0: Regular languages and finite automata

Regular expressions and languages
Deterministic finite automata (DFA) and equivalence with regular expressions
Nondeterministic finite automata (NFA) and equivalence with DFA
Regular grammars and equivalence with finite automata
Properties of regular languages
Pumping lemma for regular languages
Minimization of finite automata

Unit- 3.0: Context-free languages and pushdown automata

Context-free grammars (CFG) and Context-free languages (CFL)
Chomsky and Greibach normal forms
Nondeterministic pushdown automata (PDA) and equivalence with CFG
Parse trees
Ambiguity in CFG
Pumping lemma for context-free languages
Deterministic pushdown automata
Closure properties of CFLs

Unit- 4.0: Context-sensitive languages

Context-sensitive grammars (CSG) and Context-sensitive languages
Linear bounded automata and equivalence with CSG

Unit- 5.0: Turing machines

The basic model for Turing machines (TM)
Turing recognizable (Recursively enumerable) and Turing-decidable (recursive) languages and their closure properties
Variants of Turing machines
Nondeterministic TMs and equivalence with deterministic TMs
Unrestricted grammars and equivalence with Turing machines
TMs as enumerators

Unit-6.0: Undecidability

Church-Turing thesis
Universal Turing machine
The universal and diagonalization languages
Reduction between languages and Rice's theorem
Undecidable problems about languages

Design and Analysis of Algorithms

105403

Theory Course • 6 Units

View PYQ Papers

Unit-1.0

Introduction: Characteristics of algorithm
Analysis of algorithm: Asymptotic analysis of complexity bounds best
Average and worst-case behavior
Performance measurements of Algorithm
Time and space trade-offs
Analysis of recursive algorithms through recurrence relations: Substitution method
Recursion tree method and Masters' theorem

Unit-2.0

Introduction to Divide and Conquer paradigm: Binary Search
Quick and Merge sorting techniques
Linear time selection algorithm
Strassen's Matrix Multiplication
Karatsuba Algorithm for fast multiplication etc.
Introduction to Heap: Min and Max Heap
Build Heap
Heap Sort

Unit-3.0

Overview of Brute-Force
GreedyProgramming
Dynamic Programming
Branch-and-Bound and Backtrackingmethodologies
Greedy paradigm examples of exact optimization solution: Minimum Cost Spanning Tree
Knapsack problem
Job Sequencing Problem
Huffman Coding
Single source shortest path problem

Unit-4.0

Dynamic Programming
Difference between dynamic programming and divide and conquer
Applications: Fibonacci Series
Matrix Chain Multiplication
0-1 Knapsack Problem
Longest Common Subsequence
Travelling Salesman Problem
Rod Cutting
Bin Packing
Heuristics characteristics and their application domains

Unit-5.0

Graph and Tree Algorithms: Representational issues in graphs
Traversal algorithms: Depth First Search (DFS) and Breadth First Search (BFS)
Shortest path algorithms: Bellman- Ford algorithm
Dijkstra's algorithm & Analysis of Dijkstra's algorithm using heaps
Floyd-Warshall's all pairs shortest path algorithm
Transitive closure
Topological sorting
Network Flow Algorithm
Connected Component

Unit-6.0

Tractable and Intractable Problems: Computability of Algorithms
Computability classes P
NP-complete and NP-hard
Cook's theorem
Standard NP-complete problems and Reduction techniques
Approximation algorithms
Randomized algorithms

Database Management System

105404

Theory Course • 6 Units

View PYQ Papers

Unit 1.0- Database system architecture

Data Abstraction
Data Independence
Data Definition Language (DDL)
Data Manipulation Language (DML)
Data models: Entity-relationship model
Network model
Relational and object oriented data models
Integrity constraints
Data manipulation operations

Unit 2.0- Relational query languages

Relational algebra
Tuple and domain relational calculus
SQL3
DDL and DML constructs
Open source and Commercial DBMS - MYSQL
ORACLE
DB2
SQL server
Relational database design: Domain and data dependency
Armstrong's axioms
Normal forms
Dependency preservation
Lossless design
Query processing and optimization: Evaluation of relational algebra expressions
Query equivalence
Join strategies
Query optimization algorithms

Unit 3.0-Storage strategies

Indices
B-trees
Hashing

Unit 4.0- Transaction processing

Concurrency control
ACID property
Serializability of scheduling
Locking and timestamp based schedulers
Multi-version and optimistic Concurrency Control schemes
Database recovery

Unit 5.0-Database Security

Authentication
Authorization and access control
DAC
MAC and RBAC models
Intrusion detection
SQL injection

Unit 6.0- Advanced topics

Object oriented and object relational databases
Logical databases
Web databases
Distributed databases
Data warehousing and data mining

Effective Technical Communication

105405

Theory Course • 6 Units

View PYQ Papers

Unit 1.0- Information Design and Development

Different kinds of technical documents
Information development life cycle
Organization structures
Factors affecting information and document design
Strategies for organization
Information design and writing for print and for online media

Unit 2.0- Technical Writing, Grammar and Editing

Technical writing process
Forms of discourse
Writing drafts and revising
Collaborative writing
Creating indexes
Technical writing style and language
Basics of grammar
Study of advanced grammar
Editing strategies to achieve appropriate technical style
Introduction to advanced technical communication
Usability
Human factors
Managing technical communication projects
Time estimation
Single sourcing
Localization

Unit 3.0-Self-development and Assessment

Self assessment
Awareness
Perception and Attitudes
Values and belief
Personal goal setting
Career planning
Self-esteem. Managing Time
Personal memory
Rapid reading
Taking notes
Complex problem solving
Creativity

Unit 4.0- Communication

Public speaking
Group discussion
Oral presentation
Interviews
Graphic presentation
Presentation aids
Personality Development

Unit 5.0-Technical Writing

Writing reports
Project proposals
Brochures
Newsletters
Technical articles
Manuals
Official notes
Business letters
Memos
Progress reports
Minutes of meetings
Event report

Unit 6.0- Ethics

Business ethics
Etiquettes in social and office settings
Email etiquettes
Telephone Etiquettes
Engineering ethics
Managing time
Role and responsibility of engineer
Work culture in jobs
Personal memo

Computer Networks

105406

Theory Course • 6 Units

View PYQ Papers

Unit-1.0

Overview of Data Communication and Networking: OSI Reference Model
TCP/IP Protocol Suite
Network Architecture and Physical Topology

Unit-2.0

Physical Layer: Analog and Digital Signals
Transmission Impairment
Data Rate Limits
Performance Analysis of a Network
Representation and Synchronization of Bits
Analog and Digital Transmission Multiplexing and Spreading Techniques
Guided Transmission Media
Circuit
Packet and Virtual Circuit Switching

Unit-3.0

Data Link Layer: Framing
Flow and Error Control (Noiseless and Noisy Channels Protocols)
PointToPoint Protocol
Random Access protocols (Pure/slotted ALOHA, CSMA/CD, CSMA/CA)
Controlled Access Protocol (Bit-Map, Polling and Token Passing)
Channelization (TDMA, FDMA, CDMA)
Physical Addressing and Ethernet
Connecting LANs and Virtual LANs

Unit-4.0

Network Layer: Internet Protocol version 4 and 6
Address Mapping (ARP, RARP, BOOTP and DHCP)
ICMP and IGMP
Routing Algorithms

Unit-5.0

Transport Layer: UDP
TCP
Congestion Control and QoS
Client-Server Model and Socket Interface

Unit-6.0

Application Layer: DNS
Remote Logging
Electronic Mail (SMTP, POP)
FTP
Introduction to WWW and HTTP

NPTEL-I (Open Course)

105407

Theory Course • 1 Units

View PYQ Papers

12 Weeks (3 Credits)

NPTEL (Open Course) Guidelines: NPTEL (Open Course) should be taken from the course other than core subjects of the branch.

Computer Organization and Architecture Lab

105401P

Laboratory Subject • Course Details

View PYQ Papers

Design and Analysis of Algorithms Lab

105403P

Laboratory Subject • 1 Units

View PYQ Papers

Topics Part 1

Sort a given set of elements using the Quick sort 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. The elements can be read from a file or can be generated using the random number generator.
Implement a 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.The elements can be read from a file or can be generated using the random number generator.
Compute the transitive closure of a given directed graph using Warshall's algorithm.
Implement 0/1 Knapsack problem using Dynamic Programming.
From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijikstra's algorithm.
Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm.
Print all the nodes reachable from a given starting node in a digraph using the BFS method.
Check whether a given graph is connected or not using the DFS method.
Find a subset of a given set S={s1,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.
Implement any scheme to find the optimal solution for the Travelling Salesperson problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation.
Find Minimum Cost Spanning Tree of a given undirected graph using Prim's algorithm.
Implement N Queen's problem using Backtracking.

Prescribed Experiments

Sort a given set of elements using the Quick sort 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. The elements can be read from a file or can be generated using the random number generator.
Implement a 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.The elements can be read from a file or can be generated using the random number generator.
Compute the transitive closure of a given directed graph using Warshall's algorithm.
Implement 0/1 Knapsack problem using Dynamic Programming.
From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijikstra's algorithm.
Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm.
Print all the nodes reachable from a given starting node in a digraph using the BFS method.
Check whether a given graph is connected or not using the DFS method.
Find a subset of a given set S={s1,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.
Implement any scheme to find the optimal solution for the Travelling Salesperson problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation.
Find Minimum Cost Spanning Tree of a given undirected graph using Prim's algorithm.
Implement N Queen's problem using Backtracking.

Database Management System Lab

105404P

Laboratory Subject • 1 Units

View PYQ Papers

Topics Part 1

Student should decide on a case study and formulate the problem statement.
Conceptual Designing using ER Diagrams (Identifying entities, attributes, keys and relationships between entities, cardinalities, generalization, specialization etc.) Note: Student is required to submit a document by drawing ER Diagram to the Lab teacher.
Converting ER Model to Relational Model (Represent entities and relationships in Tabular form, Represent attributes as columns, identifying keys) Note: Student is required to submit a document showing the database tables created from ER Model.
Normalization -To remove the redundancies and anomalies in the above relational tables, Normalize up to Third Normal Form.
Creation of Tables using SQL- Overview of using SQL tool, Data types in SQL, Creating Tables (along with Primary and Foreign keys), Altering Tables and Dropping Tables.
Practicing DML commands- Insert, Select, Update, Delete.
Practicing Queries using ANY, ALL, IN, EXISTS, NOT EXISTS, UNION, INTERSECT, CONSTRAINTS etc.
Practicing Sub queries (Nested, Correlated) and Joins (Inner, Outer and Equi).
Practice Queries using COUNT, SUM, AVG, MAX, MIN, GROUP BY, HAVING, VIEWS Creation and Dropping.
Practicing on Triggers creation of trigger, Insertion using trigger, Deletion using trigger, Updating using trigger.

Prescribed Experiments

Student should decide on a case study and formulate the problem statement.
Conceptual Designing using ER Diagrams (Identifying entities, attributes, keys and relationships between entities, cardinalities, generalization, specialization etc.) Note: Student is required to submit a document by drawing ER Diagram to the Lab teacher.
Converting ER Model to Relational Model (Represent entities and relationships in Tabular form, Represent attributes as columns, identifying keys) Note: Student is required to submit a document showing the database tables created from ER Model.
Normalization -To remove the redundancies and anomalies in the above relational tables, Normalize up to Third Normal Form.
Creation of Tables using SQL- Overview of using SQL tool, Data types in SQL, Creating Tables (along with Primary and Foreign keys), Altering Tables and Dropping Tables.
Practicing DML commands- Insert, Select, Update, Delete.
Practicing Queries using ANY, ALL, IN, EXISTS, NOT EXISTS, UNION, INTERSECT, CONSTRAINTS etc.
Practicing Sub queries (Nested, Correlated) and Joins (Inner, Outer and Equi).
Practice Queries using COUNT, SUM, AVG, MAX, MIN, GROUP BY, HAVING, VIEWS Creation and Dropping.
Practicing on Triggers creation of trigger, Insertion using trigger, Deletion using trigger, Updating using trigger.

Computer Networks Lab

105406P

Laboratory Subject • 1 Units

View PYQ Papers

Topics Part 1

Write a report that includes a diagram showing the topology, type of connection devices, and speed of the wired and wireless LAN in your organization. Also find out the MAC and IP addresses and the subnet mask of your computer.
Install and run a network diagnosis tool such as TCP dump or Wireshark. Start capturing packets on an active interface, open a browser and type the address of your favourite search engine. Wait till the page loads and stop capture. List out the type and number of each type of packets captured.
Write a program to create a server that listens to port 53 using stream sockets. Write a simple client program to connect to the server. Send a simple text message "Hello" from the client to the server and the server to the client and close the connection.
Write a program to create a chat server that listens to port 54 using stream sockets. Write a simple client program to connect to the server. Send multiple text messages from the client to the server and vice versa. When either party types "Bye", close the connection.
Write a program to create a server that listens to port 55 using stream sockets. Write a simple client program to connect to the server. The client should request for a text file and the server should return the file before terminating the connection.
Write a program to create a server that listens to port 56 using stream sockets. Write a simple client program to connect to the server. Run multiple clients that request the server for binary files. The server should service each client one after the other before terminating the connection
Write a program to create a server that listens to port 57 using stream sockets. Write a simple client program to connect to the server. Run multiple clients that request the server for text files. The server should service all clients concurrently.
Write a program to create a server that listens to port 59 using datagram sockets. Write a simple client program that requests the server for a binary file. The server should service multiple clients concurrently and send the requested files in response.
Creation of sample network topologies using CISCO packet tracer.
Creation of a subnet, assignment of addresses and communication within and outside the subnet.
Error Detection using CRC (Python/Java): Implement the Cyclic Redundancy Check (CRC) algorithm for error detection in data transmission.
Hamming Code for Error Correction (Python/Java): Implement the Hamming Code algorithm to detect and correct single-bit errors in transmitted data.
Sliding Window Protocol (Python/Java): Simulate Stop-and-Wait and Go-Back-N ARQ protocols to demonstrate flow control in a network.
Selective Repeat ARQ (Python/Java): Implement the Selective Repeat ARQ protocol for reliable data transmission.
CSMA/CD and CSMA/CA Simulation (Python/Java): Simulate Carrier Sense Multiple Access with Collision Detection (CSMA/CD) and Collision Avoidance (CSMA/CA).
IPv4 and IPv6 Addressing (Python/Java): Implement a program to validate and classify IP addresses as IPv4 or IPv6.
ARP and RARP Implementation (Python/Java): Simulate Address Resolution Protocol (ARP) and Reverse Address Resolution Protocol (RARP).
BOOTP and DHCP Simulation (Python/Java): Implement the BOOTP and DHCP mechanisms for dynamic IP address allocation.
Routing Algorithms (Python/Java): Implement the Distance Vector Routing (DVR) and Link State Routing (LSR) algorithms.
TCP and UDP Simulation (Python/Java): Implement a client-server model to demonstrate TCP and UDP socket programming.
Congestion Control using Leaky Bucket Algorithm (Python/Java): Simulate the Leaky Bucket algorithm for congestion control.
Congestion Control using Token Bucket Algorithm (Python/Java): Implement the Token Bucket algorithm to regulate network traffic.
FTP and HTTP Simulation (Python/Java): Implement a program to simulate FTP file transfer and send HTTP GET/POST requests.
DNS Query Resolution (Python/Java): Write a program to perform DNS resolution and retrieve IP addresses for given domain names.
Email Client Simulation (Python/Java): Implement a basic email client that can send and receive messages using SMTP and POP3 protocols.

Prescribed Experiments

Write a report that includes a diagram showing the topology, type of connection devices, and speed of the wired and wireless LAN in your organization. Also find out the MAC and IP addresses and the subnet mask of your computer.
Install and run a network diagnosis tool such as TCP dump or Wireshark. Start capturing packets on an active interface, open a browser and type the address of your favourite search engine. Wait till the page loads and stop capture. List out the type and number of each type of packets captured.
Write a program to create a server that listens to port 53 using stream sockets. Write a simple client program to connect to the server. Send a simple text message "Hello" from the client to the server and the server to the client and close the connection.
Write a program to create a chat server that listens to port 54 using stream sockets. Write a simple client program to connect to the server. Send multiple text messages from the client to the server and vice versa. When either party types "Bye", close the connection.
Write a program to create a server that listens to port 55 using stream sockets. Write a simple client program to connect to the server. The client should request for a text file and the server should return the file before terminating the connection.
Write a program to create a server that listens to port 56 using stream sockets. Write a simple client program to connect to the server. Run multiple clients that request the server for binary files. The server should service each client one after the other before terminating the connection
Write a program to create a server that listens to port 57 using stream sockets. Write a simple client program to connect to the server. Run multiple clients that request the server for text files. The server should service all clients concurrently.
Write a program to create a server that listens to port 59 using datagram sockets. Write a simple client program that requests the server for a binary file. The server should service multiple clients concurrently and send the requested files in response.
Creation of sample network topologies using CISCO packet tracer.
Creation of a subnet, assignment of addresses and communication within and outside the subnet.
Error Detection using CRC (Python/Java): Implement the Cyclic Redundancy Check (CRC) algorithm for error detection in data transmission.
Hamming Code for Error Correction (Python/Java): Implement the Hamming Code algorithm to detect and correct single-bit errors in transmitted data.
Sliding Window Protocol (Python/Java): Simulate Stop-and-Wait and Go-Back-N ARQ protocols to demonstrate flow control in a network.
Selective Repeat ARQ (Python/Java): Implement the Selective Repeat ARQ protocol for reliable data transmission.
CSMA/CD and CSMA/CA Simulation (Python/Java): Simulate Carrier Sense Multiple Access with Collision Detection (CSMA/CD) and Collision Avoidance (CSMA/CA).
IPv4 and IPv6 Addressing (Python/Java): Implement a program to validate and classify IP addresses as IPv4 or IPv6.
ARP and RARP Implementation (Python/Java): Simulate Address Resolution Protocol (ARP) and Reverse Address Resolution Protocol (RARP).
BOOTP and DHCP Simulation (Python/Java): Implement the BOOTP and DHCP mechanisms for dynamic IP address allocation.
Routing Algorithms (Python/Java): Implement the Distance Vector Routing (DVR) and Link State Routing (LSR) algorithms.
TCP and UDP Simulation (Python/Java): Implement a client-server model to demonstrate TCP and UDP socket programming.
Congestion Control using Leaky Bucket Algorithm (Python/Java): Simulate the Leaky Bucket algorithm for congestion control.
Congestion Control using Token Bucket Algorithm (Python/Java): Implement the Token Bucket algorithm to regulate network traffic.
FTP and HTTP Simulation (Python/Java): Implement a program to simulate FTP file transfer and send HTTP GET/POST requests.
DNS Query Resolution (Python/Java): Write a program to perform DNS resolution and retrieve IP addresses for given domain names.
Email Client Simulation (Python/Java): Implement a basic email client that can send and receive messages using SMTP and POP3 protocols.