DSA-UCP-2020

Data Structures and Algorithms

by Sarfraz Raza

https://sites.google.com/site/sarfrazraza

Other related course:

ITC 2017: https://sites.google.com/view/itc-ucp-2017

PF/OOP 2018: https://sites.google.com/view/pf-ucp-2018/

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

DSA 2017: https://sites.google.com/view/dsa-ucp2017

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

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

Algo 2020: https://sites.google.com/view/algo-ucp-2020/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
      - Growable Array with fixed addition
        Its push_back function time complexity analysis
        Vector Implementation
        Its push_back function time complexity analysis
        Arraylist implementation
        Its push_back function time complexity analysis (exercise)

Lecture # 1 -Video Lecture

Lecture 2 - Stack Data Structures

- - - Stack Data Structures
      - FIXED SIZE STACK
        Its ADT (multiple implementations)
        Push/Pop/To multiple versions
        Applications of STACK
        Decimal to any base converter
        Dynamic Stack
        Using Vector implementation

Lecture # 2 -Video Lecture

NOTE - We shifted to online lectures (due to COVID-19 corona virus), and started recording lecture for both the sections, through MicrosoftTeams. In some of the playlist you will see two videos of the same lecture content(One for Section A and other for M). Please take one of the lecture.

Lecture 3 - Stack/Queues Data Structures

- - - Stack Data Structures
      - Discussion on Parenthesis balancing problem
        Implementing THree Stacks Using One array
        Maintaining Minimum and Maximum in Stack
        Maintaining three stacks
        Maintaining one stack of augmented entry
        Tower of Hanoi
        Sorting the Stack
    - QUEUE Data Structures
      - Circular Queue
        Queue Using Two Stacks
        Steueue

Lecture # 3 -Video Lecture

Lecture 4 - Time Complexity

- - Which algorithm is faster
    - - Big-O (Upper Bound)
        Logarithmic function
        little o
        Big Omega
        Little Omega
        Big Theta

Lecture # 4 -Notes

Lecture # 4 -Video Lecture

Lecture 5 - Time Complexity II (Big O, Big Omega and Theta)

- - Which algorithm is faster
    - - Big-O (Upper Bound)
        Logarithmic function
        little o
        Big Omega
        Little Omega
        Big Theta

Lecture # 5 -Notes

Lecture # 5 -Video Lecture (Section M and A)

Lecture 5b(Tutorial) - We did saveral examples and calculated Time Complexity (Big O, Big Omega and Theta)

Problem Set Link

Lecture # 5b -Video Lecture (Section M and A)

Lecture 6 - Expression Evaluator (Infix to Postfix Notation)

- - Expression Evaluator
    - - N^2 Algorithm
  - Infix to Postfix Convertor
    - - Postfix Expression solver

Notes from GeeksforGeeks

Lecture # 6 -Video Lecture (Section M and A)

Lecture 7 - Recursion Begins

- - 1. Sum(N) = 1+2+3+...+N
    - - Recursive Definition
        Sum(N) = N+Sum(N-1); ==> Converts into Recursive function
        Sum(1) = 1 ==> Base case....
  - 2. Factorial(N) = N*N-1*N-2*...*3*2*1
    - - Recursive Definition
        N! = N . (N-1)!
        0! = 1
  - 3. int GCD(int Dividend, int Divisor)
    - - Recursive Definition
        GCD(A, B) = B if (A%B==0)
        GCD(A, B) = GCD(B, A%B)
  - 4. SearchLastOccurence
    - - Recursive Definition

- - - - SearchLAST(A[], Size, T) = -1 Size = 0
        SearchLAST(A[], Size, T) = Size-1 if A[Size-1]==T
        SearchLAST(A[], Size, T) = Search(A[], Size-1, T) if A[Size-1]!=T

- - 5.SearchFirstOccurence
    - - Recursive Definition

- - - - Search(A[], Size, si, T) = -1 Size = si
        Search(A[], Size, si, T) = si if A[si]==T
        Search(A[], Size, si, T) = Search(A[], Size, si+1 T) if A[Size-1]!=T

