INFORMATION TECHNOLOGY
Course Contents and Lecture Schedule
Module 1: Introduction to data structures 9hrs
Data Structures-Introduction and Overview: Definitions, Concept of
1.1 data structure, classifications of data structure- ADT and CDT- Linear 1
and nonlinear.
Arrays: definition, Representation of Single/Two dimensional arrays,
1.2 Applications of array – searching –Sorting - Sparse Matrix- conversion 2
of sparse matrix into 3 tuple form.
Algorithm/Program Development: Analysis of algorithms. Space
Complexity, Time Complexity - Best case, worst case, average case.
1.3 2
Searching : linear and binary search – Complexity Analysis (Detailed
analysis is not required)
Sorting: classifications- Internal sorting – External sorting ,
N2 Sorting : Selection, bubble and insertion- Complexity analysis
1.4 2
(Detailed analysis is not required)
N log n Sorting : Quick Sort and Merge Sort (Recursive Algorithms)-
1.5 2
Complexity Analysis (Detailed analysis is not required)
Module 2: Linked lists 10 hrs
Linked lists: static and dynamic representation, Classification -Singly
linked list- Doubly linked list- Circular linked list, array and linked list.
2.1 2
Singly linked list: Operations on Singly linked list- Traversal-Insertion-
deletion, copying -searching - Merging.
Doubly linked list: Operations on doubly linked list- Insertion-deletion.
2.2 2
Circular Linked list : Operations on circular linked list-Insertion and
2.3 2
deletion
Applications of linked list: Polynomial representation and manipulation
2.4 2
(addition)- Dynamic Memory management.
Dynamic Memory management: Fixed sized and variable sized
2.5 memory allocation and de-allocation. First-fit, best-fit and worst-fit 2
allocation schemes and problems.
Module 3: Stacks and Queues 9 hrs
Stack: Definition, Schematic Diagram of stack, Array and Liked list
3.1 representation of stack , operations on stack using array and linked list ( 2
PUSH(),POP(),STATUS() ) .
Applications of stacks: Infix to postfix conversion- post fix evaluation,
3.2 string reversal, delimiter matching. 3
Queues: Definition, Schematic Diagram of queue, Array and Liked list
representation of queue , operations on queue using array and linked list
3.3 2
( EQUEUE(),DEQUEUE(),STATUS() ) .
Types of queue : circular queue-priority queue- doubly ended queue
3.4 2
Downloaded from Ktunotes.in
INFORMATION TECHNOLOGY
Module 4: Trees and graphs 10 hrs
Trees: Basic terminologies, Binary Trees, Properties of binary trees,
4.1 2
linear and linked representations, Complete and full Binary Tree.
Binary Tree Traversals: Preorder -In order and post order (Recursive,
4.2 non-recursive )-problems 1
Binary tree Applications: Expression tree creation, heap trees
4.3 (concepts), Binary search tree – creation, insertion and deletion and 3
search operations
Graph: Terminologies, set representations, linked/adjacency list
representation, Adjacency matrix linear representation
4.4 2
Graph traversal: Breadth First Search (BFS), Depth First Search (DFS)
- related problems.
4.5 Graph Applications: Shortest Path Problem-Dijkstras Algorithm 2
Module 5: Hash Table 7 hrs
5.1 Hash Tables-Hash Functions- Features of hash function. 1
Different Hash Functions: Division Method- Multiplication Method -
5.2 2
Mid Square Method, Folding Method- related problems.
Collision Resolution Techniques: Closed hashing (Linear probing) and
Open Hashing (Separate Chaining) .
Closed hashing(Linear probing ) -Drawbacks- Remedies - Radom
5.3 3
Probing – Double hashing/Re-hashing –Quadratic Probing, problems to
create hash tables using linear probing and Random probing, double
hash and quadratic probing .
5.4 Open Hashing (Separate Chaining) 1
Downloaded from Ktunotes.in
