CS 4th Semester Syllabus
CS 4th Semester Syllabus
4th Semester
Basket of Open Elective – 1
CSO441 Data Structures and Algorithms
CSO442 Object Oriented Technology
CSC 401 Computer Organization and Architecture 3-1-0 4Credits 4Hours
UNIT-II: Fundamental concepts of the processing Unit: Fetching and Storing words,
Register Transfer, Execution of instruction, Arithmetic Operations: Addition and
Subtraction of Signed Numbers, Design of Fast Adders, Combinational and Sequential
ALU, ALU expansion strategies, Design of Multipliers and Dividers, Wallace tree and
Booth’s Multipliers, Floating Point Numbers (IEEE754), Floating Point Operations,
Multiplication of Positive Numbers, Signed Operand Multiplication (Booth’s Multiplication
etc.), Fast Multiplication, Integer Division. (10L)
UNIT-III: Computer Organization and Design (Datapath and control path): Instruction
codes, computer registers, computer instructions, timing & control, instruction cycle,
memory reference instructions, Hard-wired Control, Micro programmed Control: Micro
instruction, Microprogram sequencing, 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, Interface
Circuits, Standard I/O Interfaces – PCI Bus, SCSI Bus, Bus Arbitration schemes, USB.
(Brief overview of 8085/8086 microprocessor). (12L)
UNIT-IV: Memory System: Basic Concepts, Semiconductor RAM Memories, Read Only
Memories, Speed, Size, and Cost, Cache Memories – Mapping Functions, Replacement
Algorithms, page mode access, interleaved access. Performance Considerations, Virtual
Memories, Secondary Storage. (12L)
UNIT-V: Basic concepts of pipelining, the instruction pipeline – pipeline hazards –
instruction level parallelism – reduced instruction set –Computer principles – RISC versus
CISC. Introduction to GPP, ASIP and ASIC etc. (10L)
Text Books, Text Books:
and/or 1. David A Patterson, John L Hennessy, “Computer Organization and Design”, (The
reference Hardware/Software Interface) Morgan Kaufmann.
material 2. Carl Hamacher, Zvonko Vranesic, Safwat Zaky: Computer Organization, 5th Edition,
Tata McGraw Hill.
Reference Books:
1. William Stallings, “Computer Organization and Architecture”.
2. Nicholas P Carter, “Computer Architecture & Organisation”.
CSC 402 Theory of Computation 3-0-0 3Credits 3Hours
Reference Books:
1. Elements of the Theory of Computation
By Harry R. Lewis and Christos H. Papadimitriou
Prentice Hall of India.
2. Theory of Automata and Formal Languages
By Anand Sharma
University Science Press
CSC 403 Design and Analysis of Algorithms 3-1-0 4Credits 4Hours
Lower bound: Lower bound for a problem. Computing the lower bound for sorting
(comparison based sorting) and computing the lower bound for computing convex hull using
the lower bound for sorting problem. (2L)
Using Induction to Design algorithm: The celebrity problem, Majority Finding problem.
(2L)
Divide and conquer Problem: Multiplication of two n-bit integers, Strassen’s Matrix
Multiplication problem, Closest pair of points, linear time median finding algorithm,
Convex hull and its computation. (6L)
The Greedy Algorithm: Greedy algorithms and their correctness proof: Interval
scheduling problem, Interval partitioning problem, Minimizing the Lateness of Intervals
problem, Fractional Knapsack Problem. (5L)
Graph Algorithms: Depth First Search, Breadth First Search, Dijkstra's Single Source
Shortest Path algorithm; All pair shortest path algorithm, Minimum Spanning Tree (Prim's
and Kruskal's algorithm). (7L)
Randomized Algorithm: Las Vegas and Monte Carlo; Randomized Quick Sort algorithm
and Min Cut problem. (3L)
Reference Books:
Others: Tim Roughgarden’s video lectures and notes of CS161 and CS261; NPTEL’s
lectures on Design and Analysis of Algorithms; NMEICT video on Design of Algorithms
(http://www.nmeict.iitkgp.ac.in/Home/videoLink/10/3gp).
CSC 404 Object Oriented Programming 2-1-0 3Credits 3Hours
Others:
NPTEL course link by Prof. Partha Pratim Das - https://onlinecourses-
archive.nptel.ac.in/noc19_cs10/preview
CSC 405 Signals and Systems 3-0-0 3Credits 3Hours
Introduction to Fourier analysis, Fourier series for periodic signals, discrete spectrum of
periodic signals; (2L)
Introduction to Fourier transform, properties of Fourier transform, energy and power
spectral density, frequency response of continuous-time systems, some problem examples;
(4L)
Fourier analysis of Discrete Signals, Discrete Time Fourier Transform (DTFT), Properties
of DTFT, Examples of DTFT, DFT. (4L)
Concept of state, state space analysis, state space representation of continuous time
systems (2L)
Reference Books:
1. William Stallings, “Computer Organization and Architecture”.
2. Nicholas P. Carter, “Computer Architecture & Organisation”.
Others: Laboratory Manual
CSS 452 Object Oriented Programming Laboratory 0-0-3 1.5Credits 3Hours
Others: