Other related course: 

 DSA 2021: https://sites.google.com/view/dsa-itu-2021 

DM 2017: https://sites.google.com/view/ds-ucp-2017/home

DSA 2023: https://sites.google.com/view/dsa-itu-2023 

Algo 2020: https://sites.google.com/view/algo-ucp-2020/home 

Algo 2021: https://sites.google.com/view/algo-itu-2021/home

Lecture 1 - The Story of Data Structures Begins

• • • • The Central Question of Data structures

      • We started with variable data structures

        • • • Their pros 

            • Their limitation

      • We moved to static arrays

        • • • Their applications 

              • • Sorting

                • Searching

            • Their issues

      • Dynamic Arrays (templates implementation)

        • • • Growable Array with fixed addition

              • • Its push_back function time complexity analysis

            • Special Growable Array Implementation

              • • Its push_back function time complexity analysis

Lecture # 1 -Video Lecture

Assignment#1

Lecture 2 - Implementing Vector Iterator

• • • • Why iterators?

        •  Example shown through an array and a vector of STL library.

      • Dynamic Array - Forward Iterator

        •  Using Iterators to:

          • Initializing list

          • Details of the operators * (two implementations), ++ (two implementations), +, !=

        •  begin() and end() functions in DynamicArray class

        •  Constructor details (why they are private in the iterator class)

          •  Constructor of the DynamicArray class, with ranges.

        •  Use of friend relation in the iterator class

      • Discussion on reverse_iterator, const_iterator

Lecture # 2 -Video Lecture

Assignment 1.2

Lecture 3 - Time Complexity

• • • Big O

    • Little o

    • Big Omega

    • Little omega

    • Big Theta

    • Examples and Quiz 

      • Problem Set 1 

      • Problem Set 2 

      • Problem Set 3 

      • Problem Set 4 

Lecture # 3 -Video Lecture

Assignment 2 - Time Complexity

Lecture 4 - Importance of Geometric Series (discussion on assignment)

• • • • Arithemetic Sequence and Series and its bounds, The square series, Power k series and its bounds, square root sequences and series

      • Geometric Sequence

        • What does it mean that something is geometrically decreasing or increasing?

        • Its impact in real life - like deforestation, energy requirements, population growth, food requirements in a country?

        • Why Geometric function is the most essential function to know for an educated mind?

      • The impact of Geometric Series

        • Homework: Watch - Exponential Growth Arithmetic, Population and Energy, Dr. Albert A. Bartlett 

        • Homework 2: Write a 2-3 pages note with examples discussing all what Albert has discussed in terms of Exponential Growth Arithmetic, Population and Energy?  It has to be latex document written on overleaf.com. 

      • Special Topic - Harmonic Series and why it diverges?

Lecture # 4 -Video Lecture

Lecture # 4b -Video Lecture

Assignment 2 - Time Complexity

Lecture 5 - Stack and Queues

• • • • We covered: 

        • Stacks 

          • 1. Fixed Size Stack 

            2. Dynamic Size Stack 

            3. STL::Vector based Implementation 

            4. HW - STL::array<Type, Size> based STL implementation

        • Queue 

          • 1. Why shifting will not work? Time Complexity Violation.

            2. Why only two pointers approach will not work? Space Waste Issue.

            3. Why Circular Array like structure will work? 

        • Quiz 2

          • 1. Implement Static Fixed Size Circular Queue Using Array Based Implementation?

            2. Implement Dynamic Queue using Dynamic Array. 

            3. Implement Static Queue using STL::array. 

            4. Implement Dynamic Queue using STL::vector. 

Lecture # 5 -Video Lecture

Quiz 2 - Stack and Queue

Lecture 6 - Problem Solving with Stack/Queues/Deque/Vector

• • • • We covered:
        
        

        • MinStack -⁠ ⁠https://leetcode.com/problems/min-stack/

        • Trapping Rain Water Problem  - https://leetcode.com/problems/trapping-rain-water/

        • Sliding Window Problem - https://leetcode.com/problems/sliding-window-maximum/

Lecture # 6 -Video Lecture

Quiz 2 - Stack and Queue

Lecture 7 - Expression Converter, Evaluator, Calculator

We covered:

