Resources of Certification Program

[dpraveen]

Asymptotic analysis (Big-O notation):

Basic

• https://www.youtube.com/watch?v=V42FBiohc6c&list=PL2_aWCzGMAwI9HK8YPVBjElbLbI3ufctn (Time complexity of a computer program)
• https://www.hackerearth.com/practice/basic-programming/complexity-analysis/time-and-space-complexity/tutorial/
• https://www.youtube.com/watch?v=__vX2sjlpXU (Big-O notation in 5 minutes — The basics)
• https://www.youtube.com/watch?v=i1F_Uu0bYCc (Definition Of Big O Notation - Intro to Theoretical Computer Science)
• https://www.youtube.com/watch?v=aGjL7YXI31Q (Algorithms Lecture 1 – Introduction to asymptotic notations)

Advanced

• https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
• https://www.youtube.com/watch?v=v4cd1O4zkGw (Big O Notation, Gayle Laakman McDowell)
• http://web.mit.edu/16.070/www/lecture/big_o.pdf
• http://eniac.cs.qc.cuny.edu/andrew/csci700/lecture2.pdf (A very nice tutorial with examples)
• https://www.youtube.com/watch?v=ncpTxqK35PI (Time and space complexity analysis of recursive programs - using factorial)

Practice Problems

• You can see some problems with solutions here: http://www.iitk.ac.in/esc101/08Jul/lecnotes/practise_sol.pdf

---

Arrays:

Resources

• https://discuss.codechef.com/questions/87915/data-structure-tutorial-array
• https://www.cs.cmu.edu/~rjsimmon/15122-f14/lec/04-arrays.pdf

Practice Problems

• Try some problems from here: https://www.hackerrank.com/domains/data-structures/arrays

• https://www.codechef.com/problems/LECANDY/, Editorial: https://discuss.codechef.com/questions/1108/lecandy-editorial

• https://www.codechef.com/problems/CNOTE, Editorial: https://discuss.codechef.com/questions/65992/cnote-editorial

• https://www.codechef.com/problems/SALARY, https://discuss.codechef.com/questions/5144/salary-editorial

• https://www.codechef.com/problems/CHN15A, Editorial: https://discuss.codechef.com/questions/77487/chn15a-editorial

• https://www.codechef.com/problems/RAINBOWA, Editorial: https://discuss.codechef.com/questions/107967/rainbowa-editorial

• https://www.codechef.com/problems/FRGTNLNG, Editorial: https://discuss.codechef.com/questions/75211/frgtnlng-editorial

• https://www.codechef.com/problems/COPS, Editorial: https://discuss.codechef.com/questions/72499/cops-editorial

---

Strings:

• C++ strings: https://www.tutorialspoint.com/cplusplus/cpp_strings.htm
• Java strings: https://www.guru99.com/java-strings.html
• Python strings: https://docs.python.org/2/library/string.html
• Python strings: https://www.tutorialspoint.com/python/python_strings.htm
• Many questions on the string: http://www.geeksforgeeks.org/string-data-structure/

Practice Problems

• Try some problems from here: https://www.hackerrank.com/domains/algorithms/strings
• https://www.codechef.com/problems/CSUB, Editorial: https://discuss.codechef.com/questions/47237/csub-editorial
• https://www.codechef.com/problems/LAPIN, Editorial: https://discuss.codechef.com/questions/13991/lapin-editorial

---

Stack and Queue:

• https://www.hackerearth.com/practice/data-structures/stacks/basics-of-stacks/tutorial/
• https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm
• https://www.cs.cmu.edu/~wlovas/15122-r11/lectures/10-stacks.pdf
• https://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html
• https://www.cs.cmu.edu/~rjsimmon/15122-s13/09-queuestack.pdf

Practice Problems

• http://www.spoj.com/problems/JNEXT/
• http://www.spoj.com/problems/STPAR/
• http://www.spoj.com/problems/ONP/
• https://www.codechef.com/problems/COMPILER
• http://www.spoj.com/problems/MMASS/
• http://www.spoj.com/problems/HISTOGRA/
• http://codeforces.com/problemset/problem/281/D
• http://www.spoj.com/problems/ANARC09A/
• http://codeforces.com/contest/797/problem/C
• http://codeforces.com/contest/343/problem/B
• http://codeforces.com/contest/5/problem/C
• Try some problems from here on stacks: https://www.hackerrank.com/domains/data-structures/stacks
• Try some problems from here on queues: https://www.hackerrank.com/domains/data-structures/queues

---

Basic math operations (addition, subtraction, multiplication, division, exponentiation)

• https://discuss.codechef.com/questions/20451/a-tutorial-on-fast-modulo-multiplication-exponential-squaring

---

Euclid’s GCD Algorithm

• Mycodeschool video: https://www.youtube.com/watch?v=7HCd074v8g8
• https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm
• Example program to find gcd in c++: http://www.geeksforgeeks.org/c-program-find-gcd-hcf-two-numbers/

---

– Prime Numbers, divisibility of numbers

Basic

