Skip to content

sauravjaiswalsj/Competitive-Programming

Repository files navigation

cp

Competitive-Programming Preparation

Ongoing Project

This program developed to learn Algorithms for using in Competitive Prorgamming, but can be used for:

  • Competitive Programming
  • Practicing for Interviews
  • Improving Algorithmic Thinking
  • Practicing for College Class
  • FUN

The course requires:

  • To know at least one programming language well. (You have to be able to use the language efficiently.)
  • You have to be familiarize with some of the basic Data Structures (Array, Stack, Queue, etc.) (Although if you don't know some of them, you may learn it when you come accross.)
PS: I am saying "Any programming language" but in this course mostly we used Java and C++ some C. But still you can follow the curriculum without any knowledge of these languages

Resources

In this course we will use some tools for the questions. As I mentioned above all of these questions already exists, we just highlight them so that you can reach better. Here are the websites/tools that we use through this course:

I gave these tools name because you may not be able to submit your solution or display the question for some websites. It would be better if you just sign up. Although it is not neccesary...

Topics

Here are the topics we included in this curriculum.

DS

  • Stacks
  • Queues
  • Priority queue
  • Hashmap
  • Linked List
  • Trees
  • Heaps
  • Advanced Trees
    • Tries
    • Segment trees
    • Fenwick tree or Binary indexed trees
    • RMQ
  • SQRT Decomposition
  • Disjoint Data Structure
  • C++ STL (optional)

Algo

  • Number Theory

    • Prime Numbers (Sieve of Eratosthenes)
    • GCD and LCM Euclid’s Algorithm
    • Modular Exponentiation
    • Long arithmetic (Multi, Add)
    • Efficient Prime Factorization
  • Combinatorics(Probability-Combinations-Permutations-Matrix..)

  • Computational geometry

    • Primitive Operations
      • Intuition
      • Polygon Inside, Outside
      • Implementing CCW
      • Immutable Point ADT
    • Convex Hull
    • Closest pair problem
    • Line intersection
  • Sorting

    • QuickSort
    • Counting Sort
    • Merge Sort
  • Searching

    • Binary Search
    • Ternary Search
  • Graph Theory

    • Depth First Search (DFS)
    • Breadth First Search (BFS)
    • Dijkstra’s Shortest Path
    • Minimum Spanning Tree
    • Ford Bellman
    • Floyd Warshall
    • LCA (Lowest Common Ancestor)
    • Max Flow / Min Cut
  • Dynamic programming

    • Knapsack
    • Matrix chain multiplication
    • Coin Change
    • Kadane
    • Longest increasing Subsequence (with RMQ)
  • Strings

    • Z algorithm
    • Suffix Trees/Arrays
    • Knuth-Morris-Pratt Algorithm (KMP)
    • Rabin-Karp Algorithm
    • Hash
  • Bit Manipulation

  • Game theory

    • Nim game
    • Grundy numbers
    • Sprague-Grundy theorem
  • Optional Advanced Algorithms

    • AVL Trees
    • Graph Coloring
    • Mo's Algorithm
    • Palindromic Tree
    • Heavy Light Decomposition
    • Dynamic Programming by Profile
    • Rod Cutting
    • Topological Sorting
    • DP with Bitmask - Dynamic Programming
    • Diobhantine Equation - Math
    • Flood Fill - Graph

Here is our Curriculum

Week Topics Optional Topics
1.Week
  • Prime Numbers (Sieve of Eratosthenes)
  • Efficient Prime Factorization
  • Modular Exponentiation
    2.Week
    • GCD and LCM Euclid’s Algorithm
    • Long arithmetic (Multi, Sum, Div, Sub)
    • C++ STL:Vector
    • C++ STL:Pairs
    • C++ STL:Iterators
    3.Week
    • QuickSort
    • Counting Sort
    • C++ STL:String
    • C++ STL:Set
    • C++ STL:Map
    4.Week
    • Merge Sort
    • Binary Search
    • Ternary Search
    5.Week
    • Queue (DS)
    • Stack (DS)
    • Breadth First Search
    • Depth First Search
    • C++ STL: Queue
    • C++ STL: Stack
    6.Week
    • Linked List (DS)
    • Dijkstra’s Shortest Path
    • Minimum Spanning Tree (MST)
    • Floyd Warshall
      7.Week
      • Knapsack
      • Coin Change
      • Kadane
      8.Week Questions from previous topics
      9.Week
      • Trees (DS)
      • Segment Trees (DS)
      • Range Minimum Query (RMQ)
      • Lowest Common Ancestor (LCA)
      • Topological Sorting
      10.Week
      • Ford Bellman
      • Max Flow / Min Cut
      • Longest increasing Subsequence (with RMQ)
      • Heavy Light Decomposition
      11.Week
      • Primitive Operations
        • Intuition
        • Polygon Inside, Outside
        • Implementing CCW
        • Immutable Point ADT
      • Convex Hull
      • Closest pair problem
      • Line intersection
      12.Week
      • Tries (DS)
      • Suffix Trees/Arrays (DS)
      • Knuth-Morris-Pratt Algorithm (KMP)
      • Rabin-Karp Algorithm
      13.Week
      • Heaps (DS)
      • Priority queue (DS)
      • Combinatorics
      14.Week
      • Z algorithm
      • Hash
      • Disjoint Data Structure (DS)
      15.Week
      • Matrix chain multiplication
      • SQRT Decomposition (DS)
      • Mo's Algorithm
      • Rod Cutting
      16.Week Questions from previous topics
      17.Week
      • Nim game
      • Grundy numbers
      18.Week
      • Sprague-Grundy theorem
      • Fenwick tree or Binary indexed trees (DS)
      19.Week
      • Bit Manipulation
      • Palindromic Tree
      • AVL Trees
      20.Week
      • Heavy Light Decomposition
      • Dynamic Programming by Profile
      • Graph Coloring

      Footsteps

      This repository contains examples of various algorithms written on different programming languages...

      Important Algorithms

      Maths C CPP Java Python
      Euclidean GCD
      Fibonacci series
      Pallindrome number
      Perfect number
      Searching and Sorting C CPP Java Python
      QuickSort
      Merge Sort
      Insertion Sort
      Counting Sort
      Radix Sort
      Bubble Sort
      Heap Sort
      Linear Search
      Binary Search
      Tree traversal C CPP Java Python
      Pre-Order Traversal
      Post-Order Traversal
      In-Order Traversal
      Binary Search Tree
      Height of the Tree
      Depth of the Tree
      AVL Tree
      Spanning Tree
      Segment Tree
      Fenwick Tree
      Trie
      Graph Traversal C CPP Java Python
      Breadth First Search
      Depth First Search
      Topological Sort
      Kruskals Algorithms
      Prim's Algorithms
      Belmon Ford Algorithms
      Floyd-Warshall Algorithm
      Dijkstra's Algorithm

      Curated resources

      Coding Practices

      Video Lectures

      Interview Books

      Guides

      Courses

      Sites

      Videos

      System Design

      Computer Science News

      New to programming; follow these resources:

      * Codecademy 
      * Freecodecamp
      * Progate
      * Cs50 by Harvard university 
      

      Few learning websites:

      * udacity
      * Coursera - recommended courses -  Algorithmic toolbox, java programming
      * Edx - CS50 , Mit introduction to programming with python
      * Datacamp
      

      Things to learn before you wanna grab a good companies:

      • Git
      • Postman
      • Learn an Object oriented programming language - Java, c++, python etc
      • Learn DS, Algo
      • Learn Database and dbms concepts
      • Networking
      • Operating systems
      • Web Programming - CS50 web programming course by Harvard university
      • Learn basics of unix

      Github, projects and few use full links:

      Contributing

      1. Fork it!
      2. Clone the forked repository to local system.
      3. Create your feature branch: git checkout -b my-new-feature
      4. Commit your changes: git commit -am 'Add some feature'. Go through Commit Messages guidelines
      5. Push to the branch: git push origin my-new-feature
      6. Submit a pull request 😄

      See Contributor.md ilename] |

      Notes

      Only project maintainers should merge a PR. Other members can add their reviews to a PR but the merging should be done by only a project maintainer.

      Authors