# Programming Challenges Syllabus (GB20602)

## Basic Data:

- 2 credits, 3rd and 4th year,
- Spring AB, Tue 3,4
**Lecturer**: Claus Aranha**Class Type**: Lecture / Flipped Classroom

## Outline:

We will study several algorithms using programming challenges. This lecture is focused on programming and implementation. Main topics: Dynamic Programming, Graphs, Data Structures, String Manipulation, Computational Geometry, etc.

## Competences:

- General Competences:
- (2) Critical and Creative thinking
- (4) Wide perspective and internationality

- Specific Competences:
- (2) Software Science Knowledge
- (6) Problem Solving and Practical Skills
- (7) Ethics in Computer Sciences

## Educational Objectives

The goal of this course is to learn how to identify the necessary algorithm to solve a given program, and how to correctly implement it. This course aims at giving a practical view of previously learned algorithms and programming techniques.

## Keywords:

Algorithms, Programming, Problem Solving, Programming Contests

## Lecture Plan

- Course Introduction, General Ideas for Solving Problems
- Data Structures:1D Vector, 2D Vector, Sets, Tree Structures, UFDS
- Search Methods: Full Search, Binary Search, Greedy Search
- Dynamic Programming: Grid Search, MaxSum, LIS, MaxSum, TSP
- Graph I:Graph Structure, BFS, DFS, Flood Fill, TopoSort, Spanning Tree
- Graph II:Shortest Paths, Flow
- Strings: String Matching, Edit Distance, Suffix Array
- Mathematics: Number Theory, Combinatoric Problems
- Geometry: Lines, Angles, Circles, Triangles, Polygons
- Final Remix: Problems using multiple of the algorithms studies in this course.

## Course Requirements

Basic programming concepts (Compiling, loops, if-then-else operators, etc.) [C, C++ or Java]

## Evaluation Criteria

This course does not implement a final examination. The evaluation is based on weekly programming assignments.

## Study time and expected work outside the classroom:

The student must complete at least 2 short programming assignments every week (out of 8 possible choices) to pass the course.

## Reference Materials

- Steven Halim, Felix Halim,”Competitive Programming”, 4th edition.
- Steven S. Skiena, Miguel A. Revilla,”Programming Challenges”, Springer, 2003
- 秋葉拓哉、 岩田陽一、 北川宜稔,『プログラミングコンテストチャレンジブック』

Lecture notes and videos will also be distributed online.

## Other notes:

Lectures are held in Japanese. Class materials are in English. Reports and communication with the professor are accepted in either language.