DSCI 599 Homework 1
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.
