/SIG-2018

This is the repository which includes, problems, sample code of a data structure and everything else done in class.

Primary LanguageHTML

Introduction to Competitive programming

Why?

  • Because its fun
  • Helps learn programming deeply
  • Asked in most of the interviews
  • Platform to prove yourself

What we will cover?

  1. Introduction to why algorithms are important and why they are important part of being a Computer Programmer
  2. Big-O, Big-theta, Big-Ohmega Notations this includes time complexity and space complexity and also way to avoid tle error in program
  3. Problem format
    • Problem statement
    • Input
    • Output
    • Estimating if a problem will run on our coding style
    • Estimated complexity we require to build solution
  4. Simple Questions i.e. very easy from hackerearth, cakewalk or beginner from codechef and div2 A from codeforces
  5. Algorithm paradigms
    • Brute force
    • Divide and Conquer
    • Greedy
    • Dynamic Programming
  6. Data Structures and their algorithms
    • Arrays
    • Strings
      • Basic String Searching
      • Knuth Morris Pratt Algorithm
      • Z-Algorithm*
      • Manachar's Algorithm*
    • Trees
      • Traversal (DFS and BFS)
      • Binary Seach Tree
      • AVL and Red-Black tree
      • Heaps
        • Priority Queue
        • Heap Sort
        • Construction time of a heap
    • Graphs
      • Construction using adjacency list
      • Traversal DFS
      • Disjoint Set Unions
      • Minimum Spanning Trees using Kruskal and Prims Algorithm
      • Minimum Distance Algorithms using Floyd-Warshall, Bellman-Ford and Dijkstra
      • Maximum Flow Algorithms*
      • Topological Sort*
      • Will See if more needs to be done
    • Hashing
      • What is hashing.
      • Unneccessary theory but kinda important
    • Segment Tree
      • Basic
      • Lazy propogation*
      • Persistant*
      • Fenwick Binary Tree
    • Stack
      • A simple introduction
      • Few important stack questions
    • Queue
      • Will be done before BFS traversal
    • Trie
  7. Mathematics
    • Euclid's GCD -Mobius function
    • Prime Numbers
    • Sieve of Eratosthene
    • Golbach Conjecture
    • Will add on as I remember
  8. Standard Template Library for C++ coders
    • Vectors
    • Set
    • Multiset
    • Maps
    • Unordered Maps
    • Queue
    • Priority Queue
    • Stack
    • Deque
    • Important STL Functions
  9. Important Algorithms that needs to be covered as well
    • Sorting
      • Quick Sort
      • Counting Sort
      • Radix Sort
    • Binary Search
    • Linear Search
    • Kardane's Algorithm -Greedy algorithm

* If class has reached level to study that topic.