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:
-
T. H. Cormen, C. E. Lieserson, R. L. Rivest, Introduction to Algorithms, PHI, 1998
-
S. Sahni, Data structures, Algorithms, and Applications in C++, McGraw Hill, 1998
CSU 296 DBMS LAB
Pre-requisite: Knowledge of database design and applications
-
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:
-
Elmasr, Navathe, ‘Fundamentals of Database Systems’, 4/e, Pearson Education
-
Reghu Ramakrishnan, Databse Management Systems, McGrawHill
-
http://www.cs.wisc.edu/coral/minibase/minibase.html
CSU 301 DESIGN AND ANALYSIS OF ALGORITHMS
Pre-requisite: CSU 203 Data Structures & Algorithms
-
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:
-
Anany Levitin, Introduction to the Design & Analysis of Algorithms, Pearson Education. 2003
-
Basse S., Computer Algorithms: Introduction to Design And Analysis, Addison Wesley.
-
Manber U., Introduction to Algorithms: A Creative Approach, Addison Wesley
-
Aho A. V., Hopcroft J. E. & Ullman J. D., The Design And Analysis of Computer Algorithms, Addison Wesley
Dostları ilə paylaş: |