Algorithms and Olympiad Track Lev 1

These slides and the video capture the key ideas that are covered in the class. These are designed to be self-contained. We strongly recommend that parents and students review these slides/video and try out the small code snippets before and while attempting the Homework activity for the class.

Submit your projects here

Submit Projects

Class 1 – Introduction

Class Material and Notes

Class Notes

Independent Activity

Revise Concepts Covered in Python Level 1 and Level 2
Revise the Level 1 and Level 2 Projects

A (very) quick Introduction to Google COLAB
Website Structure: Class Project and the Homework COLAB Notebook
How to submit HOMEWORK for evaluation?
How to join the Discussion Forum on GITHUB

Class 2 – Fun with Numbers

Class Videos

  1. Introduction and Learning Goals
  2. A naive algorithm to test for primality
  3. Runtime of the naive algorithm for primality
  4. An efficient algorithm to determine primality
  5. Runtime of the efficient algorithm for Primality
  6. A naive algorithm to get a list of ALL prime numbers
  7. Runtime of the naive algorithm to get a list of ALL primes
  8. A Naive algorithm to compute GCD of two numbers
  9. Runtime of the naive algorithm to compute GCD of two numbers
  10. Euclid’s algorithm for efficient GCD computation
  11. Runtime for the efficient GCD computation algorithm
  12. The KEY message — naive algorithms are often not efficient

Enhancement Ideas/Videos

Class Material and Notes

Class Notes , Class Project (COLAB),

  • Algorithms for prime numbers, GCD.
  • Notion of Naive algorithms
  • Study of efficiency in algorithms

Homework Activity

Activity and Marking Criteria

Work on practice problems related to algorithms that work on numbers.

Leaderboard

Class 3 – Time to Search

Class Videos

  1. Introduction and Learning Goals

    Linear Search
  2. Linear Search: Concept and Code
  3. Correctness and Efficiency of Linear Search
  4. Python Commands that do Linear Search
  5. Search options for sorted data

    Jump Search
  6. Concept, Intuition and cases of interest
  7. Jump Search: Implementation in code
  8. Jump Search: Complexity Analysis
  9. Jump Search: Optimal Choice for the Jump

    Binary Search
  10. Binary Search: The Intuition
  11. Binary Search: Implementation in Code
  12. Binary Search: Cases of interest
  13. Why Floor Division and not normal division
  14. Why low = mid + 1, high = mid – 1 (why +1/-1)
  15. Why low <= high in the while loop?
  16. Complexity Analysis of Binary Search (Log complexity)
  17. Compare Linear Search, Jump Search, Binary Search

Class Material and Notes

Class Notes
Class Project (COLAB),

Key Learning Objectives

  1. Linear, Jump and Binary Search
  2. How, from a complexity perspective, binary search wins for sorted data!

Bonus Videos

Independent Activity

Activity and Marking Criteria

Leaderboard

Class 4 – Applications of Binary Search

Class Videos

  1. Introduction and Learning Objectives

Flight Path Problem

2. Problem Statement

3. Why/How Binary Search can be used for the Flight Path Problem

4. Binary Search code for the Flight Path Problem

5. An alternative implementation of Binary Search for Flight Path Problem

Peak Search Problem
6. Problem Statement

7. Why/How Binary Search can be used for the Peak Search Problem

8. Binary Search Code for solving the peak search problem

Shipping Capacity Problem
9. Problem Statement

10. Why/How Binary Search for the Shipping Capacity Problem

11. Helper function

12. Binary Search to find the LEAST shipping capacity

Important Principles
13. Two Conditions for problems where Binary Search Can be applied

Class Material and Notes

Class Notes
Class Project

Key Learning Objectives

  1. Applying binary search to interesting search problems.

Bonus Videos

Independent Activity

Activity and Marking Criteria

Leaderboard

Project Showcase

Class 5 – The Two Pointers Technique

