Other related courses:

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

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

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

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

Lecture 1: "THE ALGORITHM" and Reachability, Finding Continents Problem

• What is The Algorithms?
  • GCD, Euclid and Alkhwarzmi and The Algorithms
• Robots and Path Finding and reach-ability problem
• Introduction to Graphs
  • Exploring the Graphs
• Finding the Disconnected regions in the graph (Counting the number of Continents or Villages searching problem).

Reading Material: Chapter 3.1, 3.2 (DPV)

Lecture 1(Videos).

Lecture 2: DFS and Its Applications

• Graphs Algorithms?
  • Exploring the Graphs for finding Connectivity in the graph
• DFS and its Application
  • Traversing in Undirected Graphs
  • Traversing in Directed Graphs
    • Tree, Back, forward and cross edges
    • Finding Cycles in a directed graph
  • Sink Vertex and How to find it?
  • Source Vertex and How to find it?

Lecture 2(Videos).

Reading Material: Chapter 3.2, 3.3 (DPV)

Lecture 3: DFS and Its Applications II (Topological Sorting)

• DFS
• Connectivity in DAG
• Finding Source Efficiently in DAG
• Topological Sort

Lecture 3(Videos).

Reading Material: Chapter 3.3 (DPV)

Assignment

Assignment # 1

https://drive.google.com/drive/my-drive

(Solution)

Lecture 4: DFS and Its Applications III (Strongly Connected Components)

• Applications of DFS
  • Topological Sorting and many Dependency based Problems solving.
  • Strongly Connected Components
    • Removing Sink Algorithm
    • Kosaraju's Two Pass Algorithm

Lecture 4(Videos).

Reading Material: Chapter 3.4 (DPV)

Lecture 5: DFS and SCC

• Revision of finding Strongly Connected Components
  • Removing Sink Algorithm
  • Kosaraju's Two Pass Algorithm

Lecture 5(Videos).

Reading Material: Chapter 3.4 (DPV)

Lecture 6: Designing Path Finder for Tesla Car

• Designing Tesla Car's Path Finding algorithm
  • Why DFS will be extremely inefficient?
  • BFS
  • Alarm Clock Algorithm
  • Dijkstra

Lecture 6(Videos).

Reading Material: Chapter 4.1, 4.2, 4.3, 4.4 (DPV)

Lecture 7: Designing Path Finder for Autonomous Driving Car

• BFS (revision)
• Alarm Clock Algorithm
  • Introduction to Heap
  • Dijkstra's Algorithm
    • Where Dijkstra Fails?
  • Bellman-Ford
• Designing Road-map for the Country?

Lecture 7(Videos).

Reading Material: Chapter 4.4, 4.5, 4.6, 4.7 (DPV), Chapter 24 (CLRS)

Assignment # 2

Lecture 8: Designing the road network

• Designing Road-map for the Country?
  • Why Dijkstra cannot give the the minimum road network?
• Minimum Spanning Tree
  • Generalized MST Algorithm
  • Prim's Algorithm
  • Kruskal Algorithm

Lecture 8(Videos).

Reading Material: Chapter 5.1 (DPV), CLRS Chapter 23, Chapter 23 (CLRS)

Video Tutorial Session on Assignment # 2

Lecture 9: Minimum Spanning Tree

• Minimum Spanning Tree
  • Generalized MST Algorithm
  • Kruskal Algorithm
  • Prim's Algorithm
    • Union Find Data Structures

Lecture 9(Videos).

Reading Material: Chapter 5.1 (DPV), CLRS Chapter 23, Chapter 23 (CLRS)

Lecture 10: Closest Pair Problem, and Sorting Algorithms

• Selection Sort
• Bubble Sort
• Insertion Sort and Loop Invariant
• Divide and Conquer
  • Merge Sort
  • Hats Finding problem
  • Quick-Sort

Lecture 10(Videos).

Reading Material:

Lecture 11: Prune and Search (Application of geometric series)

• Finding the missing number from the range of 0-(N-1) in an array of N Size
  • O(N) Solution
  • O(N) Bit Complexity Algorithm
• The Fundamental of Master Theorem

Lecture 11(Videos).

Reading Material:

Lecture 12: Geometric Series and Solving Recurrences

• Geometric Series and Solving Recurrences
• Master Theorem and its three cases
• Randomized Algorithm
• Finding the Median in Linear Time

Lecture 12(Videos).

Reading Material: Chapter 4 CLRS, DPV 2.2 (Recurrences, Merge Sort, Medians)

Lecture 13: Quick-Sort, Median of Median Problem, Lower Bounds and Counting Sort

• Quick Sort
  • Worst Case
  • Best Case
  • Even if the partitions are in skewed proportions...???
• Finding K'th smallest Element using Median of Median Problem
• Lower Bound
• Sorting in linear time (pseudo-algorithms).

Lecture 13(Videos).

Reading Material: Chapter 9 CLRS

Lecture 14: Median of Median Problem, Counting Sort, Bucket-Sort, Radix Sort.

• Deterministic Quick Sort
  • Finding K'th smallest Element using Median of Median Problem
• Sorting in linear time (pseudo-algorithms).
  • Range Search
• Radix Sorting
  • Range between (1-N^2) and how to sort them
• Bucket Sorting

