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

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

Interview Books

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

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

Fork it!
Clone the forked repository to local system.
Create your feature branch: git checkout -b my-new-feature
Commit your changes: git commit -am 'Add some feature'. Go through Commit Messages guidelines
Push to the branch: git push origin my-new-feature
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

muskanmahajan37 / competitive-programming-1 Goto Github PK

competitive-programming-1's Introduction