Homework before week 4

This week our theme is the divide-and-conquer paradigm for algorithm design. In the homework we will cover the following topics:

  • segment tree data structures for answering range queries

  • union–find data structures for storing a collection of disjoint sets

  • square-root tricks that can lead to very simple algorithms that are sometimes fast enough

Homework reading

We will follow Competitive Programmer’s Handbook by Antti Laaksonen. Please read at least the following parts to prepare for week 4:

  • Chapter 9: Range queries

  • Section 15.2: Union-find structure

  • Chapter 27: Square root algorithms

Homework problems

Here you will find a mini-contest with one task. Please ask the course staff if you need help!

Use the pre-created CSES homework account assigned to you. Its name will look like aalto26dh_NNN. You will receive the account credentials at a course meeting; do not use a personal CSES account.

The homework contest details and point submission form will be added here soon.

Posting submission...