Department of Computer Science and Engineering

Module 1 (10 (T) + 7(P) Hours)

Computer abstraction and technology: basic principles, hardware components, Measuring performance: evaluating, comparing and summarizing performance.

Instructions: operations and operands of the computer hardware, representing instructions, making decision, supporting procedures, character manipulation, styles of addressing, starting a program.

 

Module 2 (10 (T) + 7(P) Hours)

Computer arithmetic: signed and unsigned numbers, addition and subtraction, logical operations, constructing an ALU, multiplication and division, floating point representation and arithmetic, Parallelism and computer arithmetic.

 

Module 3 (10 (T) + 7(P) Hours)

The processor: building a data path, simple and multicycle implementations, microprogramming, exceptions, Pipelining, pipeline data path and Control , hazards in pipelined processors

Module 4 (12 (T) + 7(P) Hours)

Memory hierarchy: caches, cache performance, virtual memory, common framework for memory hierarchies

Input/output: I/O performance measures, types and characteristics of I/O devices, buses, interfaces in I/O devices, design of an I/O system, parallelism and I/O.
References:

1. 
   D. A. Pattersen and J. L. Hennesy, Computer Organisation and Design: The Hardware/ Software Interface, 4/e, Morgan Kaufman, 2009.
   
2. 
   V. P. Heuring and H. F. Jordan, Computer System Design and Architecture, Prentice Hall, 2003.
   

CS2005 DATA STRUCTURES AND ALGORITHMS

Pre-requisite: Nil

L	T	P	C
4	0	0	4

Total Hours: 56 Hrs  

Module 1 (14 Hours)

Time and space complexity analysis of algorithms - Asymptotic analysis - Big Oh - Omega - theta notations - Searching and Sorting - Binary search - Quick sort - Heap sort - priority queue using heap - complexity analysis of search and sorting algorithms - average case analysis of quick sort.

Module 2 (14 Hours)

Linked lists - Stack and Queue - Binary tree - in-order, pre-order and post-order traversals - complexity analysis - representation and evaluation of arithmetic expressions using binary tree - Binary Search trees - insertion, deletion and search - average case complexity analysis.

Module 3 (14 Hours)

File structure - Merge sort - B Tree - complexity analysis - Data structures for disjoint sets - union by rank and path compression - complexity analysis - Hash tables.

Module 4 (14 Hours)

Graph representation- DFS, BFS, minimum spanning tree problem - Kruskal's algorithm - implementation using disjoint set data structure - complexity analysis – Prim’s algorithm - Shortest path problem - Dijkstra's algorithms - implementation of Prim's and Dijkstra's algorithms using priority queue data structure - complexity analysis. Floyd-Warshall algorithm.

References:

1. 
   T. H. Cormen, C. E. Lieserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3/e, MIT Press, 2003
   
2. 
   S. Dasgupta, C. H. Papadimitriou, U. Vazirani, Algorithms, McGraw Hill, 2006.
   
3. 
   A. V. Aho, J. D. Ullman and J. E. Hopcroft, Data Structures and Algorithms, Addison Wesley, 1983.
   

CS2094 DATA STRUCTURES LABORATORY

Pre-requisite: Nil

L	T	P	C
1	0	3	3

Total Hours: 56 Hrs  
Theory (14 Hours)

Review of dynamic memory allocation - use of pointers - review of recursion. File organization.

Practical (42 Hours)

1. Searching: Binary search implementation

2. Sorting: Heap sort, Quick sort and Merge sort implementation

3. Stack and Queue implementation using linked list

4. Arithmetic expression to postfix

5. Postfix to expression tree, tree traversal and evaluation

6. Binary search tree - insert, delete and search

7. Linear time DFS and BFS implementation with adjacency list representation

8. Kruskal's algorithm implementation in O((n+e)log n) complexity.

9. Prim's algorithm implementation in O((n+e) log n) complexity.

10 Dijskstra's algorithm implementation in O((n+e) log n) complexity.

References:

1. 
   T. H. Cormen, C. E. Lieserson and R. L. Rivest, Introduction to Algorithms, PHI, 1998.
   
2. 
   S. Sahni, Data structures, Algorithms, and Applications in C++, McGraw Hill, 1998.
   

CS3002 DATABASE MANAGEMENT SYSTEMS

Pre-requisite: Nil

L	T	P	C
3	0	2	4

Total Hours: 70 Hrs