Rabeeh Abbasi

Rabeeh Abbasi

Doing research in social media and network analytics

Data Structures and Algorithms

Undergraduate course, Quaid-i-Azam University, 2021

Offered: Fall 2011, Fall 2012, Fall 2014, Fall 2015, Fall 2018, Fall 2019, Fall 2020, Fall 2020, Spring 2011, Spring 2012, Spring 2014, Spring 2015, Spring 2019, Spring 2020, Fall 2020, Spring 2021, Fall 2021, Spring 2023

Aims and Objectives

Data structures are used to store and retrieve data efficiently. The main purpose of this course is to understand basic data structures and algorithms associated with these data structures. The course covers a wide range of data structures and their applications for solving various problems. At the end of the course, students should be able to implement basic data structures, compare performance of various data structures, and use appropriate data structures to solve a variety of problems.

Weekly Contents

  1. Introduction to course, Structures in C++, Templates (functions, specialization)
  2. Handling text files. Working with command line arguments, Handling binary files
  3. Time complexity, Selection Sort, Bubble Sort, Insertion Sort
  4. Stack ADT (array based implementation)
  5. Introduction to linked structures, Stack ADT (linked structures based implementation)
  6. Queue ADT (array based implementation), Queue ADT (linked structures based implementation)
  7. Array based unsorted list ADT, iterator functions, Linked structures based list ADT (unsorted)
  8. Array based sorted list ADT, binary search, Sorted linked list
  9. Recursion, Pointers by reference
  10. Binary Trees, Binary Search Trees (BST), Node structure, search, insert
  11. BST: delete, BST: iterators: in/pre/post/level-order traversals, copy constructor, assignment operator overloading, tree deletion
  12. AVL trees concepts, AVL trees - implementation insert
  13. Heap structures and priority queues, heap sort
  14. Hashing: direct addressing and chaining, open addressing, linear/quadratic/double hashing probing, string hashing
  15. Graphs, Breadth First Search, Depth First Search, Shortest Path

Textbook(s)

  1. C++ Plus Data Structures (5th Ed) by Nell Dale (2013)
  2. C++ Programming: Program Design including Data Structures (8th Ed) by D. S. Malik (2018)