National Institute of Technology Calicut

Module II (3 Lab Sessions)

 

String manipulation programs: sub-string search, deletion – lexicographic sorting of a given set of strings – generation of all permutations of the letters of a given string using recursion..

 

Module III (3 Lab Sessions)

 

Matrix operations: Programs to find the product of two matrices – inverse and determinant (using recursion) of a given matrix – solution to simultaneous linear equations using Jordan elimination.

 

Module IV (3 Lab Sessions)

 

Files: Use of files for storing records with provision for insertion, deletion, search, sort and update of a record.

 

References

1. 
   H. Schildt, C: The Complete Reference, 4/e, Tata McGraw Hill, 2000.
   
2. 
   H. H. Tan and T. B. D'Orazio, C Programming for Engineering & Computer Science, McGraw Hill, 1999.
   
3. 
   T. H. Cormen, C. E. Lieserson, R. L. Rivest, Introduction to Algorithms, PHI, 1998.
   

 

 

 

CSU 215 COMPUTER ORGANISATION
Pre-requisite: CSU 202 Logic Design

L	T	P	C
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 213 DATABASE MANAGEMENT SYSTEMS
Pre-requisite: CSU 212 Computational Combinatorics / MAG 501 Discrete Mathematics

L	T	P	C
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 211 Formal Languages and Automata

Pre-requisite: NIL

L	T	P	C
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 230 PROGRAM DESIGN
Pre-requisites: CSU 101 Computer Programming, Knowledge of Graphs and Trees

L	T	P	C
3	0	2	4

Module1: (10 + 5 Hours)

Review of Programming Constructs- Conditional and Iterative constructs, Data types, Control Structures, Functions, Parameter passing- calling conventions, Recursion, Asymptotic notation for complexity analysis.

Module2: (11 + 12 Hours )

Pointers and dynamic memory allocation, Abstract Data Types, Lists, Stacks, Queues, Trees, Search Trees and traversal algorithms, Heaps and Priority queues.

Module3: .(11 + 7 Hours )

Searching - Linear and Binary, Sorting- Insertion and Selection sorting, Divide an conquer, Quick sort, Merge Sort, Heap Sort, External Sorting.

Module4: (10 + 4 Hours )

Memory Management, Garbage collection algorithms, , Storage allocation for objects with mixed sizes, Buddy systems, Storage compaction.

References:

1. 
   Aho A.V., Hopcroft J.E., and Ullman J.D., Data Structures and Algorithms, Pearson Education, New Delhi, 1983.
   
2. 
   Cormen T.H., Leiserson C.E, Rivest R.L. and Stein C, Introduction to Algorithms, Prentice Hall India, New Delhi, 2004
   
3. 
   Sahni S., Data Structures, Algorithms, and Applications in C++, Mc Graw Hill, Singapore, 1998.
   
4. 
   Wirth N., Algorithms +Data Structures = Programs, Prentice Hall India, New Delhi, 1976.
   

CSU 296 DBMS LAB
Pre-requisite: Knowledge of database design and applications

L	T	P	C
0	0	3	2

Lab 1: Familiarization of the MySQL database – creation and manipulation of tables.

(3 Hours)

Lab 2: Analyze a given situation, develop an ER model and convert the ER model to Relational model. Implement the database using MySQL and manipulate the tables using SQL commands. (6 Hours)

Lab 3: Development of a 2 tier application using a suitable front end. (6 Hours)
Lab 4: Development of a 3 tier application involving manipulation of web databases. (6 Hours)

Lab 5: Implementation of B Trees and B+ Trees. (6 Hours)

Lab 6: Implementation of a single user RDBMS called ‘Minibase’

Write codes for both logical layer and physical layer. (15 Hours)

References:

1. 
   Elmasri, Navathe, ‘Fundamentals of Database Systems’, 4/e, Pearson Education
   
2. 
   Reghu Ramakrishnan, Databse Management Systems, McGrawHill
   
3. 
   http://www.cs.wisc.edu/coral/minibase/minibase.html
   

CSU 203 DATA STRUCTURES AND ALGORITHMS
Pre-requisites: CSU 230 Program Design

CSU 212 Computational Combinatorics / MAG 503 Graph Theory and Combinatorics

L	T	P	C
3	0	0	3

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.

2. Sahni S., Data Structures, Algorithms, and Applications in C++, Mc Graw Hill, Singapore, 1998.

3. Aho A. V., Hopcroft J. E. & Ullman J. D., The Design And Analysis of Computer Algorithms, Addison Wesley

 

CSU 304 COMPUTER NETWORKS

Pre-requisite: CSU 203 Data Structures and Algorithms / CSU 230 Program Design

L	T	P	C
3	0	0	3

Module I (10 hours)

Computer Networks and Internet, the network edge, the network core, network access, delay and loss, protocol layers and services, Application layer protocols, socket programming, content distribution.

Module II (10 hours)

Transport layer services, UDP and TCP, congestion control, Network layer services, routing, IP, routing in Internet, router, IPV6, multicast routing, mobility.

Module III (10 hours)

Link layer services, error detection and correction, multiple access protocols, ARP, Ethernet, hubs, bridges, switches, wireless links, PPP, ATM.

Module IV (12 hours)

Multimedia networking, streaming stored audio and video, real-time protocols, security, Cryptography, authentication, integrity, key distribution, network management.

 

References:

1. 
   J. F. Kurose and K . W. Ross, Computer Networking: A Top-Down Approach Featuring Internet, 3/e, Pearson Education, 2005.
   
2. 
   Peterson L.L. & Davie B.S., Computer Networks, A systems approach, 3/E, Harcourt Asia, 2003.
   
3. 
   Andrew S. Tanenbaum, Computer Networks, 3/E, PHI, 1996.
   
4. 
   IEEE/ACM Trans on Networking
   

CSU 291 DATA STRUCTURES LAB
Prerequisite: CSU 230 Program Design

L	T	P	C
0	0	5	3