• • • • • • Expression Converter

            • • What is Infix and Postfix Notation

              • How Infix based solution will take O(N^2) time

              • How can Postfix can help

                • Postfix based Expression Evaluator

              • Converting Infix to Postfix Notation Algorithm

          • What is Windows Form Application

            • • Adding Buttons

              • Properties and their understanding

              • Adding Text Boxes

              • Properties and their understanding

              • Adding mouse_click event on buttons and adding their functionalities

              • Adding Attributes of calculator (input1, input2, operation, isFirst)

              • Adding Equal Button

Lecture # 7 -Video Lecture

Assignment 3 - Expression Converter, Evaluator, Calculator

Help Session - Huge Integer

• Discussion of Huge Integer class

• Basic Introduction - Why we need Huge-Integer library and its applications

• Constructor (Allocating memory, increasing and decreasing the size) and Destructor

• Why we need to store the digits in reverse order?

• Making Basic Structure of the class 

  1. 1. • Making UTILITY Functions

          1. • Quantity-wise addition of huge integers

             • Quantity-wise subtraction of huge integers

             • Quantity-wise less than function - Why less than function is all you need?

               1. • • Quantity-wise greaterThan function that uses the lesser than function as a utility. 

                    • Quantity-wise equal function which uses the lesser than function again as a utility. 

• Operator Overloading

  1. 1. • Loading and Printing Huge Integers

          1. • Friend functions operator << and operator >> in huge integers

        • Overloading operator[] to access specific index of a huge integer

        • Adding operator+ - Adding two huge integers

        • Subtracting two huge integers

        • Why You need the static functions ONE, ZERO

        • Implementing operator< , operator> , operator<= , operator>=, operator==

        • Multiplying two huge integers

          1. • Naive Implementation

               1. • Its time complexity analysis

             • FAST Implementation

               1. • Its time complexity analysis

        • Overloading ++ and -- operators

        • Dividing 2 huge integers and discussion on operator/ and operator%

          1. • Discussion on this. 

Help Session -Video Lecture

Assignment 3 - Expression Converter, Evaluator, Calculator

Lecture 8 - Mathematical Induction and Recursion 

• Recall Mathematical Induction

  1. 1. • What is Base Case - and what is its importance

        • What is the inductive Hypothesis implications

        • How to construct the proof argument which completes the proof together with base case. 

        • How it is related to Algorithmic Thinking and Recursion

        • Connection Between Recursion and Induction

          • Base case in recursion ↔ base step in induction

          • Recursive step ↔ induction step

        • Proving Recursive Algorithms Correct Using Induction

• Understanding Recursion (concept of a function calling itself, base case, recursive case)

  1. 1. • Examples of Simple Recursion (factorial, Power, BinarySearch)

          • 1. 1. 1. Need for a Base Case

• How Recursion works - Stack Behavior in Recursion (how function calls are stored and returned)

  1. 1. • How stack frames helps in executing recursion. 

• Efficiency Considerations (recursive vs iterative solutions)

• Common Mistakes (missing base case, wrong induction step, excessive recursive calls)

• Examples - 

• How String Induction and Strong Recursion works

  1. 1. • Example - FAST Power algorithm 

Lecture 8 -Video Lecture

Lecture 9 - Recursion II 

We covered some advanced recursion Problems - Set

• Number Conversion

  • • Stack solution

    • Recursive solution and how the order of display before and after recursive call changes everything?

• Binary number generation upto N using Queue and recursion

  • • How queue solution can help reach the printing of binaries.

      • Its iterative solution

• Power Set

  • • Constructing the inductive hypothesis by looking into the details of how recursive solution we construct it in mathematics.

• Permutations

  • • How Inductive hypothesis works and create the solution.

    • Why double swap is important and if not done can really create a problem?

• Matrix Determinant

Lecture 9 -Video Lecture

Lecture 10 - Recursion III

We covered some more advanced recursion Problems - Set

• Sorting Algorithms's Recursive Implementations

  • • InsertionSort

      • • InsertInSortedArray - Recursive

        • InsertionSort - Recursive

    • SelectionSort

      • • FindMax - Recursively

        • SelectionSort - Recursive

    • Bubble Sort

      • • Utility Function - BubbleUp - Recursive

        • BubbleSort - Recursive

• Tower Of Hanoi

  • • Two Recursive Implementations

      • • With 3 recursive calls.

        • With 2 recursive calls

