ListofTopicsforprogrammingCompetitions
1. BasicGeometry/EuclideanGeometry/CoordfinateGeometry/[3Dvariantsofeverything].
2. ComputationalGeometry.
a. GrahamScanalgorithmforConvexHullO(n*log(n)).
b. Onlineconstructionof3DconvexhullinO(n^2).
c. BentleyOttmannalgorithmtolistallintersectionpointsofnlinesegmentsinO((n+I)*logn).
SuggestedReading
1. [Link]
d. RotatingCalipersTechnique.
SuggestedReading[Link]
ProblemsReferthearticleforalistofproblemswhichcanbesolvedusingRotatingCaliperstechnique.
e. LineSweep/PlaneSweepalgorithms
Area/PerimeterofUnionofRectangles.
Closestpairofpoints.
SuggestedReading
1. [Link]
ProblemsFollowthetutorialforlistofproblems.
f. AreaofUnionofCircles.
g. DelayunayTriangulationofnpointsinO(n*logn).
h. VoronoiDiagramsofnpointsinO(n*logn)usingFortunesalgorithm.
i. Pointinapolygonproblem
O(n)solutionwithoutpreprocessing.
O(logn)algorithmwithO(n*logn)preprocessingforconvexpolygons.
j. Problemsoncomputationalgeometry
BSHEEP,BULK,SEGVIS,CONDUIT,RUNAWAY,DIRVS,RAIN1,SHAMAN,TCUTTER,LITEPIPE,RHOMBS,FSHEEP,FLBRKLIN,CERC07P,
BAC,ALTARS,CERC07C,NECKLACE,CH3D,RECTANGL,POLYSSQ,FOREST2,KPPOLY,RAIN2,SEGMENTS,ARCHPLG,BALLOON,
CIRCLES,COMPASS,EOWAMRT,ICERINKonSPOJ.
CultureGrowth,PolygonCoveronTopcoder.
k. SuggestedReading
ComputationalGeometry:[Link].
3. StringAlgorithm.
a. KnuthMorrisPrattalgorithm.
ProblemsNHAY,PERIODonSPOJ.
SuggestedReading
1. CormenchapteronStrings.
2. [Link]
b. AhoCorasickalgorithm.
ProblemsWPUZZLESonSPOJ.
c. SuffixArrays
O(n^2*logn)Naivemethodofsuffixarrayconstruction
O(n*logn^2)methodofsuffixarrayconstruction
O(n*logn)methodofsuffixarrayconstruction.
O(n)methodofsuffixarrayconstruction
O(n)LCApreprocessonSuffixArraystosolveavarietyofstringproblems.
d. SuffixTrees
O(n)constructionofSuffixtreesusingUkkenonsalgorithm.
O(n)constructionofSuffixTreesifprovidedwithSuffixArraysusingFarachsalgorithm.
e. SuffixAutomata
O(n)SuffixAutomatonconstruction.
f. DictionaryOfBasicFactors
O(n*logn)methodofDBFconstructionusingRadixSort.
g. ManacharsalgorithmtofindLenghofpalindromicsubstringofastringcenteredatapositionforeachpositioninthe
[Link]>O(n).
h. SearchingandpreprocessingRegularExpressionsconsistingof?,*.
i. Multidimentionalpatternmatching.
j. ProblemsonStrings[canbesolvedwithavarietyoftechniques]
DISUBSTR,PLD,MSTRING,REPEATS,JEWELS,ARCHIVER,PROPKEY,LITELANG,EMOTICON,WORDS,AMCODES,UCODES,PT07H,
MINSEQ,TOPALIN,BWHEELER,BEADS,SARRAY,LCS,LCS2,SUBST1,PHRASES,PRETILEonSPOJ
[Link]
4. BasicGraphs[beginner].
a. Representationofgraphsasadjacencylist,adjacencymatrix,incidencematrixandedgelistandusesofdifferent
representationsindifferentscenarios.
b. BreadthFirstSearch.
problems
1. PPATH,ONEZERO,WATERonSPOJ
c. DepthFirstSearch.
d. StronglyConnectedComponents.
problems
1. TOURandBOTTOMonSPOJ.
e. BiconnectedComponents,Findingarticulationpointsandbridges].
problems
1. RELINETS,PT07AonSPOJ.
f. Dijkstraalgorithm
problems
1. SHPATHonSPOJ.
g. FloydWarshallalgorithm
problems
1. COURIERonSPOJ.
h. MinimumSpanningTree
problems
1. BLINNETonSPOJ.
i. Floodfillalgorithm
j. Topologicalsort
k. BellmanFordalgorithm.
l. EulerTour/Path.
problemsWORDS1onSPOJ.
m. SuggestedreadingformostofthetopicsinGraphalgorithms
[Link]
Alsorefertothetutorialforproblemsconcerningthesetechniques.
Cormenchapter22to24.
5. Flownetworks/matchingetcetc.[Interdiate/Advanced].
a. MaximumflowusingFordFulkersonMethod.
SuggestedReading
1. [Link]
problemsTAXI,POTHOLE,IM,QUEST4,MUDDY,EN,CABLETV,STEAD,NETADMIN,COCONUTS,OPTMonSPOJ.
b. MaximumflowusingDinicsAlgorithm.
ProblemsPROFITonspoj.
c. MinimumCostMaximumFlow.
SuccessiveShortestpathalgorithm.
CycleCancellingalgorithm.
SuggestedReading
1. [Link]
d. MaximumweightedBipartiteMatching(KuhnMunkrasalgorithm/HungarianMethod)
problemsGREED,SCITIES,TOURSonSPOJ|[Link]
e. StoerWagnermincutalgorithm.
f. HopcroftKarpbipartitematchingalgorithm.
problemsANGELSonSPOJ.
g. Maximummatchingingeneralgraph(blossomshrinking)
h. GomoryHuTrees.
i)ProblemsMCQUERYonSpoj.
i. ChinesePostmanProblem.
problems[Link]
SuggestedReading[Link]
j. SuggestedReadingforthefullcategory>
NetworkflowAlgorithmsandApplicationsbyAhuja
Cormenbookchapter25.
6. DynamicProgramming.
a. SuggestedReadingDynamicProgramming(DP)asatabulationmethod
CormenchapteronDP
b. Standardproblems(youshouldreallyfeelcomfortablewiththesetypes)
[Link]
[Link]
c. Statespacereduction
[Link]
[Link]
[Link]
d. Solvinginthereverseeasiercharacterizationslookingfromtheend
[Link]
[Link]
e. Counting/optimizingarrangementssatisfyingsomespecifiedproperties
[Link]
[Link]
f. Strategiesandexpectedvalues
[Link]
[Link]
[Link]
[Link]
g. DPonprobabilityspaces
[Link]
[Link]
[Link]
h. DPontrees
[Link]
[Link]
[Link]
i. DPwithdatastructures
[Link]
[Link]
[Link]
[Link]
j. SymmetriccharacterizationofDPstate
[Link]
k. Agoodcollectionofproblems
[Link]
[Link]
7. Greedy.
a. SuggestedReading
ChapteronGreedyalgorithmsinCormen.
[Link]
b. problemsrefertothetopcodertutorial.
8. NumberTheory.
a. Modulusarithmeticbasicpostulates[Includingmodularlinearequations,ContinuedfractionandPell'sequation]
SuggestedReading
1. Chapter1fromNumberTheoryforComputingbySYYan[Recommended]
2. 31.1,31.3and31.4fromCormen
3. [Link]/tc?module=Static&d1=tutorials&d2=primeNumbers
Problems
1. [Link]
2. [Link]
3. [Link]
4. [Link]
5. [Link]
b. Fermat'stheorem,EulerTotienttheorem(totientfunction,order,primitiveroots)
SuggestedReading
1. 1.6,2.2fromNumberTheorybySYYan
2. 31.6,31.7fromCormen
Problems
1. [Link]
2. [Link]
c. Chineseremaindertheorem
SuggestedReading
1. 31.5fromCormen
2. 1.6fromNumberTheorybySYYan
Problems
1. ProjectEuler271
2. [Link]
d. Primalitytests
DeterministicO(sqrt(n))approach
ProbabilisticprimalitytestsFermatprimalitytest,MillerRabinPrimalitytest
1. SuggestedReading
a. [Link]
b. Cormen31.8
c. 2.2fromNumberTheorybySYYan
2. Problems
a. PON,PRIC,SOLSTRASonSPOJ
b. [Link]
e. PrimegenerationtechniquesSieveofErastothenes
SuggestedProblemsPRIME1onSPOJ
f. GCDusingeuclideanmethod
SuggestedReading
1. 31.2Cormen
Problems
1. GCDonSPOJ
2. [Link]
g. LogarithmicExponentiation
SuggestedReading
1. [Link]
h. IntegerFactorization
NaiveO(sqrt(n))method
PollardRhofactorization
SuggestedReading
1. 2.3fromNumberTheorySYYan
2. 31.9Cormen
Problems
1. [Link]
2. [Link]
3. [Link]
i. Stirlingnumbers
j. Wilsontheorem
nCr%pinO(p)preprocessandO(logn)query
k. LucasTheorem
l. SuggestedReadingforNumberTheory
NumbertheoryforcomputingbySongYYan[Simplebookdescribingconceptsindetails]
ConceptsarealsosuperficiallycoveredinChapter31ofIntroductiontoAlgorithmsbyCormen
[Link]
[Link]
m. ProblemsonNumberTheory
[Link]
[Link]
9. Math(Probability,Counting,GameTheory,GroupTheory,Generatingfunctions,PermutationCycles,LinearAlgebra)
a. Probability.
Syllabus
BasicprobabilityandConditionalprobability
1. Suggestedproblems
a. [Link]
b. [Link]
Randomvariables,probabilitygeneratingfunctions
Mathematicalexpectation+Linearityofexpectation
1. Suggestedproblems
a. [Link]
b. [Link]
Specialdiscreteandcontinuousprobabilitydistributions
1. Bernoulli,Binomial,Poisson,normaldistribution
2. SuggestedProblem
a. [Link]
SuggestedReadings
1. CormenappendixC(verybasic)
2. Topcoderprobabiltytutorial[Link]
3. [Link]
4. [Link]
5. WilliamFeller,Anintroductiontoprobabilitytheoryanditsapplications
b. Counting
Syllabus
BasicprinciplesPigeonholeprinciple,addition,multiplicationrules
1. Suggestedproblems
a. [Link]
b. [Link]
3. Suggestedreadings
a. [Link]
b. [Link]
c. [Link]
Inclusionexclusion
1. Suggestedreadings
a. [Link]
2. Suggestedproblems
a. [Link]
b. [Link]
Specialnumbers
1. SuggestedreadingStirling,eurlerian,harmonic,bernoulli,fibonnaccinumbers
a. [Link]
b. [Link]
c. [Link]
d. [Link]
e. [Link]
f. ConcretemathematicsbyKnuth
2. Suggestedproblems
a. [Link]
b. [Link]
c. [Link]
d. [Link]
AdvancedcountingtechniquesPolyacounting,burnsideslemma
1. Suggestedreading
a. [Link]
b. [Link]
2. SuggestedProblems
a. [Link]
b. [Link]
[Link]
Syllabus
BasicprinciplesandNimgame
1. Spraguegrundytheorem,grundynumbers
2. Suggestedreadings
a. [Link]
b. [Link]
c. [Link]
d. [Link]
3. Suggestedproblems
a. [Link]
b. [Link]
Hackenbush
1. Suggestedreadings
a. [Link]
b. [Link]
2. Suggestedproblems
a. [Link]
b. [Link]
[Link]
Syllabus
MatrixOperations
1. Additionandsubtractionofmatrices
a. SuggestedReading
i. Cormen28.1
2. Multiplication(Strassen'salgorithm),logarithmicexponentiation
a. Suggestedreading
i. Cormen28.2
ii.LinearAlgebrabyKennethHoffmanSection1.6
b. Problems
i. [Link]
3. Matrixtransformations[Transpose,RotationofMatrix,RepresentingLineartransformationsusingmatrix]
a. SuggestedReading
i. LinearAlgebraByKennethHoffmanSection3.1,3.2,3.4,3.7
b. Problems
i. [Link]
[Link]
4. Determinant,RankandInverseofMatrix[GausseanElimination,GaussJordanElimination]
a. SuggestedReading
i. 28.4Cormen
ii.LinearAlgebrabyKennethChapter1
b. Problems
i. [Link]
ii.[Link]
iii. [Link]
[Link]
5. Solvingsystemoflinearequations
a. SuggestedReading
i. 28.3Cormen
ii.LinearAlgebrabyKennethChapter1
b. Problems
i. [Link]
6. Usingmatrixexponentiationtosolverecurrences
a. SuggestedReading
i. [Link]
b. Problems
i. REC,RABBIT1,PLHOPonspoj
ii.[Link]
[Link]
[Link]
7. EigenvaluesandEigenvectors
a. Problems
i. [Link]
Polynomials
1. Rootsofapolynomial[Primefactorizationofapolynomial,Integerrootsofapolynomial,Allrealroots
ofapolynomial]
a. Problems
i. [Link]
[Link],ROOTCIPHonSpoj
2. LagrangeInterpolation
a. Problems
i. [Link]
ii.[Link]
[Link]
SuggestedReading
1. ArtofComputerProgrammingbyKnuthVol.3
Problems
1. ShuffleMethod,PermutationandWordGameontopcoder.
[Link]
BernsideLemma,Poliastheorem
1. SuggestedReading
a. Hernstein'stopicsinalgebra
b. [Link]
2. Problems
a. TRANSPonspoj
b. [Link]
b. Generatingfunctions
SuggestedReading
1. HerbertWilf'sgeneratingfunctionology
2. RobertSedgewickandFlajoulet'sCombinatorialanalysis
[Link].
i. Basic
a. Arrays/Stacks/Queues:
Problems
1. [Link]
2. [Link]
3. [Link]
Reading:
1. CLRS:section10.1
2. [Link]
[Link]/DoublyLinkedList:
Problems
1. [Link]
Reading:CLRS:section10.2,MarkAllenWeiesChapter3
[Link]:
Problems
1. [Link]
2. [Link]
Reading:CLRS:Chapter11,MarkAllenWeiesChapter5
[Link]/queue
Problems
1. [Link]
[Link]/naryTrees
Reading
1. CLRS:section10.4
2. CLRS:Chapter12
3. MarkAllenWeiesChapter4
4. [Link]
[Link]
Problems
1. [Link]
2. [Link]
Reading:MarkAllenWeiesChapter6
[Link]
a. Trie(Keywordtree)
Problems
1. [Link]
2. [Link]
Reading
b. Intervaltrees/SegmentTrees
Problems
1. [Link]
2. [Link]
Reading
c. Fenwick(BinaryIndexed)trees
Problems
1. [Link]
Reading:[Link]
d. Disjointdatastructures
Problems
1. [Link]
2. [Link]
Reading:
1. [Link]
2. MarkAllenWeiesChapter8
e. RangeminimumQuery(RMQ)
Problems
1. [Link]
Reading[Link]
f. Customizedinterval/segmenttrees(AugmentedDS)
Problems
1. [Link]
2. [Link]
Reading:CLRS:Chapter14(augmentedDS)
[Link]
Problems
1.[Link]
Reading
[Link](Nottobecovered)
a. SplayTrees
b. B/B+Trees
c. kdTrees
d. RedblackTrees
e. SkipList
f. Binomial/Fibonacciheaps
[Link]
1. [Link]
2. [Link]
3. [Link]
4. [Link]
5. [Link]
6. [Link]
7. [Link]
8. [Link]
9. [Link]
[Link]/Bruteforcewritingtechniques/Randomizedalgorithms.
a. Backtracking[Beginner].
problems>
1. Nqueensproblems
2. KnightsTour
3. SudokuProblem
4. TilingProblem.
5. 15puzzle.
b. DancingLinksandAlgorithmXgivenbyKnuth[Advanced]
problemsPRLGAME,SUDOKU,NQUEENonSPOJ
Suggestedreading
1. [Link]
c. BinarySearch[Beginner].
[Link].
findingallrealrootsofapolynomialusingbinarysearch.[intermediate].
SuggestedReading
1. [Link]
d. TernarySearch[Intermediate].
problems
1. [Link]
2. [Link]
3. [Link]
4. [Link]
5. [Link]
6. [Link]
7. [Link]
e. Meetinthemiddle[Intermediate].
problems
1. [Link]
2. [Link]
f. HillClimbing[Advanced].
g. RegularIterationtoreachafixedpoint[Advanced].
NewtonRaphsonmethodtofindrootofamathematicalfunction.
Iterationstosolvelinearnonhomogeneoussystemofequations.
h. RandomizedAlgorithms[Intermediate]
QuickSort.
[Link]>
a. ArithmeticPrecision[Beginner].
SuggestedReading
1. [Link]
b. Representingsetswithbitmasksandmanipulatingbitmasks[Beginner].
SuggestedReading
1. [Link]
problemsrefertothetutoriallinkinSuggestedreadingsection.
reshareno
