Securing Higher Grades Costing Your Pocket? Book Your Assignment at The Lowest Price Now!

Get assignment help service to meet the high expectations of your professors


CMP 561 algorithm analysis

Ava’s software is contracted to enhance the CPU efficiency of a system which performs the following operations on several set of data records stored in files:


Percentage of Use

Search data records


Insert data records


Update data records


Programs of the current system are written in Java, with 90% of them utilizing java.util.TreeMap.

Ava was told that the Red Black Tree provides the best CPU efficiency for such an application. Before making the final decision, she wishes to develop a testing program to verify such a theory.

You are tasked by Ava to:

  1. (5%) Write a half-page summary to compare java.util.TreeMap and java.util.TreeSet.

(Copying words directly from resources will not give you credits.)

  1. (15%) Develop a Java program to compare the CPU efficiency between util.TreeSet and java.util.TreeMap.

The key operations of this program are:

o Search by the User Name, using the following 5 user names

  • Amber, Yetta, Allen, Mercedes, Jeanette

o Insert all records from the file “finalUpdat.csv” file.

The time needed to read records into data structures has nothing to do with the requirements. The data file “finalData.csv” will be used to test the program.

Each line in “finalData.csv” and “finalUpdate.csv” contains 4 fields, separated by commas: § User Name

  • Email Address
  • Zone Code
  • PIN

For example,




  • No more than 5%, if your program does not compile
  • No more than 8%, if your program compiles, but, produces an incorrect output




Type Parameters:

E - the type of elements maintained by this set

Data records stored in the java.util.TreeSet are sorted in natural order by the data values. No duplicated data records will be stored. The java.util.TreeSet data structure is also known as red-black binary tree which is a balanced binary tree. A red-black binary tree is a binary tree which satisfies the following:

  • Every node in the tree is red or black
  • The root is always black
  • If a node is red, its children must be black
  • Every path from the root to a leaf must contain the same number of black nodes

The red-black binary tree algorithm ensures that the binary tree is balanced.

CMP 561 algorithm analysis Image 1



Type Parameters:

K - the type of keys maintained by this map

V - the type of mapped values

Data records stored in java.util.TreeMap are sorted according to the natural order of the key values. The java.util.TreeMap data structure does NOT eliminate duplicated records.

Example shows the use of java.util.TreeMap

import java.util.*; public class UseTreeMap {

public static void main(String[] args) {

String []data = { "Hey", "How", "Hey", "Haha", "Hi", "Haha", "How" }; Map <String, Integer> tm = new TreeMap <String, Integer>(); for (String a : data) { Integer cnt = tm.get(a);

tm.put(a, (cnt == null) ? 1 : cnt + 1);


System.out.println(tm.size() + " distinct words:");


} // main

} // UseTreeMap

4 distinct words:

{Haha=2, Hey=2, Hi=1, How=2}

Data class and data file used in the next program example

Data class: OrderRec

Input file: orderinfo.txt

Import java.util.*;

public class OrderRec implements { int ID;

String name; double amount;

public OrderRec() { ID = -999; name = null; amount = 0.0; }

public OrderRec(int i, String n, double a)

{ ID = i; name = n; amount = a; } public OrderRec(String s, String d) {

StringTokenizer st = new StringTokenizer(s, d);

ID = Integer.valueOf(st.nextToken(d)); name = st.nextToken(d);

amount = Double.valueOf(st.nextToken(d));


public int getID() { return ID; } public String getName() { return name; } public double getAmount() { return amount; } public void setID(int i) { ID = i; } public void setName(String n) { name = n; } public void setAmount(double a) { amount = a; }

public String toString() { return ID + "; " + name + "; " + amount; } } // OrderRec

10198; Rainy Day Gear; 8976.0

10260; Fresh Air Fun; 1238.0

10334; Seaside Boats; 1156.0

10329; Bradley Boat Supply; 5674.0

10413; Reliable Hardware; 452.0

10180; Backyard Supplies; 7722.0

10247; Mountain Goods; 7456.0

10415; Spots Birdcage; 887.0

10125; Bird Outfitter; 3542.0

10121; Fresh Air Goods; 6785.0

10287; Outdoor Furnishings; 6852.0

Use java.util.TreeMap to sort records: UseTreeMap2


import java.util.*; import*;

public class UseTreeMap2


public static void main(String []args) {

TreeMap <Integer, OrderRec> orders =

new TreeMap <Integer, OrderRec>();

BufferedReader infile;

String line;

OrderRec temp=null;



infile = new BufferedReader(new FileReader("orderinfo.txt")); while ((line = infile.readLine()) != null)


temp = new OrderRec(line, ";");

orders.put(new Integer(temp.getID()), temp);



} catch (IOException x) { System.err.println(x); System.exit(1); } Infile.close();

Collection c = orders.values();

Iterator ir = c.iterator(); while (ir.hasNext())


} // main

} // UseTreeMap2

10121; Fresh Air Goods; 6785.0

10125; Bird Outfitter; 3542.0

10180; Backyard Supplies; 7722.0

10198; Rainy Day Gear; 8976.0

10247; Mountain Goods; 7456.0

10260; Fresh Air Fun; 1238.0

10287; Outdoor Furnishings; 6852.0

10329; Bradley Boat Supply; 5674.0

10334; Seaside Boats; 1156.0

10413; Reliable Hardware; 452.0

10415; Spots Birdcage; 887.0

Assignment Help Features
Assignment Help Services
  • Assignment Help
  • Homework Help
  • Writing Help
  • Academic Writing Assistance
  • Editing Services
  • Plagiarism Checker Online
  • Proofreading
  • Research Writing Help
QR Code Assignment Help