00 Preliminaries: Sets, Combinatorics, Functions

image.png լուսանկարի հղումը, Հեղինակ՝ Misak Aghababyan

📚 Նյութը

Մինչ բուն նյութին անցնելը ծանոթանում ենք մի քանի նախնական կարևոր գաղափարների՝

  1. Բազմություններ (գործողություններ, կցման-արտաքսման սկզունք, դեկարտյան արտադրյալ)
  2. Զուգորդություններ, կարգավորություններ
  3. Ֆունկցիաներ (պատկեր, նախապատկեր, ինյեկտիվ, սյուրյեկտիվ, բիյեկտիվ, կենտ, զույգ)

🏡 Տնային

Note
  1. ❗❗❗ DON’T CHECK THE SOLUTIONS BEFORE TRYING TO DO THE HOMEWORK BY YOURSELF❗❗❗
  2. Please don’t hesitate to ask questions, never forget about the 🍊karalyok🍊 principle!
  3. The harder the problem is, the more 🧀cheeses🧀 it has.
  4. Problems with 🎁 are just extra bonuses. It would be good to try to solve them, but also it’s not the highest priority task.
  5. If the problem involve many boring calculations, feel free to skip them - important part is understanding the concepts.
  6. Submit your solutions here (even if it’s unfinished)

Sets

01 Two-annotator inclusion–exclusion

Out of 1,000 images, annotator \(A\) flags 260 as “elephant,” annotator \(B\) flags 310 as “elephant,” and both flag 190.

  1. How many images at least one annotator called “elephant”?
  2. How many images neither annotator called “elephant”?

02 Train/Test split

When creating Machine Learning (ML) models, we split the data into 2 parts - one for training the model and one for testing how good it is (well, we actually usually split to 3 parts - train, validation, test, but for this problem we’ll go with the half-truth)

You collected 200 images. Train set \(T\) has 140 indices; Test set \(S\) has 60. We noticed an overlap \(|T\cap S|=4\).

  1. Are the splits disjoint? If not, how many unique images actually exist across both sets?
  2. How many items must be moved to make \(T\) and \(S\) disjoint with target sizes \(140\) and \(60\) (no duplicates)? Propose a minimal-move strategy.

03 Divisibility via inclusion–exclusion

How many integers in \({1,\dots,100}\) are divisible by \(5\) or \(7\).

04 Inclusion-exclusion principle for 3 sets

Figure out the equation of the inclusion-exclusion principle for 3 sets. You may find it useful to draw a Venn diagram.

Combinatorics

05 Augmentation pipeline counting

Sometimes we have the need of expanding our dataset size, but we can’t acquire more data. For such cases we use a technique called data augmentation to artificially expand the size of a training dataset by creating modified versions of images in the dataset - like rotating them, flipping and so on.

An image pipeline does: random crop (3 sizes), color jitter (on/off), horizontal flip (on/off), and chooses one of 4 background textures.

Assuming independence, how many distinct augmentation “recipes” can be produced for a given image? Example recipe is (crop: 2nd size, flip: 1 (on), texture: 3rd type).

06 Two hyperparameters — combinations

In ML, we often need to specify some parameters (we call them hyperparameters) beforehand - for example we need to choose which optimization algorithm to use.

Let hyperparameter set \(H_1\) have \(m\) options and \(H_2\) have \(n\) options.

If we want to try the whole grid of options how many combinations do we have? How is the set of all combinations called?

07 Armenian car plates

Armenian cars have the format DD LL DDD, digits 0–9, letters A–Z, repetition allowed.

  1. How many distinct plates exist?
  2. How does the answer change if letters cannot repeat inside the same plate?

08 Anagrams of “cheeses”

How many distinct words can you form by rearranging the letters of “cheeses”? (Handle repeated letters carefully.)

Functions

09 (my favorite exercise) Real-world examples

Give one real-life example (and short justification) for 1. injective 2. surjective and 3. bijective mapping.

10 Counting small functions

How many functions \(f:\{1,2,3\}\to\{a,b\}\)?

How many are injective? How many are surjective? (Hint: total is \(2^3\).)

11 Even/odd — activation symmetry

Classify each as even, odd, or neither, and briefly note the symmetry implication:

  • \(f(x)=x^2\)
  • \(g(x)=x^3\)
  • \(p(x)=\max(0,x)\) (same as above, but the name is REctified Linear Unit (ReLu))
  • \(s(x)=\frac{1}{1+e^{-x}}\) (this function is called Sigmoid and we’ll encounter it a lot in ML) (if the function is neither please specify what we can do with it to make it even/odd)

12 Function properties

Given \(f:\mathbb{R}\to\mathbb{R}\), \(f(x)=x+3x^2\), determine:

  • Is it injective or not?
  • Is it surjective or not?
  • Is it bijective or not?
  • What is the image of \(A\) under \(f\), when \(A=[-1,2]\)?
  • What is the preimage of \(B\) under \(f\), when \(B=[0,5]\)?

13 Both even and odd

Describe all functions \(f:\mathbb{R}\to\mathbb{R}\) that are simultaneously even and odd.

14 Inclusion–exclusion for surjections

Count surjective functions \(f:\{1,2,3,4\}\to\{a,b,c\}\) using inclusion–exclusion. Show your work.

🛠️ Գործնական

🎲 37 (00)