• Computing Fibonacci Numbers

  • • Recursive Implementation

      • • Its analysis and why it is taking too much time. 

    • Memoization-Based Implementation 

      • • Using vector its memoized code and its analysis (and some errors discussions - related to not passing by reference of vector)

Lecture 10 -Video Lecture

Lecture 11 - Link List

We covered :

Problems in Using Vector Data Structure

• Insertion or deletion at the i-th index requires shifting elements.

• This leads to O(n) time complexity for maintaining sorted order.

• Inefficient when frequent insertions/deletions are required.

Forward List (Train) Implementation

• Forward List can be visualized as a train with nodes as coaches.

• A dummy engine node is used to simplify edge cases (empty list, insertions at front).

• Each node contains:

  • Data (payload).

  • Pointer to the next node.

Operations in Forward List

• InsertAtFront()

  • Adds a new node immediately after the dummy engine node.

  • Runs in O(1) time.

• DeleteAtFront()

  • Removes the node immediately after the dummy engine node.

  • Also takes O(1) time.

• InsertAtTail()

  • Insert at the end of the list by keeping a tail pointer.

  • Possible in O(1) time if tail is maintained.

Why DeleteAtTail() is Not Possible in O(1)

• In a forward list, there is no backward link.

• To delete the last node, we must traverse the list to find the node before the last.

• Hence, DeleteAtTail() requires O(n) time.

Printing a Forward List

• Use a loop to traverse nodes one by one starting from the node after the dummy engine.

• Continue until reaching the last node (nullptr).

• Print each node’s data during traversal.

Lecture 11 -Video Lecture

Lecture 12 - Link List Problem Set

Started with checking basic linked list implementation (insert, delete, traverse).

Showed how Stack can be implemented on top of linked list:

• Push/Pop at head (O(1)).

Showed how Queue can be implemented using linked list:

• Enqueue at tail, Dequeue at head (O(1)).

Discussed common linked list problems:

• Merge Two Sorted Lists → pointer manipulation, iterative + recursive ways.

• Linked List Cycle → two-pointer (slow/fast) technique.

• Remove Nth Node From End → two-pointer, handle edge cases.

• Middle of Linked List → slow/fast pointer method.

Recursive thinking:

• Reverse Linked List → recursive definition of reversal (also hinted with queue).

• Reverse Linked List II → reverse a sublist between two indices.

• Palindrome Linked List → split list, reverse second half, compare halves.

• Maximum Twin Sum → similar idea to palindrome, compute twin sums after reversing half.

• Swap Nodes in Pairs → careful pointer updates, can be recursive or iterative.

Lecture 12 -Video Lecture

Lecture 13 - Doubly Link List and intro to BST

Doubly Linked List (DLL)

• A list where each node contains:

  • Data

  • Pointer to the previous node

  • Pointer to the next node

• Can be traversed forward and backward.

• Supports easy insertion and deletion at both ends.

• Still has linear search time (O(n)).

DLL and Sorted Data

• DLL can be sorted, but searching remains slow compared to arrays.

• Unlike vectors, DLL does not allow direct access to the middle node.

• So normal binary search cannot be applied efficiently.

Using DLL Node Structure as a Tree-Like Idea

• Notice DLL node already has two pointers.

  • Left pointer → can be treated as “smaller” branch.

  • Right pointer → can be treated as “larger” branch.

• Instead of linking in a straight line, we can link nodes in a branching manner.

• Starting from a sorted vector:

  • Pick the middle element as the “root”.

  • Left half becomes the left side.

  • Right half becomes the right side.

• This creates a balanced structure using DLL-style nodes.

Lecture 13 -Video Lecture

Lab 07 - BST creation, insertion and traversals 

Binary Search Tree (BST) Introduction

• Each node has:

  • data

  • L (left child, values ≤ current)

  • R (right child, values > current)

• Recursive structure, naturally fits searching & sorting.

Insertion

• Start at root:

  • If smaller or equal → go left.

  • If larger → go right.

• Insert when a null child is reached.

• Implemented with recursive helper recInsert.

Traversal

• In-order (LNR) → left, node, right.

• Produces values in sorted order.

• Implemented with recprintLNR.

Storing In-order Traversal

• Instead of printing, store values in a vector.