• Only O(sqrt(n)) algorithm for finding whether a number is a prime, factorization of a number.

Advanced

• Sieve algorithms also included.

Practice Problems
Basic

• https://community.topcoder.com/stat?c=problem_statement&pm=6186&rd=9823
• https://community.topcoder.com/stat?c=problem_statement&pm=4475&rd=8012
• https://community.topcoder.com/stat?c=problem_statement&pm=3458&rd=5869
• https://community.topcoder.com/stat?c=problem_statement&pm=2986&rd=5862

Advanced Level problems

• Problems based on sieve.

Basic Recursion

• https://www.topcoder.com/community/data-science/data-science-tutorials/an-introduction-to-recursion-part-1/
• https://www.topcoder.com/community/data-science/data-science-tutorials/an-introduction-to-recursion-part-2/
• http://www.geeksforgeeks.org/recursion/ (along with questions)
• http://web.mit.edu/6.005/www/fa15/classes/10-recursion/
• https://www.csee.umbc.edu/~chang/cs202.f98/readings/recursion.html (Examples with exercises)
• https://loveforprogramming.quora.com/Backtracking-Memoization-Dynamic-Programming

Practice Problems

• https://www.codechef.com/problems/NOKIA, Editorial: https://discuss.codechef.com/questions/1280/nokia-editorial
• https://www.codechef.com/problems/TRISQ, Editoria: https://discuss.codechef.com/questions/64151/trisq-editorial
• https://www.codechef.com/problems/LFSTACK, Editorial: https://discuss.codechef.com/questions/84364/lfstack-editorial
• https://www.codechef.com/problems/FICE, Editorial: https://discuss.codechef.com/questions/85839/fice-editorial

---

Greedy Algorithms:

• https://www.topcoder.com/community/data-science/data-science-tutorials/greedy-is-good/
• https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/tutorial/
• http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf

Practice Problems

• https://www.codechef.com/problems/TACHSTCK, Editorial: https://discuss.codechef.com/questions/18267/tachstck-editorial
• https://www.codechef.com/problems/CIELRCPT, Editorial: https://discuss.codechef.com/questions/1748/cielrcpt-editorial
• https://www.codechef.com/problems/MAXDIFF, Editorial: https://discuss.codechef.com/questions/8114/maxdiff-editorial
• https://www.codechef.com/problems/CHEFST, Editorial: https://discuss.codechef.com/questions/77629/chefst-editorial
• https://www.codechef.com/problems/CAKEDOOM, Editorial: https://discuss.codechef.com/questions/1119/cakedoom-editorial
• https://www.codechef.com/problems/CLETAB, Editorial: https://discuss.codechef.com/questions/49342/cletab-editorial
• https://www.codechef.com/problems/TADELIVE, Editorial: https://discuss.codechef.com/questions/60005/tadelive-editorial
• https://www.codechef.com/problems/MANYCHEF, Editorial: https://discuss.codechef.com/questions/5606/manychef-editorial
• https://www.codechef.com/problems/MMPROD, Editorial: https://discuss.codechef.com/questions/82151/mmprod-editorial
• https://www.codechef.com/problems/CHEFTMA, Editorial: https://discuss.codechef.com/questions/78212/cheftma-editorial
• https://www.codechef.com/problems/STICKS, Editorial: https://discuss.codechef.com/questions/82568/sticks-editorial
• http://www.spoj.com/problems/BAISED/
• http://www.spoj.com/problems/BALIFE/
• http://www.spoj.com/problems/GCJ101BB/
• http://www.codechef.com/problems/FGFS
• http://www.codechef.com/problems/KNPSK
• http://www.codechef.com/problems/LEMUSIC
• http://www.spoj.com/problems/ARRANGE/
• http://www.spoj.com/problems/FASHION/

---

Dynamic programming (DP)

