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, Spring 2024, Fall 2024, Fall 2025, Spring 2026

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.

Lectures

1. Introduction to the course
2. Time complexity: Linear Search, Comparing Time Complexities
3. Time complexity: Asymptotic time complexity notations and analysis; rate of growth; logrithmic time complexities
4. Sorting algorithms selection, insertion, and bubble sort and their time complexities.
5. Stack ADT implementation using arrays.
6. Stack ADT implementation: comparison operators: operator==, operator<
7. Stack ADT implementation using linked structures: constructor, push, top, size, empty.
8. Implementation of linked-structures-based stack ADT: pop, destructor, operator=, and copy constructor
9. Applications of Stack: Infix to Postfix conversion and Postfix evaluation
10. Queue ADT implementation using arrays (linked-based covered in lab)
11. Singly linked list (forward_list in STL). Implementation using a circular linked list with dummy head node.
12. Implementing STL like iterators in singly linked list. Nested classes. Overloading operator*, operator++, and operator++(int) for forward_list
13. Forward_list: implementing operator->, operator==, operator!=. Functions using iterators in forward_list: insert_after, erase_after.
14. Midterm Exam
15. Doubly Linked List/ std::list in STL: Structure of a doubly linked list in STL; Doubly circular linked list with a dummy head node; push_front; pop_front; push_back; pop_back;
16. Implementing iterators (forward / reverse) for the doubly linked list; implementing insert function for inserting a value before a node;
17. Binary Search Tree: graph, tree, binary tree, binary search tree, full tree, minimum height, maximum height, inserting a value in a tree
18. Introduction to Binary Search Trees in STL (set, multiset, map, multimap); Implementation of std::set in STL; implementing insert function for set
19. Deleting a node in a BST. Implementing erase function
20. Traversals in BST: in-order iterative traversal)
21. Traversals in BST: Recursive traversals (in-order, pre-order, post-order)
22. Balanced BST: AVL insertion and deletion
23. Implementing key/value pairs in BST (map); Implementing at and operator[] functions for map ADT
24. Heap: properties, complete binary tree, ReheapUp, ReheapDown
25. Heap Sort. Priority Queue.
26. Hashing: direct addressing, collisions, chaining, search, delete; properties of good hash functions; Chaining-based hashing
27. Hashing: How hashing (unordered_map) is implemented in STL?
28. Hashing: Implementing STL like iterators
29. Hashing: hashing strings, open addressing: linear probing, quadratic probing, double hashing;
30. Graphs: introduction, applications, time complexity of basic graph functions, graph representation (adjacency list, adjacency matrix)
31. Graphs: adjacency list based implementation; Breadth First Search (BFS); Depth First Search;

Textbook(s)

1. C++ Plus Data Structures (6th Ed) by Nell Dale (2016)
2. C++ Programming: Program Design including Data Structures (8th Ed) by D. S. Malik (2018)
3. Data Structures and Program Design in C++ (1st Ed) by Robert L. Kruse and Alexander J. Ryba (2000)
4. C++ Reference Website