Programming Challenges

Code:

CC3036

Acronym:

CC3036

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2018/2019 - 1S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~pribeiro/aulas/pc1819/
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Master's Degree in Network and Information Systems Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:CC	16	Plano de estudos a partir de 2014	3	-	6	42	162
MI:ERS	10	Plano Oficial desde ano letivo 2014	2	-	6	42	162

Teaching language

Suitable for English-speaking students

Objectives

The main goals are to consolidate and to acquire new knowledge on algorithms and data structures and their efficient design and implementation by solving multiple programming challenges on the style of programming contests and job interviews.

Learning outcomes and competences

When finishing this curricular unit the students should:
- Have demonstrated creative problem solving skills in problems of algorithmic nature;
- Know a varied range of algorithmic ideas and data structures and how o adapt/augment for application on concrete problems;
- Have created a personal portfolio of code with solutions for multiple problems, including efficient and reusable implementations of the corresponding algorithms and data structures;
- Have demonstrated the ability to do high level discussions on the problems and their possible variations, understanding the efficiency implications of those variations-

Working method

Presencial

Program

By solving the problems, multiple area will be tackled and combined, including topics in (inside parentheses are example of sub-topics inside the areas):
- General problem solving strategies (ex: understand/plan/do/check, generalizations and specializations, separation of concerns)
- Data Structures (ex: binary search trees, segment trees, interval trees, fenwick trees, range trees, quadtrees, kd-trees, union-find, sqrt decomposition, sparse tables)
- Algorithmic Stategies (ex: exhaustive search, backtracking, branch&bound, meet-in-the-middle, divide and conquer and variant, greedy algorithms, dynamic programming, lazy propagation in trees, sliding windows)
- Mathematics (ex: topics in numbers theory such as generating prime numbers, modular arithmetic and equation solving; combinatorics such as permutations, arrangements, binomical coefficients, inclusion-exclusion principle; probabilities calculation; game theory including games like nim and the Sprague-Grundy theorem)
- Advanced Dynamic Programming (ex: designing new recurrences in multiple dimensions; optimizations such as knuth or convex hull optimization);
- Graphs (ex: dfs and bfs with applcations such as cycle detection, articular points and ssc, ;minimum spanning trees;  minimum spanning trees; minimal distances and variantes; tree algoritjms such as diameter and LCA; flow, matchings and min-cuts incluing algorithms such as Hopcroft-Karp and Dinic)
- Computational Geometry (ex: representing geometric objects, robust primitives such as ccw, intersections, convex hull, coordinate compressions, line sweep)
- Strings (ex: hash tables, KMP, Aho-Corasick, suffix arrays)
It is also expected that in order to solve the problems the students gain an in-depth knowledge of the library available in the preferred programming language (ex: STL in C++, Java API)

Mandatory literature

Steven Halim and Felix Halim; Competitive Programming, 3rd Edition, 2013

Complementary Bibliography

Cormen Thomas H. 070; Introduction to algorithms. ISBN: 978-0-262-03384-8
Skiena Steven S.; Programming challenges. ISBN: 0-387-00163-8
Skiena Steven S.; The algorithm design manual. ISBN: 978-1-84800-069-8
Antti Laaksonen; Competitive Programmer's Handbook

Teaching methods and learning activities

The lectures include the exposition of selected topics, as well as presentations and discussion os the selected problems. The students are expected to implement solutions for a large range of problems (to submit not only to the class automatic judge, but algo to multiple platforms such as UVA Online Judge, Codeforces, Kattis or SPOJ). The participation on competitive programming events with controled time will also be promoted, in varios types of events, such as Codeforce rounds. The students will also present on the classes some selected parts of their solutions and a collaborative Wiki will be created with relevant links and explanations of various solutions and strategies.

Evaluation Type

Distributed evaluation without final exam

Assessment Components

designation	Weight (%)
Apresentação/discussão de um trabalho científico	30,00
Trabalho prático ou de projeto	70,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Apresentação/discussão de um trabalho científico
Estudo autónomo
Frequência das aulas
Trabalho escrito
Trabalho laboratorial
Total:	0,00

Eligibility for exams

Not applicable.

Calculation formula of final grade

- Presentations and explanations of the algorithms and problems in class, and wiki: 30%
- Implementations submitted: 30% to 60%
- Participation on competitive events: 10% to 40%

The weight of the competitive events depends on the obtained success and of the event difficulty (ex: a Div. 1 Codeforces round has more value than a Div. 2 round)

Observations

It is recommended that students had attended CC1007 (Data Structures) and CC2001 (Design and Analysis of Algorithms), or some equivalent couse units, to improve potential of success.