Data Structure and Algorithm
Subject Code: IT/T/121
Credit Hours/Class:
Theory Class: 3 Periods/Week
- Theory Class
Marks Distribution:
Theory Class: Two Class Test of 30 marks each for one hour duration.
Final exam of 100 marks for 3 hours written exam
Course Outcomes:
- Students will be introduced with the mathematics of complexity analysis.
- To be familiar with different data structures (linear: stack, queue; non-liner: tree, graph) and their variants.
- Students will be able write ‘C’ program to solve different problems using different data structures.
- To be acquainted with sorting and searching problems with different solutions.
- To be able to solve different problems related to searching and traversal
Syllabus Outline:
PART – I
Introduction: Algorithms, Order Notation: Time and Space Analysis of Algorithms
Sequential Representations of lists: Arrays and Lists, Linked Representation - Linear linked lists. Circular linked lists. Doubly linked lists. Operations on all types of lists. Applications.
Special Lists: Stacks, Queues and their applications.
Recursion: Design of recursive algorithms, Recursion vs. Iteration, Removal of Recursion
PART - II
Trees - Binary Trees, Traversals of binary trees, Structural properties of binary trees. Representation of binary trees in terms of pointers and arrays. General trees
Binary Search Trees: Search, Insertion and Deletion algorithms, Structural properties. Threaded Binary trees.
Balanced Binary Search Trees: AVL tree, B-trees, B+- trees.
PART - III
Sorting and Searching Algorithms: Bubble sort, Selection Sort, Insertion Sort, Quick sort, Merge Sort, Heap sort and Radix Sort, Binary Search, Interpolation Search.
PART - IV
Graphs: Representations, Breadth-first and Depth-first Traversals, Shortest Path algorithms, Minimal Spanning Tree Algorithms
Hashing: Hashing Functions, Collision Resolution Techniques.