Write a program to do the following. • Input an integer n. • Create a BST...

Write a program to do the following.

• Input an integer n.

• Create a BST B containing the same items, but inserting them in an order that will yield the tree balanced. The following algorithm, known as pre-order traversal, gives you a strategy to produce that sequence.

seq(low, high, T){
   if (low <= high){
       mid = (low+high)/2
       T.insert(mid)
       seq(low, mid-1, T)
       seq(mid+1, high, T)
   }
}

• Measure the time to search for n + 1 in B.

• Display the time taken for search.

/**
* Exception class for access in empty containers
* such as stacks, queues, and priority queues.
* @author Mark Allen Weiss
*/
public class UnderflowException extends RuntimeException
{
}

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// boolean contains( x ) --> Return true if x is present
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as appropriate

/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>
{
/**
* Construct the tree.
*/
public BinarySearchTree( )
{
root = null;
}

/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
root = insert( x, root );
}

/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
root = remove( x, root );
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public AnyType findMin( )
{
if( isEmpty( ) )
throw new UnderflowException( );
return findMin( root ).element;
}

/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public AnyType findMax( )
{
if( isEmpty( ) )
throw new UnderflowException( );
return findMax( root ).element;
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if not found.
*/
public boolean contains( AnyType x )
{
return contains( x, root );
}

/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}

/**
* Print the tree contents in sorted order.
*/
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}

/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return new BinaryNode<AnyType>( x, null, null );
  
int compareResult = x.compareTo( t.element );
  
if( compareResult < 0 )
t.left = insert( x, t.left );
else if( compareResult > 0 )
t.right = insert( x, t.right );
else
; // Duplicate; do nothing
return t;
}

/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return t; // Item not found; do nothing
  
int compareResult = x.compareTo( t.element );
  
if( compareResult < 0 )
t.left = remove( x, t.left );
else if( compareResult > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = remove( t.element, t.right );
}
else
t = ( t.left != null ) ? t.left : t.right;
return t;
}

/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the smallest item.
*/
private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
{
if( t == null )
return null;
else if( t.left == null )
return t;
return findMin( t.left );
}

/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the largest item.
*/
private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
{
if( t != null )
while( t.right != null )
t = t.right;

return t;
}

/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the subtree.
* @return node containing the matched item.
*/
private boolean contains( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return false;
  
int compareResult = x.compareTo( t.element );
  
if( compareResult < 0 )
return contains( x, t.left );
else if( compareResult > 0 )
return contains( x, t.right );
else
return true; // Match
}

/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the subtree.
*/
private void printTree( BinaryNode<AnyType> t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}

/**
* Internal method to compute height of a subtree.
* @param t the node that roots the subtree.
*/
private int height( BinaryNode<AnyType> t )
{
if( t == null )
return -1;
else
return 1 + Math.max( height( t.left ), height( t.right ) );
}
  
// Basic node stored in unbalanced binary search trees
private static class BinaryNode<AnyType>
{
// Constructors
BinaryNode( AnyType theElement )
{
this( theElement, null, null );
}

BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
{
element = theElement;
left = lt;
right = rt;
}

AnyType element; // The data in the node
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
}


/** The tree root. */
private BinaryNode<AnyType> root;


// Test program
public static void main( String [ ] args )
{
BinarySearchTree<Integer> t = new BinarySearchTree<Integer>( );
final int NUMS = 4000;
final int GAP = 37;

System.out.println( "Checking... (no more output means success)" );

for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( i );

for( int i = 1; i < NUMS; i+= 2 )
t.remove( i );

if( NUMS < 40 )
t.printTree( );
if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
System.out.println( "FindMin or FindMax error!" );

for( int i = 2; i < NUMS; i+=2 )
if( !t.contains( i ) )
System.out.println( "Find error1!" );

for( int i = 1; i < NUMS; i+=2 )
{
if( t.contains( i ) )
System.out.println( "Find error2!" );
}
}
}

In: Computer Science

Summarize the basic process for valuing assets

Summarize the basic process for valuing assets

In: Finance

Why business owners should know about finance?

Why business owners should know about finance?

In: Finance

The Alpine House, Inc., is a large retailer of snow skis. The company assembled the information...

