These are the lecture notes for the “Programming Challenges” undergraduate class at the University of Tsukuba.

last change: 2020/05/25 – Materials for Lecture 1-5 uploaded

Course Outline:

In this course, we study several algorithms by solving programming competition style challenges. The mail goal is to improve our programming skill and algorithm knowledge through implementation.

Class Syllabus

Class curriculum

• Week01 – Introduction/Ad Hoc Problems
  • Lecture notes
  • Video lectures
    • Video 1: Introduction
    • Video 2: Course Structure
    • Video 3: Ad hoc problems
• Week02 – Data Structures
  • Lecture notes
  • Video lectures
    • Video 1: Motivating Problems
    • Video 2: Library Data Structures
    • Video 3: UFDS and Segment Tree
• Week03 – Search Problems
  • Lecture notes
  • Video lectures
    • Video 1: Introduction
    • Video 2: Search and Binary Search
    • Video 3: Greedy and Problem Analysis
• Week04 – Dynamic Programming
  • Lecture notes
  • Video lectures
    • Video 1: Introduction
    • Video 2: Classical DP Problems
    • Video 3: Conclusion
• Week05 – Graphs Problems I
  • Lecture notes
  • Video lectures
    • Video 1: Introduction
    • Video 2: Graph Problems
    • Video 3: Articulation Points and MST
• Week06 – Graphs Problems II
  • Lecture notes
  • Video lectures
    • Video 1: Single Source Shortest Path
    • Video 2: All Pairs Shortest Path
    • Video 3: Maximum Flow
• Week07 – String Manipulation
  • Lecture notes
  • Video lectures
    • Video 1: Introduction
    • Video 2: String Matching
    • Video 3: DP and Trie
• Week08 – Math Problems
  • Lecture notes
  • Video lectures
    • Video 1: Introduction
    • Video 2: Prime Factors
    • Video 3: Catalan Numbers
• Week09 – Geometry Problems
  • Lecture notes
  • Video lectures
    • Video 1: Introduction
    • Video 2: Circles
    • Video 3: Convex Hull
• Week10 – Final Problem Remix
  • Lecture notes
  • Video lectures
    • Video 1: Introduction
    • Video 2: Binary Search + Alpha

Links:

• Online Judge – Use this site to test your submissions
• Class Monitor – Use this website to see links for specific problems and your submission status
• Manaba Webpage – manaba system for accessing class material and submit reports (only for Tsukuba University Students - Self registration code 2020: 6910967)

References:

Books

• Competitive Programming (3rd Edition) by Steven Halim – Textbook for this lecture.
• Programming Challenges by Steven Skiena – Another useful reference.