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:

    1. Students will be introduced with the mathematics of complexity analysis.
    2. To be familiar with different data structures (linear: stack, queue; non-liner: tree, graph) and their variants.
    3. Students will be able write ‘C’ program to solve different problems using different data structures.
    4. To be acquainted with sorting and searching problems with different solutions.
    5. 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.