The Alpine House, Inc., is a large retailer of snow skis. The company assembled the information shown below for the quarter ended March 31:

Amount
Sales $ 1,012,000
Selling price per pair of skis $ 440
Variable selling expense per pair of skis $ 48
Variable administrative expense per pair of skis $ 18
Total fixed selling expense $ 140,000
Total fixed administrative expense $ 110,000
Beginning merchandise inventory $ 75,000
Ending merchandise inventory $ 105,000
Merchandise purchases $ 305,000

Required:

1. Prepare a traditional income statement for the quarter ended March 31.

2. Prepare a contribution format income statement for the quarter ended March 31.

3. What was the contribution margin per unit?

In: Accounting

Dr. North, a surgeon practicing in Georgia, engaged an Arizona professional corporation consisting of twenty lawyers...

Dr. North, a surgeon practicing in Georgia, engaged an Arizona professional corporation consisting of twenty lawyers to represent him in a dispute with a Georgia hospital. West, a member of the law firm, flew to Atlanta and hired local counsel with Dr. North’s approval. West represented Dr. North in two hearings before the hospital and in one court proceeding, also negotiating a compromise between Dr. North and the hospital. The total bill for the law firm’s travel costs and professional services was $21,000, but Dr. North refused to pay $6,000 of it. The law firm brought an action against Dr. North for the balance owed. Dr. North argued that the action should be dismissed because the law firm failed to register as a foreign corporation in accordance with the Georgia Corporation Statute. Will the law firm be prevented from collecting on the contract? Explain.

In: Economics

Project management Expediting a Project Task Predecessor Normal Time Weeks Normal Cost Crash Time Crash Cost...

Project management

Expediting a Project

Task

Predecessor

Normal Time Weeks

Normal Cost

Crash Time

Crash Cost

A

-

4

$2000

4

-

B

A

4

$1500

2

4500

C

A

6

5000

4

8000

D

B

2

1000

2

-

E

B

6

8000

3

10000

F

C

10

10000

7

14000

G

D

7

3500

4

5000

H

E

4

2500

2

5000

I

G,H

3

2000

2

3500

J

I,F

3

3000

1

4500

Consider the project shown above.

a)Draw the network diagram and find the critical path, time and cost for an all-normal level of project activity.

b)Calculate the crash cost-per-week assuming that all activities may be partially crashed.

c)Which tasks should be crashed to do the project in 21 weeks? What is the project cost?

d)Calculate the shortest delivery time for the project. What is the cost?

In: Operations Management

Roger issued 40 year bonds six years ago at a coupon rate of 4.50 percent, and...

Roger issued 40 year bonds six years ago at a coupon rate of 4.50 percent, and the bond smake semi-annual payments. If the YTM on these bonds is 4.6 percent, what is the current bond price

In: Finance

Consider the following data on real GDP per capita in: Year Per Capita Real GDP 1950...

Consider the following data on real GDP per capita in:

Year

Per Capita Real GDP

1950

14 339

1960

17 351

1970

23 790

1980

30 732

1990

35 868

2000

43 288

2010

46 406

2011

47 554

2012

47 741

2013

48 066

2014

48 780

a) Calculate the percentage growth rates in real GDP per capita in each of the years 2011 through 2014, from the previous year.

b) Now, instead of calculating the annual percentage growth rates in the years 2011 through 2014 directly, use as an approximation

100×logyt-logyt-1

where yt is real per capita GDP in year t. How close does this approximation come to the actual growth rates you calculated in part (a)?

In: Economics

Explain what ‘consumer surplus” and “producer surplus” are , and why they are important concepts

Explain what ‘consumer surplus” and “producer surplus” are , and why they are important concepts

In: Economics

One learned lecturer once commented that “It is a questionable honour to be a professional in...

One learned lecturer once commented that “It is a questionable honour to be a professional in today’s society.” Discuss this statement in light of the expansion of professional liability and the reasons for the expansion. Also comment on how many professionals can now protect themselves and their property from claims against them in terms of civil liability. (Canadian Law)

In: Operations Management

Describe the Pyramid System Training Routine and give an example with a Flat Bench Press?

Describe the Pyramid System Training Routine and give an example with a Flat Bench Press?

In: Psychology