Lecture 14(Videos).

Reading Material: Chapter 9, Chapter 8 CLRS

Lecture 15: Revision (Median of Median and Master Theorem)

• Deterministic Quick Sort
• Master Theorem (revisited)

Lecture 15(Videos).

Reading Material: DPV 2.2 (Recurrences, Merge Sort, Medians)

Lecture 16: Divide and Conquer

• Divide and Conquer (BASIC IDEA)
  • Karatsuba Algorithm of Multiplication
  • Recurrences Relations
  • Iterative Merge Sort
  • Contiguous Sequence

Lecture 16(Videos).

Reading Material: Chapter 2 DPV

Lecture 17: Dynamic Programming Begins

• Catalan Numbers
  • Its Recurrence and Recursive Implementation
  • Its Time Complexity???
  • Memorization Based Implementation.
• Fibonacci Numbers
  • Its DP solution
• TriSum Problem

Lecture 17A(Videos).

Reading Material: Chapter 6.1 DPV

Lecture 17B: Dynamic Programming II

• Paths in DAG
  • Shortest Path Implementation
  • Longest Path Implementation
• Longest Increasing Sequence
  • Its connection with DAG
  • How to use PathDAG Solver to solve this increasing decreasing sequence.
  • The Idea of Array based Implementation

Lecture 17B(Videos).

Reading Material: Chapter 6.1, 6.2 DPV

Lecture 18: Dynamic Programming III

• Paths in DAG and its connection with recursive tree of DP problems
• Longest Increasing Sequence
  • Array based Implementation
• Contiguous Max Subset sum problem
  • Its Divide and Conquer solution
  • Its recurrence???

Lecture 18(Videos).

Reading Material: Chapter 6.1-2 DPV

Lecture 19: Dynamic Programming IV

• CONTIGUOUS Sequence
• Rod Cutting Problem
• Edit Distance and LCS and its connection with DAG

Lecture 19(Videos).

Reading Material: Chapter 6

Lecture 20: Dynamic Programming V

• Edit Distance and LCS and its connection with DAG
• Edit Distance and LCS DAG and 2D-Array Based (Top DOwn as well as Bottom Up implementations).
  • Book Keeping and Printing the solution

Lecture 20(Videos).

Reading Material: Chapter 6

Lecture 21: Dynamic Programming VI

• Edit Distance and LCS DAG and 2D-Array Based (Top DOwn as well as Bottom Up implementations).
  • Book Keeping and Printing the solution
• Knapsack Problem
• Coin Change Problem
• Activity Selection Problem
• Matrix Chain Multiplication

Lecture 21 (Videos).

Reading Material: Chapter 6 and Dynamic Programming Slides by Dr Ashraf Sb

Lecture 22: Dynamic Programming VII

• Matrix Chain Multiplication and Dynamic Programming

Lecture 22(Videos).

Reading Material: Chapter 6

Dynamic Programming Slides by Dr Ashraf Sb

Lecture 23: P vs NP

• P Class Problems
• Evolution of Graphs Problems
• NP Class
• Complexity-Reduction

Lecture 23(Videos).

Reading Material: Chapter 8: NP-complete problems (DPV) , Chapter 34 NP-Completeness (CLRS)

Lecture 24: P vs NP (Reduction)

• NP Class
• Complexity-Reduction

Lecture 24 (Videos).

Reading Material: Chapter 8

All Slides upto P-VS NP

Lecture 25: Introduction to computational geometry: Sweepline Algorithm

• Finding maxima points set in 2D
  • Divide and Conquer algorithm
  • Sweep-line algorithm

https://en.wikipedia.org/wiki/Maxima_of_a_point_set

• Convex Hull computation
  • Sweepline and Jarvis March

http://db.cs.duke.edu/courses/fall08/cps230/Lectures/L-20.pdf

• Rectangles union fixed on the real line

https://briangordon.github.io/2014/08/the-skyline-problem.html

Lecture 25 (Videos).

Reading Material: Chapter 33 (CLRS)

Lecture 26: All Pair Shortest Paths (APSP)

• Review of Single Source Shortest Paths (SSSP)
  • BFS, Dijkstra, Bellman-Ford Algorithms
• Using SSSP algorithms to find APSP
  • Results
• First Slow APSP Algo with Dynamic Programming Approach
• Building connection with DP-Approach algorithm to Matrix Multiplications
  • Slow Algorithm for APSP using Matrix Multiplications (V^4)
  • FAST Powering Algorithm and FAST-APSP-Algo (V^3 x log V)
• Floyd Warshal Algorithm

Lecture 26 (Videos).

Reading Material: Chapter 6.6 (DPV), Chapter 25.1, 25.2 (CLRS)

The War of Algorithms (Talk by Dr. Ashraf)

• History of Algorithm and its repurcussions and whats the future forward (A beautiful talk by Dr. Ashraf Iqbal).

The Talk by Dr. Ashraf.

Lecture 28-29: Greedy Algorithms

• Cake Cutting Problem
  • Proving the Optimality of Greedy property/selection
• Maximizing the Activity Selection Problem
• File Compression Technique (Huffman Coding)

Youtube Playlist 1: Lecture 28

Youtube Playlist 2: Lecture 29

Reading: Slides , DPV 5.2 , CLRS: Chapter 16