[go: up one dir, main page]
Scribd
Upload
64 views9 pages

ROADMAP

The document outlines a comprehensive curriculum for learning data structures and algorithms, covering topics such as Git, Java basics, sorting algorithms, recursion, dynamic programming, and graph algorithms. It emphasizes the importance of understanding both basic and advanced data structures, mathematical concepts, and various problem-solving techniques essential for competitive programming. Additionally, it provides resources for further study and practice in these areas.

Uploaded by

black.sakura881
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as XLS, PDF, TXT or read online on Scribd
64 views9 pages

ROADMAP

The document outlines a comprehensive curriculum for learning data structures and algorithms, covering topics such as Git, Java basics, sorting algorithms, recursion, dynamic programming, and graph algorithms. It emphasizes the importance of understanding both basic and advanced data structures, mathematical concepts, and various problem-solving techniques essential for competitive programming. Additionally, it provides resources for further study and practice in these areas.

Uploaded by

black.sakura881
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as XLS, PDF, TXT or read online on Scribd
You are on page 1/ 9

<img src="https://static-

fastly.hackerearth.com/static/hackerearth/images/
marketing/algorithm_blog/algo-og.jpg"
width="100%">
1. Introduction to Git
2. Introduction to Programming
- Types of languages
- Flowcharts & Pseudocode
- Flow of the program
- Time & Space Complexity
3. Basics of Java
- Array
o Introduction
o Memory management
o Input and Output
o ArrayList Introduction
o Sorting
o Insertion Sort
o Selection Sort
o Bubble Sort
o Count Sort
o Radix Sort
o Searching
o Linear Search
o Binary Search
o Modified Binary Search
o Two Pointer
o Subarray Questions
- Strings
o Introduction
o How Strings work
o Comparison of methods
o Operations in Strings
o StringBuilder in java
- Maths for DSA
o Introduction

o Complete Bitwise Operators


o Prime numbers
o HCF / LCM
o Sieve of Eratosthenes
o Newton's Square Root
Method
o Number Theory
o Euclidean algorithm
o Advanced Concepts for CP
(later in the course)
o Bitwise + DP
o Extended Euclidean
algorithm
o Modulo Properties
o Modulo Multiplicative
Inverse
o Linear Diophantine
Equations
o Fermat’s Theorem
o Wilson's Theorem
o Lucas Theorem
o Chinese Remainder Theorem
- Functions
o Introduction
o Solving the above math
problems in code
o Scoping in Java
o Shadowing
o Variable Length Arguments
- Recursion
o Introduction
o Why recursion?
o Flow of recursive programs -
stacks
o Convert recursion to iteration
o Tree building of function calls
o Tail recursion
- Sorting:
o Merge Sort
o Quick Sort
o Cyclic Sort
- Backtracking
o Sudoku Solver
o N-Queens
o N-Knights
o Maze problems
o Recursion String Problems
o Recursion Array Problems
o Recursion Pattern Problems
o Subset Questions

- Space and Time Complexity Analysis


o Introduction
o Comparisons of various cases
o Solving Linear Recurrence Relations
o Solving Divide and Conquer Recurrence
Relations
o Big-O, Big-Omega, Big-Theta Notations
o Get equation of any relation easily - best
and easiest approach
o Complexity discussion of all the problems
we do
o Space Complexity

o Memory Allocation of various languages


o NP-Completeness and Hardness
- Object Oriented Programming
o Introduction
o Classes & its instances
o this keyword in Java
o Properties
o Inheritance
o Abstraction
o Polymorphism
o Encapsulation
o Overloading & Overriding
o Static & Non-Static
o Access Control
o Interfaces
o Abstract Classes
o Singleton Class
o final, finalize, finally
o Exception Handling
- Stacks & Queues
o Introduction
o Interview problems
o Push efficient
o Pop efficient
o Queue using Stack and Vice versa
o Circular Queue
- Linked List
o Introduction
o Fast and slow pointer
o Cycle Detection
o Single and Doubly LinkedList
o Reversal of LinkedList
- Dynamic Programming
o Introduction
o Recursion + Recursion
DP + Iteration + Iteration
Space Optimized
o 0/1 Knapsack
o Subset Questions
o Unbounded Knapsack
o Subsequence questions
o String DP
- Trees
o Introduction
o Binary Trees

