当前位置:天才代写 > 作业代写 > Problem Set代写 distance function代写 1-dimensional clustering代写

Problem Set代写 distance function代写 1-dimensional clustering代写

2020-11-23 17:45 星期一 所属: 作业代写 浏览:94

Problem Set代写

Problem Set 2

Problem Set代写 Due date: Wed, Nov 7, 2018 at 5:00pm. Submit a hard copy in the closed CS565 dropbox. Write every problem on a separate page

Due date: Wed, Nov 7, 2018 at 5:00pm. Submit a hard copy in the closed CS565 dropbox. Write every problem on a separate page, make sure your name is on each page and staple them together. Typed solutions are preferred but had writing is also accepted.

Exercise 1 (25 points): Problem Set代写

  1. Consider a set of d-dimensional points X = {x1, . . . , xn} and distance function

Show that the representative

is the mean of the points in X. That is, for every A ∈ {1, . . . , d} x(A) = 1 Σxi(A).  (10 points).

  1. Consider a set of d-dimensional points X = {x1, . . . , xn} and distancefunction
Problem Set代写
Problem Set代写

Show that the representative

is  the  median  of  the  points  in  X.  That  is,  for  every  A 1, . . . , d    x(A) = median(x1(A), . . . , xn(A)  . (15 points).

Problem Set代写
Problem Set代写

Exercise 2 (30 points):Problem Set代写

Consider the following 1-dimensional clustering problem: given a set of n 1- dimensional data points X = x1, . . . , xn  and an integer k partition these points into clusters of size at least k such that if the resulting number of clusters is A

is minimized. In the above equation, Ci is the i-th cluster and µi is the representative of this cluster – in this case the mean of the data points in the cluster.

  • Designa polynomial-time algorithm for finding the optimal clustering C. (15 points)
  • If the running time of the algorithm you described above is linear then, you get 15 points. If the running time is more than linear, design a linear-time algorithm for the above problem. (15 points)Problem Set代写

Exercise 3 (30 points):

 In this exercise you will devise an algorithm A that, given two degree sequences,generates a graph with corresponding degrees. That is, the input to A are two integer sequences d =

{d1, d2, . . . dn} and q {q1, q2, . . . qn}. The output of A(d, q) is a bipartite graph tt(U, V, E), such that the number of nodes |U | = n1, |V | = n2 and the nodes in U have degrees d1, d2, . . . dn1 and nodes in V have degrees q1, q2, . . . qn2 .Problem Set代写

(tt is simple, that is, it has no multi-edges.)
  1. First,give a necessary and sufficient condition on the sequences d and q that there exist such a  (ex. There is clearly no graph for the sequences d and q, such that every i we have di = 1 and for every  j  we  have qj  = 0.)  Prove  that  the  condition  is  necessary.  You will  prove  that  it  is  sufficient  in part 3 of this problem. (7 points)
  1. Definethe algorithm A and analyze its running  (10 points)Problem Set代写
  2. Provethatyour algorithm always terminates and, given that the condition in part 1 is fulfilled, always outputs a valid (8 points)
  3. Algorithm A takes two sequences as an input. It is a natural question to ask, whether we can also devise an algorithm B that takes only one sequence as input and outputs a general (non-bipartite) graph with the given degree sequence as output? This problem is in fact harder to solve (though, it  is still polynomial), and you are not asked to do that. However, give an example that shows that the same algorithmic approach as A does not always work for this case. (e.g. show a graph, such that givenits degree sequence, the single partite version of A would not find the corresponding  ) (5 points)Problem Set代写

Exercise 4 (25 points):

Consider the edit distance between two labeled graphs tt1 = (V, E1) and tt2 = (V, E2) with the same set of nodes to be the number of edges in E1 that are not in E2 plus the number of edges in E2 that are not in E1. That is,

∆(tt1, tt2) = |E1 \ E2| + |E2 \ E1|.

  • Prove that ∆() is a metric. (10points)Problem Set代写

Given a set of graphs tt1, tt2, . . . , ttn consisting of n graphs all sharing the same set of labeled nodes design an algorithm for finding the centroid of the set of clusters, when distance ∆ is used as a distance function between graphs. (15 points)

Problem Set代写
Problem Set代写

更多其他:C++代写 考试助攻 C语言代写 finance代写  计算机代写 report代写 project代写 物理代写 数学代写 经济代写  java代写 python代写 程序代写 algorithm代写

合作平台:天才代写 幽灵代写 写手招聘 Essay代写

 

天才代写-代写联系方式