Course description
Learnbay Provides competitive Programming training for working professional and college graduate those who are interested to attend programming competition and targeting for interviews in companies like Microsoft,Facebook,Google etc.
Our course content is designed by experts to match with the real world requirements for advance level.50 Advance problems are implemented and discussed in the class with tons of assignments for practice.
Prerequisites:
Should have knowledge of data structures and Algorithms.This course covers the advance problems only and you should know data structures and algorithms to attend this session.
Who Should Attend:
Working Professional And College Graduate preparing for interviews in companies like Facebook,Google,Microsoft etc
Those who wants to learn and improve problem solving skills and improve their rank/Score in Competitive Programming.
Course delivery:
Online training
What will you Learn:
This course will benefit you to perform your programming jobs better and also help you to get to better positions, with confidence, in case you are looking out for jobs.This course will help you to to handle Advance Algorithm based interview with more confidence.
About Instructor:
Our Data Structures And Algorithms Trainers are Working in Top product based MNCs like Micrsoft,Amazon and premier institute like IIIT hyderabad,IIT and NIT and expert in problem solving and competitive programming.
Course Content:
List of Topics for programming Competitions –
- Basic Geometry/Euclidean Geometry/Coordinate Geometry/ [3-D variants of everything].
- Computational Geometry.
- Graham Scan algorithm for Convex Hull O(n * log(n)).
- Online construction of 3-D convex hull in O(n^2).
- Bentley Ottmann algorithm to list all intersection points of n line segments in O((n + I) * log
- Rotating Calipers Technique.
- Line Sweep/Plane Sweep algorithms –
- Area/Perimeter of Union of Rectangles.
- Closest pair of points.
- Area of Union of Circles.
- Delayunay Triangulation of n points in O(n * logn).
- Voronoi Diagrams of n points in O(n * logn) using Fortunes algorithm.
- Point in a polygon problem –
- O(n) solution without preprocessing.
- O(logn) algorithm with O(n * logn) preprocessing for convex polygons.
- Problems on computational geometry
- String Algorithm.
- KnuthMorrisPratt algorithm.
- Problems – NHAY, PERIOD on SPOJ.
- Aho Corasick algorithm.
- Problems – WPUZZLES on SPOJ.
- Suffix Arrays
- O(n^2 * logn) Naive method of suffix array construction
- O(n * logn^2) method of suffix array construction
- O(n * logn) method of suffix array construction.
- O(n) method of suffix array construction
- O(n) LCA preprocess on Suffix Arrays to solve a variety of string problems.
- Suffix Trees
- O(n) construction of Suffix trees using Ukkenon’s algorithm.
- O(n) construction of Suffix Trees if provided with Suffix Arrays using Farach’s algorithm.
- Suffix Automata
- O(n) Suffix Automaton construction.
- Dictionary Of Basic Factors
- O(n * logn) method of DBF construction using Radix Sort.
- Manachar’s algorithm to find Lengh of palindromic substring of a string centered at a position for each position in the string. Runtime -> O(n).
- Searching and preprocessing Regular Expressions consisting of ‘?’, ‘*’.
- Multi-dimensional pattern matching.
- KnuthMorrisPratt algorithm.
- Basic Graphs
- Representation of graphs as adjacency list, adjacency matrix, incidence matrix and edge list and uses of different representations in different scenarios.
- Breadth First Search.
- Depth First Search.
- Strongly Connected Components.
- Biconnected Components, Finding articulation points and bridges].
- Dijkstra algorithm –
- problems –
- SHPATH on SPOJ.
- problems –
- Floyd Warshall algorithm –
- problems –
- COURIER on SPOJ.
- problems –
- Minimum Spanning Tree
- problems –
- BLINNET on SPOJ.
- problems –
- Flood-fill algorithm
- Topological sort
- Bellman-Ford algorithm.
- Euler Tour/Path.
- problems – WORDS1 on SPOJ.
- Flow networks/ matching etc etc. [Interdiate/Advanced].
- Maximum flow using Ford Fulkerson Method.
- Maximum flow using Dinics Algorithm.
- Problems – PROFIT on spoj.
- Minimum Cost Maximum Flow.
- Successive Shortest path algorithm.
- Cycle Cancelling algorithm.
- Maximum weighted Bipartite Matching (Kuhn Munkras algorithm/Hungarian Method)
- Stoer Wagner min-cut algorithm.
- Hopcroft Karp bipartite matching algorithm.
- problems – ANGELS on SPOJ.
- Maximum matching in general graph (blossom shrinking)
- Gomory-Hu Trees.
- i) Problems – MCQUERY on Spoj.
- Chinese Postman Problem.
- Dynamic Programming.
- Suggested Reading – Dynamic Programming(DP) as a tabulation method
- Cormen chapter on DP
- Standard problems (you should really feel comfortable with these types)
- State space reduction
- Solving in the reverse – easier characterizations looking from the end
- Counting/optimizing arrangements satisfying some specified properties
- Strategies and expected values
- DP on probability spaces
- DP on trees
- DP with data structures
- Symmetric characterization of DP state
- A good collection of problems
- Suggested Reading – Dynamic Programming(DP) as a tabulation method
- Greedy.
- Number Theory.
- Modulus arithmetic – basic postulates [Including modular linear equations , Continued fraction and Pell’s equation]
- Fermat’s theorem, Euler Totient theorem ( totient function, order , primitive roots )
- Chinese remainder theorem
- Problems
- Project Euler 271
- http://www.topcoder.com/stat?c=problem_statement&pm=10551&rd=13903
- Problems
- Primality tests –
- Deterministic O(sqrt(n) ) approach
- Probabilistic primality tests – Fermat primality test, Miller-Rabin Primality test
- Suggested Reading –
- http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting
- Cormen 31.8
- 2.2 from Number Theory by SY Yan
- Problems –
- PON, PRIC, SOLSTRAS on SPOJ
- http://www.topcoder.com/stat?c=problem_statement&pm=4515
- Suggested Reading –
- Prime generation techniques – Sieve of Erastothenes
- Suggested Problems – PRIME1 on SPOJ
- GCD using euclidean method
- Problems –
- Logarithmic Exponentiation
- Integer Factorization
- Naive O(sqrt(n)) method
- Pollard Rho factorization
- Problems –
- Stirling numbers
- Wilson theorem
- nCr % p in O(p) preprocess and O(log n ) query
- Lucas Theorem
- Math (Probability, Counting, Game Theory, Group Theory, Generating functions, Permutation Cycles, Linear Algebra)
- Probability.
Syllabus
- Basic probability and Conditional probability
- Suggested problems
- Random variables, probability generating functions
- Mathematical expectation + Linearity of expectation
- Suggested problems
- Special discrete and continuous probability distributions
- Bernoulli, Binomial, Poisson, normal distribution
- Suggested Problem
- Counting
Syllabus
- Basic principles – Pigeon hole principle, addition, multiplication rules
- Suggested problems
- Advanced counting techniques – Polya counting, burnsides lemma
- Game theory
Syllabus
- Basic principles and Nim game
- Sprague grundy theorem, grundy numbers
- Suggested problems
- Hackenbush
- Linear Algebra
Syllabus
- Matrix Operations
- Addition and subtraction of matrices
- Multiplication ( Strassen’s algorithm ), logarithmic exponentiation
- Matrix transformations [ Transpose, Rotation of Matrix, Representing Linear transformations using matrix ]
- Problems
- Determinant , Rank and Inverse of Matrix [ Gaussean Elimination , Gauss Jordan Elimination]
- Solving system of linear equations
- Using matrix exponentiation to solve recurrences
- Eigen values and Eigen vectors
- Polynomials
- Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial, All real roots of a polynomial ]
- Lagrange Interpolation
- Permutation cycles
- Problems
- ShuffleMethod, Permutation and WordGame on topcoder.
- Group Theory
- Bernside Lemma, Polias theorem
- Suggested Reading
- Hernstein’s topics in algebra
- http://petr-mitrichev.blogspot.com/2008/11/burnsides-lemma.html
- Problems
- TRANSP on spoj
- http://www.topcoder.com/stat?c=problem_statement&pm=9975
- Suggested Reading
- Generating functions
nisha – :
.