Other related course:

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

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

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

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

Lecture 1: Proof Techniques

• Direct Proof
• Prove by Contraposition
• Prove by Contradiction
• Introduction to Mathematical Induction

Notes: Slides on Proofs

Notes: Proofs by Contradiction

Notes: Some more notes on Proofs

Video Lecture (Youtube-Playlist): https://goo.gl/utvq1Z

Assignment # 1 (Proofs and problem solving)

Lecture 2: Mathematical Induction

• Week Induction
  • Principle of Mathematical Induction and Dominos effect
  • Examples of Induction
    • Arithematic Summation
    • Diagonals count in a polygon is N(N-3)/2
    • The cardinality of the power Set of a set A is 2^|A| i.e. 2^n if |A| = n
    • The Game of 4n+1 (where we have 4n+1 biscuits and whoever eats the last one looses, with maximum of 3 can be eaten once) is always 2nd player winning game.
• Strong Induction
  • Prime factorization
  • Coin change problem
• Connection with Recursion
  • Factorial Example and how it is evaluated using Stack recording

Discrete Mathematics Applications by Rosen 7th edition (PDF)

Video Lecture (Youtube-Playlist)

Lecture 03: Recursion and Mathematical Induction

• Recursive algorithm for GCD
  • and its analysis
• Recursive algorithm for Power
• FAST Powering Algorithm
  • Its analysis
• N_P_R and N_C_R their recursive definition and their algorithm.

Video Lecture (Youtube-Playlist)

Assignment # 2 (Induction and Recursion)

Lecture 04: Advanced Recursion Problems

• Calculating AxB using Addition
  • AxB with using Addition-Analysis
• Determinant (Recursive formation) and Its algorithm
  • Its analysis
• Tower of Hanoi
• Prison Break/Maze Solver
• K-length string permutation

Video Lecture (Youtube-Playlist)

Lecture 05: MineSweeper, Stack and its application Bracketing Problem

• Introduction to C#
• Discussion of MineSweeper project
• Stack Data-Structure
  • Bracketing matching problem
  • Decimal to Binary conversion

Video Lecture (Youtube-Playlist)

Assignment # 3 (Stacks and Queues)

Project # 1 (MineSweeper)

Lecture 06: Time Complexity BIG O, Omega, Theta (Talk by Kashif Murtaza)

• Time Complexity (Why hardware improve vs Software Improve)? Should I buy a new hardware or the new software
• Program Time Complexity Analysis
• Time Complexity- Asymptotic Analysis and Comparing two programs
• Time Complexity- Notation BIG O Little o Big Omega and Little omega

Video Lecture (Youtube-Playlist)

Project # 2 (Expression Evaluator based Calculator)

Lecture 07: Time Complexity, Expression-Evaluator, Vector, The idea of dynamic sized linked structures

• Time Complexity (Big O Big Omega and Big Theta)
  • Polynomial Summation
  • Loops (Non recursive)
  • The Story of When the thrill of the quest of finding the most efficient algorithm closes
• Loops + Geometric sequences and Summations (Log N)
• Expression Evaluator
• Circular Queue
• Dynamic Structures
  • Vectors
  • ArrayList
  • LinkedList (idea only)

Video Lecture (Youtube-Playlist)

Lecture 08: Quiz Review and Linked-List

• Quiz related to Stacks and Queues
• Linked List : Node (we called that Dabba/Box)
  • InsertAtFront
  • InsertAtEnd
  • Print (Iteratively /Recursively)
  • DeleteFront
  • DeleteTail

Video Lecture (Youtube-Playlist)

Assignment # 4 (Singly Linked Lists, and Implementing Stacks/Queues based on Linked-List)

Lecture 09 : Doubly LinkedList, Merging Lists, Maintaining the Sorted List, Sorting

• LinkedList Review- InsertAtFront/InsertAtTail/DeleteFront/DeleteTail
  • Making Stack using LinkedList
  • LinkList.InsertAfter and InsertBefore
• Doubly Linked List (lay out)
• Merging Sorted Lists
• Merge Sort over linked list (Discussion and analysis)

Video Lecture (Youtube-Playlist)

Lecture 10- Maintaining the SortedList, DoublyLinkedList, ReversingAList, Using STL

• Linked-List (Revision)
  • Linked-List AddAfter
  • AddBefore
• Doubly Linked-List
• Insert In SortedOrder (revisited)
• Reversing a Linked-List
• STL + Discussing assignment

