Data Structures & Algorithms (BTCS 301-18)

Course Objectives

This course aims to enable students to:

Detailed Syllabus

Module 1: Introduction

Basic Terminologies, Elementary Data Organizations, Data Structure Operations (insertion, deletion, traversal etc.), Analysis of an Algorithm, Asymptotic Notations, Time-Space trade off. Searching: Linear Search and Binary Search Techniques and their complexity analysis.

Module 2: Stacks and Queues

ADT Stack and its operations: Algorithms and their complexity analysis, Applications of Stacks: Expression Conversion and evaluation. ADT queue, Types of Queue: Simple Queue, Circular Queue, Priority Queue; Operations on each type of Queue: Algorithms and their analysis.

Module 3: Linked Lists & Trees

Singly linked lists: Representation in memory, Algorithms of operations: Traversing, Searching, Insertion, Deletion; Linked representation of Stack and Queue, Header nodes, Doubly linked list, Circular Linked Lists. Trees: Basic Tree Terminologies, Different types of Trees: Binary Tree, Threaded Binary Tree, Binary Search Tree, AVL Tree; Tree operations and their algorithms with complexity analysis. Applications of Binary Trees. B Tree, B+ Tree: definitions, algorithms and analysis.

Module 4: Sorting and Hashing

Sorting algorithms: Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort, Heap Sort; Performance and Comparison among all methods, Hashing.

Module 5: Graph

Basic Terminologies and Representations, Graph search and traversal algorithms and complexity analysis.

Suggested Books

Core Books

Reference Books

Data Structures & Algorithms Lab (BTCS 303-18)

List of Experiments

  1. Write a program to insert a new element at end as well as at a given position in an array.
  2. Write a program to delete an element from a given array whose value or position is given.
  3. Write a program to find the location of a given element using Linear Search.
  4. Write a program to find the location of a given element using Binary Search.
  5. Write a program to implement push and pop operations on a stack using linear array.
  6. Write a program to convert an infix expression to a postfix expression using stacks.
  7. Write a program to evaluate a postfix expression using stacks.
  8. Write a recursive function for Tower of Hanoi problem.
  9. Write a program to implement insertion and deletion operations in a queue using linear array.
  10. Write a menu driven program to perform insertion operations in a single linked list:
  11. Write a menu driven program to perform deletion operations in a single linked list:
  12. Write a program to implement push and pop operations on a stack using linked list.
  13. Write a program to implement push and pop operations on a queue using linked list.
  14. Program to sort an array of integers in ascending order using bubble sort.
  15. Program to sort an array of integers in ascending order using selection sort.
  16. Program to sort an array of integers in ascending order using insertion sort.
  17. Program to sort an array of integers in ascending order using quick sort.
  18. Program to traverse a Binary search tree in Pre-order, In-order and Post-order.
  19. Program to traverse graphs using BFS.
  20. Program to traverse graphs using DFS.

    21. Lab Outcomes

    The student will be able to:

    1. Improve practical skills in designing and implementing basic linear data structure algorithms
    2. Improve practical skills in designing and implementing Non-linear data structure algorithms
    3. Use Linear and Non-Linear data structures to solve relevant problems
    4. Choose appropriate Data Structure as applied to specific problem definition
    5. Implement Various searching algorithms and become familiar with their design methods