Class Videos

  1. Introduction and Learning Goals

    Pair Sum Problem
  2. Pair Sum Problem Statement
  3. Naive algorithm
  4. Complexity Analysis of the Naive algorithm O(N-squared)
  5. Discussion on Improving the Efficiency
  6. Smart Solution (Two Pointer Technique)
  7. Code for the Two pointer technique
  8. Two pointer technique has O(N) complexity

    Merge Sorted Lists
  9. Problem Statement
  10. Approaches to solve
  11. Two Pointer Technique (Intuition)
  12. Two Pointer Technique (Code)

    Carpet Area Problem
  13. Problem Statement
  14. Naive Solution
  15. Two Pointer technique (Intuition)
  16. Two Pointer technique (Code)

    Summary
  17. Summary and Key highlights of the Two Pointer technique

Bonus Videos

Activity and Marking Criteria

Leaderboard

Class Material and Notes

Class Notes
Class Project

Key Learning Objectives

  1. Two pointer techniques to increase efficiency of algorithms

Class 6 – Midterm Revision and Quiz.

Class Material (Live Quiz)

Key Learning Objectives

  1. Revise the concepts covered so far with an interactive quiz.  
  2. More discussion on the Big-O notation.

Independent Activity

Activity and Marking Criteria

Leaderboard

Class 7 – Sliding Window Algorithms

Class Videos

  1. Introduction and Learning Goals

    Sub-Array Sum problem
  2. Problem Statement
  3. Naive algorithm for the Sub-Array Sum problem
  4. Complexity of the Naive algorithm is O(N-squared)!
  5. Intuition for Fixed Size Sliding Window
  6. CODE for Fixed Size Sliding Window using WHILE loop
  7. Alternate CODE for Fixed Size Sliding Window using FOR loop
  8. Fixed size sliding window is O(N)

    Shortest Sub-Array for a given sum
  9. Problem Statement
  10. Naive Solution
  11. Variable size Sliding Window intuition
  12. Variable Sliding Window Code 1
  13. Closer Analysis
  14. CODE using FOR LOOP
  15. Example Problems from Olympiads

    Shortest Sub-string Problem
  16. Problem Statement
  17. Comparison with the shortest SubArray problem
  18. Illustration of the solution
  19. Code
  20. What happens if the subarray or the substring is NOT found?

Class Material & Notes

Class Notes, Class Project

Key Learning Objectives

  1. Introduction to the sliding window techniques
  2. Problems solved with sliding windows.

Bonus Videos

Independent Activity

Activity and Marking Criteria

Leaderboard

Class 8 – Basic Sorting Algorithms

Class Videos

Class Material and Notes

Class Notes , Class Project

Key Learning Objectives

  1. Basic Sorting Algorithms
  2. Selection Sort, Insertion Sort, Bubble Sort and their variations.

Bonus Videos

Independent Activity

Activity and Marking Criteria

Leaderboard

Project Showcase

Class 9 – Binary Trees and Heaps

Class Videos

  1. Introduction and Learning Goals

    Binary Trees
  2. A very quick introduction to Trees
  3. Perfect Binary Trees
  4. The notion of complete trees
  5. Imposing a Tree Structure on lists
  6. Child and Parent Indices

    Heaps
  7. Introducing Heaps
  8. Determining if a list is a heap or not. (Intuition)
  9. Determining if a list is a heap or not. (Code)

    Heapify
  10. Intuition behind Heapify
  11. Heapify using heapq module
  12. Complexity of Heapify operation is O(N)
  13. Comparing Heapify, Sorting and Min Finding

    Priority Queue Problem
  14. Hospital ER Waiting Room (Priority queue) Problem Statement
  15. Analysis of options to solve the priority queue problem
  16. Heaps based solution for the priority queue problem
  17. Handling new arrival with heappush
  18. Handling root extraction with heappop
  19. Restoring the Heap structure after a customer walks away

    Summary
  20. Summary of Heaps

Class Material

Class Notes, Class Project
Code to Visualize (REPLIT)

Key Learning Objectives

  1. Tree Data structure
  2. Heaps — min/max
  3. Important heap operations
  4. Priority Queues

Bonus Videos

Independent Activity

Activity and Marking Criteria

Leaderboard

Class 10 – Applying Heaps

Class Videos

Class Material

Class Notes, Class Project

Key Learning Objectives

  1. Applying min/max heaps to solve problems
  2. Using python heapq module functions

Bonus Videos

Independent Activity

Activity & Marking Criteria

Apply heaps to solve interesting problems, eg sorting, live leaderboard, running median etc.

Leaderboard

Project Showcase

Class 11 Quiz

Class 12 Project Showcase