Video Lecture (Youtube-Playlist): https://goo.gl/uLmZVr

Assignment # 5 (Doubly Linked List/and LinkList Related Problems)

Lecture 11- Linked-List (Swapping two nodes/Dabbas without touching the Data) and Sorting

• Swapping Two Dabbas/Boxes (nodes) in a Doubly Linked-List without touching the data
• BubbleSort of Arrays and Doubly LinkedList

Video Lecture (Youtube-Playlist): https://goo.gl/XJiR6s

Lecture 12- DEBUGGING(LinkedList), Using STL, Implementing Iterators (custom iterators), std::vector, std::list and their iterators

• Debugging programs in Data Structures
• STL-Containers
  • Interface and properties/functionalities
• Iterators
  • Interface and properties/functionalities
• Examples of Vector-Iterator-Matrices through Vector Implementation
• Matrix -Print

Video Lecture (Youtube-Playlist): https://goo.gl/pH6FgB

Project # 3 (Matrices)

Lecture 13- Vector of Vector of int and Vector of list and Sparse matrix

• Vector of Vector internal structures (How pictorially the pointers and shapes will look like)
  • QUIZ Vector Indexing Analysis
  • Vector Indexing and how internally it translates
• Matrix Representation as Vector of vector<int>
  • Transpose of Matrix
  • Matrix Printing
  • Addition
  • Subtraction
  • Multiplication
• Sparse Matrix Implementation and Neighbourhood Maps

Video Lecture (Youtube-Playlist): https://goo.gl/439Xeq

Lecture 14- Matrices Revisited (through Vector of list of int and Sparse Matrix )

• Matrix Multiplication vector of vector of integers
• Matrix vector of list
  • iterators
  • Index(ri, ci) function
  • Addition/Subtraction/Multiplication/Transpose
• How to handle Sparse Matrix
• Take Home MID-TERM EXAM Discussion

Video Lecture (Youtube-Playlist): https://goo.gl/3XBn3C

Lecture 15: Time Complexity in depth analysis

• Time Complexity Variable -Arithmetic Sequence-Series- Dependent-Independent loops
• Time Complexity Geometric Sequence-Series-Function dependent loops
• Time Complexity Arithmetic-Geometric Sequences-Series-
• Time Complexity Practice Problems I:
• Time Complexity Practice Problems II:
• Time Complexity Practice Problems: Variable dependents Three nesting III

Video Lecture (Youtube-Playlist): https://goo.gl/UFbmiG

Grand Quiz (Time Complexity)

Lecture 16- Reversing the Stack, BST recursive definition, Insert, Traversals

• ReverseStack
  • Static Queue
  • Static Stack
• Summary of Previous Vector, Stack, Queue, Linked List) and Need of BST
• BST-Construction
• BST-Insert(continued) and Traversals
  • Inorder Traversal(LNR)
  • PostOrder Traversal(LRN)
  • PreOrder Traversal(NLR)

Video Lecture (Youtube-Playlist): https://goo.gl/BUVeLC

Lecture 17- BST- (Revisited with addition of parent) - BST- Operations and many recursive problems related to binary tree

• BST (Revisited)
  • SearchRecursive
  • PropertiesComputing
• Updating Parent in BST
• Recursive Problems
  • LeavesCount
  • NonLeavesInternal
  • NodesCount
  • PrimesCount
  • EvensCount
  • Binary Search Recursively and Iteratively

Video Lecture (Youtube-Playlist): https://goo.gl/jkDwtP

Lecture 17- (BST- Tutorial Session) BST-Assignment Part I

• Tree Equality
  • Value-wise and Picture-wise
