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:

• Leetcode
• Spoj
• Hackerrank
• Topcoder
• Codeforces
• Lightoj
• ACM-Timus

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

• Project Euler
• LeetCode
• InterviewBit
• Codility
• HackerRank
• Project Euler
• Spoj
• Google Code Jam practice problems
• HackerEarth
• Top Coder
• CodeChef
• Codewars
• CodeSignal
• CodeKata
• Firecode

Video Lectures

• Data Structures
  • UC Berkeley Data Structures
  • MIT Advanced Data Structures
• Algorithms
  • MIT Introduction to Algorithms
  • MIT Advanced Algorithms

Interview Books

• Competitive Programming 3 - Steven Halim & Felix Halim
• Cracking The Coding Interview - Gayle Laakmann McDowell
• Cracking The PM Interview - Gayle Laakmann McDowell & Jackie Bavaro
• Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein

Guides

• GeeksForGeeks – A CS portal for geeks
• Learneroo – Algorithms
• Top Coder tutorials
• Infoarena training path (RO)
• Steven & Felix Halim – Increasing the Lower Bound of Programming Contests (UVA Online Judge)

Courses

• MIT – Hacking a Google Interview
• Coderust 2.0 ($$)
• Interview Cake ($$$) [review]
• How to Ace the Software Engineering Interview ($$)
• Grokking the System Design Interview ($$)

Sites

• Coding for Interviews
• Career Cup
• HiredInTech
• Codela
• TestDome
• FreeCodeCamp "Learn to code and help nonprofits"
• Dynamic Programming Practice Problems

Videos

• How to: Work at Google – Candidate Coaching Session for Technical Interviewing [45:45]
• Gayle McDowell – Cracking the Coding Interview [1:14:24]
• Gayle McDowell - Cracking the Coding Interview (examples) [9:05]
• Google Recruiters Share Technical Interview Tips [31:06]
• Google Recruiters Share Non-Technical Interview Tips [28:23]
• Moishe Lettvin – What I Learned Doing 250 Interviews at Google [1:00:24]
• Sean Lee – How to Get a Job at the Big 4 [42:34]
• Ladies Storm Hackathons – Interview Prep Round 1: Strings, Arrays, Linked Lists [1:12:39]
• Randall Koutnik – Rethinking the Developer Career Path [25:03]

System Design

• donnemartin/system-design-primer
• Grokking the System Design Interview
  • This is a paid course but has several free previews such as Designing Instagram
• binhnguyennus/awesome-scalability
• Raph Levien – Rope Science
• Architecture of Open Source Applications
• How should I prepare system design questions for Google/Facebook interview?
• Jeff Atwood – How Good an Estimator Are You?
• 0xAX/linux-insides

Computer Science News

• Hacker News
• Lobsters

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:

• Open Source CS
• A-Z Student Resouce
• Project based in C
• Fnplus
• Build your own X
• Project based Learning *Awesome Beginners

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

• Saurav Jaiswal