Codes Done in class

How Recursion works???

Notes on Recursion from GeeksforGeeks

Lecture # 7 -Video Lecture

Lecture 8 - Recursion II (Advanced Recursion)

- - 1. Power Function
    - - Recursive Definition
        SlowPower(X, Y) = X * SlowPower(X, Y-1) Y!=0
        SlowPower(X, Y) = 1 Y=0
        The Problem of Stack Overflow
  - 2. Multiplication Using Addition
    - - Recursive Definition
        SlowMult(X, Y) = X + SlowMult(X, Y-1) Y!=0
        SlowMult((X, Y) = 0 Y=0
        The Problem of Stack Overflow
  - 3. FAST POWER
    - - Recursive Definition
        FASTPower(X, Y) = 1 Y=0
        FASTPower(X, Y) = FASTPower(X, Y/2)^2 Y%2==0
        FASTPower(X, Y) = X * FASTPower(X, Y/2)^2 Y%2!=0
  - 3. FAST Multiplication.
    - - Recursive Definition
        Using Doubling Technique
  - 4. FAST Division
    - - Recursive Definition
        Using Doubling Technique
  - 5. Fibonacci Numbers
    - - Recursive Definition
        Recursive Formulation
        Problem with repetition of the same recursive problem
        Memoization
        Bottom Up Approach and Dynamic Programming

Codes Done in class

Notes on Recursion from GeeksforGeeks

Lecture # 8 -Video Lecture (Section A)

Lecture # 8 - Video Lecture (Section M)

Lecture 9 - Revision Session over previous homeworks

- - 1. Queue
    - - Linear Queue
        Problem of dequeue function
        Circular Queue
        All functions implementation
        enqueue, dequeue, top, isFull, isEmpty
  - Some more time complexity problems.

Notes-Discussion Written in class

Lecture # 9 -Video Lecture (Section A) [Not Yet Uploaded]

Lecture # 9 - Video Lecture (Section M)

Lecture 10 - The Journey of Data Structures So far... Building a Train through connections

- - Journey of Data Structures so far
    - - Variables (pros and cons)
        Why we have to leave Variables???
      - Static Arrays (pros and cons)
        Why we have to leave static arrays???
      - Dynamic Grow-able Heap Array(pros and cons)
        Why have to leave Grow-able Heap Array???
      - Vectors/Arraylist (pros)
        Its analysis
        Its applications
        Stack/Queues Grow-able and static
      - Why Vectors have issues also???
  - Building a linked Train
    - - Using Boggies/Dabbas analogy

Notes Written in class

Lecture # 10 - Video Lecture (Section M)

Lecture 10b - Linked List Data Structures

- - Print Function for Train (made up of Bogies)
  - Recursive Print Function for Train (made up of Bogies)
  - Making Linked List Data Structures
    - - InsertAtbeginning
        Insert At Head
      - InsertAtEnd
        O(N) Implementation
        Using Tail Find and then insert after Tail and update the Tail
        O(1) Implementation using Tail pointer

Notes Written in class (Including the code)

Lecture # 10b - Video Lecture

Lecture 11 - Linked List Data Structures

- - - Circular Linked List
    - Deletion form Linked List
    - Doubly Linked-List

Notes Written in class (Including the code)

Lecture # 11 - Video Lecture

Lecture 12 - Linked List Data Structures (Iterators and STL list data structure)

- - Kth Last Element
  - Detecting the cyclic list.
    - - - iterators
        - forward
        - reverse
  - STL Linked List
    - - - insert and its saveral variants
        - insert(List.begin(), value)
        - insert(List.end(), value)
        - insert(iterator, value)

Notes Written in class (Including the code)

Lecture # 12 - Video Lecture

Lecture 13 - Sorting Algorithms (Bubble Sort and mergeSort) using Iterators and STL list data structure Vectors and List Data Structures

- - Bubble Sort
    - - Using Vectors
        Using list Data Structures
  - Merge
    - - Using Vectors
        Using list
  - MergeSort
    - - Using Vectors
        Using list

Slides

Lecture # 13 - Video Lecture

Lecture 14 - Introduction to Graphs Data Structures

- - Introduction to Graphs
    - - Undirected Graphs
        Directed Graphs
  - Graphs Modeling
    - - Adjacency Matrix
        Adjacency List

Notes

Lecture # 14 - Video Lecture

Lecture 15 - Graphs Traversals

- Graphs Modeling
  - - - Adjacency Matrix
        Adjacency List
- Robot Path Finder Problem
- Finding Connected Components in the graph
- Depth First Search

- - - Its applications

- Breadth First Search

- - - Finding the shortest path in a graph

Slides

Codes I Made during class

Lecture # 15 - Video Lecture

Lecture 16 - Graphs Traversals (DFS, BFS) and finding the paths

- Graphs Modeling
  - - - Adjacency Matrix
        Adjacency List
- Robot Path Finder Problem
- Finding Connected Components in the graph
- Depth First Search and Path Finder

- - - Its applications

- Breadth First Search and Path Finder

- - - Finding the shortest path in a graph

- Grid Graph

- - - Finding DFSpath in Grid Graph
    - FInding BFSPath in Grid Graph

Slides

Codes I Made during class

Lecture # 16 - Video Lecture

Lecture 17 - Union Find Data Structure over Disjoint Sets

AND Segregating/Partitioning the Vector

- Set Data Structure
  - - Input: Given Input of Different Disjoint Set
    - Query 1: Find(x) == Find(y) whether both elements x and y belongs to same Set
    - Query 2: Union(x, y)

- - Union Find Data Structure
    - - Union by Size
        READ about UNION BY RANK (Height of the Set)
        Find(x) and Path Compression

- Segregating/Partitioning the Vector (Discussion on Quiz)

- - 1. Load an array (You may use STL vector, you are not allowed to use any extra vector/array). Then move all the 0’s to the left and the 1’s to the right.
    2. Load a list in an array (You may use STL vectors here, you are not allowed to use any extra memory-array-vector). Then move all the even numbers to the left and the odd numbers to the right.
    3. Load a list in an array (You may use STL vectors here, you are not allowed to use any extra memory) and a value T (which will not be in the list). Then move all the numbers smaller than 7 to the left,and all the numbers greater than 7 to the right end of the vector/array.
    4. Load a list in an array (You may use STL vectors here, you are not allowed to use any extra vectors ). Then move all the 0’s to the left and the 2’s to the right, and all the 1’s in the middle.
    5. Load a list in an array (You may use STL vectors here, you are not allowed to use any extra vectors ) and a value T (which will be in the vector). Then move all the numbers smaller than 7 to the left, in the middle all the 7’s and all the numbers greater than 7 to the right end of the array.

Slides

Codes/Notes - For Segregation/Partitioning the Vector

Lecture # 17 - Video Lecture

Lecture 18 - QuickSort AND Binary Search Tree (Traversals, Searching,

FindMax/Min, Insertion, BinarySearchTree Sort)

- QuickSort
  - - Writing Special Randomized Partition

- - Recursive QuickSort Implementation

- The Story of Data Structures
  - - Why we moved
      - Variables to Static Arrays
        Static Arrays to Dynamic Growable Arrays
        Dynamic Growable Arrays to Vector
        Vector to Linked List
        Where are we standing now???
    - Solving the issue of Binary Searching in the Linked List by Introducing
    - Binary Search Tree
      - Search (recursive and iterator)
        FindMax/FindMin
        LNRTraversal
        Its Output
        BSTAscendingSort
        RNLTraversal
        Its Output
        BSTDescendingSort

Codes (TO ADD)

The Story of Data Structures

Lecture # 18 - Video Lecture

Lecture 19 - Binary Search Tree and its Traversal's Applications

- Binary Search Tree
  - - - Search (recursive and iterator)
        FindMax/FindMin
- Tree Traversal and their applications

- - InOrder Traversal
    - - LNRTraversal
        Its Output
        BSTAscending-Sort
      - RNLTraversal
        Its Output
        BSTDescending-Sort
  - Post Order Traversal
    - - LRN or RLN