o Binary Search Trees


o DFS
o BFS
o AVL Trees
o Segment Tree
o Fenwick Tree / Binary Indexed
Tree
o Square Root Decomposition
- Heaps
o Introduction
o Theory
o Priority Queue
o Two Heaps Method
o k-way merge
o top k elements
o interval problems
- HashMap
o Introduction
o Theory - how it works

o Comparisons of various forms


o Limitations and how to solve
o Map using LinkedList
o Map using Hash
o Chaining
o Probing
o Huffman-Encoder
o Tries
-

What basic data structures and algorithms should one learn before starting
competitive programming?
1.
2. Bit manipulation.
3.
- Union-Find Disjoint Sets.
- Segment Tree.
- Binary Indexed Tree (a.k.a Fenwik Tree).
- Graph.
- Tree
- Skip Lists.
- Some self balanced Binary Search trees (e.g. Red Black Trees).

4.
5.
6. Greedy.

7.
8.
Graphs
o Introduction
o BFS
o DFS
o Working with graph components
o Minimum Spanning Trees
o Kruskal Algorithm
o Prims Algorithm
o Dijkstra’s shortest path algorithm
o Topological Sort
o Bellman ford
o A* pathfinding Algorithm

t basic data structures and algorithms should one learn before starting
petitive programming?
Basic data sturctures (arrays, queues, linked lists, etc.).
manipulation.
Advanced data structures:
on-Find Disjoint Sets.
ment Tree.
ary Indexed Tree (a.k.a Fenwik Tree).
ph.
e
p Lists.
e self balanced Binary Search trees (e.g. Red Black Trees).
Brute force and it's tricks and advanced techniques (such as, pruning, bitmasks, meet in
the middle, iterative deepining etc.)
Binary Search (not only the basic code).
edy.
Dynamic programming and it's tricks and optimisations (Knuth optimisation, convex hull
optimisation, bitmasks, etc.).
Graph algorithms:
- Traversal (DFS & BFS) algorithms and how to use them.
- Finding Connected Components.
- Flood Fill.
- Topological Sorting (the famous algorithm uses DFS but you should also
know Kahn's
algorithm that uses BFS as it has much applications).
- Bipartite Check.
- Finding Strongly Connected Components.
- Kruskal's and Prim's algorithms for finding the Minimum Spanning Tree of a
graph and
the variants of the problem.
- Dijkstra's algorithm for solving the Single Source Shortest Path (SSSP)
Problem with out
negaitive cycles.
- Bellman-Ford's algorithm for solving the SSSP problem with negative sycles.
- Floyd-Warshall's algorithm for solving the All Pairs Shortest Path (APSP)
problem and it's
variants.
- Network Flow problem (all it's algorithms, variants and the problems reducable to it).
9 Mathematics:
- You should be familiar with the BigInteger class in Java (maybe write your
own if you are
in love with C++).
- Some Combinatorics.
- Number Theory (all what you can learn about it).
- Probability Theory.
- Floyd-Cycle detection algorithm.
- Game Theory (especially impartial games and Sprague-Grundy Theorem).
10. Strings:
- Basic Manipulation.
- Z-Algorithm for finding a pattern in a text.
- Knuth-Morris-Pratt Algorithm for finding a pattern in a text.
- Hashing and Rabin-Karp Algorithm for finding a pattern in a text.
- Trie data structure.
- Aho-Corasick Algorithm for finding multiple patterns in a text.
- Suffix Array data structure.
- Suffix Automaton data structure.
11. Computational Geometry Algorithms.
Resources
- Codeforces Candidate Master RoadMap
- DSA Cracker Sheet
- Striver's CP List
- SDE-Problems
- A2OJ
- Competitive Programming Algorithms

You might also like