Lecture 4 - Stack/Queue Data Structures

• • • • Stack

        • Integer to any base convertor + Complexity Analysis 

      • Queue 

        • • Dynamic Queue using Heap Array and Vector

          • Shifting and two pointer approach - O(N^2)

          • Efficient two pointer approach (in-place reversal) only when resizing - O(N)

          • Queue using 2 dynamic stacks 

          • Stueue data structure

            • Implemented using 3 stacks

            • Works both as a stack and a queue

          • Deque (double-ended queue)

      • Next Lab

        • • Question 1: Implementing Dynamic Queue using vector

          • Question 2: Implementing Dynamic Queue using vector (reversal strategy)

          • Question 2: double-ended queue

      • Next Class

        • Expression Evaluator

Lecture # 4 -Video Lecture

Lecture 5 - Stack Applications

• • • • MinStack

      • Trapping Rain Water Problem 

      • Sliding Window Problem

      • Expression Evaluator

Lecture # 5 -Video Lecture

Lecture 6 - Solitaire Design Project

• • • • Solitaire Project Design

      • Big O

      • Little o

      • Big Omega

      • Little omega

      • Big Theta

Lecture # 6 -Video Lecture

Project-Solitaire Document

Lecture 7:  Time Complexity ( Analysis of Several Examples)

• Problem Set 1 

• Problem Set 2 

• Problem Set 3 

• Problem Set 4 

Lecture 7 - Recording (Time Complexity - Analysis)  

Homework 2 (Time Complexity - Analysis) - Document 

Lecture 8:  Recursion ( In Depth Analysis)

• Recursion Review

• Use Of Base Case And Recursive Calls 

• Denary To Binary Conversion Using Recursion

• Step By Step Analysis Of Function Call Stack During Recursion

Lecture # 8-Video Lecture

