Competitive Programming and Contests

• Teacher: Rossano Venturini
• CFU: 6
• Period: First semester
• Language: English
• Classroom: here
• Lectures schedule: Monday 14-16 and Wednesday 11-13 (Google Meet).
• Question time: After lectures or by appointment
• Google group to discuss solutions

Goals and opportunities

The goal of the course is to improve programming and problem solving skills of the students by facing them with difficult problems and by presenting the techniques that help their reasoning in the implementation of correct and efficient solutions. The importance of these skills has been recognized by the most important software companies worldwide, which evaluate candidates in their job interviews mostly by the ability in addressing such difficult problems (e.g., see here).

A natural goal is to involve the students in the intellectual pleasure of programming and problem solving, also preparing them for the most important international online contests, such as Topcoder, Codeforces, HackerRank, CodeChef, Facebook Hacker Cup, Google Code Jam and so on, for internships in most important companies and their interviews. A desirable side-effect of the course could be to organize and prepare teams of students for online contests.

The course will provide the opportunity of

• facing with challenging algorithmic problems;
• improving problem solving and programming skills;
• getting in touch with some big companies for internships, scholarships, or thesis proposals.

Exam

The exam consists of two parts: Homeworks 50% - Written/oral test 50%.

Extra points for

• active participation to our Google group
• serious participation to online contests, e.g., CodeForces, TopCoder, Hacker Rank, Google Code Jam, ...
• successful interview with a big company

For full marks in the "Homeworks" part of the exam you must solve all the problems. I'll check your solutions by reading the code and their descriptions and by submitting them to the problems' sites. I should be able to submit any solution without any change. A solution that doesn't pass the tests (for any reason) will be considered wrong!

Please create a github repository to collect all your solutions and their descriptions. The repository can be either private or public. In both cases I should be able to access it. Please send me a link to your repository and keep the repository updated. I should be able to monitor your progresses.

The quality of your code will be evaluated. As your style will improve a lot with practice, I'll evaluate only the quality of the last submitted solutions.

How to solve a problem

• Read carefully the description of the problem.
• Make sure you understand the problem by checking the examples.
• Design a first trivial solution.
• Think about a more efficient solution. The use of some running examples usually helps a lot in finding a better solution. If your are not able to find such solution, try to find some hints by discussing with other students, by asking questions on the group, by looking at the solution in our Web page, or by searching on internet. This is perfectly fine for the first problems and for most difficult ones. In any case, make sure you really understand the solution and the properties it is exploiting!
• Write a brief description of your solution in English. Provide an analysis of its time and space complexity.
• Implement your own solution in C++.
• Submit your implementation to the problem's site. Fix it until it passes all the tests.
• Always compare your solution and your implementation with existing ones.

Background

If you wish to refresh your mind on basic Algorithms and Data Structures, I suggest you to look at the well-known book Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.

I strongly suggest you to watch the following video lectures as soon as possible.

• Insertion Sort and Merge Sort
• Heaps and Heap Sort
• Counting Sort, Radix Sort, Lower Bounds for Sorting
• Binary Search Trees
• AVL trees
• Hashing with Chaining

References

• Introduction to Algorithms,  3rd Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press, 2009 (Amazon) [CCLR]
• Algorithms, 4th Edition, Robert Sedgewick, Kevin Wayne, Addison-Wesley Professional, 2011 (Amazon) [RS]
• Algorithms, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw-Hill, 2006. (Amazon) [DPZ]
• Programming Challenges: The Programming Contest Training Manual, Steven S. Skiena, Miguel A. Revilla, Springer, 2003 (Amazon) [SR]
• Competitive Programming 4: The New Lower Bound of Programming Contests, Steven Halim, Felix Halim, (here) [HH]
• Competitive Programmer's Handbook, Antti Laaksonen (here) [L]
• The C++ Programming Language, 4th Edition, Bjarne Stroustrup, Addison-Wesley Professional, 2013 (Amazon)
• A tour of C++, 2nd Edition, Bjarne Stroustrup, Addison-Wesley Professional, 2018 (Amazon)
• The C++ Standard Library: A Tutorial and Reference, 2nd Edition, Nicolai M. Josuttis, Addison-Wesley Professional, 2012 (Amazon)

Useful links

• Erik D Demaine, Srini Devadas, Nancy Ann Lynch, "MIT  Design and Analysis of Algorithms", MIT Algorithm course which includes video lectures
• Tim Roughgarden, "Algorithm specialization", Coursera
• Visualgo: visualising data structures and algorithms through animation
• Geeks for Geeks: Company interviews preparation
• Interviews common coding questions
• How to: Work at Google — Example Coding/Engineering Interview Video
• Google's Code Jam
• Topcoder
• Codeforces
• Geeks for Geeks
• CodeChef - Data Structures and Algorithms links
• Geeks for Geeks: Top 10 Algorithms and Data Structures for Competitive Programming
• List of resources for competitive programming

Lectures

Last year lectures

Lectures from past years

* Notes marked with "Rossano's notes" are rough and non-exhaustive notes that I used while lecturing. Please use them just to have a list of the topics of each lecture and use other reported references to study these arguments.

Further (optional) topics

• Aho-Corasick String Matching Algorithm
• Convex Hull
• Interval tree
• Merge Sort Tree
• Manacher's Algorithm: here and here
• Maximum flow
• Splay trees
• Sweep line algorithm