• Gives a sorted vector directly.

• Implemented with storeLNR.

Using BST for Sorting

• Insert all values of a vector into BST.

• Clear the vector.

• Traverse (in-order) to refill vector in sorted order.

• This is Tree Sort.

Lab 07 -Video Lecture

Lecture 14 - BST Problem Set

Tree Traversals

• Print_LNR (InOrder)

• Print_NLR (PreOrder)

• Print_LRN (PostOrder)

• Print_RLN (reverse PostOrder variant)

Leaf-related operations

• Print all the leaves of a BST.

• Delete all leaves of a binary tree.

Nodes at distance K

• Recursive function to print all nodes that are K edges away from root.

Counting problems

• Prime_Counts → recursively count primes in integer tree.

• Even_Counts → recursively count even numbers in integer tree.

• Count number of internal nodes.

• Count number of leaves.

• Count internal nodes with exactly 1 child.

Tree height and balance

• Function to compute the height of the tree.

• Check if a subtree is balanced (height difference ≤ 1).

• Height_Count_Initialization → each node stores height of its subtree.

Comparing trees

• Recursive check if two binary trees are the same (shape + values).

• Recursive check if two BSTs are the same value-wise (shape may differ).

Min/Max in BST

• Recursive TREE-MINIMUM and TREE-MAXIMUM.

Successor / Predecessor

• TREE-SUCCESSOR(x): next value in inorder traversal.

• TREE-PREDECESSOR(x): previous value in inorder traversal.

Closest / Farthest leaves

• Find the closest leaf from root.

• Find the farthest leaf from root.

• Find path from root to closest leaf.

• Find path from root to farthest leaf.

BST validation

• Recursive algorithm to check if a binary tree is a BST.

Inorder traversal with Successor

• Start from TREE-MINIMUM, then repeatedly call TREE-SUCCESSOR.

• Proved this still runs in O(n) total time.

Sorting with BST (Tree Sort)

• Build BST by inserting all elements.

• Inorder traversal produces sorted sequence.

• Best case: balanced tree → O(n log n).

• Worst case: skewed tree → O(n²).

Lecture 14 -Video Lecture

Lecture 15 - BST Problem Set Continued

Questions from Deitel’s Book

• Focused on recursive binary tree problems from Deitel.

• Practiced writing clean, reusable helper functions for:

  • Counting nodes, leaves, and internal nodes.

  • Checking equality and mirror properties of two trees.

  • Finding min/max and verifying BST property.

• Discussed good coding structure — separating logic (recursion) from I/O.

• Reinforced tree traversal orders (Preorder, Inorder, Postorder) as building blocks for all later problems.

• Talked about importance of recursion termination conditions and null checks in tree algorithms.

• These questions served as a warm-up to more conceptual and applied problems in Section III.

Advanced BST Problems

• IsBalancedBT

  • Check if all leaves are at roughly the same level.

  • No two leaf depths differ by more than 1.

  • Used recursive height calculation.

• Efficient Write / Read of BST

  • Need both serialization and deserialization in O(n) time.

  • Used preorder traversal with range limits to rebuild efficiently.

  • Highlighted why naive insertion-based reconstruction causes O(n × h)** time.

• Linked Lists at Each Depth

  • Created a linked list for every level of the tree (one per depth).

  • Used recursion or level-order traversal (queue).

  • Introduced concept of “list of levels.”

• Maintain Next / Previous Links

  • Modified BST nodes to keep explicit in-order successor and predecessor pointers.

  • Also maintained parent link.

  • Discussed logic for updating these links during insertions/deletions.

  • Introduced idea of threaded BSTs for efficient in-order traversal.

• First Common Ancestor (FCA)

  • Found the lowest common ancestor of two given nodes.

  • For BST: used value comparison (go left or right).

  • For Binary Tree: recursively searched both subtrees.

  • Avoided using extra storage structures (no arrays or lists).

Lecture 15 -Video Lecture

Lecture 16 - Scapegoat and AVL

Scapegoat Trees

• Another self-balancing BST, but uses partial rebuilding instead of rotations.

• Based on size balance rather than height balance.

• Each node maintains subtree sizes instead of heights.

• Concept:

  • When tree becomes too unbalanced, find a “scapegoat node” (ancestor causing imbalance).

  • Rebuild that node’s subtree into a perfectly balanced tree.

