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.