## Description

1. [2.5 points] Describe the principle of Dynamic Programming. Pick a problem of interest

in Data Science which can be solved efficiently using Dynamic Programming. Describe

the problem and the applicaBon of Dynamic Programming on it.

2. [2.5 points] Describe the main ingredients of local search. Pick a problem of interest in

Data Science which can be solved efficiently using local search in a discrete space.

Describe the problem and the applicaBon of local search on it. What happens if the

search space is conBnuous?

3. [2.5 points] Describe the K-means clustering algorithm. Is it an ExpectaBon-MaximizaBon

algorithm? Explain. What are some drawbacks of the K-means algorithm?

4. [2.5 points] Describe the FastMap algorithm. What does it achieve and how does it do

so? Comment on its efficiency. Describe two applicaBons of FastMap in Data Science.