National Institute of Technology Calicut

Module I (20 Hours)

Stack and Queue: Implementation using arrays and Linked lists

Searching Methods: Binary search and Hashing

Sorting: Recursive implementation of Quick Sort and Merge Sort

Module II (15 Hours)

Binary Search Tree: Implementation with insertion, deletion and traversal

Infix Expression Evaluation: Using expression tree

Module II (20 Hours)

Graph Search Algorithms: DFS and BFS on a connected directed graph

Minimal Spanning Tree: Implementation of Kruskal’s and Prim’s Algorithms

Shortest Path Algorithms: Dijkstra and Floyd Warshall Algorithms

Module II (15 Hours)

Disjoint Set operations: Union and Find using rank and path compression.

Applications of Heap: Priority Queue and Heap Sort.

 

References:

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

 

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

L	T	P	Cr
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)
Lab6: Implementation of a single user RDBMS called ‘Minibase’

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

References:

1. 
   Elmasr, 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 301 DESIGN AND ANALYSIS OF ALGORITHMS
Pre-requisite: CSU 203 Data Structures & Algorithms

L	T	P	Cr
3	0	0	3

Module I (10 Hours)

Analysis: RAM model - cost estimation based on key operations - big Oh - big omega - little Oh - little omega and theta notations - recurrence analysis - master's theorem - solution to recurrence relations with full history, probabilistic analysis - linearity of expectations - worst and average case analysis of quick-sort - merge-sort - heap-sort - binary search - hashing algorithms - lower bound proofs for the above problems - amortized analysis - aggregate - accounting and potential methods - analysis of Knuth-Morris-Pratt algorithm - amortized weight balanced trees

 

Module II (10 Hours)

Design: divide and conquer - Strassen's algorithm, o(n) median finding algorithm - dynamic programming - matrix chain multiplication - optimal polygon triangulation - optimal binary search trees - Floyd-Warshall algorithm - CYK algorithm - greedy - Huffman coding - Knapsack, Kruskal's and Prim's algorithms for mst - backtracking - branch and bound - travelling salesman problem - matroids and theoretical foundations of greedy algorithms
Module III (10 Hours)

Complexity: complexity classes - P, NP, Co-NP, NP-Hard and NP-complete problems - cook's theorem (proof not expected) - NP-completeness reductions for clique - vertex cover - subset sum - hamiltonian cycle - TSP - integer programming - approximation algorithms - vertex cover - TSP - set covering and subset sum

 

Module IV (12 Hours)

Probabilistic algorithms: pseudo random number generation methods - Monte Carlo algorithms - probabilistic counting - verifying matrix multiplication - primality testing - miller rabin test - integer factorization - Pollard’s rho heuristic - amplification of stochastic advantage - applications to cryptography - interactive proof systems - les vegas algorithms - randomized selection and sorting - randomized solution for eight queen problem - universal hashing - Dixon’s integer factorization algorithm 
Text Books:

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

New Delhi, 2004, Modules I, II and III.

2. Motwani R. & Raghavan P., Randomized Algorithms, Cambridge University Press, Module IV

References:

1. 
   Anany Levitin, Introduction to the Design & Analysis of Algorithms, Pearson Education. 2003
   
2. 
   Basse S., Computer Algorithms: Introduction to Design And Analysis, Addison Wesley.
   
3. 
   Manber U., Introduction to Algorithms: A Creative Approach, Addison Wesley
   
4. 
   Aho A. V., Hopcroft J. E. & Ullman J. D., The Design And Analysis of Computer Algorithms, Addison Wesley