Homework 1

“Oh, he seems like an okay person, except for being a little strange in some ways. All day he sits at his desk and scribbles, scribbles, scribbles. Then, at the end of the day, he takes the sheets of paper he’s scribbled on, scrunges them all up, and throws them in the trash can.”
– John von Neumann’s housekeeper, describing the employer

This HW is due on 04th February 2025. Please write down the solutions neatly in your own handwriting, and submit the completed HW by email by the beginning of class on 04th February 2025. Please submit the HW as a single pdf file - you can scan / take a photo of your completed HW (handwritten) and convert it into a pdf file (please name your file first.last_hw1.pdf). To get credit, please provide all details and give complete reasoning for all your work. Do not consult any books, internet resources or AI. If you have questions about the problems, we can discuss them in class.

Exercise 1 (2 points) Prove that the set \mathbb{R}^2 with the function d: \mathbb{R}^2 \times \mathbb{R}^2 \to \mathbb{R} given by d((x,y),(x',y'))=\max\{{|x-x'|, |y-y'|}\} is a metric space.

Exercise 2 (2 points) Let (X,d) be a metric space. Is the function d: X \times X \to \mathbb{R} given by d(x,x')=\sqrt{d(x,x')} a metric on X?

Exercise 3 (2 points) Let (X,d) be a metric space and a \in X. Show that the function f_a: X \to \mathbb{R} given by f_a(x)=d(x,a) is continuous.

Exercise 4 (2 points)  

Let n \in \mathbb{N}, and let X_n be the set of binary strings of length n, i.e., X_n:=\{(x_1x_2\cdots x_n): x_i \in \{0,1\}\}. Define a function d:X_n \times X_n \to [0, \infty) by d((x_1x_2\cdots x_n),(y_1y_2\cdots y_n))=|\{i:x_i \ne y_i\}|. Show that d defines a metric on X_n

Exercise 5 (2 points) Let A and B two line segments (possibly of different lengths) in the metric space (\mathbb{R}^2,d_2). Write down a pseudocode for finding the Hausdorff distance between A and B.