• Avoids constant rotations — instead rebuilds occasionally.

• Balancing triggered when:

  • A specific threshold is met.

• Steps in Scapegoat Insert:

  • Insert as in normal BST.

  • Check depth vs threshold.

  • If too deep, move upward to find first scapegoat node where size condition fails.

  • Rebuild subtree rooted at that node.

• Advantages:

  • No need to store height or balance factor.

  • Average-case efficient (O(log n)).

  • Simpler deletion (lazy rebuilding).

AVL Trees (Adelson-Velsky and Landis Tree)

• Definition: A BST where for every node,
  abs (height(left) – height(right)) ≤ 1

• Purpose: Keeps tree height = O(log n).

• Balance Factor (BF)

  • BF = height(left) – height(right)

  • Must be in range {–1, 0, +1}.

  • Used to detect imbalance after insertion or deletion.

• Rotations (Rebalancing operations):

  • LL Rotation – Right rotation.

  • RR Rotation – Left rotation.

  • LR Rotation – Left-Right double rotation.

  • RL Rotation – Right-Left double rotation.

• Insertions and deletions may trigger one of these rotations.

• Insertion algorithm (conceptually):

  • Perform normal BST insert.

  • Update heights going upward.

  • If node becomes unbalanced, perform appropriate rotation.

• Deletion algorithm:

  • Similar: delete, update heights, and rebalance if needed.

• Time Complexity:

  • Search / Insert / Delete → O(log n) in all cases.

Lecture 16 -Video Lecture

Lecture 17 - Path Finding

• • Introduction to graph traversal

  • DFS and BFS review

  • Path-finding problems

  • Grid-based path finding

  • Applications of traversal algorithms

Lab 09 -Video Lecture Part-01

Lecture 17 -Video Lecture Part-02

Lecture 18 - Complete Binary Tree and Min/Max Heap

• • Complete binary tree

  • Heap properties

  • Min heap and max heap

  • Heap insertion and deletion

Lecture 18 -Video Lecture

Lecture 19 - Heap, Heap Sort, Merge k Sorted list and Disk Sort

• • Heap sort

  • Merge k sorted lists

  • Disk sorting concept

  • Priority queue implementation

Lecture 19 -Video Lecture

Lecture 20/21 - Problem Set on Priority Queue

• •  Priority queue ADT

  • Heap-based priority queue

  • Scheduling problems

  • Real-world applications

  • Advanced problem solving

Lecture 20 -Video Lecture

Lecture 21 -Video Lecture

Lecture 22 - Splay Tree, Treaps, Skip List

• •  Splay trees

  • Treaps

  • Skip lists

  • Performance comparison

Lecture 22 -Video Lecture

Lecture 23 - Sorting techniques(bubble, selection, insertion, bucket, merge)

• • Bubble sort

  • Selection sort

  • Insertion sort

  • Bucket sort

  • Merge sort

  • Comparison of sorting techniques

Lecture 23 -Video Lecture

Lecture 24 - B-Tree and its Algorithmic Details

• • B-Tree structure

  • Insertion algorithm

  • Deletion overview

  • Use of B-Trees in databases and file systems

Lecture 24 -Video Lecture

Lecture 25 - SLT-set/multiset/map/multimap

• • Set and multiset

  • Map and multimap

  • Internal working principles

  • Time complexity analysis

Lecture 25 -Video Lecture

Lecture 26 - KD-Trees and Union-Find Intro

• • KD-Trees

  • Multidimensional searching

  • Applications of KD-Trees

  • Union-Find data structure

  • Union and find operations

  • Path compression

  • Applications

Lecture 26 -Video Lecture

Lecture 27/28/30 - Story Of DS and Hashing

• • Hash tables

  • Hash functions

  • Collision handling techniques

  • Chaining

  • Open addressing

  • Rehashing

  • Performance analysis

  • Load factor

  • Practical implementation considerations

Lecture 27 -Video Lecture Part-01

Lecture 27 -Video Lecture Part-02

Lecture 28 -Video Lecture

Lecture 30 -Video Lecture

Lecture 29 - File Compression

• • Motivation for compression

  • Lossless compression overview

  • Role of data structures in compression

Lecture 29 -Video Lecture