National Institute of Technology Calicut

CSU 297 HARDWARE LAB

Pre-requisites: Knowledge of Digital Electronics and Assembly Language Programming

L	T	P	Cr
0	0	3	2

Digital electronics (12 Hours)

Sequential circuits-Flip flops-shift registers-ring counters and Johnson counter-synchronous and asynchronous counters

80X86 Assembly language programming:

Integer operations-recursive subroutines-two dimensional arrays. (9 Hours)

String manipulation, floating point operations. (6 Hours )

DOS and BIOS interrupts. (6 Hours)

Embedded system experiments (RTLinux). (9 Hours)
References:

1. 
   B. B. Brey, The Intel Microprocessors 8086 to Pentium: Architecture, Programming and Interface, 6/e, Prentice Hall of India, New Delhi, 2003.
   
2. 
   Programming for embedded systems Dream Software team , Willey 2002
   
3. 
   The art of Assembly language programming Randy Hyde
   

CSU 211 Formal Languages and Automata

Pre-requisites: NIL

L	T	P	Cr
3	0	0	3

Module I (12 Hours)

Basic concepts of Languages, Automata and Grammar.

Regular Languages - Regular expression - finite automata equivalence, Myhill Nerode theorem and DFA State Minimization, Pumping Lemma and proof for existence of non-regular languages.

Module I (12 Hours)

Context Free languages, CFL-PDA equivalence, Pumping Lemma and proof

for existence of non- Context Free languages, CYK Algorithm,

Deterministic CFLs.

Module III (9 Hours)

Turing Machines: recursive and recursively enumerable languages,

Universality of Turing Machine, Church Thesis

Module IV (9 Hours)

Chomsky Hierarchy, Undecidability, Reducibility.

References:
1. M. Sipser, Introduction to the Theory of Computation, Thomson, 2001.
2. Hopcroft J. E., Rajeev Motwani, and Ullman J. D., Introduction to Automata Theory, Languages and Computation, Pearson Education Asia,2001.
3. J. C. Martin, Introduction to Languages and the Theory of Computation, Mc Graw Hill, 2002.
4. P. Linz, Introduction to Formal Languages and Automata, Narosa,1998

CSU 201 DISCRETE COMPUTATIONAL STRUCTURES
Pre-requisite: CSU 212 Computational Combinatorics

L	T	P	Cr
3	0	0	3

Module I (10 Hours)

Review of set theory, The Well ordering principle, Mathematical induction, Logic: Basic connectives and truth tables, Logical equivalence, Laws of logic, Rules of inference, Use of quantifiers, Proofs of theorems.

Module II (10 Hours)

Relations and Functions, properties of relations, partial ordering, Hass diagrams, Equivalence relations and partitions, lattices, Boolean algebra, Special functions, The Pigeonhole principle.

Module III (10 Hours)

Groups: Definitions and properties, homomorphisms, isomorphisms and cyclic groups, Coset's and Lagrange's Theorem, Elements of Coding Theory.

Module IV (12 Hours)

 Rings: Definitions, ring properties and substructures, properties of integers, the integer modulo n, ring

homomorphism and isomorphism, polynomial rings, finite fields.

Text Books:

1. 
   Grimaldi R. P., Discrete and Combinatorial Mathematics, 4/e, Pearson Education, New Delhi, 1999
   
2. 
   B. Kolman and R.C. Busby, Discrete Mathematical Structures for Computer Science, PHI, New Delhi, 1994.
   

References:

1. 
   Truss J. K., Discrete Mathematics for Computer Scientists, Pearson Education, New Delhi, 1999
   
2. 
   C. L. Liu C. L., Elements of Discrete Mathematics, 2/e, McGraw Hill, Singapore, 1985
   
3. 
   J. L. Mott J. L., Kandel A and Baker T. P., Discrete Mathematics for Computer Scientists and Mathematicians, 2/e, Prentice Hall of India, New Delhi, 1986.
   

CSU 213 DATABASE MANAGEMENT SYSTEMS
Pre-requisite: CSU 212 Computational Combinatorics / MAG 501 Discrete Mathematics