You have taken a random sample of 286 children in Virginia’s homeless shelters to establish their...

You have taken a random sample of 286 children in Virginia’s homeless shelters to establish their needs (using an establish Needs Scale). The mean is 5.32, the mode is 6, and the median is 6.
A. Provide a complete description of this sample (including shape and appropriate measures of center and spread).
B. Why did you choose the measure of center detailed above?
C. Regardless of 10b, why is a confidence interval of the mean a valid estimate of the mean?
D. Calculate and interpret a 95% confidence interval for the mean.
E. What is the population for this analysis?

In: Math

A comorbidity is a hospital-acquired condition that contributes to an individual’s morbidity and/or mortality. Question 1...

A comorbidity is a hospital-acquired condition that contributes to an individual’s morbidity and/or mortality.

Question 1 options:

True
False

Question 2 (1 point)

Hospital value-based purchasing (HVBP) is a product of the Affordable Care Act (ACA) that allows hospitals to receive monetary rewards if quality care is provided.

Question 2 options:

True
False

Question 3 (1 point)

A managed care organization (MCO) can utilize physician report cards and profiling of physicians in order to show employers the quality of care the MCO provides.

Question 3 options:

True
False

Question 4 (1 point)

People who are single tend to have higher mortality rates, which may be related to poorer health, risky behavior, and differences in lifestyle.

Question 4 options:

True
False

Question 5 (1 point)

Geographic information systems (GISs) provide useful descriptive data, but the slow retrieval process deters some epidemiologists and clinicians from using this tool.

Question 5 options:

True
False

In: Operations Management

Could you implement a gpa calculator so that it asks for a letter grade for each...

Could you implement a gpa calculator so that it asks for a letter grade for each of four classes, calculates the gpa, and prints the GPA out along with the student id, major, and name.

/*****************************Student.java*************************/


public class Student {

   // private data members
   private String id;
   private String name;
   private String major;
   private double gpa;

   // default constructor which set the data member to defualt value
   public Student() {

       this.id = "";
       this.name = "";
       this.major = "";
       this.gpa = 0;
   }

   // parameterized constructor
   public Student(String id, String name, String major, double gpa) {
       this.id = id;
       this.name = name;
       this.major = major;
       this.gpa = gpa;
   }

   // getter and setter
   public String getId() {
       return id;
   }

   public void setId(String id) {
       this.id = id;
   }

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   public String getMajor() {
       return major;
   }

   public void setMajor(String major) {
       this.major = major;
   }

   public double getGpa() {
       return gpa;
   }

   public void setGpa(double gpa) {
       this.gpa = gpa;
   }

   // print student data
   public void printStudent() {

       System.out.println("Student ID: " + id);
       System.out.println("Student name: " + name);
       System.out.println("Student major: " + major);
       System.out.println("Student GPA: " + gpa);
   }

}

/**************************StudentApplication.java*******************/


public class StudentApplication {

   public static void main(String[] args) {
      
       //create object by default constructor
       Student s1 = new Student();
       //create object by overloaded constructor
       Student s2 = new Student("S12345", "Virat Kohli", "Computer Science", 4.5);
       //set the information of object 1
       s1.setName("John Doe");
       s1.setId("S123456");
       s1.setMajor("Electronics");
       s1.setGpa(4.0);
      
       s1.printStudent();
       System.out.println();
       s2.printStudent();
   }
}

In: Computer Science

What questions, comments to you have about the experiences (150-250 Words) My experience regarding love and...

What questions, comments to you have about the experiences (150-250 Words)

My experience regarding love and intimate relationships is based on how I was raised by my family and traditions of American culture. Growing up, I always saw the family unit as a man and woman who made a commitment to each other, set goals together and would eventually have a family. Generationally, things are different now compared to when I married my husband. Today we have people identifying more with heterosexual, homosexual, bisexual, lesbian, gay, and transgender as well as interracial and interethnic relationships and marriages. Many girls dream about marrying someday, however, many people today are holding off getting married or choosing not to marry at all. When my husband and I chose to get married, we wanted to spend the rest of our lives making each other happy, have a family, and grow old together. We have watched our three children grow into amazing young adults and will be celebrating 25 years of marriage on New Years Day.

In: Psychology