(Unfortunately we lost this lecture recording, you may see the previous year's recording)

Lab#4-Recursion

Lecture 9:  Forward List

• Problems In Using Vector Data Structure Involving Insertion/Deletion At iTh Index While Maintaining Sorted Order

• Forward List(Train) Implementation Using A Dummy Engine Node

• InsertAtFront(), DeleteAtFront(), And InsertAtTail() Functions, Doing Insertions And Deletion In O(1)

• Why DeleteAtTail() Is Not Possible In Forward List, Hence Requiring The Need For Doubly Linked List

• Printing Forward List Using Loop

• Discussion On Implementing Stack And Queue Data Structures Using Forward List

Lecture # 9-Video Lecture

lecture 10 :2nd implementation Forward list-Doubly ended list

• A recap on variables, arrays ,Dynamic Arrays ,Growable array, vector ,stack , queue,(Min/Max stack),Dequeue , strew,Forward List.

• Forward List without a Dummy Engine Node.

• insertFront() ,insertAtBack() functions and iterators  .begin(), .end()  ,postincrement, preincrement,== operator and Dereference operator(*) were implemented.

•  Doubly ended list  by maintaining a previous node  pointer (pre), updating all functions accordingly.

• Discussion  on reverse iterators of Doubly ended list.

                                                                                                                                    Lecture 10-Video Lecture 

Lab#5-Linked List 

Project#2-Excel 

lecture 11 : FakeBook, Twitter and Google Maps idea

• A recap on variables, arrays ,Dynamic Arrays ,Growable array, vector ,stack , queue,(Min/Max stack),Dequeue , strew,Forward List.

• Talk about graphs, adjacency matrix

• Idea on how to store user's friends and posts etc

  • need fast access to such information with billions of users

  • advantages & disadvantages of vectors, lists etc for such data.

• Road intersection on map can be thought of as a vertex of directed graph, and each edge is the possible road we can take from there.

                                                                                                                                      Lecture 11-Video Lecture 

Lab#6-Designing Twitter 

Lecture 12:  Binary Search Tree(BST)

• Problems In Using Linked List Data Structure, Searching Being An O(N) Operation 

• Recursive Definition Of A Binary Tree: Being Either Empty Or Having Some Data And A Sub Tree To Its Left Or To Its Right

• Constructing Binary Tree Using A Node Having Data, Left Node Pointer, and Right Node Pointer

• Insertion Function, Setting A Criteria For Insertion Converts A Binary Tree To A Binary Search Tree

• Minimum Value Is On The Extreme Left Of A BST While Maximum Value Stored Is On The Extreme Right

• IN-Order Traversal LNR ,RNL Using Recursion To Sort The Binary Tree In Ascending And Descending

• Pre-Order, Post-Order Traversal Discussion

Lecture # 12-Video Lecture

Lecture 13:  BST Traversal Applications And Problems

• Post-Order LRN, RLN,  Solves Most Problems Of BST.

• Finding Size, Counting Leaves Of BST, Counting Primes, Finding Height All Using Post-Order Traversal

• Printing Nodes Kth Distance Away Also Using Post-Order Traversal

• Pre-Order NLR,NRL Saves The Shape Of A Tree

• Level-Order Traversal Using Queue

• Is Equal Tree And Is Mirror Tree Done Using Pre-Order Traversal

• Special Print For Binary Search Tree 

• Is Balanced Tree Problem Discussion, O(N) Solution By Going Down To Up Instead Of Up To Down

• Implementing BST Using Parent Pointer

• Deletion In BST Using Parent Pointer, 3 Special Cases:  1-Leaf, 2- One Node,  3-Two Node

• Successor And Predecessor Discussion

Lecture # 13-Video Lecture

Lecture 14:  Successor, Predecessor, BST Iterator,  And Synthesize Attribute

• Implementation Of Successor In BST

• In-Order LNR Iterator Class Implementation Using Successor And Predecessor Functions

• Creating MinNode And MaxNode Helper Functions For In-Order Iterator 

• LNRBegin() And LNREnd() Functions For BST

• FindNode Implementation, O(Depth Of The Tree)

• Maintaining Synthesize Attribute In Binary Tree 

• IsBalancedTree() Implementation

• IsBST() Problem Discussion

• Finding Common Ancestor Of Two Nodes

• Path From Root To Leaf For Target Sum Problem

Lecture # 14-Video Lecture

Lecture 15:  BST LeetCode problems

• Symetric tree problem (leetcode 101)

• Construct BST from inorder and postorder traversals (leetcode 106)

• Largest value in tree row 

• Level order traversal II (leetcode 107)

• Validate BST (leetcode 98)

• Same tree (leetcode 100)

Lecture # 15-Video Lecture

Assignment#2-BST Problems

Lecture 16:  Scapegoat Trees & AVL Trees

• Problem with BST is it can get skewed if data inserted in in ascending order.

• Scapegoat and AVL are both self balancing trees.

• Scapegoat saves a size variable in every node, where size is the size of tree below the node.

• at insertion, the tree is imbalanced, (difference in size of both subtrees is more than 1) then the subtree is reconstructed.

• AVL saves height at every node

• If imbalance happens, it applies zig or zag movement of subtree to balance it.

Lecture # 16-Video Lecture

Lab#7-Tree Iterators

Lecture 18:  Leet Code Problems using Sets, Multisets, Maps, Multimaps

• Problems discussed in Lecture:

  • 1. Longest uploaded prefix (Leet code problem no. 2424)

    2. Merge similar Items (Leet code 2363)

    3.  Design a number container system (Leet code 234)

    4. Stock Price Fluctuation (Leet code 2034)

    5. The number of Smallest Unoccupied (Leet code 1942)                                                                         

Lab#8-Map/Sets STL

Lecture 19:  Heap Data Structure and their applications

• Abstract Data type of Heap: Insert, Remove Max, Build Heap, Heapify (Up and Down)

• Definition of Complete Tree and its Advantages Over BST

• Recursive Definition Of Min Heap and Max Heap

• Height Of Complete Tree is Log(N)

• How To Know If Tree is Complete And If Is Heap

• Insertion Operation, Heapifying Up To Maintain Heap Property

• Extraction Operation, Heapifying Down To Maintain Heap Property

• Build Heap and Its Time Complexity Analysis

• Heap Sort, with Discussion On How To Do Heap Sort Using Emplace

Lecture # 19-Video Lecture

Lab#9-Heap 

Lecture 20:  Disk Sort + Treaps + Splay Trees + Skiplists

• Implementation Of Disk Sort Using Priority Queue (Introduction to I/O Models)

• Introduction To Randomized Data Structures

• Treaps Data Structure (Tree +Heap)

• Insertion In Treap Based On BST Property, Order is Maintained According to Heap Property

• Splay Trees (Last Searched Or Inserted Elements are Kept At Or Near The Top)

• Visualization And Discussion On Implementation Of Skiplist

• Proof that Height Of SkipList is O(Log N)

Lecture # 20-Video Lecture

Lab#10-Leet Code Problems

Lecture 21:  Discussion on DOS and text Editor project

• dos shell/cmd intro

• basic dos commands

• directory structure explained.

  • root directory having sub directories or files, which is true recursively downwards.

    • can have multiple root directories (C: D:).

    • or Linux like implementation where only one root directory (/)

• some macro commands.

  • Ctrl+C to terminate commands.

• Vim intro

• basic vim functionality

• command mode and insert mode.

• Expected to use std::list

Lecture # 21-Video Lecture

Project#3-DOS and Text Editor

Lecture 22:  B Trees

• • Why B Tree are Important?

  • Split in B Tree.

  • Insert in B Tree using Preemptive split.

• Further Discussion:

1.       B Trees to store large amount of data (on hard disk)

2.       How many disk reads are required to find data in 1GB and 1TB of data?

Lecture # 22 Part 1-Video Lecture

Lecture # 22 Part 2-Video Lecture

Lecture 23:  B Trees- Deletion

Deletion of node in B Tree

Cases:

1. If k key of a node x and the x is a leaf.

2. If the key k is in node x and x is an internal node.

3. If the key k is not present in internal node x.

Lecture # 23-Video Lecture

Lab#11-B-Tree

Lecture 24.1:  KD Trees

We need a DSA which:

• store 2d-points / nd-points

• find/locate if point exists.

• find nearest neighbour.

KD-Tree

• points on a plane

• subdivide the plane such that no more than one point lies in a single partition.

  • divide in x-axis in middle

  • divide in y-axis in middle.

  • and so, on

• basically, partitioning in half space on each point

Lecture # 24 Part 1 -Video Lecture

Lab#12-KD-Tree

Lecture 24.2:  Sorting Algorithms

• Merge Sort

  • split the array and sort in chunks.

  • and merge back in sorted fashion

  • cost: O(2N*LogN)

• Heap Sort

  • build Heap (Lecture 19 for more info)

  • and read it back.

  • implemented with std::priority_queue

• Quick Sort

  • pick random pivot point.

  • sort around that pivot recursively

    • partition and call quick sort on both sections.

  • cost: O(N^2)

• Count Sort

  • find frequency or count of each element

  • then rebuild the original collection based on the count of each element in sorted fashion

• Bucket Sort

  • each value divided into "buckets"

  • sort them

  • K-way merge them (see lecture 20)

• Radix Sort

  • sorts 2d matrix

  • start from last column, sort it and move to previous column

  • sort until first column

  • matrix sorted such that each row is a number and is sorted as a whole.

Lecture # 24 Part 2 -Video Lecture

Lecture 25: Trapping Rain Water 2 |  Disjoint Union Sets 

• Disjoint Union Set Implementation

• Difference Between log(N) and log*(N)

• Union Operation Based on Ranking Of Elements

• Find Operation, Basic and Then Enhanced To Compress Path

• Kruskal Algorithm, Application of Disjoint Union Sets 

• Problems discussed in the Lecture:

  • 1. Trapping Rain Water 2 (Leet code problem no. 407)

Lecture # 25-Video Lecture

Lecture 26:  The Story of DSA Revisited + Introduction To Hashing
 

• Re-visited Data Structures covered and discussed their downside: 

  • Fixed Size Arrays, Dynamic Arrays, Vectors

  • Stack, Queue, Stueue, Deque, MinMaxStack

  • Singly Linked List, Doubly Linked List

  • Binary Tree, Balance Tree, Scapegoat tree, AVL Trees, Graphs 

  • Heap/Priority Queue, Treap, splay

  • BTrees, KD Trees

• Hashing

  • key, value pair concept

  • searching through key

  • Direct Addressing: Search, Insert, Delete

  • Hash Tables and Hash Functions

  • Collisions because of keys

  • Solution for Collisions: Chaining, Linear Probing, Quadratic Probing, Double Hashing 

Lecture # 26-Video Lecture

Lecture 27:  Hashing, Expected Time Complexity, Universal Hashing

• Review Of The Concept Of Hashing

• Importance of Load Factor In Hash Table

• Case Of Deletion If Collisions Occurred During Insertion

• Analysis of different methods

  • For Chaining: usually cost O(α), where α is N/m

  • No more than m^2 probes in open addressing

• Double hashing

  • rerun on collission

• Universal Hashing

  • chance of collision is 1/m

Lecture # 27-Video Lecture

Lab#13-Hashing

Lecture 28:  Search Engine Project Discussion

• Aim: Perform Queries Such as Word Search, Sentence Search From Over Large Sum Of Data

• Tries Implementation

• Hashing Implementation

• Saving Indexes Of Each Word Of Every File

• Discussion On How To Find Sentence Occurrences

• Setting Priorities In Query Results

• Comparison Between The Two Implementations

Lecture # 28-Video Lecture

Lab14#Huffman Tree

Project#4-Search Engine