Note that dp optimizations are not included in the syllabus (the ones given here - http://codeforces.com/blog/entry/8219)

Basic

• https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/
• https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/
• http://jeffe.cs.illinois.edu/teaching/algorithms/notes/05-dynprog.pdf (Exercises are recommended)
• https://www.codechef.com/wiki/tutorial-dynamic-programming
• http://www.geeksforgeeks.org/dynamic-programming/ (Contains a lot of practice sessions)

Advanced Dynamic programming

• http://apps.topcoder.com/forums/?module=Thread&threadID=697369&start=0
• http://apps.topcoder.com/forums/?module=Thread&threadID=700080&start=0
• http://apps.topcoder.com/forums/?module=Thread&threadID=697925&start=0

Problems for Basic DP

• http://www.spoj.com/problems/MDOLLS/
• http://www.spoj.com/problems/MSTICK/
• http://www.spoj.com/problems/MCARDS/
• http://www.spoj.com/problems/MIXTURES/
• https://www.spoj.pl/problems/SAMER08D/
• http://www.spoj.com/problems/HIST2/ (dp bitmask)
• http://www.spoj.com/problems/LAZYCOWS/ (dp bitmask)
• http://www.spoj.com/problems/TRSTAGE/ (dp bitmask)
• https://www.spoj.pl/problems/AIBOHP/

Problems for Advanced DP

• http://www.spoj.pl/problems/MARTIAN/
• http://www.spoj.pl/problems/SQRBR/
• http://www.spoj.pl/problems/ACMAKER/
• http://www.spoj.pl/problems/AEROLITE/
• https://www.spoj.pl/problems/BACKPACK/
• http://www.spoj.pl/problems/COURIER/
• http://www.spoj.pl/problems/DP/
• http://www.spoj.pl/problems/EDIST/
• http://www.spoj.pl/problems/KRECT/
• http://www.spoj.pl/problems/GNY07H/
• http://www.spoj.pl/problems/LISA/
• http://www.spoj.pl/problems/MINUS/
• http://www.spoj.pl/problems/NAJKRACI/
• http://www.spoj.pl/problems/PHIDIAS/
• http://www.spoj.pl/problems/PIGBANK/
• http://www.spoj.pl/problems/PT07X/
• http://www.spoj.pl/problems/VOCV/
• http://www.spoj.pl/problems/TOURIST/
• http://www.spoj.pl/problems/MKBUDGET
• http://www.spoj.pl/problems/MMAXPER
• http://www.spoj.pl/problems/ANARC07G
• http://www.spoj.pl/problems/MENU
• http://www.spoj.com/problems/RENT/ (dp with segment tree/BIT)
• http://www.spoj.com/problems/INCSEQ/ (dp with segment tree/BIT)
• http://www.spoj.com/problems/INCDSEQ/ (dp with segment tree/BIT)

---

Naive string searching

• http://www.geeksforgeeks.org/searching-for-patterns-set-1-naive-pattern-searching/

---

Sorting

Merge sort

• https://www.youtube.com/watch?v=TzeBrDU-JaY

Practice Problems

• https://www.codechef.com/problems/MRGSRT

Quick sort

• https://www.youtube.com/watch?v=COk73cpQbFQ

Practice Problems

• TSORT codechef

Counting sort

• http://www.geeksforgeeks.org/counting-sort/

Practice Problems

• https://www.codechef.com/problems/TACHSTCK, https://discuss.codechef.com/questions/18267/tachstck-editorial
• https://www.codechef.com/problems/STICKS, Editorial: https://discuss.codechef.com/questions/82568/sticks-editorial

---

Binary Search

• https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/
• https://www.hackerearth.com/practice/algorithms/searching/binary-search/tutorial/
• https://www.codechef.com/wiki/tutorial-binary-search

Detailed Theoretical anaylysis

• https://www.cs.cmu.edu/~fp/courses/15122-f10/lectures/03-binsearch.pdf (A theoretical analysis)

Problems

• http://www.geeksforgeeks.org/binary-search/ (Contains some solved problems)
• https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/(Try solving problems of Simple and Moderate level as mentioned in the end of the link)
• https://www.codechef.com/problems/STRSUB, Editorial: https://discuss.codechef.com/questions/66064/strsub-editorial
• https://www.codechef.com/problems/ASHIGIFT, Editorial: https://discuss.codechef.com/questions/66867/ashigift-editorial
• https://www.codechef.com/problems/STACKS, Editorial: https://discuss.codechef.com/questions/75205/stacks-editorial
• https://www.codechef.com/problems/DIVSET, https://discuss.codechef.com/questions/107068/divset-editorial
• https://www.codechef.com/problems/LOWSUM, https://discuss.codechef.com/questions/29659/lowsum-editorial
• https://www.codechef.com/problems/SNTEMPLE, https://discuss.codechef.com/questions/99456/sntemple-editorial
• https://www.codechef.com/problems/SNAKEEAT, Editorial: https://discuss.codechef.com/questions/98802/snakeeat-editorial
• https://www.codechef.com/problems/SCHEDULE, Editorial: https://discuss.codechef.com/questions/92702/schedule-editorial
• https://www.codechef.com/problems/RIGHTTRI, Editorial: https://discuss.codechef.com/questions/82375/righttri-editorial
• https://www.codechef.com/problems/FORESTGA, Editorial: https://discuss.codechef.com/questions/81382/forestga-editorial
• https://www.codechef.com/problems/CHEFHCK2, Editorial: https://discuss.codechef.com/questions/6650/chefhck2-editorial
• http://www.spoj.com/problems/ABCDEF
• http://www.spoj.com/problems/NOTATRI
• http://www.spoj.com/problems/SCALE
• http://www.spoj.com/problems/SUMFOUR
• http://www.spoj.com/problems/SUBSUMS
• http://www.spoj.com/problems/ANARC05B
• http://www.spoj.com/problems/RENT
• http://www.spoj.com/problems/PIE
• http://www.spoj.com/problems/MKUHAR
• http://www.spoj.com/problems/SVADA
• http://www.spoj.com/problems/SUBS

====

Expert Users:

The syllabus is not defined. You can see some outline and guidelines about the possible syllabus at https://discuss.codechef.com/questions/48877/data-structures-and-algorithms