Write algorithm which divides n objects of u into k clusters

Assignment Help Data Structure & Algorithms

Reference no: EM1370538

You are given a set U of n objects labeled p1, p2, . . . , pn. A distance function d(pi, pj) provides a numeric value measuring the "closeness" of two objects pi, pj, where 1 i, j n. You are asked to make use of this distance function to divide the n objects into k clusters, where k is a given parameter. You can think of a cluster as a subset of U, where objects in a cluster are "closer" to one another than to objects in another cluster. Propose an algorithm that divides the n objects of U into k clusters, making use of the MST of a graph. Provide a simple argument of correctness and a bound on the running time of the algorithm you are proposing.

Reference no: EM1370538

Questions Cloud

Questions based on corporate governance : Recent corporate governance concepts have redefined the responsibilities of management to ensure greater protection and accountability of management to the relevant stakeholders.

Write a xquery which returns all concert titles : Write a XQuery which returns all concert titles whose type is chamber orchestra where average ticket price is at least $50.

Determine the size in aggregate expenditure line : Suppose the simple spending multiplier equals 10. Estimate the size and direction of any shifts in the aggregate expenditure line, the level of real GDP demanded,

What is the monopolist profit maximizing level of output : Assume a monopolist faces the following demand curve: P = 180 - 4Q. Marginal cost of production is stable and equal to $20, and there're no fixed costs. What is the monopolist's profit maximizing level of output?

Write algorithm which divides n objects of u into k clusters : Suggest the algorithm which divides n objects of U into k clusters, making use of MST of a graph. Give a simple argument of correctness and bound on the running time of the algorithm you are proposing.

How market structure affects market performance : Describe how market structure affects market performance and conduct. Recognize three types of government regulation that aid to enhance market performance

Effectiveness of control mechanisms within starbucks : Evaluate the effectiveness of these control mechanisms (ways controls are applied) in Starbucks and examine the positive and negative reactions to the use of these controls in Starbucks.

Create database management system for bike shop : Your job is to create a database management system for bike shop who ‘buys' and ‘sells' new and second-hand bikes, and also parts of bike. Bike is constructed with parts while part can be fitted to different bikes.

Explain what are arrival rate and service rate : Explain what are the arrival rate and the service rate - Analyze fast food drive-through window: What are the arrival rate and the service rate?

User Account

All Pages