• Tree Reflection (Given Two BST's one is the reflection of the other)
• Delete All Leaves
• BST-Max
• Binary Tree Max
• Binary Tree Min
• Balanced tree Checking
• LEVEL-ORDER Traversal
• Closest-Leaf to Root
• Farthest-Leaf to Root
  • How to find the closest-Leaf to Root path
  • How to find the Farthest-Leaf to Root path
• Predecessor/Successor in a BST
• Sorting Array Using BST

Video Lecture (Youtube-Playlist): https://goo.gl/kF7D41

Lecture 18- BST- related problems (BST-Assignment Part II)

• BST-Assignment Part II
• BST (Search/Maximum/Minimum)
  • Successor
  • Predecessor
  • Iterative_Insert
  • Level-Order Traversal
  • Level-Order(with Labeling)
  • LevelwiseLinkedList
  • Deletion(Basic Cases)
  • Deletion-Transplant-and Deletion(discussed)
  • BinaryTreeCreation
  • RandomizedBinaryTree
  • Sorting an Array using LNR
  • RNL Treewise-Printing

Video Lecture (Youtube-Playlist): https://goo.gl/PPH92o

Lecture 19- BST and its related (BST-Assignment Part III)

• BST and its related problems
  • IsBalancedBinarySearchTree ( O(Nx2^H) VS O(N) algo)
  • DryRun of IsBalancedBST algo
  • Reading-Writing-BST
  • LevelOrder-Lists
  • Maintaining Predecessor and Successor
  • BST-Common Ancestor
  • Finding-Common Ancestor BinTree Subtree & Path-Searching
  • RangeSearch - Merging Trees into Sorted Arrays

Video Lecture (Youtube-Playlist): https://goo.gl/PN82hy

Lecture 20- N-ary Tree and Implementing Directory Structures

• N-ary Tree and DOS-shell Directory Structure
  • Implementing DOS-shell CD and MKDir Command
  • Implementing Deleting a folder under a subdirectory
  • Testing and DirectoryStructure- Writing and Reading and then Notepad related discussions

Video Lecture (Youtube-Playlist): https://goo.gl/1MUK54

Project 4: Dos-Shell

Lecture 21- Notepad (Maintaining Minimum with Deletion) AVL-Tree

• DOS and Notepad (Project Discussion)
  • SHELL Q-A
  • Notepad (Project Part II )
  • Printer related Instructions
• Maintaining Minimum with Delete Problem(The need of AVL)
• Animation of AVL

https://courses.csail.mit.edu/6.006/spring11/rec/rec04.pdf

ANIMATION: https://visualgo.net/en/bst

Video Lecture (Youtube-Playlist): https://goo.gl/LCjgHL

Lecture 22- AVL Tree (Rotations and their impact) + Heap (Tree Based + Array/Vector Based Heap)

• AVL (Revisit)
  • AVL-Rotations and their Impact + Why the height of AVL is O(Log N)
  • AVLSort
• Heap (Tree based construction, HeapifyUp Operation and Insert, Delete )
  • Array Based Heap (Mapping, Left, Right, Parent)
  • Array/Vector Based Heap (HeapifyUp , HeapifyDown, BuildHeap, Insert, FindMin, DeleteMin, HeapSort)

Video Lecture (Youtube-Playlist): https://goo.gl/1stBZ4

Lecture 24- Universal Hashing + String Hashing + Search Engine (By Sarim)

• Hashing and the need to Universal Hashing
  • Universal Hashing I
  • How to Hash strings
  • Discussion on Universal Hashing
• Discussion on the FINAL PROJECT
  • Search Engine Project

Video Lecture (Youtube-Playlist): https://goo.gl/f5k2JY

Lecture 25- BitVector, Implementing dictionaries, Blooms Filters, MergeSort, Nuts and Bolts(Hats Problem), Quick Sort

• Bloom Filter
  • Bit Vector
  • Bloom Filter I (Dictionary building)
  • Bloom Filter Construction
  • Bloom Filter (Analysis for the having a False positive)
• Merge-Sort
• Nuts and Bolts
• Quick-Sort

Video Lecture (Youtube-Playlist): https://goo.gl/8uWT7o

Lecture 26- Sorting (Heap, Bubble, Selection, AVL, Quick-Sort)+Disk-Sort and I-O Complexity and B-Trees

• Sorting Algorithms
  • Heap Sort (using STL priority_queue)
  • BubbleSort (using STL-vector)
  • SelectionSort(using STL-vector)
  • Balanced Tree Sort (using STL-MAP)
  • Merge-Sort
  • Randomized Partition and QuickSort
  • Disk Sort
• I/O Complexity and B-Tree

Video Lecture (Youtube-Playlist): https://goo.gl/VN3jzE

Grand Quiz: All Sorts

Interesting External Links for Help

• ANIMATIONs related to make data structures and algorithms
  • https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
• Practice Quizzes from GEEKsforGeeks.org
  • Data Structures
  • Algorithms Links
  • C++ Programming Links
• Programming Interviews Questions
  • Link - https://www.geeksforgeeks.org/commonly-asked-data-structure-interview-questions-set-1/