# Generic Functions

This chapter serves as review of what are essentially the
prerequisites of this course. Everything in here should already be
familiar. If there are constructs or techniques that you don't
understand, you should either look them up in the study materials
for PB161¹ or use third-party material (books, online resources) to
catch up.

If you didn't read Chapter A (directory ‹00› in the source bundle)
yet, please do so now. More information about how to use the files
in this chapter can be found in ‹00/t3_sources.txt› (Section T.3).

The first block of files are «demos» – those mainly showcase the
concepts that are new in each chapter, using small but thoroughly
commented programs. These are named ‹d?_*.cpp› in the source bundle.
In this chapter, there are no new concepts, so we will revisit some
of the old ones:

 1. ‹null›    – working with containers and ‹std::optional›
 2. ‹rotsort› – leveraging standard algorithms
 3. ‹diff›    – simple automatic differentiation

The next block of files are «elementary exercises» (‹e?_*.cpp›),
which should be generally very easy and quick to solve. Reference
solutions for these are provided at the back. For this chapter, it's
these 3 exercises:

 1. ‹count› – count vertices reachable from a given vertex
 2. ‹flip›  – go from ‹map< K, V >› to ‹map< V, set< K > >›
 3. ‹tfold› – fold a binary tree using a given function

A very important part of each lecture are «practice exercises»,
which are «graded» (confused? you «really» need to check out
Chapter A now). You will work on those on your own, each week, for
the remainder of the semester:

 1. ‹backoff›  – exponential backoff (unknown size search)
 2. ‹isbst›    – strom zadaný polem (ala halda)
 3. ‹dijkstra› – shortest paths in a generic graph
 4. ‹msort›    – sort elements of a row-sorted matrix
 5. ‹sparse›   – addition of sparse matrices
 6. ‹spanning› – construct a minimum spanning tree

Finally, there are the «regular exercises», which are going to be
the subject of seminars (classes). Again, reference solutions are to
be found in the back. For the first week, those are:

 1. ‹rekey› – ‹map< K, V >› × ‹f : K → L› ⇒ ‹map< L, set< V > >›
 2. ‹tensor› – outer (tensor) product of 1D vectors
 3. ‹topsort› – topological sort of a directed graph
 4. ‹nfold› – N-ary tree fold (input given as a multimap)
 5. ‹integrate› – numerical integration of arbitrary functions
 6. ‹basecvt›  – convert arbitrary bases to binary

¹ Please note, however, that those are only available in Czech.