16-08-2013, 04:44 PM
Syllabus for MCA First Year Semester – II (with effect from the academic year 2007-2008)
Syllabus for MCA.pdf (Size: 116.43 KB / Downloads: 146)
DATA STRUCTURES
1. SORTING AND SEARCHING TECHNIQUES
Bubble, Selection, Insertion, Shell sorts and Sequential, Binary, Indexed Sequential Searches,
Interpolation, Binary Search Tree Sort, Heap sort, Radix sort
Analysis of Algorithms
Algorithm, Pseudo code for expressing algorithms, time complexity and space complexity,
O-notation, Omega notation and theta notation.
2. HASHING TECHNIQUES
• Hash function
• Address calculation techniques, Common hashing functions
• Collision resolution
• Linear probing, Quadratic
• Double hashing
• Bucket hashing
• Deletion and rehashing
3. LINEAR LISTS
• Stacks: LIFO structure, create, POP, PUSH, delete stack
• Queues: FIFO structure Priority Queues, Circular Queues, operations on Queues
• Linear List Concept
• List v/s Array, Internal pointer & External pointer, head, tail of a list, Null list, length of a
list
GRAPHS
Terminology
• Operations (Add vertex, Delete Vertex, Add Edge, Delete Edge, Find Vertex)
• Traverse Graph (Depth-First, Breadth-First)
• Graph Storage Structures (Adjacency Matrix, Adjacency List)
• Networks
o Minimum Spanning Tree
o Shortest Path Algorithm
o (Dijkstra’s algorithm, Kruskal’s algorithm, Prim’s algorithm, Warshall’s
algorithm)
Term work/Practical : Each candidate will submit a journal /assignments in which at least 10
assignments based on the above syllabus along with the flow chart and program listing. Internal
tests to be conducted separately.
1. Data structure – A Pseudocode Approach with C – Richard F Gilberg Behrouz A.
Forouzan, Thomson
nd
2. Schaum’s Outlines Data structure Seymour Lipschutz Tata McGraw Hill 2 Edition
3. Data structures & Program Design in C Robert Kruse, C.L.Tondo, Bruce Leung Pearson
4. “Data structure using C” AM Tanenbaum, Y Langsam & MJ Augustein, Prentice Hall
India
5. “An Introduction to Structure with application” Jean – Paul Trembly & Paul Sorenson
6. Data structure & program design in C RL Kruse, BP Leung & CL Tondo Prentice-Hall
7. Data structure &Algorithm Analysis in C Weiss, Mark Allen Addison Wesley
PROGRAM LIST IN DATA STRUCTURES
1. Write a program in C to implement simple Stack, Queue, Circular Queue, Priority Queue.
2. Write a menu driven program that implements singly linked list for the following operations:
Create, Display, Concate, merge, union, intersection
3. Write a menu driven program that implements doubly linked list for the following
operations:
Create, Display, Count, Insert, Delete, Search, Copy, Reverse, Sort
4. Write a menu driven program that implements doubly linked list for the following
operations:
Create, Display, Concate, merge, union, intersection
5. Write a menu driven program that implements Singly circular linked list for the following
operations:
Create, Display, Count, Insert, Delete, Search, Copy, Reverse, Sort
6. Write a program in C for sorting methods.
7. Write a menu driven program in C to
a. Create a binary search tree
b. Traverse the tree in Inorder, Preorder and Post Order
c. Search the tree for a given node and delete the node
Write a program in C to implement insertion and deletion in B tree
8. Write a program in C to implement insertion and deletion in AVL tree
9. Write a menu driven program that implements Heap tree (Maximum and Minimum Heap
tree) for the following operations. (Using array) Insert, Delete
10. Write a program to implement double hashing technique to map given key to the address
space. Also write code for collision resolution (linear probing)
11. Write a program in C to implement Dijkstra’s shortest path algorithm for a given directed
graph.