L	T	P	Cr
3	0	0	3

   

Module I (10 Hours)

Database System concepts and architecture, Data modeling using Entity Relationship (ER) model and Enhanced ER model, Specialization, Generalization, Data Storage and indexing, Single level and multi level indexing, Dynamic Multi level indexing using B Trees and B+ Trees.

Module II (11 Hours)

The Relational Model, Relational database design using ER to relational mapping, Relational algebra and relational calculus, Tuple Relational Calculus, Domain Relational Calculus, SQL.

Module III (11 Hours)

Database design theory and methodology, Functional dependencies and normalization of relations, Normal Forms, Properties of relational decomposition, Algorithms for relational database schema design.

Module IV (10 Hours)

 Transaction processing concepts, Schedules and serializability, Concurrency control, Two Phase Locking Techniques, Optimistic Concurrency Control, Database recovery concepts and techniques, Introduction to database security.

References:

1. Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems, IE, Pearson Education, 2006

2. Ramakrishnan R. & Gehrke J., Database Management Systems, Third edition, 2003, McGraw Hill

3. S K Singh, Database Systems-Concepts, Design and Applications, Pearson Education, 2006

CSU 203 DATA STRUCTURES AND ALGORITHMS

L	T	P	Cr
3	0	0	3

Pre-requisites: CSU 230 Program Design

CSU 212 Computational Combinatorics / MAG 503 Graph Theory and Combinatorics

Module I (10 Hours)

Review of basic data structures, Representation of sets, Set implementation using bit string, linked list.

Hashing – Introduction to simple hash functions, resolution of collisions, Disjoint sets- representations, Union, Find algorithms.
Module II (12 Hours)

Graphs: Representation of graphs, Depth First and Breadth First Traversals, Strong connectivity. Minimum Cost Spanning Tree algorithms- Prim’s, Kruskal’s. Path Finding algorithms – Single Source shortest path and All Pairs Shortest Path algorithms.

Module III (10 Hours)

Balanced Binary Search trees: Red-Black trees- Properties of Red Black trees, Rotations, Insertion, Deletion.

B-Trees- Basic operations on B-Trees – Insertion and Deletion.
Module IV (10 Hours)

Binomial Heaps- Binomial trees and Binomial heaps, Operations on Binomial Heaps.

Fibonacci heaps- Structure of Fibonacci heaps, Mergeable heap operations.
Text Book:

Cormen T.H., Leiserson C.E, Rivest R.L. and Stein C, Introduction to Algorithms, Prentice Hall India, New Delhi, 2004

References:

1. Aho A.V., Hopcroft J.E., and Ullman J.D., Data Structures and Algorithms, Pearson Education, New Delhi, 1983.

1. 
   Sahni S., Data Structures, Algorithms, and Applications in C++, Mc Graw Hill, Singapore, 1998.
   
2. 
   Aho A. V., Hopcroft J. E. & Ullman J. D., The Design And Analysis of Computer Algorithms, Addison Wesley
   

 

CSU 215 COMPUTER ORGANISATION

Pre-requisite: CSU 202 Logic Design

L	T	P	Cr
3	0	2	4

Module I (11 + 10 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 II (10 + 6 Hours)

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

 

Module III (10 + 6 Hours)

The processor: building a data path, simple and multicycle implementations, microprogramming, exceptions, Case study: Pentium Pro implementation.

 

Module IV (11 + 6 Hours)

Memory hierarchy: caches, cache performance, virtual memory, common framework for memory hierarchies, Case study: Pentium Pro memory hierarchy.

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.

 

 

References:

1. 
   D. A. Pattersen and J. L. Hennesy, Computer Organisation and Design: The Hardware/ Software Interface, 3/e, Morgan Kaufman, Singapore, 2004.
   

 

2. 
   V. P. Heuring and H. F. Jordan, Computer System Design and Architecture, Addison Wesley, New Delhi, 1997.
   

CSU 291 DATA STRUCTURES LAB
Prerequisite: CSU 230 Program Design

L	T	P	Cr
0	0	5	3