Your project will not be graded if You do not produce outputs for all the test cases by executing...

Question

Your project will not be graded if You do not produce outputs for all the test cases by executing your source code Your source code is not included in the required extensions (.c, .cpp, *.java, or...

1 answer below »

Your project will not be graded if

You do not produce outputs for all the test cases by executing your source code

Your source code is not included in the required extensions (*.c, *.cpp, *.java, or *.py)

Your report (PDF file) does not include results for all test cases

Your report is in some other format than PDF

Problem 1 (30 points)

Perform the following by reading in two graphs (networks), G1 (Project3_G1_Data.csv) and G2 (Project3_G2_Data.csv):

Design and implement an algorithm to merge these two input graphs into one graph (network), called G. Your algorithm must create a new adjacency matrix representing the merged graph (G) in two ways: one by using a two-dimensional array and another by using a linked-list.

Implement Kruskal’s algorithm in the textbook to find a minimum-spanning tree in graph G.

Print the computed minimum-spanning tree as you did in Quiz 6 and Quiz 7.

Report on the memory usage by each of the two data structures.

Submission Items

Three programs (one for merging graphs and two for finding a minimum-spanning tree, one for each data structure)

A PDF file containing
- The result of the computed minimum-spanning tree and the total distance on it
- The analysis of the memory usage by each data structure

Problem 2 (70 points)

Design and implement your own algorithm to perform K-Means clustering. Your algorithm must implement methods for handling centroid initialization, calculating distance, assigning centroids, moving centroids, calculating loss, and stopping criteria (see Resources below). You must run your algorithm on two different datasets (see below). The first dataset, test case, is synthetic data designed for the purpose of checking the result of your algorithm before running your algorithm on the second dataset which is real data about electric power consumption.

Requirements for Test Case Dataset (
P
roject3_Test_
Case.csv
)

This dataset contains three variables: X1, X2, and Y. Use X1 and X2 to perform clustering. Use Y as the ground truth in your experiments. Run the algorithm with K=2 and report on the following:

The coordinates of each centroid

A count of the number of points assigned to each centroid

The losses for each iteration of training

Requirements for Electric Power Consumption Dataset (
Project3_Power_Consump
tion.csv
)

This dataset provides samples for individual household electric power consumption. For a description of the dataset checkhere(Links to an external site.). Perform K-Means clustering using all variables in this dataset. Report on the following for the different values of K.

For K=2
- The coordinates of each centroid
- A count of the number of points assigned to each centroid
- The losses for each iteration of training

For K from 3 to 20
- A scatter plot containing the loss of the last iteration of training for each value of K
- The coordinates of each centroid for each value of K
- The number of points assigned to each centroid for each value of K
- Using the elbow method (see Resources) find the value of K which best fits the data

Additional Requirements

Explain the stopping criteria you selected for your algorithm (see Resources) and how they may impact your results.

Explain the centroid initialization method you selected and how that may impact your results.

Explain why your algorithm may require different amounts of time to run on the same input and parameters.

Explain why your algorithm may produce different results on the same input and parameters.

Resources

Project3_Resources.pdf

Submission Items

Two programs (one for each dataset) that output the centroid coordinates, loss, and number of points assigned to each centroid by your algorithm for K=2

A PDF file with the required information for each dataset and the responses to the additional requirements

Quiz 8 (March 18, 2021)" wfd-id="224" style="float: left;">Previous

downloads-2jqszhwd-i520iikm.zip

Answered 13 days AfterMar 18, 2021

Kushal · Accepted Answer

Question 1/ms (1) (1).java
Question 1/ms (1) (1).java
import java.util.*;
import java.io.*;
import java.io.BufferedReader;  
import java.io.FileReader;  
import java.io.IOException;  
public class ms {
    
public static void main(String[] args) {
            ms graph = new ms();    
            String line = "";  
            String splitBy = ","; 
            ArrayList graphEdges = new ArrayList(); 
            try   
            {  
            //parsing a CSV file into BufferedReader class constructor  
            BufferedReader br = new BufferedReader(new FileReader("C:\Users\sonid\Downloads\downloads-2jqszhwd-i520iikm (1)\project3g1data-1-521hapwl.csv"));  
            while ((line = br.readLine()) != null)   //returns a Boolean value  
            {  
            
                String[] employee = line.split(splitBy);    
                String a =employee[0];
                String b = employee[1];
                String c = employee[2];
                
                int inum1 = Integer.parseInt(a);
                int inum2 = Integer.parseInt(b);
                int inum3 = Integer.parseInt(c);
                
                graphEdges.add(new Edge(inum1,inum2,inum3));
                
            
            
        
            
            }
            }
            
            catch (IOException e)   
            {  
            e.printStackTrace();  
            }
            
            
            int nodeCount = 1468;       
            graph.kruskalMST(graphEdges, nodeCount);
}
        public void kruskalMST(ArrayList graphEdges, int nodeCount){
            String outputMessage="";
            Collections.sort(graphEdges);       //sort edges with smallest weight 1st
            ArrayList mstEdges = new ArrayList();   //list of edges included in the Minimum spanning tree (initially empty)
            DisjointSet nodeSet = new DisjointSet(nodeCount+1);     //Initialize singleton sets for each node in graph. (nodeCount +1) to account for arrays indexing from 0
            for(int i=0; i{
        private int vertex1;    //an edge has 2 vertices & a weight
        private int vertex2;
        private int weight;
        public Edge(int vertex1, int vertex2, int weight){
            this.vertex1=vertex1;
            this.vertex2=vertex2;
            this.weight=weight;
        }
        public int getVertex1(){
            return vertex1;
        }
        public int getVertex2(){
            return vertex2;
        }
        public int getWeight(){
            return weight;
        }
        @Override
        public int compareTo(Edge otherEdge) {              //Compare based on edge weight (for sorting)
            return this.getWeight() - otherEdge.getWeight();
        }
        @Override
        public String toString() {
            return "Edge ("+getVertex1()+", "+getVertex2()+") weight="+getWeight();
        }
    }
    // DisjointSet class
    //
    // CONSTRUCTION: with int representing initial number of sets
    //
    // ******************PUBLIC OPERATIONS*********************
    // void union(root1, root2) --> Merge two sets
    // int find(x)              --> Return set containing x
    // ******************ERRORS********************************
    // No error checking is performed
    // http://users.cis.fiu.edu/~weiss/dsaajava3/code/DisjSets.java
    /**
     * Disjoint set class, using union by rank and path compression
     * Elements in the set are numbered starting at 0
     * @author Mark Allen Weiss
     */
    class DisjointSet{
        private int[] set;      //the disjoint set as an array
        public int[] getSet(){      //mostly debugging method to print array
            return set;
        }
        /**
         * Construct the disjoint sets object.
         * @param numElements the initial number of disjoint sets.
         */
        public DisjointSet(int numElements) {       //constructor creates singleton sets
            set = new int [numElements];
            for(int i = 0; i  0){       //Loop until we find a root
                next=set[next];
            }
            return next;
        }
        
    }
    
    
    
    
    
    
Question 1/Result (1).

Your project will not be graded if You do not produce outputs for all the test cases by executing your source code Your source code is not included in the required extensions (.c, .cpp, *.java, or...

Problem 1 (30 points)

Problem 2 (70 points)

Answer To: Your project will not be graded if You do not produce outputs for all the test cases by executing...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment

Your project will not be graded if You do not produce outputs for all the test cases by executing your source code Your source code is not included in the required extensions (*.c, *.cpp, *.java, or...

Problem 1 (30 points)

Problem 2 (70 points)

Answer To: Your project will not be graded if You do not produce outputs for all the test cases by executing...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment

Your project will not be graded if You do not produce outputs for all the test cases by executing your source code Your source code is not included in the required extensions (.c, .cpp, *.java, or...