Solutions Manual

for
Data Structures
with Java

John R. Hubbard
Anita Huray
University of Richmond

Chapter 1
Object-Oriented Programming
Exercises
1.1

The requirements stage would generate a user manual like that shown here:
User Manual
Enter the string:
java CelsiusToFahrenheit <first> <last> <incr>
at the command line, where <first> is the first Celsius temperature to be
converted, <first> is the last Celsius temperature, and <incr> is the Celsius
increment for the table. The output will be a conversion table with that range
and increment.
Example:
Input:
java Convert 0 40 10
Output: 032
1050
2068
3086
40104

The design stage could adapt the same class as shown in Listing 1.1.
The implementation stage could adapt the same class as shown in Listing 1.2.
The testing stage could run a test driver like this:
public class CelsiusToFahrenheit {
public static void main(String[] args) {
if (args.length!=3) exit();
double first = Double.parseDouble(args[0]);
double last = Double.parseDouble(args[1]);
double incr = Double.parseDouble(args[2]);
for (double i=first; i<=last; i += incr)
System.out.println(i + \t + new MyTemperature(value,'F') );
}

Chapter 1 Binary Trees

private static void exit() {
System.out.println(
"Usage: java CelsiusToFahrenheit <first> <last> <incr>"
+ "\nwhere:"
+ "\t<first> is the first celsius temperature to be listed"
+ "\t<last> is the last celsius temperature to be listed"
+ "\t<incr> is the increment"
+ "\nExample:"
+ "\tjava CelsiusToFahrenheit 0 40 4"
Design
);
System.exit(0);
}
Implementation
}

1.2

Another likely cycle is shown in here. This is the common Debug

Cycle, consisting of repeated two-part test-and-correct step.

Testing

1.3
CombinationLock
-n1:int
-n2:int
-n3:int
-open:boolean
+changeComb(int,int,int,int,int,int):boolean
+close()
+isOpen():boolean
+open(int,int,int):boolean

1.4

If d is a divisor of n that is greater than n , then m = n/d must be a whole number (i.e., an
integer), and therefore another divisor of n. But since d > n , we have m = n/d < n/ n =
n . So by checking for divisors only among those integers that are less than n ,
the existence of the divisor d > n will be found indirectly from m = n/d < n .

1.5
Course

Section

Instructor

Student

Person

Solutions

1.6

Department

Course

Chair

Section

Instructor

Student

Person

1.7
Course

Undergraduate

Section

Instructor

Graduate

Person

Student

1.8
Vehicle

Bus

Car

Driver

Owner

Person

Chapter 1 Binary Trees

1.9

Bank

Manager

Person

BankBranch

Customer

CheckingAccount

Account

Credit

SavingsAccount

Transaction

1.10

Debit
Media

BroadcastMedia

RadioProgram

TVProgram

Journal

PrintMedia

Periodical

Magazine

Website

Book

Newspaper

Programming Problems
1.1

/**
*
*
*
*
*/

An interface for representing temperatures, with functionality

for converting their values between Celsius and Fahrenheit.
@author John R. Hubbard
@see
MyTemperature

Solutions

public interface Temperature {

/** @return the Celsius value for this temperature.
*/
public double getCelsius();
/** @return the Fahrenheit value for this temperature.
*/
public double getFahrenheit();
/** @return the Kelvin value for this temperature.
*/
public double getKelvin();
/** @param celsius the Celsius value for this temperature. */
public void setCelsius(double celsius);
/** @param fahrenheit the Fahrenheit value for this temp. */
public void setFahrenheit(double fahrenheit);
/** @param kelvin the Kelvin value for this temperature.*/
public void setKelvin(double kelvin);
}
public class MyTemperature implements Temperature {
private double celsius;
// stores temperature as a Celsius value
public MyTemperature(double value, char scale) {
if (scale=='C') setCelsius(value);
if (scale=='F') setFahrenheit(value);
else setKelvin(value);
}
public double getCelsius() {
return celsius;
}
public double getFahrenheit() {
return 9*celsius/5 + 32.0;
}
public double getKelvin() {
return celsius + 273.16;
}
public void setCelsius(double celsius) {
this.celsius = celsius;
}
public void setFahrenheit(double fahrenheit) {
this.celsius = 5*(fahrenheit - 32)/9;
}
public void setKelvin(double kelvin) {
this.celsius = kelvin - 273.16;
}
public String toString() {
// Example: "25.0 C = 77.0 F"

Chapter 1 Binary Trees

return round(getCelsius())+ " C = "
+ round(getFahrenheit())+ " F = "
+ round(getKelvin())+ " K";
}
private static double round(double x) {
// returns x, rounded to one digit on the right of the decimal:
return Math.round(10*x)/10.0;
}

1.2

}
public class MyTemperature implements Temperature {
private double celsius; // stores temperature as a Celsius value
private int digits;
// number of digits to right of decimal
public MyTemperature(double value, char scale, int digits) {
if (scale=='C') setCelsius(value);
else setFahrenheit(value);
this.digits = digits;
}
public double getCelsius() {
return celsius;
}
public double getFahrenheit() {
return 9*celsius/5 + 32.0;
}
public void setCelsius(double celsius) {
this.celsius = celsius;
}
public void setDigits(int digits) {
this.digits = digits;
}
public void setFahrenheit(double fahrenheit) {
this.celsius = 5*(fahrenheit - 32)/9;
}
public String toString() {
// Example: "25.0 C = 77.0 F"
return round(getCelsius())+" C = "+round(getFahrenheit())+" F";
}
private double round(double x) {
// returns x, rounded to one digit on the right of the decimal:
double p = Math.pow(10,digits);
return Math.round(p*x)/p;
}
}

Solutions

1.3

public class Convert {

public static void main(String[] args) {
if (args.length!=3) exit();
double value = Double.parseDouble(args[0]); // convert string
char scale = Character.toUpperCase(args[1].charAt(0));
int digits = Integer.parseInt(args[2]);
if (scale!='C' && scale!='F') exit();
Temperature temperature= new MyTemperature(value, scale, digits);
System.out.println(temperature);
}
private static void exit() {
// prints usage message and then terminates the program:
System.out.println(
"Usage: java Convert <temperature> <scale> <digits>"
+ "\nwhere:"
+ "\t<temperature> is the temperature that you want to convert"
+ "\n\t<scale> is either \"C\" or \"F\"."
+ "\n\t<digits> is the number of digits to use right of decimal."
+ "\nExample: java Convert 67 F 2"
);
System.exit(0);
}
}
public class MyTemperature implements Temperature {
private static final String s = "###,###,###,###.################";
private double celsius; // stores temperature as a Celsius value
private int digits;
// number of digits to right of decimal
private DecimalFormat formatter; // used for formatted output
public MyTemperature(double value, char scale, int digits) {
if (scale=='C') setCelsius(value);
else setFahrenheit(value);
this.digits = digits;
setFormatter();
}
private void setFormatter() {
String pattern = new String(s.toCharArray(), 0, 16 + digits);
this.formatter = new DecimalFormat(pattern);
}
public double getCelsius() {
return celsius;
}

Chapter 1 Binary Trees

public double getFahrenheit() {
return 9*celsius/5 + 32.0;
}
public void setCelsius(double celsius) {
this.celsius = celsius;
}
public void setDigits(int digits) {
this.digits = digits;
setFormatter();
}
public void setFahrenheit(double fahrenheit) {
this.celsius = 5*(fahrenheit - 32)/9;
}
public String toString() {
// Example: "25.0 C = 77.0 F"
return formatter.format(getCelsius()) + " C = "
+ formatter.format(getFahrenheit()) + " F";
}
}
public class Convert {
public static void main(String[] args) {
if (args.length!=3) exit();
double value = Double.parseDouble(args[0]); // convert string
char scale = Character.toUpperCase(args[1].charAt(0));
int digits = Integer.parseInt(args[2]);
if (scale!='C' && scale!='F') exit();
Temperature temperature= new MyTemperature(value, scale, digits);
System.out.println(temperature);
}
private static void exit() {
// prints usage message and then terminates the program:
System.out.println(
"Usage: java Convert <temperature> <scale> <digits>"
+ "\nwhere:"
+ "\t<temperature> is the temperature that you want to convert"
+ "\n\t<scale> is either \"C\" or \"F\"."
+ "\n\t<digits> is the number of digits to use right of decimal."
+ "\nExample: java Convert 67 F 2"
);
System.exit(0);
}
}

Solutions
1.4

1.5

public class TestPrimeAlgorithm {

public static void main(String[] args) {
Random random = new Random();
for (int i=0; i<100; i++) {
int n = random.nextInt(Integer.MAX_VALUE);
if (isPrime(n)) System.out.print(n + " ");
}
}
public static boolean isPrime(int n) {
if (n < 2) return false;
if (n < 4) return true;
if (n%2 == 0) return false;
for (int d=3; d*d <= n; d += 2)
if (n%d == 0) return false;
return true;
}
}
public class Course {
private float credit;
private String dept;
private String id;
private String name;
private Section[] sections = new Section[1000];
public Course(String dept, String id, String name, float credit) {
this.credit = credit;
this.dept = dept;
this.id = id;
this.name = name;
}
public void add(Section section) {
int i=0;
while (sections[i] != null)
++i;
sections[i] = section;
}
public String toString() {
String s = dept + " " + id + " \"" + name + "\", "
+ credit + " credits";
for (int i=0; sections[i] != null; i++)
s += sections[i];
return s;
}

10

Chapter 1 Binary Trees

public static void main(String[] args) {
Course course = new Course("CMSC", "221", "Data Structures", 4);
System.out.println(course);
}
}
public class Section {
private Course course;
private String place;
private String term;
private String time;
private Instructor instructor;
private Student[] students;
public Section(Course course, String term, String p, String t) {
this.course = course;
this.term = term;
this.place = p;
this.time = t;
}
public Course getCourse() {
return course;
}
public String getPlace() {
return place;
}
public String getTerm() {
return term;
}
public String getTime() {
return time;
}
public Instructor getInstructor() {
return instructor;
}
public Student[] getStudents() {
return students;
}
public void setPlace(String place) {
this.place = place;
}
public void setTerm(String term) {
this.term = term;

Solutions

11
}
public void setTime(String time) {
this.time = time;
}
public void setInstructor(Instructor instructor) {
this.instructor = instructor;
}
public void setStudents(Student[] students) {
int n = students.length;
// duplicate the array object:
this.students = new Student[n];
// but do not duplicate the Student objects:
for (int i=0; i<n; i++)
this.students[i] = students[i];
}
public String toString() {
return course + ": " + term + ", " + place + ", " + time + ", "
+ instructor;
}
public static void main(String[] args) {
Course course = new Course("CMSC", "221", "Data Structures", 4);
Section section = new Section(course, "Fall 2004", null, null);
System.out.println(section);
}

}
import java.util.*;
public class Person {
protected int yob;
protected String email;
protected String id;
protected boolean male;
protected String name;
public Person(String name, String id, String sex, int yob) {
this.id = id;
this.male = (sex.substring(0,1).toUpperCase() == "M");
this.name = name;
this.yob = yob;
}
public int getYob() {
return yob;
}

12

Chapter 1 Binary Trees

public String getEmail() {
return email;
}
public String getId() {
return id;
}
public boolean isMale() {
return male;
}
public String getName() {
return name;
}
public void setEmail(String email) {
this.email = email;
}
public String toString() {
String string = name + ", " + id;
if (male) string += " (M)";
else string += " (F)";
if (email != null) string += ", " + email;
string += " (" + yob + ")";
return string;
}
public static void main(String[] args) {
Person grandson = new Person("C. Hubbard", "1.2.1", "M", 2002);
System.out.println(grandson);
grandson.setEmail("abced@fgh.ijk");
System.out.println(grandson);
System.out.println("\t name: " + grandson.name);
System.out.println("\t
id: " + grandson.id);
System.out.println("\t sex: "+ (grandson.male?"male":"female"));
System.out.println("\temail: " + grandson.email);
System.out.println("\t yob: " + grandson.yob);
}
}
import java.util.*;
public class Student extends Person {
protected String country;
protected int credits;
protected double gpa;
public Student(String name, String id, String s, int y, String c) {

Solutions

13
super(name, id, s, y);
this.country = c;
}
public int getCredits() {
return credits;
}
public double getGpa() {
return gpa;
}
public String getCountry() {
return country;
}
public void setCredits(int credits) {
this.credits = credits;
}
public void setGpa(double gpa) {
this.gpa = gpa;
}
public void setCountry(List record) {
this.country = country;
}
public static void main(String[] args) {
Student student =
new Student("Anne Miller", "200491", "F", 1985, "US");
System.out.println(student);
}

}
import java.util.*;
public class Instructor extends Person {
protected String dept;
protected String office;
protected String tel;
public Instructor(String name, String id, String sex, int yob) {
super(name, id, sex, yob);
}
public String getDept() {
return office;
}
public String getOffice() {
return office;
}

14

Chapter 1 Binary Trees

public String getTel() {
return tel;
}
public void setDept(String dept) {
this.dept = dept;
}
public void setOffice(String office) {
this.office = office;
}
public void setTel(String tel) {
this.tel = tel;
}
public String toString() {
String s = super.toString();
if (dept != null) s += ", " + dept;
if (office != null) s += ", " + office;
if (tel != null) s += " (" + tel + ")";
return s;
}
public static void main(String[] args) {
Instructor knuth = new Instructor("Don Knuth","8122063","M",1938);
System.out.println(knuth);
knuth.setDept("CS");
System.out.println(knuth);
}

1.6

}
public class ComboLock {
private int n1, n2, n3;
private boolean open;
public ComboLock(int n1, int n2, int n3) {
this.n1 = n1;
this.n2 = n2;
this.n3 = n3;
}
public boolean changeComb(int n1, int n2, int n3, int n4,
int n5, int n6) {
if (this.n1 != n1 || this.n2 != n2 || this.n3 != n3) return false;
this.n1 = n4;
this.n2 = n5;
this.n3 = n6;
open = false;
return true;

Solutions

15
}
public void close() {
open = false;
}
public boolean isOpen() {
return open;
}
public boolean open(int n1, int n2, int n3) {
if (this.n1 == n1 && this.n2 == n2 && this.n3 == n3) open = true;
else open = false;
return open;
}

1.7

public class TestComboLock {

public static void main(String[] args) {
ComboLock lock = new ComboLock(10, 20, 30);
System.out.println("lock.isOpen(): " + lock.isOpen());
System.out.println("lock.open(10,20,30): "+lock.open(10,20,30));
System.out.println("lock.isOpen(): " + lock.isOpen());
lock.close();
System.out.println("lock.isOpen(): " + lock.isOpen());
System.out.println("lock.open(11,20,30): "+lock.open(11,20,30));
System.out.println("lock.isOpen(): " + lock.isOpen());
System.out.println("lock.changeComb(11, 20, 30, 11, 22, 33): "
+ lock.changeComb(11, 20, 30, 11, 22, 33));
System.out.println("lock.isOpen(): " + lock.isOpen());
System.out.println("lock.open(11,22,33): "+lock.open(11,22,33));
System.out.println("lock.isOpen(): " + lock.isOpen());
System.out.println("lock.changeComb(10, 20, 30, 15, 25, 35): "
+ lock.changeComb(10, 20, 30, 15, 25, 35));
System.out.println("lock.isOpen(): " + lock.isOpen());
System.out.println("lock.open(15,25,35): "+lock.open(15,25,35));
System.out.println("lock.isOpen(): " + lock.isOpen());
}
}
import java.util.*;
public class Student extends Person { // Student inherits Person
private String country;
// Student aggregates String
private int credits;
private double gpa;
private final Transcript transcript = new Transcript();

16

Chapter 1 Binary Trees

public Student(String name, boolean male, int yob, String c) {
super(name, male, yob);
this.country = c;
}
public void updateTranscript(Section section, Grade grade) {
transcript.add(section, grade);
}
public void printTranscript() {
System.out.println(transcript);
}
private class Transcript {
// composition
Map map = new HashMap();
void add(Section section, Grade grade) {
map.put(section, grade);
}
public String toString() {
return map.toString();
}
}
}
package chap01.prob07;
public class TestStudent {
public static void main(String[] args) {
Student joe = new Student("Joe", true, 1983, "IT");
joe.updateTranscript(new Section("CS211.02"), new Grade("A-"));
joe.updateTranscript(new Section("EC110.07"), new Grade("B+"));
joe.printTranscript();
}
}

1.8

class Phone {
private String areaCode, number;
public Phone(String areaCode, String number) {
this.areaCode = areaCode;
this.number = number;
}
public Phone(Phone that) {
this.areaCode = that.areaCode;
this.number = that.number;
}
public void setAreaCode(String areaCode) {
this.areaCode = areaCode;

Solutions

17
}
public String toString() {
return "(" + areaCode + ")" + number.substring(0, 3)
+ "-" + number.substring(3);
}

}
public class Person {
private final boolean male;
private final String name;
private final Phone phone;
private final int yob;
public Person(String name, boolean male, int yob, Phone phone) {
this.name = name;
this.male = male;
this.yob = yob;
this.phone = new Phone(phone);
}
public String getName() {
return name;
}
public Phone getPhone() {
return phone;
}
public int getYob() {
return yob;
}
public boolean isMale() {
return male;
}
public String toString() {
return (male?"Mr. ":"Ms. ") + name+" ("+yob+"), tel. "+phone;
}
public static void main(String[] args) {
Phone tel = new Phone("808", "4561414");
Person gwb = new Person("G. W. Bush", true, 1946, tel);
System.out.println(gwb);
tel.setAreaCode("202");
System.out.println(gwb);
}
}

Chapter 2
Abstract Data Types
Exercises
2.1

ADT: Int
interface
An Int is an immutable object that represents a whole
Int
number, such as 44 or 7.
+Int(long)
Int(long n)
+isLessThan(Int)
Constructs: an Integer that is equivalent to n.
+minus(Int):Int
+plus(Int):Int
boolean isLessThan(Integer x)
+times(Int):Int
Returns: true if this integer is less than x; otherwise false.
Integer minus(Integer x)
Returns: an Integer that represents the difference of this integer minus x.
Integer plus(Integer x)
Returns: an Integer that represents the sum of this integer and x.
Integer times(Integer x)
Returns: an Integer that represents the product of this integer and x.

package chap02.exer01;
public interface Integer {
public Integer plus(Integer x);
public Integer minus(Integer x);
public Integer times(Integer x);
}

18

Solutions
2.2

19

ADT: Counter
A Counter is an object that keeps a non-negative
integer count.
Counter()
Constructs:a Counter that is initialized to 0.
integer getCount()
Postcondition:this date is unchanged.
Returns:the count.
void increment()
Postcondition:the count has been increased by 1.
void reset()
Postcondition:the count is 0.

interface
Counter
+Counter()
+getCount():int
+increment()
+reset()

package chap02.exer02;
public interface Counter {
public void add(Number x);
public void subtract(Number x);
public void multiply(Number x);
public void divide(Number x);
public Number sum(Number x);
public Number difference(Number x);
public Number product(Number x);
public Number quotient(Number x);
}

2.3

ADT: Date
A Date represents a calendar date, such as July 4,
1776.
void add(integer days)
Postcondition: this date is advanced by the
specified number of days.
integer getDay()
Returns:the day number of this date.
Postcondition:this date is unchanged.
integer getMonth()
Returns:the month number of this date.
Postcondition:this date is unchanged.
integer getYear()
Returns:the year number of this date.
Postcondition:this date is unchanged.

interface
Date
+add(int)
+getDay():int
+getMonth():int
+getYear():int
+numDays(Date):int
+setDay(int)
+setMonth(int)
+setYear(int)

20

Chapter 2 Abstract Data Types

integer numDays(Date date)

Postcondition: this date is unchanged.
Returns: the day number days from of this date to the specified date.
void setDay(integer day)
Precondition:1 day 31.
Postcondition:this dates day equals the specified day.
void setMonth(integer month)
Precondition:1 month 12.
Postcondition:this dates month equals the specified month.
void setYear(integer year)
Precondition:1700 year 2100.
Postcondition:this dates day equals the specified year.

2.4

2.5

public interface Date {

public void add(Number x);
public void subtract(Number x);
public void multiply(Number x);
public void divide(Number x);
public Number sum(Number x);
public Number difference(Number x);
public Number product(Number x);
public Number quotient(Number x);
}
Algorithm Leap Year Determination

Input: a Date date;

Output: true, if date is a leap year; otherwise, false.
Postcondition: the date object is unchanged.
1. Let y = date.getYear().
2. If y is divisible by 400, return true.
3. If y is divisible by 100, return false.
4. If y is divisible by 4, return true.
5. Return false.
Algorithm Bag Subset

Input: Two Bag objects: bag1 and bag2.

Output: true, if element of bag1 is also an element of bag2; otherwise, false.
1. Let x = bag1.getFirst().
2. Repeat steps 3-5:
3.
If x is null, return true.
4.
If bag2.contains(x) is false, return false.
5.
Let x = bag1.getNext().

Solutions
2.6

2.7

2.8

2.9

21

Algorithm Bag Intersection

Input: Two Bag objects: bag1 and bag2.

Output: the number of elements that are in both bags.
1. Let n = 0.
2. Let x = bag1.getFirst().
3. Repeat steps 4-6:
4.
If x is null, return n.
5.
If bag2.contains(x), add 1 to n.
6.
Let x = bag1.getNext().
Algorithm Bag Remove All

Input: Two Bag objects: bag1 and bag2.

Postcondition: every element of bag1 is also an element of bag2.
1. Let x = bag1.getFirst().
2. Repeat steps 3-5:
3.
If x is null, return.
4.
If bag2.contains(x) is false, bag1.remove(x).
5.
Let x = bag1.getNext().
public interface Card {
public int getRank();
public Suit getSuit();
public String toString();
}
final class Suit {
public static final Suit
public static final Suit
public static final Suit
public static final Suit
private int n;
private Suit(int n) {
this.n = n;
}
}
public interface Die {
public int nextToss();
}

interface
Card
+Card(Suit,int)
+getRank():int
+getSuit():Suit
+toString():String

SPADES = new Suit(0);

HEARTS = new Suit(1);
DIAMONDS = new Suit(2);
CLUBS = new Suit(3);

Die
-random:Random
+Die()
+Die(Random)
+nextToss():int

22
2.10

Chapter 2 Abstract Data Types

public interface Dice {
public int nextToss()
}

Dice
-random:Random
+Dice()
+Dice(Random)
+nextToss():int

2.11

a. ADT: Number
A Number object represents a real number.
void add(Number x)
Postcondition: x has been added to this number.
void subtract(Number x)
Postcondition: x has been subtracted from this number.
void multiply(Number x)
Postcondition: this number has been multiplied by x.
void divide(Number x)
Postcondition: this number has been divided by x.
Number sum(Number x)
Postcondition: this number is unchanged.
Returns: the sum of x and this number.
Number difference(Number x)
Postcondition: this number is unchanged.
Returns: the difference of x from this number.
Number product(Number x)
Postcondition: this number is unchanged.
Returns: the sum of x and this number.
Number quotient(Number x)
Postcondition: this number is unchanged.
Returns: the quotient of this number divided by x.

b. public interface Number {

public
public
public
public
public
public
public
public
}

void add(Number x);

void subtract(Number x);
void multiply(Number x);
void divide(Number x);
Number sum(Number x);
Number difference(Number x);
Number product(Number x);
Number quotient(Number x);

Solutions

2.12

23

a. ADT: Point
A Point object represents a point (x, y) in two-dimensional coordinate space.
double getX()
Postcondition: this point is unchanged.
Returns: the x-coordinate of this point.
double getY()
Postcondition: this point is unchanged.
Returns: the y-coordinate of this point.
void setX(double x)
Postcondition: the x-coordinate of this point equals x.
void setY(double y)
Postcondition: the y-coordinate of this point equals y.
void moveTo(double x, double y)
Postconditions: the x-coordinate of this point equals x;
the y-coordinate of this point equals y.
b. public interface Point {
public
public
public
public
public

double getX();
double getY();
void setX(double x);
void setY(double y);
void moveTo(double x, double y);

2.13

a. ADT: Vector
A Vector is an ordered container of objects.
Object getAtIndex(integer i)
Postcondition: this vector is unchanged.
Returns: the object at index i.
void setAtIndex(Object x, integer i)
Postcondition: the object x is at index i.
integer size()
Postcondition: this vector is unchanged.
Returns: the number of objects in this vector.
b. public interface Vector {
public interface Vector {
public Object getAtIndex(int i);
public void setAtIndex(Object x, int i);
public integer size();
}

24

2.14

Chapter 2 Abstract Data Types

a. ADT: Matrix
A Matrix is a two-dimensional array of numbers.
int getRows()
Postcondition: this matrix is unchanged.
Returns: the number of rows in this matrix.
int getColumns()
Postcondition: this matrix is unchanged.
Returns: the number of columns in this matrix.
double get(integer i, integer j)
Postcondition: this matrix is unchanged.
Returns: the number in row i and column j.
void set(integer i, integer j, double x)
Postcondition: the number in row i and column j equals x.
Matrix transpose()
Postcondition: this matrix is unchanged.
Returns: a new matrix that is the transpose of this matrix.
b. public interface Matrix {
public interface Matrix {
public int getRows();
public int getColumns();
public double getY(int i, int j);
public void set(int i, int j, double x);
public Matrix transpose();
}

2.15

a. ADT: Polynomial
A Polynomial is a mathematical function that is determined by its sequence of
coefficients and exponents.
Polynomial derivative()
Postcondition: this polynomial is unchanged.
Returns: a new polynomial that is the derivative of this polynomial.
integer getDegree()
Postcondition: this polynomial is unchanged.
Returns: the highest exponent of this polynomial.
String toString()
Postcondition: this polynomial is unchanged.
Returns: a string representation of this polynomial.
double valueAt(double x)
Postcondition: this polynomial is unchanged.
Returns: the y-value of this polynomial evaluated at x.

Solutions

25

b. public interface Polynomial {

public
public
public
public

Polynomial derivative();
int getDegree();
String toString();
double valueAt(double x);

2.16

a. ADT: Purse
A Purse is a container of coins.
integer getNumCoinsOf(integer c)
Postcondition: this purse is unchanged.
Returns: the number of c-cent coins in this purse.
void addNumCoinsOf(integer c, integer n)
Postcondition: increases the number of c-cent coins in this purse by n.
integer totalNumCoins()
Postcondition: this purse is unchanged.
Returns: the total number of coins in this purse.
double totalValue()
Postcondition: this polynomial is unchanged.
Returns: the total dollar value of all the coins in this purse.
b. public interface Purse {
public
public
public
public
}

int getNumCoinsOf(int c);

void addNumCoinsOf(int c, int n);
int totalNumCoins();
double totalValue();

26

2.17

Chapter 2 Abstract Data Types

a. ADT: Set
A Set is a container of unique objects (no duplicates).
boolean add(Object element)
Postcondition: the specified element is in this set.
Returns: true if and only if this set is changed.
void clear()
Postcondition: this set is empty.
boolean contains(Object element)
Postcondition: this set is unchanged.
Returns: true if and only if this set contains the specified element.
boolean equals(Object object)
Postcondition: this set is unchanged.
Returns: true if and only if the specified object is a set and it has
the same contents as this set.
boolean remove(Object element)
Postcondition: the specified element is not in this set.
Returns: true if and only if this set is changed.
integer size()
Postcondition: this set is unchanged.
Returns: the number of elements in this set.

b.
Set
+add(Object):boolean
+clear()
+contains(Object):boolean
+equals(Object):boolean
+remove(Object):boolean
+size():int

Solutions

2.18

27

a. ADT: Map
A Map is a container of key-value pairs, where the keys are unique.
void clear()
Postcondition: this map is empty.
boolean containsKey(Object key)
Postcondition: this map is unchanged.
Returns: true if and only if this map contains the specified key.
Object get(Object key)
Postcondition: this map is unchanged.
Returns: the value for the specified key if it is in this map,
otherwise null is returned.
Set keySet()
Postcondition: this map is unchanged.
Returns: a new set whose elements are the keys in this map.
Object put(Object key, Object value)
Postcondition: the specified key-value pair is in this map.
Returns: the previous value stored in this map for the specified key if
that key is in this map; otherwise null is returned.
boolean remove(Object key)
Postcondition: no key-value pair with the specified key is in this map.
Returns: true if and only if this map is changed.
integer size()
Postcondition: this map is unchanged.
Returns: the number of elements in this map.

b.
Map
+clear()
+containsKey(Object):boolean
+get(Object):Object
+keySet():Set
+put(Object,Object):Object
+remove(Object):boolean
+size():int

28

2.19

Chapter 2 Abstract Data Types

a. ADT: List
A List is a sequence of objects.
void add(integer index, Object element)
Postcondition: the specified element is at the specified index in
this list.
void clear()
Postcondition: this list is empty.
boolean contains(Object element)
Postcondition: this list is unchanged.
Returns: true if and only if this list contains the specified element.
Object get(integer index)
Postcondition: this list is unchanged.
Returns: the element at the specified index is returned.
integer indexOf(Object element)
Postcondition: this list is unchanged.
Returns: the index of the specified element is returned if it is in this
list; otherwise 1 is returned.
boolean remove(Object element)
Postcondition: the first occurrence of the specified element is removed
from this list if it is present.
Returns: true if and only if this list is changed.
Object set(integer index, Object element)
Postcondition: the element at the specified index in this list is
replaced by the specified element.
Returns: the replaced element.
integer size()
Postcondition: this list is unchanged.
Returns: the number of elements in this list.
List subList(integer fromIndex, integer toIndex)
Postcondition: this list is unchanged.
Returns: a new list whose elements are the element in this list that are
in the specified index range.
b.
List
+add(int,Object)
+clear()
+contains(Object):boolean
+get(int):Object
+indexOf(Object):int
+remove(Object):boolean
+set(int,Object):Object
+size():int
+subList(int,int):List

Solutions

29

Programming Problems
2.1

public interface Set {

public
public
public
public
public
public

2.2

boolean add(Object object);

boolean contains(Object object);
Object getFirst();
Object getNext();
boolean remove(Object object);
int size()

}
public class ArraySet implements Set {
private Object[] objects = new Object[1000];
private int size, i;
public boolean add(Object object) {
if (contains(object)) return false; // no duplicates
objects[size++] = object;
return true;
}
public boolean contains(Object object) {
for (int i=0; i<size; i++)
if (objects[i]==object) return true;
return false;
}
public Object getFirst() {
i = 0;
return objects[i++];
}
public Object getNext() {
return objects[i++];
}
public boolean remove(Object object) {
for (int i=0; i<size; i++)
if (objects[i]==object) {
System.arraycopy(objects, i+1, objects, i, size-i-1);
objects[--size] = null;
return true;
}
return false;
}
public int size() {
return size;
}

30

2.3

2.4

Chapter 2 Abstract Data Types

}
public class TestArraySet {
public static void main(String[] args) {
Set set = new ArraySet();
System.out.println("set.add(\"CA\"):\t" + set.add("CA"));
System.out.println("set.add(\"US\"):\t" + set.add("US"));
System.out.println("set.add(\"MX\"):\t" + set.add("MX"));
System.out.println("set.add(\"CA\"):\t" + set.add("CA"));
System.out.println("set.add(\"US\"):\t" + set.add("US"));
System.out.println("set.size():\t" + set.size());
print(set);
System.out.println("set.contains(\"CA\"):\t"+set.contains("CA"));
System.out.println("set.remove(\"CA\"):\t" + set.remove("CA"));
System.out.println("set.size(): " + set.size());
print(set);
System.out.println("set.contains(\"CA\"):\t"+set.contains("CA"));
System.out.println("set.remove(\"CA\"):\t"+set.remove("CA"));
System.out.println("set.size(): " + set.size());
print(set);
System.out.println("set.contains(\"MX\"):\t"+set.contains("MX"));
System.out.println("set.contains(\"AR\"):\t"+set.contains("AR"));
}
public static void print(Set set) {
System.out.print(set.getFirst());
for (int i=1; i<set.size(); i++)
System.out.print(", " + set.getNext());
System.out.println();
}
}
public class TestArraySet {
public static void main(String[] args) {
Date bang = new IntsDate(1776, 07, 04);
System.out.println(bang.getMonth() + "/" + bang.getDay() +"/"
+ bang.getYear());
bang.setYear(2004);
System.out.println(bang.getMonth() + "/" + bang.getDay() +"/"
+ bang.getYear());
bang.setYear(-4);
System.out.println(bang.getMonth() + "/" + bang.getDay() +"/"
+ bang.getYear());
}
}

Solutions
2.5

2.6

31

public class IntsDate implements Date {

private int day, month, year;
public IntsDate(int year, int month, int day) {
setDay(day);
setMonth(month);
setYear(year);
}
public int getDay() {
return day;
}
public int getMonth() {
return month;
}
public int getYear() {
return year;
}
public void setDay(int day) {
if (day<1 || day>31) throw new IllegalArgumentException();
if ((month == 4 || month == 6 || month == 9 || month == 11)
&& (day > 30)) throw new IllegalArgumentException();
if (month == 2 && (day > 29 || !isLeap(year) && day > 28))
throw new IllegalArgumentException();
this.day = day;
}
public void setMonth(int month) {
if (month<1 || month>12) throw new IllegalArgumentException();
this.month = month;
}
public void setYear(int year) {
if (year<1700 || year>2100) throw new IllegalArgumentException();
this.year = year;
}
private boolean isLeap(int year) {
if (year%400 == 0) return true;
if (year%100 == 0) return false;
if (year%4 == 0) return true;
return false;
}
}
public class ComboLock {
private int n1, n2, n3;
private boolean open;

32

Chapter 2 Abstract Data Types

public final long id;
private static long nextId=1000;
{ id = nextId++; } // initialization block
public ComboLock(int n1, int n2, int n3) {
this.n1 = n1;
this.n2 = n2;
this.n3 = n3;
}
public boolean changeComb(int n1, int n2, int n3, int n4,
int n5, int n6) {
if (this.n1 != n1 || this.n2 != n2 || this.n3 != n3) return false;
this.n1 = n4;
this.n2 = n5;
this.n3 = n6;
open = false;
return true;
}
public void close() {
open = false;
}
public boolean isOpen() {
return open;
}
public boolean open(int n1, int n2, int n3) {
if (this.n1 == n1 && this.n2 == n2 && this.n3 == n3) open = true;
else open = false;
return open;
}
}
public class TestComboLock {
public static void main(String[] args) {
ComboLock lock0 = new ComboLock(10, 20, 30);
System.out.println("lock0.id): " + lock0.id);
ComboLock lock1 = new ComboLock(11, 21, 31);
System.out.println("lock1.id): " + lock1.id);
ComboLock lock2 = new ComboLock(12, 22, 32);
System.out.println("lock2.id): " + lock2.id);
System.out.println("lock0.open(11,21,31): "+lock0.open(11,21,31));
System.out.println("lock1.open(11,21,31): "+lock1.open(11,21,31));
System.out.println("lock2.open(11,21,31): "+lock2.open(11,21,31));
}
}

Chapter 3
Arrays
Exercises
3.1

3.2

Algorithm Minimum Element

Input: a sequence {a0 , a1 , a2 , ..., an1 } of comparable elements.
Output: an index value m.
Postconditions: am ai , for all i.
1. Let m = 0.
2. Repeat Step 3 for i = 1 to n 1.
3.
If a i < a m , set m = i.
4. Return m.
After step 1, m = 0.
After the first iteration of the loop in steps 2-3, m is either 0 or 1; if a1 > a0 , then m
got reset to 1; otherwise, a1 a0 and m is still 0. In either case, am a0 and am a1 ; i.e.,
am = max{a0 , a1 }.
After the second iteration of the loop in steps 2-3, m is either 0, 1, or 2. If a2 > am ,
then m got reset to 2; otherwise, a2 am and m is still 0 or 1. In the first case, a2 > am and
am a0 and am a1 , so a2 a0 and a2 a1 , so a2 = max{a0 , a1 , a2}; thus setting m = 2
makes am = max{a0 , a1 , a2 }. In the second case, a2 am and am a0 and am a1 , so
am = max{a0 , a1 , a2 } without resetting m. Thus, in either case, am = max{a0 , a1 , a2 }.
Before iteration i begins, am = max{a0 , a1 , ..., ai1 }. On that ith iteration, either
ai > am or ai am . In the first case, ai > max{a0 , a1 , ..., ai1 }, so ai = max{a0 , a1 , ..., ai };
thus, after m is set to i, am = max{a0 , a1 , ..., ai }. In the second case, am ai , so
am = max{a0 , a1 , ..., ai } without resetting m. Thus, in either case, after the iteration has
finished step 3, am = max{a0 , a1 , ..., ai }. This is the loop invariant.
The argument in the previous paragraph applies to every index i, all the way up to
i = n 1. Therefore, after that last iteration, am = max{a0 , a1 , ..., an1 }. Thus, the correct
value of m is returned at step 4.

33

34
3.3

3.4

3.5

3.6

3.7

Chapter 3 Arrays
Algorithm Sequential Search
Input: a sequence {a0 , a1 , a2 , ..., an1 } and a target value x.
Output: an index value i.
Postconditions: Either ai = x, or i = n and each aj x.
If ai = x, then aj x for all j > i.
1. For each i from n1 down to 0, do step 2:
2.
If ai = x, return i.
3. Return n.
If the algorithm returns i at step 2, then ai = x, as required by the first alternative of the
postcondition.
If the algorithm returns n at step 3, then the condition ai = x at step 2 was never true
for any of the values of i in the range 0 to n1. That is the second alternative of the postcondition.
Algorithm Maximum Element
Input: a sequence {a0 , a1 , a2 , ..., an1 } of comparable elements.
Output: an element am .
Postconditions: am ai , for all i.
1. Repeat Step 2 for i = n 1 down to 1:
2.
If ai > ai1 , swap ai with ai1 .
3. Return a0 .
On the first iteration of the loop in steps 1-2, i = n 1. If an1 an2, then no swap occurs
in step 2, and an2 = max{an2 , an1 }. But if an1 > an2 , then the swap occurs, thereby
making an2 the larger. Thus, in either case, after the first iteration has finished, an2 =
max{an2 , an1 }.
On the second iteration, i = n 2. If an2 an3 , then no swap occurs, and therefore
an3 an2 = max{an2 , an1 }. But if an1 > an2 , then the swap occurs, thereby making
an3 the larger of those two, and thus again an3 an2 = max{an2 , an1 }. Therefore, in
either case, after the second iteration, an3 = max{an3 , an2 , an1 }.
Similarly, on the jth iteration, anj1 = max{anj1 , ..., an2 , an1 }. This is a loop
invariant for the algorithm. Note that j = n i, so i = n j and the loop invariant can be
expressed as ai1 = max{ai1 , ..., an2 , an1 }. Since this is true for each i from n 1 down
to 1, it is true when i = 1; i.e., a0 = max{a0 , ..., an2, an1 }. Thus the correct value is
returned at step 3.
The assignment b = a merely makes b an alias for the array named a; i.e., there is still
only one array.
In order to return a separate array, we must allocate new storage for that array
int[] b = new int[a.length];

and then copy all elements from a into b

System.arraycopy(a, 0, b, 0, a.length);

Solutions
3.8

35

The method statements have this effect:

int temp = i;
i = j;
j = temp;

// assignes the value of i to temp

// assigns the value of j to i
// assigns the value of temp to j

This has no effect upon the array a[] (or even on the variables passed to i and j).
Here is a correct version:
public static void swap(double[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

3.9

This doesnt work because everythin gets swapped twice, thereby putting it back where it
started. The only change required is to run the for loop only half-way through the array:
for (int i = 0; i < n/2; i++)
swap(a, i, n-1-i);

3.10

3.11

3.12
3.13

The first two output statements merely show that x and y are arrays and that they are
stored at different locations in memory. Consequently, the boolean value eqeq is false
because the == operator tests for identity. But the java.util.Arrays.equals() method
tests for equality of content, so its value is true.
The assignment y = x changes y to an alias for the x array. So then x and y are identically equal, and thus the last output is true.
The Binary Search algorithm requires the array to be in ascending order. So, if the target is
found, all other elements that contain it must be adjacent to the element where it is found.
So to find the smallest index among those elements that contain the same value, we can
simply decrement the index until its element is no longer equal to the target:
Algorithm Modified Binary Search
Input: a sequence {a0 , a1 , a2 , ..., an1 } and a target value x.
Output: an index value i.
Precondition: The sequence is sorted: a0 a1 a2 an1 .
Postcondition: Either ai = x;
or i = p 1, where aj < x for all j < p, and aj > x for all j p.
1. Let p = 0 and q = n 1.
2. Repeat steps 3-5 while p q:
3.
Let i = (p + q)/2.
4.
If ai = x, then decrement i until i < 0 or ai x, and then return i + 1.
5.
If ai < x, let p = i + 1; otherwise let q = i 1.
6. Return p 1.
To change the Binary Search to the Interpolation Search, replace step 3 with:
3. Let i = p + r (q p), where r = (x ap )/(aq ap ).
f (g) f(n)/g(n) is bounded and g(n)/f(n) is bounded f (g) and g (f).

36
3.14
3.15
3.16

3.17
3.18

Chapter 3 Arrays
f o(g) f(n)/g(n) 0 f(n)/g(n) is bounded and g(n)/f(n) is not bounded
f (g) and f (g) f (g) (g).
f (g) g(n)/f(n) 0 g(n)/f(n) is bounded and f(n)/g(n) is not bounded
f (g) and f (g) f o(g) (g).
The functions f(n), g(n), f(n)/g(n), and g(n)/f(n) have the values shon in this table:
n

f(n)

g(n)

f(n)/g(n)

g(n)/f(n)

1/2

1/4

64

1/8

64

64

64

1024

1/16

16

When n is even, both ratios equal 1; thus, f(n)/g(n) does not approach 0, and so f o(g).
When n is odd, g(n)/f(n) grows exponentially; thus, g(n)/f(n) is not bounded, so f (g).
But f(n)/g(n) never exceeds 1; thus f(n)/g(n) is bounded, and so f O(g).
Thus, f O(g) (g) o(g).
f O(g) f(n)/g(n) is bounded g (f).
f o(g) f(n)/g(n) 0 g (f).

Programming Problems
3.1

public class Main {

private java.util.Random random = new java.util.Random();
public Main(int n) {
double[] a = randomDoubles(n);
double[] aa = (double[])a.clone();
print(a);
print(aa);
a[0] = a[1] = a[2] = 0.888;
print(a);
print(aa);
}

Solutions

37
private double[] randomDoubles(int n) {
double[] a = new double[n];
for (int i=0; i<n; i++)
a[i] = random.nextDouble();
return a;
}
private void print(double[] a) {
printf(a[0], "{#.###");
for (int i=1; i<a.length; i++)
printf(a[i], "','#.###");
System.out.println("}");
}
private void printf(double x, String fs) {
System.out.print(new java.text.DecimalFormat(fs).format(x));
}
public static void main(String[] args) {
new Main(Integer.parseInt(args[0]));
}

3.2

public class Main {

boolean[] z = new boolean[8];
char[] c = new char[8];
byte[] b = new byte[8];
short[] s = new short[8];
long[] j = new long[8];
float[] f = new float[8];
double[] d = new double[8];
Object[] x = new Object[8];
public Main() {
int[] a = { 33,44,55,66};
try {a[8]=0;} catch(Exception e){}
System.out.println("z:\t" + z);
System.out.println("c:\t" + c);
System.out.println("b:\t" + b);
System.out.println("s:\t" + s);
System.out.println("j:\t" + j);
System.out.println("f:\t" + f);
System.out.println("d:\t" + d);

38

Chapter 3 Arrays
System.out.println("x:\t" + x);
}
public static void main(String[] args) {
new Main();
}
}

3.3

private String letters(int n) {

// Returns: an object s of type String;
// Postconditions: s.length() == n;
//
each character of s is a calital letter;
StringBuffer buf = new StringBuffer(n);
for (int i=0; i<n; i++) {
int j = random.nextInt(26);
char ch = (char)('A'+j);
buf.append(ch);
}
return buf.toString();
}

3.4

private int[] permutation(int n) {

// Returns: an array a[] of type int[];
// Postconditions: a.length == n;
//
0 <= a[i] < n, for all i;
//
all n elements of a[] are different;
int[] a = new int[n];
for (int i=0; i<n; i++)
a[i] = i;
for (int i=0; i<n; i++)
swap(a,i,random.nextInt(n));
return a;
}

3.5

int search(int[] a, int target) {

for (int i = a.length - 1; i >= 0; i--)
if (a[i]==target) return i;
return -a.length;
}

3.6

public class TestArrays {

public static void main(String[] args) {
int[] a = {22, 33, 44, 55, 66, 77, 88, 99};
IntArrays.print(a);
System.out.println("IntArrays.isSorted(a): "

Solutions

39
+ IntArrays.isSorted(a));
a = IntArrays.randomInts(8, 100);
IntArrays.print(a);
System.out.println("IntArrays.isSorted(a): "
+ IntArrays.isSorted(a));
a = IntArrays.resize(a, 12);
IntArrays.print(a);
IntArrays.swap(a, 2, 6);
IntArrays.print(a);
}

3.7

public static int[] truncate(int[] a, int n) {

// returns a new array with the first n elements of a[];
if (n > a.length) throw new IllegalArgumentException();
int[] aa = new int[n];
System.arraycopy(a, 0, aa, 0, n);
return aa;
}

3.8

public static int[] reverse(int[] a) {

// returns a new array with the elements of a[] in reverse order;
int[] aa = new int[n];
int n = a.length;
int[] aa = new int[n];
for (int i=0; i<n; i++)
aa[i] = a[n-i-1];
return aa;
}

3.9

public static int[] uniqueRandomInts(int n, int range) {

// returns a new array of length n with unique nonnegative random
// integers that are less than the specified range;
if (n > range) throw new IllegalArgumentException();
int[] a = new int[n];
for (int i=0; i<n; i++) { // insert a unique integer:
next:
for (;;) { // repeat until another unique one is found
int x = random.nextInt(range);
for (int j=0; j<i; j++) {
if (a[j] == x)
// a[i] is not unique
continue next; // try again
}
a[i] = x; // insert it

40

Chapter 3 Arrays
break;

// a[i] is unique among {a[0]..a[i-1]}

}
}
return a;
}

3.10

public static int[] permutation(int n) {

// returns a new array of length n whose elements are the n
// nonnegative integers that are less than n, in random order;
int[] a = new int[n];
for (int i=0; i<n; i++)
a[i] = i;
for (int i=0; i<n; i++)
swap(a, i, random.nextInt(n));
return a;
}

3.11

/**
* Determines whether the specified array is in descending order.
*
* @param a the array.
* @return true if a[] is in descending order, otherwise false.
*/
public static boolean isDescending(int[] a) {
for (int i=1; i<a.length; i++)
if (a[i] > a[i-1]) return false;
return true;
}
/**
* Determines whether the specified array is sorted, either
* in ascending order or in descending order.
*
* @param a the array.
* @return true if a[] is sorted, otherwise false.
*/
public static boolean isSorted(int[] a) {
return isAscending(a) || isDescending(a);
}

3.12

public class TestBinarySearch {

public static void main(String[] args) {
int[] a = {22, 33, 44, 55, 66, 77, 88, 99};
int k = search(a, 50);

Solutions

41
System.out.println("search(a," + 50 + "): " + k);
int i = -k-1;
System.out.println("i: " + i);
System.out.println("a[" + (i-1) + "]: " + a[i-1]);
System.out.println("a[" + i + "]: " + a[i]);
}
static int search(int[] a, int x) {
int p = 0, q = a.length-1;
while (p <= q) {
// search the segment a[p..q]
int i = (p+q)/2;
// index of element in the middle
if (a[i] == x) return i;
if (a[i] < x) p = i+1;
// search upper half
else q = i-1;
// search lower half
}
return -p-1;
// not found
}

}
/* Output:
search(a,50): -4
i: 3
a[2]: 44
a[3]: 55
*/
}

3.13

void bubble(int[] a) {
for (int i=1; i<a.length; i++)
if (a[i] < a[i-1]) IntArrays.swap(a, i-1, i);
}

3.14

void select(int[] a) {
int m=0;
for (int i=1; i<a.length; i++)
if (a[i] > a[m]) m = i;
IntArrays.swap(a, m, a.length-1);
}

3.15

void insert(int[] a) {
int i = a.length - 1;
int ai = a[i], j = i;
for (j=i; j>0 && a[j-1]>ai; j--)
a[j] =a[j-1];

42

Chapter 3 Arrays
a[j] = ai;
}

3.16

void merge(int[] a) {
int n=a.length, m=n/2;
int i=0, j=m, k=0;
int[] aa = new int[n];
while (i < m && j < n)
if (a[i] < a[j]) aa[k++] = a[i++];
else aa[k++] = a[j++];
if (i < m) System.arraycopy(a, i, a, k, m-i);
System.arraycopy(aa, 0, a, 0, k);
}

3.17

int frequency(int[] a, int value) {

int f = 0;
for (int i=0; i<a.length; i++)
if (a[i] == value) ++f;
return f;
}

3.18

int numRuns(int[] a, int length) {

int num = 0;
int value = a[0], lengthThisRun = 1;
for (int i=1; i<a.length; i++) {
if (a[i] == value) ++lengthThisRun;
else {
value = a[i];
if (lengthThisRun == length) ++num;
lengthThisRun = 1;
}
}
return num;
}

3.19

int partition(int[] a) {
int a0 = a[0], i = 0, j = a.length;
while (i < j) {
while (i < j && a[--j] >= a0)
;
if (i < j) a[i] = a[j];
while (i < j && a[++i] <= a0)
;
if (i < j) a[j] = a[i];
}

Solutions

43
a[j] = a0;
return j;

3.20

public class Main {

public static void main(String[] args) {
int len = 1, count = 0;
while (count<args.length) {
for (int j=0; j<args.length; j++) {
if (args[j].length() == len) {
System.out.println(args[j]);
++count;
}
}
++len;
}
}
}

3.21

public void copyInto(Object[] a) {

// Replaces the first n elements of a[] with the n elements of
// this vector, where n is the size of this vector.
if (size > a.length) throw new IllegalArgumentException();
for (int i=0; i<size; i++)
a[i] = objects[i];
}

3.22

public void trimToSize() {

// Resizes the backing array this vector, making its length
// equal to the size of this vector.
Object[] temp = new Object[size];
System.arraycopy(objects, 0, temp, 0, size);
objects = temp;
}

3.23

public void ensureCapacity(int n) {

// Resizes the backing array this vector, making its length
// equal to n.
Object[] temp = new Object[n];
System.arraycopy(objects, 0, temp, 0, size);
objects = temp;
}

3.24

public int indexOf(Object x) {

// Returns the smallest index of any component of this vector
// that equals(x). If not found, -1 is returned.

44

Chapter 3 Arrays
for (int i=0; i<size; i++)
if (objects[i].equals(x)) return i;
return -1;
}

3.25

public boolean contains(Object x) {

// Returns true if and only if some component of this vector
// equals(x).
for (int i=0; i<size; i++)
if (objects[i] == x) return true;
return false;
}

3.26

a. public Object elementAt(int i) {

// Returns the element at index i in this vector.
return objects[i];
}

b. public Object firstElement() {

// Returns the first element in this vector.
return objects[0];
}

c. public Object lastElement() {

// Returns the last element in this vector.
return objects[size-1];
}

d. public void setElementAt(Object x, int i) {

// Replaces the element at index i with x.
objects[i] = x;
}

3.27

a. public Object get(int i) {

// Returns the element at index i in this vector.
return objects[i];
}

b. public void set(int i, Object x) {

// Replaces the element at index i with x.
objects[i] = x;
}

c. public boolean add(Object x) {

// Appends x to the end of this vector and returns true.
if (size == objects.length) resize();
objects[size++] = x;
return true;

Solutions

45
}

3.28

public boolean remove(Object x) {

// Deletes the first occurrence of x from this vector, shifting all
// the elements that follow it back one position. Returns true if
// x is found and removed; otherwise returns false.
int i = indexOf(x);
if (i < 0) return false;
--size;
System.arraycopy(objects, i+1, objects, i, size-i);
objects[size] = null;
return true;
}

3.29

public void add(int i, Object x) {

// Inserts x at index i, shifting all the elements from that
// position to the end forward one position.
if (i<0 || i>size) throw new IndexOutOfBoundsException();
System.arraycopy(objects, i, objects, i+1, size-i);
objects[i] = x;
++size;
}

3.30

public Object remove(int i) {

// Removes the element at index i, shifting all the elements
// that follow it back one position. Returns the removed object.
if (i<0 || i>=size) throw new IndexOutOfBoundsException();
Object x = objects[i];
--size;
System.arraycopy(objects, i+1, objects, i, size-i);
objects[size] = null;
return x;
}

3.31

public boolean isHomogeneous(Object[] a) {

// Returns true iff every non-null element has the same type.
int n=a.length;
if (n<2) return true;
if (a[0] == null) {
for (int i=1; i<n; i++) {
if (a[i] != null)
return false;
}
} else {
Class c = a[0].getClass();

46

Chapter 3 Arrays
for (int i=1; i<n; i++) {
if (a[i] == null || !a[i].getClass().equals(c))
return false;
}
}
return true;
}

3.32

public void print(int[][] a) {

// Prints the two-dimensional array a[][], one row per line.
int rows=a.length, cols=a[0].length;
for (int i=0; i<rows; i++) {
for (int j=0; j<cols; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}
}

3.33

public class PascalsTriangle {

public static void main(String[] args) {
int rows = Integer.parseInt(args[0]);
int[][] a = init(rows);
print(a);
}
static int[][] init(int m) {
int[][] a = new int[m][];
for (int i = 0; i < m; i++)
a[i] = new int[i+1];
for (int i = 0; i < m; i++)
for (int j = 0; j <= i; j++)
if (j == 0 || j == i) a[i][j] = 1;
else a[i][j] = a[i-1][j-1] + a[i-1][j];
return a;
}
static void print(int[][] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j <= i; j++)
print(a[i][j],5);
System.out.println();
}

Solutions

47
}
static void print(int n, int w) {
// prints n right-justified in a field on width w:
String s = "" + n, blanks = "
";
int len = s.length();
System.out.print(blanks.substring(0, w-len) + s);
}

3.34

public class PascalsTriangle {

public static void main(String[] args) {
int rows = Integer.parseInt(args[0]);
int[][] a = init(rows);
print(a);
}
static int fact(int n) {
if (n<2) return 1;
int f=n;
for (int i=2; i<n; i++)
f *= i;
return f;
}
static int[][] init(int n) {
int[][] a = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j <= i; j++)
if (j == 0 || j == i) a[i][j] = 1;
else a[i][j] = fact(i)/(fact(j)*fact(i-j));
return a;
}
static void print(int[][] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j <= i; j++)
print(a[i][j],5);
System.out.println();
}
}

48

Chapter 3 Arrays
static void print(int n, int w) {
// prints n right-justified in a field on width w:
String s = "" + n, blanks = "
";
int len = s.length();
System.out.print(blanks.substring(0, w-len) + s);
}
}

3.35

public class MultiplicationTable {

public static void main(String[] args) {
int rows = Integer.parseInt(args[0]);
int[][] a = init(rows);
print(a);
}
static int[][] init(int n) {
int[][] a = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
a[i][j] = (i+1)*(j+1);
return a;
}
static void print(int[][] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length; j++)
print(a[i][j],5);
System.out.println();
}
}
static void print(int n, int w) {
// prints n right-justified in a field on width w:
String s = "" + n, blanks = "
";
int len = s.length();
System.out.print(blanks.substring(0, w-len) + s);
}
}

3.36

public class Main {

public Main(String file) {
int words = 0, chars = 0;

Solutions

49
try {
BufferedReader in = new BufferedReader(new FileReader(file));
String line = in.readLine();
while(line!=null) {
StringTokenizer parser
= new StringTokenizer(line," ,:;-.?!");
while (parser.hasMoreTokens()) {
++words;
String word = parser.nextToken().toUpperCase();
chars += word.length();
}
line = in.readLine();
}
in.close();
} catch(IOException e) { System.out.println(e); }
System.out.println("words: " + words);
System.out.println("characters: " + chars);
}
public static void main(String[] args) {
new Main(args[0]);
}

Chapter 4
Linked Structures
Exercises
4.1

44

22

55

33

66

50

40

free

4.2
a

44

22

55

33

66

50

free

50

Solutions
4.3

The Fibonacci number F1000 has 209 digits.

Programming Problems
4.1

4.2

4.3

4.4

void delete(int[] a, int n, int x) {

// preconditions: [0] <= ... <= a[n-1], and n <= a.length;
// postconditions: a[0] <= ... <= a[n-2], and x is deleted;
int i = 0; // find the first index i for which a[i] > x:
while (i < n && a[i] <= x)
++i;
// shift {a[i],...,a[n-1]} into {a[i-1],...,a[n-2]}:
if (i<n-1) System.arraycopy(a, i, a, i-1, n-i);
a[n-1] = 0;
}
int size(Node list) {
// returns: the number of nodes in the specified list;
int count = 0;
while (list != null) {
++count;
list = list.next;
}
return count;
}
int sum(Node list) {
// returns: the sum of the integers in the specified list;
int sum = 0;
while (list != null) {
sum += list.data;
list = list.next;
}
return sum;
}
void deleteLast(Node list) {
// precondition: the specified list has at least two nodes;
// postcondition: the last node in the list has been deleted;
if (list == null || list.next == null)
throw new IllegalStateException();
while (list.next.next != null) {
list = list.next;
}
list.next = null;
}

51

52
4.5

4.6

4.7

4.8

Chapter 4 Linked Structures

Node copy(Node list) {
// returns: the sum of the integers in the specified list;
if (list == null) return null;
Node clone = new Node(list.data);
for (Node p=list, q=clone; p.next != null; p=p.next, q=q.next)
q.next = new Node(p.next.data);
return clone;
}
Node sublist(Node list, int m, int n) {
// returns: a new list that contains copies of the q-p nodes of the
//
specified list, starting with node number p (starting with 0);
if (m < 0 || n < m) throw new IllegalArgumentException();
if (n == m) return null;
for (int i=0; i<m; i++)
list = list.next;
Node clone = new Node(list.data);
Node p=list, q=clone;
for (int i=m+1; i<n; i++) {
if (p.next == null) throw new IllegalArgumentException();
q.next = new Node(p.next.data);
p = p.next;
q = q.next;
}
return clone;
}
void append(Node list1, Node list2)
// precondition: list1 has at least one node;
// postcondition: list1 has list2 appended to it;
if (list1 == null)
throw new IllegalArgumentException("list1 == null");
while (list.next != null) {
list1 = list1.next;
}
list1.next = list2;
}
Node concat(Node list1, Node list2) {
// returns: a new list that contains a copy of list1, followed by
//
a copy of list2;
Node list3 = new Node(0), p=list1, q=list3;
while (p != null) {
q.next = new Node(p.data);
p = p.next;

Solutions

53
q = q.next;
}
p=list2;
while (p != null) {
q.next = new Node(p.data);
p = p.next;
q = q.next;
}
return list3.next; // discard dummy head node

4.9

4.10

4.11

}
void replace(Node list, int i, int x)
// replaces the value of element number i with x;
String msg = "The list must have at least " + i + " elements.";
if (list == null) throw new IllegalArgumentException(msg);
for (int j = 0; j < i; j++) {
if (list.next == null)
throw new IllegalArgumentException(msg);
list = list.next;
}
list.data = x;
}
void swap(Node list, int i, int j) {
// swaps the ith element with the jth element;
if (i < 0 || j < 0) throw new IllegalArgumentException();
if (i == j) return;
Node p=list, q=list;
for (int ii=0; ii<i; ii++) {
if (p == null) throw new IllegalStateException();
p = p.next;
}
for (int jj=0; jj<j; jj++) {
if (q == null) throw new IllegalStateException();
q = q.next;
}
int pdata=p.data, qdata=q.data;
p.data = qdata;
q.data = pdata;
return;
}
Node merged(Node list1, Node list2)
// precondition: list1 and list2 are both in ascending order;
// returns: a new list that contains all the elements of list1 and

54

Chapter 4 Linked Structures

//
list2 in ascending order;
Node list = new Node(0), p=list, p1=list1, p2=list2;
while (p1 != null && p2 != null) {
if (p1.data < p2.data) {
p = p.next = new Node(p1.data);
p1 = p1.next;
} else {
p = p.next = new Node(p2.data);
p2 = p2.next;
}
}
while (p1 != null) {
p = p.next = new Node(p1.data);
p1 = p1.next;
}
while (p2 != null) {
p = p.next = new Node(p2.data);
p2 = p2.next;
}
return list.next;

4.12

}
private void shuffle(Node list) {
// performs a perfect shuffle on the specified list;
Node p=list, q=list;
while (p != null) {
p = p.next;
if (p != null) p = p.next;
q = q.next;
}
// now q = middle node:
Node m = q;
p = list;
Node t=p.next, tt=m.next;
while (m.next != null) {
tt = m.next;
p.next = m;
p = m.next = t;
t = p.next;
m = tt;
}
p.next = m;
}

Chapter 5
Stacks
Exercises
5.1

5.2
5.3

a.
b.
c.
a.
b.
c.

x
x
*
x
x
x

Monday

Tuesday
Monday

Wednesday
Tuesday
Monday

Tuesday
Monday

Monday

Thursday
Monday

Friday
Thursday
Monday

Thursday
Monday

Saturday
Thursday
Monday

Sunday
Saturday
Thursday
Monday

Saturday
Thursday
Monday

Thursday
Monday

4 + y 8 z + /
6 y / 5 z * /
/ x / 2 y 7 z
+ 4 / y 3 + z; i.e., (x + 4)/(y 3) + z
9 + y * 6 z; i.e., x (9 + y)*(6 z)
/ 3 / y / 2 / z; i.e., x/(3/(y/(2/z)))

55

56

Chapter 5 Stacks

Programming Problems
5.1

public class IntArrayStack {

private int[] a;
private int size;
public IntArrayStack(int capacity) {
a = new int[capacity];
}
public boolean isEmpty() {
return (size == 0);
}
public int peek() {
if (size == 0) throw new IllegalStateException("stack is empty");
return a[size-1];
}
public int pop() {
if (size == 0) throw new IllegalStateException("stack is empty");
int n = a[--size];
return n;
}
public void push(int n) {
if (size == a.length) resize();
a[size++] = n;
}
public int size() {
return size;
}
private void resize() {
int[] aa = a;
a = new int[2*aa.length];
System.arraycopy(aa, 0, a, 0, size);
}
}

Solutions
5.2

57

import chap05.list01.Stack;
import java.util.ArrayList;
public class ArrayListStack implements Stack {
private ArrayList a;
public ArrayListStack(int capacity) {
a = new ArrayList(capacity);
}
public boolean isEmpty() {
return (a.isEmpty());
}
public Object peek() {
int n = a.size();
if (n == 0) throw new IllegalStateException("stack is empty");
return a.get(n-1);
}
public Object pop() {
int n = a.size();
if (n == 0) throw new IllegalStateException("stack is empty");
return a.remove(n-1);
}
public void push(Object object) {
a.add(object);
}
public int size() {
return a.size();
}

5.3

}
public String toString() {
if (size == 0) return "()";
int i = size;
StringBuffer buf = new StringBuffer("(" + a[--i]);
while (i > 0)
buf.append("," + a[--i]);
return buf + ")";
}

58
5.4

5.5

5.6

5.7

5.8

Chapter 5 Stacks
public String toString() {
if (size == 0) return "()";
StringBuffer buf = new StringBuffer("(" + top.object);
for (Node p=top.next; p!=null; p = p.next)
buf.append("," + p.object);
return buf + ")";
}
public boolean equals(Object obj) {
if (obj == this) return true;
if (!(obj instanceof ArrayStack)) return false;
ArrayStack that = (ArrayStack)obj;
if (that.size != this.size) return false;
for (int i=0; i<size; i++)
if (!that.a[i].equals(this.a[i])) return false;
return true;
}
public boolean equals(Object obj) {
if (obj == this) return true;
if (!(obj instanceof LinkedStack)) return false;
LinkedStack that = (LinkedStack)obj;
if (that.size != this.size) return false;
Node p=this.top, q = that.top;
while (p != null && q != null) {
if (!p.object.equals(q.object)) return false;
p = p.next;
q = q.next;
}
return true;
}
public Object[] toArray() {
Object[] a = new Object[size];
int i = 0;
for (Node p=top; p!=null; p = p.next)
a[i++] = p.object;
return a;
}
public ArrayStack toArrayStack() {
ArrayStack temp = new ArrayStack(2*size);
for (Node p=top; p!=null; p = p.next)
temp.push(p.object);
ArrayStack s = new ArrayStack(2*size);
for (Node p=top; p!=null; p = p.next)

Solutions

59
s.push(temp.pop());
return s;

5.9

5.10

5.11

5.12

5.13

5.14

}
public LinkedStack toLinkedStack() {
LinkedStack s = new LinkedStack();
for (int i=0; i<size; i++)
s.push(a[i]);
return s;
}
public Object peekSecond() {
if (size < 2) throw new java.util.NoSuchElementException();
return top.next.object;
}
public Object popSecond() {
if (size < 2) throw new java.util.NoSuchElementException();
--size;
Object second = a[size-1];
a[size-1] = a[size];
a[size] = null;
return second;
}
public Object bottom() {
if (size == 0) throw new java.util.NoSuchElementException();
Node p = top;
while (p.next != null)
p =p.next;
return p.object;
}
public Object popBottom() {
if (size == 2) throw new java.util.NoSuchElementException();
Object bottom = a[0];
System.arraycopy(a, 1, a, 0, --size);
a[size] = null;
return bottom;
}
public void reverse() {
if (size < 2) return;
LinkedStack stack1 = new LinkedStack();
LinkedStack stack2 = new LinkedStack();
while (this.size > 0)
stack1.push(this.pop());
while (stack1.size > 0)

60

Chapter 5 Stacks
stack2.push(stack1.pop());
while (stack2.size > 0)
this.push(stack2.pop());

5.15

5.16

5.17

5.18

}
Object removeSecondFromTop(Stack stack) {
int n = stack.size();
if (n<2) throw new IllegalArgumentException("stack is empty");
Object top1 = stack.pop();
Object top2 = stack.pop();
stack.push(top1);
return top2;
}
Object removeBottom(Stack stack) {
int n = stack.size();
if (n<1) throw new IllegalArgumentException("stack is empty");
if (n<2) return stack.pop();
Stack auxStack = new LinkedStack();
for (int i=0; i<n-1; i++)
auxStack.push(stack.pop());
Object bottom = stack.pop();
for (int i=0; i<n-1; i++)
stack.push(auxStack.pop());
return bottom;
}
void reverse(Stack stack) {
if (stack.size() < 2) return;
Stack stack1 = new LinkedStack();
Stack stack2 = new LinkedStack();
while (stack.size() > 0)
stack1.push(stack.pop());
while (stack1.size() > 0)
stack2.push(stack1.pop());
while (stack2.size() > 0)
stack.push(stack2.pop());
}
Stack reversed(Stack stack) {
Stack stack1 = new LinkedStack();
Stack stack2 = new LinkedStack();
while (stack.size() > 0) {
stack1.push(stack.peek());
stack2.push(stack.pop());
}

Solutions

61
while (stack2.size() > 0)
stack.push(stack2.pop());
return stack1;

5.19

5.20

5.21

}
public void push(Object object) {
if (contains(object)) return;
if (size == a.length) resize();
a[size++] = object;
}
private boolean contains(Object x) {
for (int i=0; i<size; i++)
if (a[i]==x) return true;
return false;
}
public void push(Object object) {
if (object == null)
throw new IllegalArgumentException("object is null");
if (size == a.length) resize();
a[size++] = object;
}
/**
* The <code>ArrayStack</code> class implements the
* <code>Stack</code> interface defined in the
* <code>chap05.list01</code> package. Its instances are
* last-in-first-out (LIFO) containers that store their
* elements in a backing array.
*/
public class ArrayStack implements Stack { ...
/**
* Creates an empty stack with a specified capacity.
*
* @param capacity the length of the backing array.
*/
public ArrayStack(int capacity) { ...
/**
* Reports whether this stack is empty.
*
* @return <code>true</code> if and only if this stack contains
*
no elements.
*/

62

Chapter 5 Stacks
public boolean isEmpty() { ...
/**
* Returns a reference to the top element on this stack, leaving
* the stack unchanged.
*
* @return
the top element on this stack.
* @exception IllegalStateException if this stack is empty.
*/
public Object peek() { ...
/**
* Removes the top element on this stack and returns it.
*
* @return
the top element on this stack.
* @exception IllegalStateException if this stack is empty.
*/
public Object pop() { ...
/**
* Inserts the specified object onto the top of this stack.
*
* @param object the element to be pushed onto this stack.
*/
public void push(Object object) { ...

5.22

/**
* Returns the number of elements in this stack.
*
* @return
the number of elements in this stack.
*/
public int size() { ...
/**
* The <code>LinkedStack</code> class implements the
* <code>Stack</code> interface defined in the
* <code>chap05.list01</code> package. Its instances are
* last-in-first-out (LIFO) containers that store their
* elements in a backing array.
*/
public class LinkedStack implements Stack { ...

Solutions

63
/**
* Reports whether this stack is empty.
*
* @return <code>true</code> if and only if this stack contains
*
no elements.
*/
public boolean isEmpty() { ...
/**
* Returns a reference to the top element on this stack, leaving
* the stack unchanged.
*
* @return
the top element on this stack.
* @exception IllegalStateException if this stack is empty.
*/
public Object peek() { ...
/**
* Removes the top element on this stack and returns it.
*
* @return
the top element on this stack.
* @exception IllegalStateException if this stack is empty.
*/
public Object pop() { ...
/**
* Inserts the specified object onto the top of this stack.
*
* @param object the element to be pushed onto this stack.
*/
public void push(Object object) { ...
/**
* Returns the number of elements in this stack.
*
* @return the number of elements in this stack.
*/
public int size() { ...

Chapter 6
Queues
Exercises
6.1

6.2

DE

DE PA

DE PA NJ

PA NJ

NJ

NJ GA

NJ GA CT

GA CT

GA CT MA

GA CT MA MD

DE MA MD
CT

MA MD

The expression new Node(object,head.prev,head) in permuted statement

head.prev.next = head.prev = new Node(object,head.prev,head);

creates the specified new node. The value of that expression is a reference to that new
node. The permuted statement first assigns that reference to head.prev . That changes the
value of head.prev . So when the second (chained) assignment is performed, the new
node reference gets assigned to the next field of that new node, since head.prev refers to
it. Thus, the new nodes next field ends up refering to itself.

64

Solutions
6.3

65

The total capital gains on these transactions are $3250:

Date

Bought

Feb 20

200@ $20

Apr 15
Jun 25

150@ $25

Aug 10

250@ $24

Sep 20

Nov 15

6.4

Sold

Gain

100@ $22

100@ $2 = $200

100@ $28

100@ $8 = $800

150@ $28

150@ $3 = $450

50@ $28

50@ $4 = $200

200@ $32

200@ $8 = $1600

With the following implementation, the worst case would be alternating calls to add()
and remove(). In that case, both operations run in linear time:
void add(Object x) {
while (!stack2.isEmpty())
stack1.push(stack2.pop());
stack1.push(x);
}
Object remove() {
while (!stack1.isEmpty())
stack2.push(stack1.pop());
return stack2.pop();
}
int size() {
return stack1.size() + syack2.size();
}

66

Chapter 6 Queues

Programming Problems
6.1

import chap06.list01.Queue;
public class ArrayQueue implements Queue {
private Object[] a;
private int front, back;
public ArrayQueue(int capacity) {
a = new Object[capacity];
}
public void add(Object object) {
if (back == a.length) resize();
a[back++] = object;
}
public Object first() {
if (size()==0) throw new IllegalStateException("queue is empty");
return a[front];
}
public boolean isEmpty() {
return (size() == 0);
}
public Object remove() {
if (size()==0) throw new IllegalStateException("queue is empty");
Object object=a[front];
a[front++] = null;
return object;
}
public int size() {
return back - front;
}
private void resize() {
Object[] aa = a;
a = new Object[2*aa.length];
System.arraycopy(aa, front, a, 0, size());
}
}

Solutions
6.2

67

/**
* The <code>ArrayQueue</code> class implements the
* <code>Queue</code> interface defined in the
* <code>chap06.list01</code> package. Its instances are
* first-in-first-out (FIFO) containers that store their
* elements in a backing array.
*/
public class ArrayQueue implements Queue { ...
/**
* Creates an empty queue with a specified capacity.
*
* @param capacity the length of the backing array.
*/
public ArrayQueue(int capacity) { ...
/**
* Adds the specified element to the back of this queue.
*
* @param object the element to be added to this queue.
*/
public void add(Object object) { ...
/**
* Returns the element at the front of this queue.
*
* @return the element at the front of this queue.
* @throws IllegalStateException if this queue is empty
*/
public Object first() { ...
/**
* Reports whether this queue is empty.
*
* @return <code>true</code> if and only if this queue contains
*
no elements.
*/
public boolean isEmpty() { ...

68

Chapter 6 Queues
/**
* Removes and returns the element at the front of this queue.
*
* @return the element at the front of this queue.
* @throws IllegalStateException if this queue is empty
*/
public Object remove() { ...
/**
* Returns the number of elements in this queue.
*
* @return the number of elements in this queue.
*/
public int size() { ...

6.3

6.4

/**
* The <code>LinkedQueue</code> class implements the
* <code>Queue</code> interface defined in the
* <code>chap06.list01</code> package. Its instances are
* first-infirst-out (FIFO) containers that store their
* elements in a linked list.
*/
public class LinkedQueue implements Queue { ...
The rest is the same as in Problem 6.2 above.
import chap06.list01.Queue;
import java.util.ArrayList;
public class ArrayListQueue implements Queue {
private ArrayList a;
public ArrayListQueue(int capacity) {
a = new ArrayList(capacity);
}
public void add(Object object) {
a.add(object);
}
public Object first() {
if (size()==0) throw new IllegalStateException("queue is empty");
return a.get(0);
}

Solutions

69
public boolean isEmpty() {
return a.isEmpty();
}
public Object remove() {
if (size()==0) throw new IllegalStateException("queue is empty");
return a.remove(0);
}
public int size() {
return a.size();
}

6.7

6.8

6.10

}
public String toString() {
if (size == 0) return "()";
StringBuffer buf = new StringBuffer("(" + head.object);
for (Node p=head.next; p!=null; p = p.next)
buf.append("," + p.object);
return buf + ")";
}
public boolean equals(Object obj) {
if (obj == this) return true;
if (!(obj instanceof LinkedQueue)) return false;
LinkedQueue that = (LinkedQueue)obj;
if (that.size != this.size) return false;
Node p=this.head, q = that.head;
while (p != null && q != null) {
if (!p.object.equals(q.object)) return false;
p = p.next;
q = q.next;
}
return true;
}
public Object[] toArray() {
Object[] a = new Object[size];
int i = 0;
for (Node p=head; p!=null; p = p.next)
a[i++] = p.object;
return a;
}

70
6.11

6.12

6.13

6.14

6.15

6.16

Chapter 6 Queues
public ArrayQueue toArrayQueue() {
ArrayQueue q = new ArrayQueue(2*size);
for (Node p=head; p!=null; p = p.next)
q.add(p.object);
return q;
}
public Object getSecond() {
if (size < 2) throw new java.util.NoSuchElementException();
return head.next.object;
}
public Object removeSecond() {
if (size < 2) throw new java.util.NoSuchElementException();
Object object=head.prev.object;
head.next.next = head.next.next.next;
head.next.next.prev = head;
--size;
return object;
}
public Object last() {
if (size == 0) throw new java.util.NoSuchElementException();
return head.prev.object;
}
public void reverse() {
Node p = head.next;
while (p != head) {
Node temp = p.next;
p.next = p.prev;
p = p.prev = temp;
}
head.next = p.prev;
}
Object removeSecond(Queue q) {
int n = q.size();
if (n<2) throw new IllegalArgumentException();
q.add(q.remove());
Object x = q.remove();
for (int i=2; i<n; i++)
q.add(q.remove());
return x;
}
}

Solutions
6.17

6.18

6.19

public static Object lastElement(Queue queue) {

Queue aux = new LinkedQueue();
while (queue.size() > 1)
aux.add(queue.remove());
Object last = queue.remove();
while (aux.size() > 0)
queue.add(aux.remove());
return last;
}
void reverse(Queue q) {
void reverse(Queue q) {
int n = q.size();
if (n<2) return;
Stack s = new ArrayStack(n);
for (int i=0; i<n; i++)
s.push(q.remove());
for (int i=0; i<n; i++)
q.add(s.pop());
}
public static Queue reversed(Queue queue) {
Stack auxStack = new LinkedStack();
Queue auxQueue = new LinkedQueue();
while (queue.size() > 0) {
Object object = queue.remove();
auxStack.push(object);
auxQueue.add(object);
}
while (auxQueue.size() > 0) {
queue.add(auxQueue.remove());
auxQueue.add(auxStack.pop());
}
return auxQueue;
}

71

Chapter 7
Collections
Exercises
7.1

7.2

7.3

7.4
7.5

7.6

[CH,
[NZ,
[NZ,
[NZ,
[CA,
[MX,
[CA,
[MX,
[CA,
[MX,
[CA,
AR
[CA,
[US,
[US,
[CA,
[CA,
[CA,
[CA,
[CA,
[CA,
[CA,

JP,
JP,
AU,
AU,
US,
AR,
US,
CO,
US,
CO,
US,

IN,
IN,
IN,
IN]
MX,
BR]
MX,
BR]
MX,
VE]
MX,

ID, AU, NZ]

ID, AU]
ID]

US,
MX,
BR]
US,
US,
US,
US,
MX,
AR,
AR,

MX, BR, CH]

BR, CH]

AR, BR, CH]

CO, BR, CH]
CO, VE, CH]
AR, BR, CH]

MX, AR, BR, CH]

MX, CO, BR, CH]
null, CO, BR, CH]
MX, AR, BR, CH]
AR, BR, CH]
BR, CH]
BR]

a. The list's size increases from 0 to 5; content are: 0, 10, 20, 30, 40 in ascending order.
b. "[0]0, [1]10, [2]20, [3]30, [4]40"
c. Three more items are inserted so that size increases from 5 to 8, and 80 precedes 0,
70 precedes 10, 60 precedes 20.
d. Three items are removed so that size increases from 8 to 5; line 16 removes 0, line
17 removes 20, and line 18 removes 40.

72

Solutions

73

e. initial size is 0
empty
**current size is 5
[0]0, [1]10, [2]20, [3]30, [4]40
****current size is 8
[0]-80, [1]0, [2]-70, [3]10, [4]-60, [5]20, [6]30, [7]40
removing 0
removing 20
removing 40
******current size is 5
[0]-80, [1]-70, [2]10, [3]-60, [4]30

7.7

a. Each time line 9 executes itr.nextIndex() returns a higher index. So the values 6.6
5.5 2.2 4.4 9.9 are inserted at indexes 0, 1, 2, 3, 4. Output from line 10 will be this:
current size is 5

b. Method printA() prints the values in order of their indexes. Method printB()
prints the values in reverse order of their indexes.
c. The ListIterator itr is moved from the end back to beginning of dList. All of
the values in the list are negated, changed to these: 6.6, 5.5, 2.2, 4.4, and 9.9.
d. Since itr is at the beginning of dList, the item at index 0 with value 6.6 is
removed, i.e. values are changed to these: 5.5, 2.2, 4.4, 9.9.
e. testing itr.add()
current size is 5
calling printB( dList )
[4]9.9
[3]-4.4
[2]-2.2
[1]5.5
[0]6.6
testing itr.set()
changing node at index 4
changing node at index 3
changing node at index 2
changing node at index 1
changing node at index 0
**current size is 5
calling printA( dList )
[0]-6.6
[1]-5.5
[2]2.2
[3]4.4
[4]-9.9
testing itr.remove()
current size is 4
calling printA( dList )
[0]-5.5
[1]2.2
[2]4.4
[3]-9.9

to
to
to
to
to

-9.9
4.4
2.2
-5.5
-6.6

74

Chapter 7 Collections

Programming Problems
7.1

7.2

7.3

public ArrayCollection() {
}
public ArrayCollection(int capacity) {
a = new Object[capacity];
}
public ArrayCollection(Object[] objects) {
a = new Object[objects.length];
for (int i=0; i<objects.length; i++)
if (objects[i] != null) a[size++] = objects[i];
}
public Object getLast() {
// returns a reference to the last element of this collection;
// or returns null if this collection is empty;
for (int i=a.length-1; i>=0; i--)
if (a[i] != null) return a[i];
return null;
}
public Object getLast(Collection collection) {
// returns a reference to the last element of the collection;
// or returns null if the given collection is empty;
Iterator it = collection.iterator();
Object object = null;
while (it.hasNext())
object = it.next();
return object;
}

7.4

public boolean removeLast() {

// removes the last element if this collection is not empty;
// returns true if and only if it changes this collection;
(int i=a.length-1; i>=0; i--)
for (int i=a.length-1; i>=0; i--)
if (a[i] != null) {
a[i] = null;
--size;
return true;
}
return false;
}

for

Solutions
7.5

75

public boolean removeLast(Collection collection) {

// removes the last element if the collection is not empty;
// returns true if and only it changes the given collection;
Iterator it = collection.iterator();
Object object = null;
if (!it.hasNext()) return false;
while (it.hasNext())
object = it.next();
it.remove();
return true;
}

7.6

public int frequency(Object object) {

// returns the number of occurrences of the given object
// in this collection;
int f=0;
for (Node p=head.next; p!=head; p = p.next)
if (p.object.equals(object)) ++f;
return f;

7.7

7.8

}
public int frequency(Collection collection, Object object) {
// returns the number of occurrences of the given object
// in the given collection;
Iterator it = collection.iterator();
int f=0;
while (it.hasNext())
if (it.next().equals(object)) ++f;
return f;
}
public boolean removeOdd() {
// removes every other element (the first, the third, etc.) from
// this collection; returns true iff this collection is changed;
if (size < 2) return false;
Node p=head.next;
while (p.next!=head) {
p = p.next = p.next.next;
--size;
}
return true;
}

76
7.9

7.10

Chapter 7 Collections
public boolean removeOdd(Collection collection) {
// removes every other element (the first, the third, etc.)
// from the given collection; returns true iff it is changed;
if (collection.size() < 2) return false;
Iterator it = collection.iterator();
while (it.hasNext()) {
it.next();
if (it.hasNext()) {
it.next();
it.remove();
}
}
return true;
}
public class LinkedCollection extends AbstractCollection {
private static class Node {
Object object;
Node prev, next;
Node() { prev = next = this; }
Node(Object o, Node p, Node n) { object=o; prev=p; next=n; }
}
private int size;
private Node head = new Node(); // dummy head node
private Node tail = new Node(); // dummy tail node
public LinkedCollection() {
head.next = head.prev = tail;
tail.next = tail.prev = head;
}
public boolean add(Object object) {
tail.prev = tail.prev.next = new Node(object, tail.prev, tail);
++size;
return true; // no object is rejected
}
public Iterator iterator() {
return new Iterator() {
// anonymous inner class
private Node cursor=head.next; // current element node
private boolean okToRemove=false;
public boolean hasNext() { return cursor != tail; }

Solutions

77
public Object next() {
if (cursor == head) throw new RuntimeException();
okToRemove = true;
Object object=cursor.object;
cursor = cursor.next;
return object;
}
public void remove() {
if (!okToRemove) throw new IllegalStateException();
cursor.prev = cursor.prev.prev;
cursor.prev.next = cursor;
--size;
okToRemove = false; // must call next() again before remove()
}
};
}
public int size() {
return size;
}

7.11

public boolean addAll(Collection collection) {

for (Iterator it=collection.iterator(); it.hasNext(); )
add(it.next());
return true;
}

7.12

public void clear() {

for (Iterator it=iterator(); it.hasNext(); )
it.remove();
}

7.13

public boolean containsAll(Collection collection) {

for (Iterator it=collection.iterator(); it.hasNext(); )
if(!contains(it.next())) return false;
return true;
}

7.14

public boolean retainAll(Collection collection) {

boolean changed=false;
for (Iterator it=iterator(); it.hasNext(); )
if(!collection.contains(it.next())) {
it.remove();
changed = false;

78

Chapter 7 Collections
}
return changed;
}

7.15

public Object[] toArray() {

int n=size();
Object[] objects = new Object[n];
Iterator it=iterator();
for (int i=0; i<n; i++)
objects[i] = it.next();
if (objects.length>n) objects[n] = null;
return objects;
}

Chapter 8
Lists
Exercises
8.1
8.2

8.3
8.4

One.
It depends upon the initial contents of the list. If it has fewer than six elements, then the
call set(6, "BE") will throw an IndexOutOfBoundsException. Otherwise, the end
result would be to insert "BE" at position 6 while shifting the existing elements that are in
positions 26 down to positions 15. The existing element at position 2 will be returned.
a. See Figure 8.1 on the next page.
b. See Figure 8.2 on the next page.
a. There are n + 1 terms. The average exponent for the n non-constant terms is n/2. So
the total number of operations averages n(n/2) = (n 2 ).
b. With Horners method, there are only n multiplications and n additions. So the total
number of operations is 2n = (n).

Programming Problems
8.1

8.2

int frequency(List list, Object object) {

// returns the number of occurrences of object in list
int f = 0;
for (Iterator it = list.iterator(); it.hasNext(); )
if (it.next().equals(object)) ++f;
return f;
}
public class TestSequence {
public TestSequence() {
String[] countries = {"CA","DE","FR","GB","IT","JP","RU","US"};
Sequence g8 = new Sequence(Arrays.asList(countries));

79

80

Chapter 8 Lists
print(g8);
g8.remove(6);
print(g8);
}
void print(Sequence s) {
for (Iterator it = s.iterator(); it.hasNext(); )
System.out.print(it.next() + " ");
System.out.println();
}
public static void main(String[] args) {
new TestSequence();
}
}

head
Polynomial

term
next
Node

head
Polynomial

term

coef

next

exp

Node

term
next
Node

term
next
Node

term
next
Node

Figure 8.1

0.0
-1

Term

Term

Term

Term

next

term
next
Node

coef 6.71
exp

term
Node

coef -9.4
exp

next
Node

coef 7.83
exp

term

term
next
Node

Figure 8.2

coef
exp

0.0
-1

Term

coef 1.83
exp

Term

coef
exp

6.0
4

Term

coef -9.4
exp

Term

coef 6.71
exp
Term

Solutions
8.3

8.4

public class TestTerm {

public TestTerm() {
Term t1 = new Term(7.0, 4);
System.out.println(t1);
System.out.println("t1.getCoef(): " + t1.getCoef());
System.out.println("t1.getExp(): " + t1.getExp());
Term t2 = new Term(t1);
System.out.println(t2);
System.out.println("t2.equals(t1): " + t2.equals(t1));
Term t3 = t1.times(-2.0);
System.out.println(t3);
System.out.println("t3.equals(t1): " + t3.equals(t1));
System.out.println(t3.abs());
System.out.println("t1.plus(t3): " + t1.plus(t3));
System.out.println("t3.plus(t1).plus(t1): "
+ t3.plus(t1).plus(t1));
System.out.println("t1.times(t3): " + t1.times(t3));
}
public static void main(String[] args) {
new TestTerm();
}
}
public class TestPolynomial {
public TestPolynomial() {
Polynomial p1 = new Polynomial(2.0, 3);
System.out.println(p1);
System.out.println("p1.degree(): " + p1.degree());
Polynomial p2 = new Polynomial(p1);
System.out.println("p2.equals(p1): " + p2.equals(p1));
p2 = p1.plus(p2);
System.out.println(p2);
System.out.println("p2.equals(p1): " + p2.equals(p1));
p1 = p1.plus(new Term(-9.0, 2));
System.out.println(p1);
System.out.println("p1.degree(): " + p1.degree());
p1 = p1.plus(new Term(5.0, 8));
System.out.println(p1);
System.out.println("p1.degree(): " + p1.degree());
p1 = p1.plus(p2);
System.out.println(p1);
System.out.println("p1.degree(): " + p1.degree());
Polynomial p3 = p1.times(-2.0);

81

82

Chapter 8 Lists
System.out.println("p3: " + p3);
System.out.println("p3.degree(): " + p3.degree());
p1 = p1.times(new Polynomial(-5.0, 3));
System.out.println(p1);
System.out.println("p1.degree(): " + p1.degree());
System.out.println("p1.valueAt(1.0): " + p1.valueAt(1.0));
System.out.println("p1.valueAt(-1.0): " + p1.valueAt(-1.0));
System.out.println("p1.valueAt(2.0): " + p1.valueAt(2.0));
p1 = p1.times(new Polynomial(5.0, -3));
}
public static void main(String[] args) {
new TestPolynomial();
}

8.5

8.6

8.7

}
public Polynomial(double[] c) {
Node p = head;
for (int i = c.length - 1; i >= 0; i--)
if (c[i] != 0.0) p = p.next = new Node(new Term(c[i], i), head);
}
public double[] toArray() {
int n = degree() + 1;
double[] a = new double[n];
for (int i=0; i<n; i++)
a[i] = 0.0;
for (Node p = head.next; p != head; p = p.next)
a[p.exp] = p.coef;
return a;
}
public Polynomial derivative() {
if (degree() < 1) return ZERO;
Polynomial poly = new Polynomial();
for (Node p = head.next; p != head; p = p.next) {
double coef = p.exp*p.coef;
if (coef != 0 && p.exp > 0)
poly = poly.plus(new Polynomial(coef, p.exp-1));
}
return poly;
}

Solutions
8.8

83
public class Polynomial {
private Node head = new Node(); // dummy node;
public static final Polynomial ZERO = new Polynomial();
private Polynomial() {
}
public Polynomial(double coef, int exp) {
head.next = new Node(coef, exp, head);
}
public Polynomial(Polynomial that) { // copy constructor
Node p = this.head, q = that.head.next;
while (q != that.head) {
p = p.next = new Node(q);
p.next = head;
q = q.next;
}
}
public int degree() {
return head.next.exp;
}
public boolean equals(Object object) {
if (!(object instanceof Polynomial)) return false;
Polynomial that = (Polynomial)object;
Node p = this.head.next, q = that.head.next;
while (q != that.head) {
if (p.coef != q.coef || p.exp != q.exp) return false;
p = p.next;
q = q.next;
}
return p == head;
}
public Polynomial plus(Polynomial that) {
if (this.equals(ZERO)) return new Polynomial(that);
if (that.equals(ZERO)) return new Polynomial(this);
Polynomial sum = new Polynomial(this);
Node p = sum.head, q = that.head.next;
while (p.next != sum.head && q != that.head) {

84

Chapter 8 Lists
if (p.next.exp <= q.exp) {
if (p.next.exp == q.exp) p.next.coef += q.coef;
else p.next = new Node(q.coef, q.exp, p.next);
q = q.next;
}
p = p.next;
}
if (q != that.head) p.next = new Node(q.coef, q.exp, p.next);
return sum;
}
public Polynomial times(double factor) {
if (this.equals(ZERO) || factor==0.0) return ZERO;
Polynomial result = new Polynomial(this);
for (Node p = result.head.next; p != result.head; p = p.next)
p.coef *= factor;
return result;
}
public Polynomial times(Polynomial that) {
if (this.equals(ZERO) || that.equals(ZERO)) return ZERO;
Polynomial result = ZERO;
for (Node p = this.head.next; p != this.head; p = p.next) {
Polynomial temp = new Polynomial(that);
for (Node q = temp.head.next; q != temp.head; q = q.next){
q.coef *= p.coef;
q.exp += p.exp;
}
result = result.plus(temp);
}
return result;
}
public double[] toArray() {
int n = degree() + 1;
double[] a = new double[n];
for (int i=0; i<n; i++)
a[i] = 0.0;
for (Node p = head.next; p != head; p = p.next)
a[p.exp] = p.coef;
return a;
}

Solutions

85

public String toString() {

if (this.equals(ZERO)) return "0";
Node p = head.next;
StringBuffer buf = new StringBuffer(p.coef + "x^" + p.exp);
for (p = p.next; p != head; p = p.next) {
buf.append( (p.coef<0 ? " - " : " + ") + Math.abs(p.coef));
if (p.exp > 0) buf.append("x");
if (p.exp > 1) buf.append("^" + p.exp);
}
return buf.toString();
}
public double valueAt(double x) {
if (this.equals(ZERO)) return 0.0;
double y = 0.0;
Node p = head.next;
int exp = p.exp;
while (p.next != head) {
double coef = p.coef;
int nextExp = p.next.exp;
y = (y + coef)*Math.pow(x, exp - nextExp);
exp = nextExp;
p = p.next;
}
return (y + p.coef)*Math.pow(x, exp);
}
private static class Node {
double coef;
int exp;
Node next;
Node() { this(0.0, -1, null); next = this; }
Node(Node that) { this(that.coef, that.exp, that.next); }
Node(double c, int e, Node n) { coef = c; exp = e; next = n; }
}
}

Chapter 9
Lists
Exercises
9.1

9.2
9.3

9.4

9.5

No.
Suppose Ann and Bob both hash to 5 in an empty hash table with open addressing.
If Ann is inserted first, it will be put in slot 5, and Bob will be put in slot 6. But if
Bob is inserted first, it will be put in slot 5, and Ann will be put in slot 6.
See the solution on page 515.
a. Let f(x) = lnx and g(x) = (x1/x)/2 for x 1. Then f(x) = 1/x and g(x) = (1+1/x2)/2.
Since 0 (1x)2 = 1 2x + x2, we have 2x 1 + x2, so 1/x (1+1/x2)/2. Thus, f(x)
g(x) for all x 1, and f(1) = 0 = g(1). Therefore f(x) g(x) for all x 1; i.e., lnx (x
1/x)/2. Letting q = x and r = 11/x (so that q = 1/(1r)), we have lnq (x1/x)/2 = (x2
1)/(2x) = r(2r)/(2(1r)). Thus, lnq rlnq = (1r)lnq r(2r)/2 = r r2/2, lnq r +
rlnq r2/2 = r(1 + lnq r/2), so (lnq)/r 1 + lnq r/2.
b. This is true because (lnq)/r = 1 + r/2 + r2/3 + ... 1 + r/2.
c. This is true because 0 < r < 1, so r(1r) < 1 and r < 1/(1r) = q.
d. This is true because 0 < r < 1, so (1r) < 1 and q = 1/(1r) > 1; thus q2 > q and
(1 + q2)/2 > (1 + q)/2.
e. Ths follows directly from the fact that q = 1 + r + r2 + r3 + ...
f. Ths follows directly from the fact that (lnq)/r = 1 + r/2 + r2/3 + r3/4 + ...
With linear probing, we dont need more than n = size probes. After finding n other elements, we will have checked them all and well know that the key is not in the table. You
cant have more than n collisions.
The same is true with quadratic probing, although the put() method may fail once the
load factor exceeds 50%, since the probe sequence reaches only half the slots.
The same is true with double hashing.
The worst case would be where all the keys are in one contiguous block.

86

Solutions

87

9.6

This design would occupy a very large file. For example, if the keys are 100-byte strings,
it would occupoy 200 GB. So this design would be very wasteful of space unless the table
size were in the range of a hundred million.
This hash function is not perfect because the Java hashCode() method is not one-to-one.
9.7
With double hashing, the probe sequence is arithmetic, with a constant difference equal to
the secondary hash value. If the array length is prime, then the probe sequence will reach
every index of the array.
As an example of what can go wrong when the length is not prime, suppose it is 12. If the
secondary hash value is a divisor (1, 2, 3, 4, or 6), then the probe sequence will not reach all
the table slots. For example, suppose the primary hash value is 5 and the secondary hash
value is 4. Then the probe sequence is 5, 9, 1, 5, 9, 1, 5, ... If slots 1, 5, and 9 are occupied,
then the insert will fail even if the table is only 25% full.

Programming Problems
9.1

9.2
9.5

public class TestHashTable {

public TestHashTable() {
HashTable t = new HashTable(11);
t.put("AT", new Country("Austria", "German", 32378, 8139299));
t.put("FR", new Country("France", "French", 211200, 58978172));
t.put("DE", new Country("Germany", "German", 137800, 82087361));
t.put("GR", new Country("Greece", "Greek", 50900, 10707135));
t.put("IT", new Country("Italy", "Italian", 116300, 56735130));
t.put("PT", new Country("Portugal", "Portuguese",35672,9918040));
t.put("SE", new Country("Sweden", "Swedish", 173732, 8911296));
System.out.println("t.size(): " + t.size());
System.out.println("t.get(\"AT\"): " + t.get("AT"));
System.out.println("t.get(\"IT\"): " + t.get("IT"));
System.out.println("t.remove(\"PT\"): " + t.remove("PT"));
System.out.println("t.size(): " + t.size());
System.out.println("t.remove(\"US\"): " + t.remove("US"));
System.out.println("t.size(): " + t.size());
}
public static void main(String[] args) {
new TestHashTable();
}
// the same test driver as in Problem 9.1 can be used.
private int nextProbe(int h, int i) {
return (h + i*i)%entries.length;
}

// Quadratic Probing

88
9.6

Chapter 9 Lists
public class HashTable implements Map { // open addressing
private Entry[] entries;
private int size, used;
private float loadFactor;
private final Entry NIL = new Entry(null,null); // dummy
public HashTable(int capacity, float loadFactor) {
entries = new Entry[capacity];
this.loadFactor = loadFactor;
}
public HashTable(int capacity) {
this(capacity,0.75F);
}
public HashTable() {
this(101);
}
public Object get(Object key) {
int h=hash(key);
int h2=hash2(key);
for (int i=0; i<entries.length; i++) {
int j = nextProbe(h, h2, i);
Entry entry=entries[j];
if (entry==null) break;
if (entry==NIL) continue;
if (entry.key.equals(key)) return entry.value;
}
return null; // failure: key not found
}
public Object put(Object key, Object value) {
if (used>loadFactor*entries.length) rehash();
int h=hash(key);
int h2=hash2(key);
for (int i=0; i<entries.length; i++) {
int j = nextProbe(h, h2, i);
Entry entry=entries[j];
if (entry==null) {
entries[j] = new Entry(key,value);
++size;

// success

Solutions

89
++used;
return null;

// insertion success
}
if (entry==NIL) continue;
if (entry.key.equals(key)) {
Object oldValue=entry.value;
entries[j].value = value;
return oldValue; // update success
}
}
return null;

// failure: table overflow

}
public Object remove(Object key) {
int h=hash(key);
int h2=hash2(key);
for (int i=0; i<entries.length; i++) {
int j = nextProbe(h, h2, i);
Entry entry=entries[j];
if (entry==null) break;
if (entry==NIL) continue;
if (entry.key.equals(key)) {
Object oldValue=entry.value;
entries[j] = NIL;
--size;
return oldValue; // success
}
}
return null; // failure: key not found
}
public int size() {
return size;
}
public String toString() {
StringBuffer buf = new StringBuffer();
for (int i=0; i<entries.length; i++)
if (entries[i] != null)
buf.append(entries[i].key + ": " + entries[i].value + "\n");
return buf.toString();
}

90

Chapter 9 Lists

private class Entry {

Object key, value;
Entry(Object k, Object v) { key=k; value=v; }
}
private int hash(Object key) {
if (key==null) throw new IllegalArgumentException();
return (key.hashCode() & 0x7FFFFFFF) % entries.length;
}
private int hash2(Object key) {
if (key==null) throw new IllegalArgumentException();
return 1 + (key.hashCode() & 0x7FFFFFFF) % (entries.length/2 1);
}
private int nextProbe(int h, int h2, int i) {
return (h + h2*i)%entries.length;
// Double Hashing
}
private void rehash() {
Entry[] oldEntries = entries;
entries = new Entry[2*oldEntries.length+1];
for (int k=0; k<oldEntries.length; k++) {
Entry entry=oldEntries[k];
if (entry==null || entry==NIL) continue;
int h=hash(entry.key);
int h2=hash2(entry.key);
for (int i=0; i<entries.length; i++) {
int j = nextProbe(h, h2, i);
if (entries[j]==null) {
entries[j] = entry;
break;
}
}
}
used = size;
}
}

Solutions
9.7

91

public class Main {

int m = 17; // table size
String[] data = {"AT","BE","DE","DK","ES","FR","GB",
"GR","IE","IT","LU","NL","SE"};
int n = data.length;
private int hash(String key) {
return key.hashCode() % m;
}
private int lin(int h, int i) {
return (h + i) % m;
}
private int quad(int h, int i) {
return (h + i*i) % m;
}
public Main() {
System.out.println("Linear Probing:");
String[] table = new String[m];
int c=0;
for (int i=0; i<n; i++) {
String s = data[i];
int j=0, h=hash(s), k = h;
System.out.print((i<9?"
":" ") + (i+1) + ". " + s +" -> "+h);
while (table[k] != null && j<m) {
++c;
k = lin(h, ++j);
System.out.print(" -> " + k);
}
table[k] = s;
System.out.println();
}
System.out.println(c + " collisions.");
System.out.println("Quadratic Probing:");
table = new String[m];
c=0;
for (int i=0; i<n; i++) {
String s = data[i];
int j=0, h=hash(s), k = h;
System.out.print((i<9?"
":" ") + (i+1) + ". " + s +" -> "+h);

92

Chapter 9 Lists
while (table[k] != null && j<m) {
++c;
k = quad(h, ++j);
System.out.print(" -> " + k);
}
table[k] = s;
System.out.println();
}
System.out.println(c + " collisions.");
}
public static void main(String[] args) {
new Main();
}

9.8

}
public class Main {
int m = 17; // table size
String[] data = {"AT","BE","DE","DK","ES","FR","IT","LU","SE"};
int n = data.length;
private int hash(String key) {
return key.hashCode() % m;
}
private int hash2(String key) {
return 1 + key.hashCode() % (m-1);
}
private int lin(int h, int i) {
return (h + i) % m;
}
private int doub(int h, int h2, int i) {
return (h + i*h2) % m;
}
public Main() {
System.out.println("Linear Probing:");
String[] table = new String[m];
int c=0;
for (int i=0; i<n; i++) {
String s = data[i];

Solutions

93
int j=0, h=hash(s), k = h;
System.out.print((i<9?"
":" ") + (i+1) + ". " + s +" -> "+h);
while (table[k] != null && j<m) {
++c;
k = lin(h, ++j);
System.out.print(" -> " + k);
}
table[k] = s;
System.out.println();
}
System.out.println(c + " collisions.");
System.out.println("Double Hashing:");
table = new String[m];
c=0;
for (int i=0; i<n; i++) {
String s = data[i];
int j=0, h=hash(s), k = h, h2=hash2(s);
System.out.print((i<9?"
":" ") + (i+1) + ". " + s +" -> "+h);
while (table[k] != null && j<m) {
++c;
k = doub(h, h2, ++j);
System.out.print(" -> " + k);
}
table[k] = s;
System.out.println();
}
System.out.println(c + " collisions.");
}
public static void main(String[] args) {
new Main();
}

Chapter 10
Recursion
Exercises
10.1
10.2
10.3

factorial(8) makes 7 recursive calls.

The top disk is the smallest, so no other disk can be placed on top of it. Step 2 requires all
three pegs, but peg B could not be used.

a.

b.

c.

-6
search(a,3,6,905)

7
search(a,0,10,905)

-6
search(a,5,6,905)

-6
search(a,3,6,910)

-6

7
search(a,6,10,905)

search(a,3,6,910)

7
search(a,6,8,905)

10.4
print(3,'A','B','C')

print(2,'A','C','B')

print(1,'A','B','C')

print(2,'C','B','A')

print(1,'C','A','B')

print(1,'B','C','A')

print(3,'A','B','C')

94

Solutions
10.5

10.6
10.7

10.8

10.9

95

a. 15.
b. 31.
c. 2n 1.
Let f(n) be the number of moves for n disks, and let g(n) = 2n 1.
If n = 1, it makes 1 move, and g(1) = 21 1 = 1. Thus, f(1) = g(1).
If n > 1, then it makes f(n 1) + 1 + f(n 1) moves; i.e., f(n) = 2f(n 1) + 1. By the inductive hypothesis, f(n 1) = g(n 1) = 2n1 1. Thus, f(n) = 2(2n1 1) + 1 = 2n 1 = g(n).
Thus, f(n) = g(n) for all n 1.
40.
Let f(n) = n! and let g(n) = 2n.
Then f(4) = 4! = 24 > 16 = 24 = g(4).
If n > 4, then f(n) = n! = n (n 1)! = n f(n 1) > n g(n 1), by the inductive hypothesis.
Thus, f(n) > n g(n 1) > 2g(n 1), since n > 2. Thus, f(n) > 2g(n 1) = 2 2n1 = 2n =
g(n). Thus, f(n) > g(n) for all n 4. Thus, g(n)/f(n) < 1 for all n 4; i.e., g(n)/f(n) is
bounded.
F1 + F2 + F3 + + F10 = 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143 = 144 1
= F12 1. More generally:
F0 + F1 + F2 + + Fn = (F2 F1 ) + (F3 F2 ) + (F4 F3 ) + + (Fn +2 Fn 1 )
The sum on the right telescopes, leaving Fn +2 F1 . Thus:
F0 + F1 + F2 + + Fn = Fn +2 F1 = Fn +2 1
Let T(n) be the run time for the recursive Fibonacci function f(n). Then:
T(n ) = c + T(n 1) + T(n 2)
> c + 2T ( n 2 )
> c + 2 [ c + 2T ( n 4 ) ]
= 3c + 4T ( n 4 )
> 3c + 4 [ c + 2T ( n 2 ) ]
= 7c + 8T ( n 6 )

= ( 2 1 )c + 2 T ( n 2k )

Thus, T(n) > (2k 1)c + 2k T(n 2k), for k = 1, 2, 3, ...

Let k = n/2 so 2k = n (assuming n is even). Then T(n) > (2n/2 1)c + 2n/2 T(0) = (2n).

96

Chapter 10 Recursion

10.10

1+ 5
= ---------------2
1 5
= ---------------2
1+ 5 1 5
2
+ = ---------------- + ---------------- = --- = 1
2
2
2
1+ 5 1 5
2 5
= ---------------- ---------------- = ---------- =
2
2
2

2
1+ 5 2
1+2 5+5
6+2 5
3+ 5
1+ 5 2
= ---------------- = ----------------------------- = ------------------- = ---------------- = ---------------- + --- = + 1
2
4
4
2
2
2
2
1 5 2
12 5+5
62 5
3 5
1 5 2
= ---------------- = ---------------------------- = ------------------- = ---------------- = ---------------- + --- = + 1
2
4
4
2
2
2

a.

f n = -----------------5

11
f 0 = ------------------ = ------------ = 0
5
5

5
f 1 = ------------------ = ------------- = ------- = 1
5
5
5

( + 1) ( + 1)

f 2 = ------------------ = ----------------------------------------- = ------------- = 1

5
5
5

b.

n1

n1

n2

n2

f n 1 + f n 2 = -------------------------------- + -------------------------------5
5
n1
n2
n1
n2
1
= ------- [ (
+
) (
+
)]
5
1
n2
n2
= ------- [ ( + 1 )
( + 1 )
]
5
1
2 n2
2
n2
= ------- [ ( )
( )
]
5
1 n
n
= ------- [ ]
5
= fn

10.11

On each iteration x is halved. Therefore, the number of iterations that it takes to reduce x
from 1.0 to 0.01 is lg(1.0/0.01) = lg(1/0.01). More generally, the number of iterations to
reduce x to 1/t will be lg(1/t); i.e., the run-time is T = (lg(1/t)) Thus, if t = t2, then
T = (lg(1/t)) = (lg(1/t2)) = (lg((1/t)2)) = (2lg(1/t)) = 2(lg(1/t)) = 2T.

Solutions
10.12

97

If n is even, then T(n) = c1 + T(n/2), and (since then n + 1 will be odd), then T(n + 1) =
c2 + T(n) = c2 + c1 + T(n/2). Thus, on average, T(n) = c + T(n/2). The same analysis as on
page 314 then applies to obtain T(n) = (lgn).

10.13

2100
exp(2,100)

250
exp(2,50)

225
exp(2,25)

224
exp(2,24)

212
exp(2,12)

26
exp(2,6)

23
exp(2,3)

22
exp(2,2)

21
exp(2,1)

98

Chapter 10 Recursion

Programming Problems
10.1

10.2

10.3

public class IterativeFactorial {

public static void main(String[] args) {
for (int i=0; i<10; i++)
System.out.println(i + "\t" + factorial(i));
}
static long factorial(int n) {
if (n<2) return 1;
long f = n;
for (int i=2; i<n; i++)
f *= i;
return f;
}
}
public class LargestFib {
private static final double SR5=Math.sqrt(5); // 2.2360679774997896
private static final double PHI=(1+SR5)/2;
// 1.6180339887498948
private static final double PSI=(1-SR5)/2;
//-0.6180339887498948
public static void main(String[] args) {
long f0 = 0;
long f1 = 1;
long f2 = 1;
for (int i=3; i<93; i++) {
f0 = f1;
f1 = f2;
f2 += f0;
if (i > 89) System.out.println("\tf(" + i + ") =\t " + f2);
}
System.out.println("Long.MAX_VALUE = " + Long.MAX_VALUE);
System.out.println("\tf(93) =\t" + (f1 + f2));
}
}
import java.math.*;
public class BigFib {
private static BigDecimal one = new BigDecimal("1");
private static BigDecimal two = new BigDecimal("2");
private static BigDecimal five = new BigDecimal("5");
private static BigDecimal sr5;
private static BigDecimal phi;
private static BigDecimal psi;

Solutions

99
public static void main(String[] args) {
BigInteger f0 = new BigInteger("0");
BigInteger f1 = new BigInteger("1");
BigInteger f2 = new BigInteger("1");
for (int i=3; i<=1000; i++) {
f0 = f1;
f1 = f2;
f2 = f0.add(f1);
if (i > 997)
System.out.println("f(" + i + ") =\t" + f2);
}
}

10.4

10.5

}
public class TestBinarySearch {
TestBinarySearch() {
int[] a = {22, 33, 44, 55, 66, 77, 88, 99};
int n = a.length;
System.out.println("search(" + 55 + "): " + search(a, 0, n, 55));
System.out.println("search(" + 50 + "): " + search(a, 0, n, 50));
}
int search(int[] a, int p, int q, int x) {
if (q <= p) return -p-1; // base
int m = (p + q)/2;
if (a[m] == x) return m;
if (a[m] < x) return search(a, m+1, q, x);
return search(a, p, m, x);
}
public static void main(String[] args) {
new TestBinarySearch();
}
}
public class TestExp {
TestExp() {
System.out.println("exp1(3, 4): " + exp1(3, 4));
System.out.println("exp2(3, 4): " + exp2(3, 4));
System.out.println("exp1(5, -2): " + exp1(5, -2));
System.out.println("exp2(5, -2): " + exp2(5, -2));
System.out.println("exp1(2, -5): " + exp1(2, -5));
System.out.println("exp2(2, -5): " + exp2(2, -5));
}

100

Chapter 10 Recursion
double exp1(double x, int n) {
if (n == 0) return 1.0;
if (n < 0) return 1.0/exp1(x, -n);
double y = 1.0;
for (int i = 0; i < n; i++)
y *= x;
return y;
}
double exp2(double x, int n) {
if (n == 0) return 1.0;
if (n < 0) return 1.0/exp2(x, -n);
double factor = (n%2 == 0 ? 1.0 : x);
if (n < 2) return factor;
// base
return factor*exp2(x*x, n/2);
// recursion
}
public static void main(String[] args) {
new TestExp();
}

10.6

10.7

}
public double valueAt(double x) {
if (this.equals(ZERO)) return 0.0;
double y = 0.0;
int e = exp;
Poly p = this;
while (p != null) {
for (int i=1; i < e - p.exp; i++)
y *= x;
y += p.coef;
e = p.exp;
p = p.next;
}
return y;
}
String commaString(long n) {
String s="";
int c = 0;
while (n > 0) {
if (c>0 && c%3==0) s = "," + s;
s = (n%10) + s;
n /= 10;
++c;
}

Solutions

10.8

10.9

10.10

10.11

10.12

return s;
}
String commaString(long n) {
String s="";
if (n==0) return "0";
for (int i=0; i<3; i++) {
s = (n%10) + s;
n /= 10;
if (n==0) return s;
}
return commaString(n) + "," + s; // recursion
}
int max(int[] a, int p, int q) {
if (q - p == 1) return a[p];
int m = (p + q)/2;
int max1 = max(a, p, m); // recursion
int max2 = max(a, m, q); // recursion
return ( max1 > max2 ? max1 : max2 );
}
int intBinLog(int n) {
if (n < 2) return 0;
return 1 + intBinLog(n/2); // recursion
}
boolean isPalindrome(String s) {
int n = s.length();
if (n < 2) return true;
if (s.charAt(0) != s.charAt(n-1)) return false;
return (isPalindrome(s.substring(1,n-1))); // recursion
}
String bin(int n) {
if (n == 0) return "0";
if (n == 1) return "1";
return bin(n/2) + bin(n%2); // recursion
}
String hex(int n) {
if (n < 10) return String.valueOf(n) ;
if (n < 16) {
switch (n) {
case 10: return "A";
case 11: return "B";
case 12: return "C";
case 13: return "D";

101

102

Chapter 10 Recursion
case 14: return "E";
case 15: return "F";
}
}
return hex(n/16) + hex(n%16);

10.13

10.14
10.15
10.16

10.17

// recursion
}
String reverse(String s) {
if (s.length() < 2) return new String(s);
return reverse(s.substring(1)) + s.charAt(0);
}

// recursion

The computable domain for the factorial() method was 0 n 20.

The computable domain for the fibonacci() method was 0 n 48.
The computable domain for the Ackermann function is:
0 n < Long.MAX_VALUE, for m = 0;
0 n < Long.MAX_VALUE - 1, for m = 1;
0 n < Long.MAX_VALUE/2 - 1, for m = 2;
0 n 60, for m = 3;
n = 0, for all m > 3.
public class TestTrigFunctions {
static final double TOL = 0.00005;
public static void main(String[] args) {
for (double x=0.0; x<1.0; x+=0.1)
System.out.println(sin(x) + "\t" + mathSin(x));
for (double x=0.0; x<1.0; x+=0.1)
System.out.println(cos(x) + "\t" + mathCos(x));
}
static double sin(double x) {
if (-TOL<x && x<TOL) return x - x*x*x/6;
return 2*sin(x/2)*cos(x/2);
}
static double cos(double x) {
if (-TOL<x && x<TOL) return 1.0 - x*x/2;
double y = sin(x/2);
return 1 - 2*y*y;
}
static double mathSin(double x) {
return Math.sin(x);
}

// base
// recursion

// base
// recursion

Solutions

103
static double mathCos(double x) {
return Math.cos(x);
}

10.18

}
public class TestTrigFunctions {
public static void main(String[] args) {
for (double x=0.0; x<1.0; x+=0.1)
System.out.println(sin(x) + "\t" + mathSin(x));
for (double x=0.0; x<1.0; x+=0.1)
System.out.println(cos(x) + "\t" + mathCos(x));
}
static double sin(double x) {
if (-0.01<x && x<0.01) return x*(1 - x*x/6*(1 - x*x/20)); // base
return 2*sin(x/2)*cos(x/2);
// recursion
}
static double cos(double x) {
if (-0.01<x && x<0.01) return 1 - x*x/2*(1 - x*x/12); // base
double y = sin(x/2);
// recursion
return 1 - 2*y*y;
}
static double mathSin(double x) {
return Math.sin(x);
}
static double mathCos(double x) {
return Math.cos(x);
}

10.19

}
public class TestHyperbolicFunctions {
public static void main(String[] args) {
for (double x=0.0; x<1.0; x+=0.1)
System.out.println(sinh(x) + "\t" + mathSinh(x));
for (double x=0.0; x<1.0; x+=0.1)
System.out.println(cosh(x) + "\t" + mathCosh(x));
}
static double sinh(double x) {
if (-0.01<x && x<0.01) return x + x*x*x/6;
return 2*sinh(x/2)*cosh(x/2);
}

// base
// recursion

104

Chapter 10 Recursion

static double cosh(double x) {

if (-0.01<x && x<0.01) return 1.0 + x*x/2;
return 1 + 2*sinh(x/2)*sinh(x/2);
}

// base
// recursion

static double mathSinh(double x) {

return (Math.exp(x) - Math.exp(-x))/2;
}
static double mathCosh(double x) {
return (Math.exp(x) + Math.exp(-x))/2;
}

10.20

10.21

}
static double tan(double x) {
if (-0.01<x && x<0.01) return x + x*x*x/3; // base
double t = tan(x/2);
return 2*t/(1.0 - t*t);
// recursion
}
public class Timing {
static double tol = 0.01;
public static void main(String[] args) {
System.out.println(time(1e-2));
System.out.println(time(1e-3));
System.out.println(time(1e-4));
System.out.println(time(1e-5));
System.out.println(time(1e-6));
System.out.println(time(1e-7));
}
static long time(double t) {
long t1 = System.currentTimeMillis();
for (double x=0.0; x<1.0; x+=0.00001)
sin(x);
for (double x=0.0; x<1.0; x+=0.00001)
cos(x);
long t2 = System.currentTimeMillis();
return t2 - t1;
}

Solutions

105
static double sin(double x) {
if (-tol<x && x<tol) return x - x*x*x/6;
return 2*sin(x/2)*cos(x/2);
}
static double cos(double x) {
if (-tol<x && x<tol) return 1.0 - x*x/2;
double s = sin(x/2);
return 1 - 2*s*s;
}

// base
// recursion

// base

Chapter 11
Trees
Exercises
11.1

11.2

a.
b.
c.
d.
e.
f.
g.
h.
i.
j.
k.
l.
m.
a.

True. A node is an ancestor if and only if it lies on the root-path.

False. Its size is one more than the number of its descendants.
True. If x is a descendant of y, then xs root-path contains ys root-path.
False. x could be a nephew of y.
True. If the root is a leaf, then the tree has only one node.
True. Each leaf of the subtree is an element of the supertree and has no children.
False. If one tree is a subtree of another and if the two roots are the same node, then
the two trees must be equal.
True. The set of all leaf-paths from x in R is the same as in S and in T.
True. A leaf is a node with no children.
False. A tree of height 2 with only one leaf (i.e., a linear tree) has two internal nodes.
False. A tree of height 1 with four nodes is not full.
True. If a leaf is omitted, then all ancestors of that leaf must also be omitted.
True. If a leaf is omitted, then all ancestors of that leaf must also be omitted.
b.
Size=7; 6 descendants

Depth=2; 2 ancestors

c.

d.
y
x

e.

Depth=1
Depth=2

Root is a leaf

Depth=1
Depth=2

f.
All 4 leaves are also leaves of T

h
106

Solutions

107

g.

h.
Root of subtree is not root of T

i.

j.
3 internal nodes; 2 leaves
A leaf has no children

k.

l.
All leaves at level 3

11.3

a.
b.
c.
d.
e.

Unordered; e.g., the order of {float, double} is irrelevant.

4
5
7
46

11.4
11.5

11.6

11.7
11.8

final

a.
b.
c.
d.
e.
f.
g.
h.
i.
j.

C, F, H, J, L, M, N, O, P
G

2
4
D, A
J, K, L, M, O, P
H, I, J, K, L, M

4
6
4

m.

108
11.9

Chapter 11 Trees
a.
b.
c.
d.

129
85
1,111
1,398,101

11.10
h+1

d
1
n = -------------------d1
n(d 1) = d

h+1

nd n + 1 = d

h+1

log d ( nd n + 1 ) = h + 1

= logd ( nd n + 1 ) 1

h
11.11
11.12

w = number of leaves = d h
path length = 0 1 + 1 d + 2 d 2 + 3 d 3 + + h d h =
h

jd

j=0

jd

j=1i=1

i=1 j=i

d d

i hi

k=0

i=1

ji

j=i

i=1

hi+1

d
1
--------------------------d1

i=1

= (d 1)

1 h

(d

h+1

d )

i=1

h+1

1
h + 1 d
1
= ( d 1 ) hd
--------------------- 1

d1

= ( d 1 ) ( ( d 1 )hd
h+2

h+1

h+1

((d

hd
(h + 1) d
+ d= ------------------------------------------------------------2
(d 1)

h+1

1) + (d 1)))

Solutions
11.13

11.14

11.15

11.16

109

a. A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P
b. A, B, E, H, I, N, F, C, D, G, J, K, O, P, L, M
c. H, N, I, E, F, B, C, J, O, P, K, L, M, G, D, A
a. level order and preorder
b. postorder
c. postorder
d. preorder
Algorithm. Iterative Preorder Traversal
1. Create an empty stack.
2. Push the tree (root) onto the stack.
3. While the stack is not empty, do steps 4-6:
4.
Pop the stack to obtain x.
5.
Visit the root of x.
6.
Traverse the subtree list of x in reverse order, pushing each subtree onto
the stack
Let x by any internal node of a full tree of degree d. Let l be the level of node x, and let y
be the left-most node at that same level. Then, by Formula 11.4, the index of y is
i(y) = (d l 1)/(d 1), and the index of the first child y of y is i(y) = (d l+1 1)/(d 1).
Let k be the number of nodes on the left of x at the same level l. Then x has index
i(x) = (d l 1)/(d 1) + k. Since the tree is full, each node at level l had d children. Thus,
there are dk children on the left of the first child of x (at level l+1). Thus, the first child x
of x has index i(x) = (d l+1 1)/(d 1) + dk = (d l+1 1 + d 2k dk)/(d 1). This is the
same as di(x) + 1 = d[(d l 1)/(d 1) + k] + 1 = (d l+1 1 + d 2k dk)/(d 1). Thus the
index of the first child of x is di(x) + 1. Thus the indexes of all d children of x are
di(x) + 1, di(x) + 2, di(x) + 3, ..., di(x) + d.

110

Chapter 11 Trees

Programming Problems
11.1

import java.util.*;
public class OrderedTree {
private Object root;
private List subtrees;
private int size;
public OrderedTree() { // constructs the empty tree
}
public OrderedTree(Object root) { // constructs a singleton
this.root = root;
subtrees = new LinkedList(); // constructs the empty list
size = 1;
}
public OrderedTree(Object root, List trees) {
this(root);
for (Iterator it=trees.iterator(); it.hasNext(); ) {
Object object=it.next();
if (object instanceof OrderedTree) {
OrderedTree tree = (OrderedTree)object;
subtrees.add(tree);
size += tree.size();
}
}
}
public int size() {
return size;
}

11.2

}
public void levelOrderPrint() {
LinkedList queue = new LinkedList();
queue.addLast(this);
while (!queue.isEmpty()) {
OrderedTree tree = (OrderedTree)queue.removeFirst();
System.out.print(tree.root + " ");
for (Iterator it=tree.subtrees.iterator(); it.hasNext(); )
queue.addLast(it.next());
}
}

Solutions
11.3

11.4

11.5

public void preorderPrint() {

System.out.print(root + " ");
for (Iterator it=subtrees.iterator(); it.hasNext(); )
((OrderedTree)it.next()).preorderPrint();
}
public void postorderPrint() {
for (Iterator it=subtrees.iterator(); it.hasNext(); )
((OrderedTree)it.next()).postorderPrint();
System.out.print(root + " ");
}
public void preorderPrint() {
if (root == null) return;
Stack stack = new Stack();
stack.push(this);
while (!stack.isEmpty()) {
OrderedTree x = (OrderedTree)stack.pop();
System.out.print(x.root + " ");
List s = x.subtrees;
ListIterator lit = s.listIterator(s.size());
while (lit.hasPrevious())
stack.push(lit.previous());
}
}

111

Chapter 12
Binary Trees
Exercises
12.1

12.2
12.3

12.4

12.5

Let T be a binary tree of height h and size n. Having height h means that it must contain at
least one root-to-leaf path of length h. Any such path has h + 1 elements. Thus, n h + 1.
By Formula 12.1, the full binary tree of height h has 2 h+1 1 elements. If T is not full,
then it can be transformed into that full binary tree by adding elements. Thus, n 2 h+1 1.
By Formula 12.2, we have n 2 h+1 1. Thus n < n 1 2 h+1, so lg n < h + 1. Since
x x (see Formula C.1.3 on page 565), we have lg n lg n. Thus, lg n < h + 1. But
both lg n and h are integers. Thus, lg n h.
Let T be a complete binary tree of height h and size n. By Formula 12.1, n 2 h+1 1.
Moreover, T contains the full binary tree of height h 1 because T includes all the elements of the full binary tree of height h except possibly for some missing leaf elements at
level h. Therefore, n 2 (h 1)+1 1 = 2 h 1. But by having height h, T must include at
least one element at level h, which means that it must have at least one element more than
the complete binary tree of height h 1. Thus, n > 2 h 1. Therefore, n 2 h (since n and 2 h
are integers).
Let T be a complete binary tree of height h and size n. Then T includes all the elements of
the full binary tree of height h except possibly for some missing leaf elements at level h.
Therefore, T has more elements than the full binary tree of height h 1, but not more than
the full binary tree of height h. Thus, by Formula 12.1, 2 h = 2 (h 1)+1 < n 2 h+1 1. Thus,
h < lg n < h + 1. Therefore, by Formula C.1.4 on page 565, we have h = lg n.
Let n be the number of nodes at lebel l in a binary tree. If l = 0, then n = 1, since the only
node at that level is the root node. If l = 1, then n = 1 or 2, since the only nodes at that level
are the children of the root, and in a binary tree each node has at most 2 children. Similary,
at any level l, n is the number of children of the nodes at level l 1. By the induction
hypothesis, there are between 1 and 2 l 1 nodes at level l 1. Therefore, n must be
between 1 and 2(2 l 1) = 2 l.

112

Solutions

113
complete

12.6

12.7

complete

12.8

12.9
12.10
12.11

There are 16 complete binary trees with height h = 4.

There are C 6 = 132 binary trees with size n = 6. [See Section C.7.]
There are C 7 = 429 binary trees with size n = 7. [See Section C.7.]

114
12.12

12.13
12.14
12.15

12.16

Chapter 12 Binary Trees

Label the subtrees A, B, etc., according to their root labels:

Subtrees D, E, and C are (valid) binary trees because they are singletons.
B
Then subtree B is a binary tree because it is a triple (x, L, R), where x is
the node (labeled B), and L and R are the binary trees D and E. Then
D
subtree A is a binary tree because it is a triple (x, L, R), where x is the
node (labeled A), and L and R are the binary trees B and C.
False. All three leaves of this binary tree are at the same level, but it is not full:

A
C
E

False. Every proper subtree of this binary tree is full, but the tree itself is not:
a. Level order: A B C D E F G H I J K L M N O P Q R S T U V
b. Preorder: A B D H E I J N O S C F K P T U G L M O V R
c. Inorder: D H B I E N J S O A F T P U K C L G V O M R
d. Postorder: H D I N S O J E B T U P K F L V O R M G C A
Prefix: - * 2 - 8 / 9 3 4
Infix: 2 * 8 - 9 / 3 - 4
4
*
Postfix: 2 8 9 3 / - * 4 Value: 6
2
8

/
9 3

12.17

Postfix: 8 7 5 - - 3 /
Infix: 8 - 7 - 5 / 3

/
3

(8 - (7 - 5)) / 3

Value: 2

12.18

Prefix: / - 0 1 + 1 3
Infix: 9 - 1 / 1 + 3
(9 - 1) / ( 1 + 3)
Value: 2

5
/
+

12.19 Algorithm: Evaluating an Expression from Its Prefix Representation

1. Create a stack for operators and operands.
2. Read the first token into x.
3. Repeat steps 4-9 until both the input and the stack are empty:
4.
If x and the stack top both are operands, do steps 5-7:
5.
Pop y from the stack.
6.
Pop z from the stack.
7.
Let x be the result of applying the operator z to y and x.
8.
Otherwise, push x onto the stack and read the next token into x.

Solutions
12.20

115

Let T be complete binary tree of size n, and let p be the number of the first leaf and q be
the number of its last leaf. (For example, the tree in Figure 12.13 has n = 11, p = 5 and
q = 10.) Then clearly, q = n 1. Moreover, the parent of the last leaf is the last internal
node of the complete tree. By Formula 12.6, that internal node has number (q 1)/2. The
node to its right is the first leaf node, so p = (q 1)/2 + 1 = (q + 1)/2 = n/2.

12.21

A
B
D

K
P

C
T

12.22

A
B

D
H

E
CI

L
C
F

M
G

N
O
P
S

Q
C
T
U
V

116

Chapter 12 Binary Trees

Programming Problems
12.1

public class BinaryTree {

private Object root;
private BinaryTree left, right;
public BinaryTree(Object root) {
this.root = root;
}
public BinaryTree(Object root, BinaryTree left, BinaryTree right) {
this(root);
if (left!=null) this.left = left;
if (right!=null) this.right = right;
}
public BinaryTree(BinaryTree that) {
this.root = that.root;
if (that.left!=null) this.left = new BinaryTree(that.left);
if (that.right!=null) this.right = new BinaryTree(that.right);
}
public Object getRoot() {
return this.root;
}
public BinaryTree getLeft() {
return this.left;
}
public BinaryTree getRight() {
return this.right;
}
public Object setRoot(Object object) {
Object oldRoot = this.root;
this.root = object;
return oldRoot;
}
public BinaryTree setLeft(BinaryTree tree) {
BinaryTree oldLeft = this.left;

Solutions

117
this.left = tree;
return oldLeft;
}
public BinaryTree setRight(BinaryTree tree) {
BinaryTree oldRight = this.right;
this.right = tree;
return oldRight;
}

12.2

12.3

12.4

12.5

12.6

12.7

public String toString() {

StringBuffer buf = new StringBuffer("[");
if (left!=null) buf.append(left + ",");
buf.append(root);
if (right!=null) buf.append("," + right);
return buf + "]";
}
public boolean isLeaf() {
return left==null && right==null;
}
public int size() {
if (left==null && right==null) return 1;
if (left==null) return 1 + right.size();
if (right==null) return 1 + left.size();
return 1 + left.size() + right.size();
}
public int height() {
if (left==null && right==null) return 0;
if (left==null) return 1 + right.height();
if (right==null) return 1 + left.height();
return 1 + Math.max(left.height(), right.height());
}
public boolean contains(Object object) {
if (this.root==object) return true;
if (left!=null && left.contains(object)) return true;
if (right!=null && right.contains(object)) return true;
return false;
}
public int numLeaves() {
if (left==null && right==null) return 1;
if (left==null) return right.numLeaves();
if (right==null) return left.numLeaves();

118

12.8

12.9

12.10

12.11

12.12

12.13

Chapter 12 Binary Trees

return left.numLeaves() + right.numLeaves();
}
public int frequency(Object x) {
int frequency = ( x.equals(root) ? 1 : 0 );
if (left!=null) frequency += left.frequency(x);
if (right!=null) frequency += right.frequency(x);
return frequency;
}
public boolean isFull() {
if (left==null && right==null) return true;
if (left==null || right==null) return false;
return left.isFull() && right.isFull()
&& left.height()==right.height();
}
public boolean isBalanced() {
if (left==null && right==null) return true;
if (left==null) return right.isLeaf();
if (right==null) return left.isLeaf();
int balance = left.height() - right.height();
return balance > -2 && balance < 2;
}
public int pathLength() {
if (left==null && right==null) return 0;
if (left==null) return right.pathLength() + right.size();
if (right==null) return left.pathLength() + left.size();
return left.pathLength() + right.pathLength() + size() - 1;
}
public BinaryTree reverse() {
if (left==null && right==null)
return new BinaryTree(this.root);
if (left==null)
return new BinaryTree(this.root,right.reverse(),null);
if (right==null)
return new BinaryTree(this.root,null,left.reverse());
return new BinaryTree(this.root,right.reverse(),left.reverse());
}
public int level(Object object) {
if (this.root==object) return 0;
int levelInLeft = ( left==null ? -1 : left.level(object) );
if (levelInLeft>-1) return 1 + levelInLeft;
int levelInRight = ( right==null ? -1 : right.level(object) );
if (levelInRight>-1) return 1 + levelInRight;

Solutions

12.14

12.15

12.16

12.17

119
return -1;
}
public boolean isDisjointFrom(BinaryTree that) {
if (that==null) return true;
if (this.contains(that.root)) return false;
return this.isDisjointFrom(that.left)
&& this.isDisjointFrom(that.right);
}
public boolean isValid() {
if (left==null && right==null) return true;
if (left==null) // so right!=null
if (right.contains(this.root) || !right.isValid())
return false;
if (right==null) // so left!=null
if (left.contains(this.root) || !left.isValid())
return false;
return left.isDisjointFrom(right);
}
public boolean equals(Object object) {
if (this == object) return true;
if (!(object instanceof BinaryTree)) return false;
BinaryTree that = (BinaryTree)object;
if (!this.root.equals(that.root)) return false;
boolean leftEqual = this.left==null && that.left==null
|| this.left!=null && this.left.equals(that.left);
boolean rightEqual = this.right==null && that.right==null
|| this.right!=null && this.right.equals(that.right);
return leftEqual && rightEqual;
}
public void preorderPrint() {
if (left!=null) left.preorderPrint();
System.out.print(root + " ");
if (right!=null) right.preorderPrint();
}
public void inorderPrint() {
if (left!=null) left.inorderPrint();
System.out.print(root + " ");
if (right!=null) right.inorderPrint();
}
public void postorderPrint() {
if (left!=null) left.postorderPrint();
if (right!=null) right.postorderPrint();

120

12.18

Chapter 12 Binary Trees

System.out.print(root + " ");
}
public void levelOrderPrint() {
java.util.List queue = new java.util.LinkedList();
queue.add(this);
while (!queue.isEmpty()) {
BinaryTree tree = (BinaryTree)queue.remove(0);
System.out.print(tree.root + " ");
if (tree.left != null) queue.add(tree.left);
if (tree.right != null) queue.add(tree.right);
}
}

Chapter 13
Lists
Exercises

121

122

Chapter 13 Lists

13.1

55
22

77

18

44

70

30
27

60
33

88
74

80

94

66
63

69

55
50

22

77

18

44
30
27

70
50

60

33

88
74

80

94

66
63

69

55
20

22

77

18

44
20

30
27

70
50

60

33

88
74

80

94

66
63

69

55
90

22

77

18

44
20

30
27

70
50

60

33

74
66

63

88
80

94
90

69

Solutions

123

13.2

55
22

77

18

44

70

30
27

88

60
33

74

80

94

66
63

69
55

-18

22

77
44

70

30
27

60
33

74

80

63

69

27

77
44

70

30

60
33

88
74

80

94

66
63

69

55
-70

27

77
44

74

30

88

60
33

80

94

66
63

55
-77

27

69
80

44
30

94

66
55

-22

88

74
60

33

94
66

63

88

69

124

Chapter 13 Lists

13.3
44

44

88

44

55

44

88

88
55

44

44

77

88

33

33

88

55

55
77

77

44
99

44

33

88

66

55

33

88

99

55

99

77

77
66

44
22

44

33

88

22

55

25
99

77

33

88
55

99

25

55

99
77
66

44

22

22

88

25

66

75

33

77
66
75

Solutions
13.4
13.5

125

If y is the inorder successor of x in a BST, then the result of deleting x and y is independent
of the order in which they are deleted.
a. True: the BST property holds for all the elements of the subtree.
b. False: the root key may not be less than all the keys in the right subtree.
c. False: here are the two
(different) BSTs resulting
44
44
88
44
from inserting 44 and 88
88
in different orders:
d. True: the balance number
of a node depends entirely
88
88
44
88
on the heights of its two
44
subtrees.
e. False: the two subtrees
could have heights that differ by more than 1.

13.6

13.7
13.8

T2

There is 1 AVL tree of height 1 and 3 AVL trees of height 2. So the number of AVL trees
of height 3 is 33 + 2(31) = 15. Thus, the number of AVL trees of height 4 is
1515 + 2(153) = 315.
T4

T5

126

Chapter 13 Lists

13.9

If h = 0, n = |T0 | = 1, which is between 1.50 = 1 and 20 = 1. If h = 1, n = |T1 | = 2, which is

between 1.51 = 1.5 and 21 = 2. If h = 2, n = |T2 | = 4, which is between 1.52 = 2.25 and
22 = 4. Assume the formula holds for all Fibonacci trees of height less than h. Then:
1.5

h2

Th 2 2

h2

1.5

h1

Th 1 2

h1

Th = Th 1 + Th 2 + 1
2
<2

h1

h1

+2

T h 1.5
> 1.5

h1

+2

h2

h1

+ 1.5

+2

+1

h2

= 2

h2

+1

+ 1.5

h2

> 2.25 ( 1.5

h2

= 2.5 ( 1.5

h2

) = 1.5

h2

13.10
1
A ( n ) = --n

n1

1
= --n

n1

Ai ( n )

i=0

i=0

1
= ----2n

1--- --ini1
+ [ 1 + A ( i ) ] + ------------------- [ 1 + A ( n i 1 ) ]
n n
n

n1

n1

n1

i=0

i=0

i=0

1 + i [1 + A( i)] + ( n i 1)[1 + A(n i 1) ]

1
= ----2- n + 2
n
1 2
= --- + ----2n n

n1

i [1 + A(i )]

i=0
n1

n1

i=0

i=0

i + i A( i)

1 2 ( n 1 )n
= --- + ----2- -------------------- +
n n
2
2
= 1 + ----2n

n1

i A( i)

i=0

n1

i A(i)

i=0

Solutions

127

13.11
2
A ( n ) = 1 + ----2n
2

n1

i A(i)

i=0

n A(n) = n + 2

n1

i A(i)

i=0
2

(n + 1 ) A(n + 1) = (n + 1 ) + 2

i A(i)

i=0

(n + 1 ) A(n + 1) n A(n ) = [ (n + 1) n ] + 2

i A( i)

i=0
2

( n + 1 ) A ( n + 1 ) n A ( n ) = [ 2n + 1 ] + 2 [ nA ( n ) ]
2

( n + 1 ) A ( n + 1 ) ( n + 2n )A ( n ) = 2n + 1
n + 2n )A ( n )2n + 1
(---------------------------------------n + 1 ) A ( n + 1 )- (---------------------------------
= ---------------------------------(n + 1)(n + 2)
(n + 1)(n + 2)
( n + 1 )( n + 2 )
(-------------------------------------n + 1 ) A ( n + 1 )- n--------------A(n)
2n + 1

= ---------------------------------n+2
n+1
(n + 1)(n + 2)
n----------+ 1n
2n + 1
A ( n + 1 ) ------------ A ( n ) = ---------------------------------n+2
n+1
(n + 1)(n + 2)
2n + 1
n
+ 1-
n----------A ( n + 1 ) = ------------ A ( n ) + --------------------------------- n + 1
n + 2
(n + 1 )(n + 2 )

n1

i A(i)

i=0

128

Chapter 13 Lists

13.12
m
f ( m ) = ------------- A ( m )
m + 1
1
1
1
f ( 1 ) = --- A ( 1 ) = --- ( 1 ) = --2
2
2
2n + 1
f ( n + 1 ) = f ( n ) + ---------------------------------( n + 1 )( n + 2 )
2(1) + 1
1
3
f ( 2 ) = f ( 1 ) + -------------------------------------------- = --- + ---------( (1 ) + 1 )( (1 ) + 2 )
2 23
5
2(2) + 1
1
3
f ( 3 ) = f ( 2 ) + -------------------------------------------- = --- + ---------- + ---------34
( (2 ) + 1 )( (2 ) + 2 )
2 23
2(3) + 1
1
3
5
7
f ( 4 ) = f ( 3 ) + -------------------------------------------- = --- + ---------- + ---------- + --------- 2 2 3 3 4 4 5
( (3 ) + 1 )( (3 ) + 2 )
etc .
1
3
5
7
2n 1
f ( n ) = ---------- + ---------- + ---------- + ---------- + + -------------------12 23 34 45
n(n + 1 )
f( n) =

2k 1

------------------k( k + 1)

k=1

Solutions

129

13.13
f(n) =

2k 1

------------------k(k + 1)

k=1

= 2

k=1

= 2

k=1

k=1

-
-- k----------+1 k

k=1

= 3

--- ------------
-
k----------+ 1 k k + 1

k=1

= 3

------------------ k------------------( k + 1) k( k + 1)

n+1

k=1

--k- --k-

k=2

k=1

n + 1
n + 1

1
1
1
= 3 --- 1 --- ------------

k
k n + 1
k = 1
k = 1

1
= 3 ( H n + 1 1 ) H n + 1 ------------

n + 1
1
= 2H n + 1 3 + -----------n+1

130
13.14

Chapter 13 Lists

The largest B-tree of degree m and height h has the maximum m 1 keys in each node,
and every internal node has the maximum m children. Thus, it has 1 node at level 0, m
nodes at level 1, m2 nodes at level 2, m3 nodes at level 3, etc. The total number of nodes is:
h+1

2
3
h
1
m
1 + m + m + m + + m = ----------------------m1

Since each node has m 1 keys, the total maximum number of keys is m h +1 1.
The smallest B-tree of degree m and height h has 1 key in its root and the minimum
m/2 keys in every other node. Let x = m/2. Then this minimal B-tree has 1 node at
level 0, 2 nodes at level 1, 2x nodes at level 2, 2x2 nodes at level 3, etc. The total number
of non-root nodes is:
2

2 + 2x + 2x + + 2x

h1

= 2 ( 1 + 2x + 2x + + 2x

h1

x 1
= 2 --------------
x1

Since each non-root node has x 1 keys, the total number of keys in all of the non-root
nodes is:
h

x 1
h
( x 1 ) 2 -------------- = 2 ( x 1 )
x 1
h

= 2x 2

13.15

There is one key in the root. Thus the total minimum number of keys is 2 m/2 h 1.
Let x = m/2. Then we have from Formula 13.8: 2 x h 1 n. Solving for x h:
h

2x 1 n
h

2x n + 1
h n+1
x -----------2

Since n 1, (n + 1)/2 (n + n)/2 = n. Thus, x h n and h logx n.

Now x = m/2 m/2, so lgx lg(m/2). Thus:
h log x n
lgn
= -------lgx
lgn
--------------------lg ( m 2 )
= log m 2 n

Finally, since m is constant, h c lg n = (lg n), where c = 1/lg(m/2).

Solutions

131

Programming Problems
13.1

public boolean isBST() {

if (this == NIL) return true;
if (this.isSingleton()) return true;
if (!(this.root instanceof Comparable)) return false;
if (!(this.left.root instanceof Comparable)) return false;
if (!(this.right.root instanceof Comparable)) return false;
Comparable thisRoot = (Comparable)this.root;
Comparable leftRoot = (Comparable)left.root;
Comparable rightRoot = (Comparable)right.root;
if (thisRoot.compareTo(leftRoot) < 0) return false;
if (thisRoot.compareTo(rightRoot) > 0) return false;
return left.isBST() && right.isBST();

13.2

13.3

13.4

13.5

public boolean isAVL() {

if (!isBST()) return false;
int leftHeight = ( left!=null ? left.height() : -1 );
int rightHeight = ( right!=null ? right.height() : -1);
return (Math.abs(leftHeight - rightHeight) < 2);
}
public int getHeight() {
return height;
}
public AVLTree getLeft() {
if (this == NIL) throw new IllegalStateException();
return left;
}
public AVLTree getRight() {
if (this == NIL) throw new IllegalStateException();
return right;
}
public int getRoot() {
if (this == NIL) return -1;
return key;
}
public boolean contains(int x) {
if (this == NIL) return false;
if (key == x) return true;
return left.contains(x) || right.contains(x);
}
public AVLTree get(int x) {
public AVLTree get(int x) {
if (this == NIL || key == x) return this;

132

Chapter 13 Lists
if (x < key) return left.get(x);
return right.get(x);

13.6

13.7

}
public boolean equals(Object object) {
if (object == this) return true;
if (!(object instanceof AVLTree)) return false;
AVLTree that = (AVLTree)object;
if (that.key != this.key) return false;
if (that.height != this.height) return false;
return that.left.equals(this.left) &&
that.right.equals(this.right);
}
public AVLTree(int[] a) {
this(a[0]);
for (int i=1; i<a.length; i++)
add(a[i]);
}

Chapter 14
Heaps and Priority Queues
Exercises
14.1

14.2

14.3
14.4
14.5

14.6

a. Byte.MAX_VALUE (27 1 = 127)

b. Short.MAX_VALUE (231 1 = 2,147,483,647)
c. Long.MAX_VALUE (263 1 = 9,223,372,036,854,775,808)
d. Float.MAX_VALUE (2128 2104 3.41038 )
e. Double.MAX_VALUE (21024 2971 1.710308 )
a. (51, 25, 12, 5, 2, 0); lg51 = 5.67 = 5
b. (333, 166, 82, 40, 19, 9, 4, 1, 0); lg333 = 8.38 = 8
c. (1000, 499, 249, 124, 61, 30, 14, 6, 2, 0); lg1000 = 9.97 = 9
d. (1024, 511, 255, 127, 63, 31, 15, 7, 3, 1, 0); lg1024 = 10.0 = 10
Only trees b and e are heaps.
Only arrays b and d are heaps.
Let m = n/2 (integer division). Then n = 2m or 2m + 1, according to whether n is even or
odd. But in either case, 2m n. Now assume that i < n/2. Then i < m. Since n and m are
integers, it follows that i m 1. Thus, 2i + 1 2(m 1) + 1 = 2m 1 n 1 < n.
a. lg10 = 3.23 = 3
b. lg1000 = 9.97 = 9
c. lg1024 = 10.0 = 10
d. lg1,000,000 = 19.93 = 19

133

134

Chapter 14 Heaps and Priority

14.7
44

44

44

66

66

66

44

66
88

66

33
44

88

44

33

88

66

88

33

77

66

44

44

88

33
77

88

77
44

33

33

55

88

77

66

44

33
66

77

55

44

55
66

33

88
22

77
44

14.8

14.9
14.10
14.11
14.12

55
66

33

22

44

44

33

66 44 33

77

88 77 33 44 66

22

88 77 33 44 66 55 22

66

66 44

88

88 66 33 44

55

88 77 33 44 66 55

a. The worst case is when the array is in descending order.

b. The algorithm makes only 1 comparison in the bast case.
c. The best case is when the array is in ascending order.
The parent of the node at a[i] will be at a[i/2], and the children will be at a[2*i] and
a[2*i+1].
The parent of the node at a[i] will be at a[i/m], and the children will be at a[m*i],
a[m*i+1], a[m*i+2], ..., a[m*i+m-1].
Both methods run in logarithmic time: (lgn).

Solutions
14.13
14.14

14.15
14.16

135

If elements A, B, C, and D with keys 44, 44, 33, and 22, are inserted in that order, A will
be removed before B. But if their keys are 44, 44, 33, and 66, then B will be removed
before A.
Each iteration of the loop moves the larger child up to become the parent of its sibling.
The loop stops when neither child is greater than the original x value, which is copied into
the last position vacated by the loop. This renders the affected path descending, all the way
down to the leaf level. Since the first step of the loop moves the maximum element up into
the root, the precondition guarantees that all other root-to-leaf paths are now descending.
If S is a subtree of T, then every root-to-leaf path in S is part of some root-to-leaf path in T.
So if T is a heap, then every root-to-leaf path in S must be descending.
The derivation on page 419 shows that W(n) is the greatest number of comparisons that
the Build Heap algorithm can make on a hep of size n, where W(n) = 2W(n) + 2 lgn. We
show by direct substitution that f(n) = 5n 2 lgn 4 is a solution to this recurrence equation:
f(n 2) =
=
=
=
2f ( n 2 ) + 2lgn =
=
=
=

14.17

14.18

5 ( n 2 ) 2lg ( n 2 ) 4
5n 2 2 ( lgn lg2 ) 4
5n 2 2 ( lgn 1 ) 4
5n 2 2lgn 2
2 ( 5n 2 2lgn 2 ) + 2lgn
5n 4lgn 4 + 2lgn
5n 2lgn 4
f( n)

The inital value is f(1) = 5(1) 2 lg(1) 4 = 5 0 4 = 1, which satisfies W(1) = 1.

Let x be the largest element in a heap. If x has a parent, then its value cannot be less than x
because of the heap property. And since x is the maximum element, its parent cannot be
greater than x. Thus, if x has a parent, it must have the same value. By the same reasoning,
every ancestor of x must have the same value. The root is an ancestor of x. Thus, the root
has the maximum value.
a. l(i) = 2i + 1
b. r(i) = 2i + 2
c. l(i, k) = 2k(i + 1) 1
d. r(i, k) = 2k(i + 2) 2
e. a(i, k) = i/2k

136

Chapter 14 Heaps and Priority

Programming Problems
14.1

14.2

14.3

public boolean isHeap(int[] a, int size) {

return isHeap(a, 0, size);
}
public boolean isHeap(int[] a, int k, int size) {
if (k >= size/2) return true; // singletons are heaps
int left = 2*k + 1, right = left + 1;
if (a[k] < a[left]) return false;
if (a[k] < a[right]) return false;
return isHeap(a, left, size) && isHeap(a, left, size);
}
public boolean isHeap(int[] a, int size) {
for (int i=(size-1)/2; i<size; i++) {
int j=i;
while (j > 0) {
int pj=(j-1)/2; // a[pj] is the parent of a[j]
if (a[j] > a[pj]) return false;
j = pj;
}
}
return true;
}
import java.util.*;
public class UnsortedListPriorityQueue implements PriorityQueue {
private List list = new LinkedList();
public void add(Object object) {
if (!(object instanceof Comparable))
throw new IllegalArgumentException();
list.add(object);
}
public Object best() {
if (list.isEmpty()) throw new IllegalMonitorStateException();
Iterator it=list.iterator();
Comparable best = (Comparable)it.next();
while (it.hasNext()) {
Comparable x = (Comparable)it.next();
if (x.compareTo(best) > 0) best = x;
}
return best;
}

Solutions

137
public Object remove() {
Object best = best();
list.remove(best);
return best;
}
public int size() {
return list.size();
}

14.4

import java.util.*;
public class SortedListPriorityQueue implements PriorityQueue {
private List list = new LinkedList();
public void add(Object object) {
if (!(object instanceof Comparable))
throw new IllegalArgumentException();
if (list.isEmpty()) {
list.add(object);
return;
}
Iterator it=list.iterator();
Comparable x = (Comparable)object;
int i=0;
while (it.hasNext()) {
Comparable y = (Comparable)it.next();
if (y.compareTo(x) <= 0) break;
++i;
}
list.add(i, x);
}
public Object best() {
if (list.isEmpty()) throw new IllegalMonitorStateException();
return list.get(0);
}
public Object remove() {
return list.remove(0);
}
public int size() {
return list.size();
}
}

138
14.5

14.6

Chapter 14 Heaps and Priority

public class PriorityQueue {
private final int CAPACITY=100;
private boolean[][] q = new boolean[CAPACITY][CAPACITY];
private int[] len = new int[CAPACITY];
public void add(int x) {
if (x >= CAPACITY) throw new IllegalArgumentException();
if (len[x] >= CAPACITY) throw new IllegalStateException();
q[x][len[x]++] = true;
}
public int best() {
if (size() == 0) throw new IllegalStateException();
for (int i=CAPACITY-1; i>=0; i--) {
if (len[i] > 0) {
return i;
}
}
throw new IllegalStateException();
}
public int remove() {
if (size() == 0) throw new IllegalStateException();
for (int i=CAPACITY-1; i>=0; i--) {
if (len[i] > 0) {
--len[i];
return i;
}
}
throw new IllegalStateException();
}
public int size() {
int size = 0;
for (int i=0; i<CAPACITY; i++) {
size += len[i];
}
return size;
}
}
public class TestHeapify {
public TestHeapify() {
int[] a = {33,88,77,52,66,73,75,44,48,69};
int n = a.length;
IntArrays.print(a);
heapify(a, 0, n);

Solutions

139
IntArrays.print(a);
}
public static void main(String[] args) {
new TestHeapify();
}
void heapify(int[] a, int i, int n) {
if (i >= n/2) return;
// a[i] is a leaf
int j = 2*i + 1;
if (j+1 < n && a[j+1] > a[j]) ++j;
if (a[j] <= a[i]) return;
int ai = a[i];
a[i] = a[j];
a[j] = ai;
heapify(a, j, n);
}

14.7

}
public class PQStack implements Stack {
private PriorityQueue pq = new HeapPriorityQueue();
private static int nextIndex;
private static class PQElement implements Comparable {
Object object;
int index;
PQElement(Object object) {
this.object = object;
this.index = PQStack.nextIndex++;
}
public int compareTo(Object object) {
PQElement that = (PQElement)object;
Long diff = new Long(this.index - that.index);
return diff.intValue();
}
}
public void push(Object object) {
pq.add(new PQElement(object));
}
public Object peek() {
PQElement e = (PQElement)pq.best();
return e.object;
}
public boolean isEmpty() {
return pq.size()==0;
}

140

Chapter 14 Heaps and Priority

public Object pop() {
PQElement e = (PQElement)pq.remove();
return e.object;
}
public int size() {
return pq.size();
}

14.8

}
public class PQQueue implements Queue {
private PriorityQueue pq = new HeapPriorityQueue();
private static int nextIndex;
private static class PQElement implements Comparable {
Object object;
int index;
PQElement(Object object) {
this.object = object;
this.index = PQQueue.nextIndex++;
}
public int compareTo(Object object) {
PQElement that = (PQElement)object;
Long diff = new Long(that.index - this.index);
return diff.intValue();
}
}
public void add(Object object) {
pq.add(new PQElement(object));
}
public Object first() {
PQElement e = (PQElement)pq.best();
return e.object;
}
public boolean isEmpty() {
return pq.size()==0;
}
public Object remove() {
PQElement e = (PQElement)pq.remove();
return e.object;
}
public int size() {
return pq.size();
}
}

Solutions
14.9

141

public class PriorityQueue {

private final int CAPACITY=100;
private int[] a = new int[CAPACITY];
private int size;
public void add(int x) {
if (size == CAPACITY) throw new IllegalArgumentException();
a[size++] = x;
}
public int best() {
return a[indexOfBest()];
}
public int remove() {
if (size() == 0) throw new IllegalStateException();
int b=indexOfBest();
int best = a[b];
--size;
for (int i=b; i<size; i++)
a[i] = a[i+1];
return best;
}
public int size() {
return size;
}
private int indexOfBest() {
if (size() == 0) throw new IllegalStateException();
int b=0;
for (int i=1; i<size; i++)
if (a[i] >= a[b]) b = i;
return b;
}

14.10

}
public class PriorityQueue {
private Node start = new Node(0, null);
private int size;
public void add(int x) {
start.next = new Node(x, start.next);
++size;
}
public int best() {
return predecessorOfBest().next.key;
}

// dummy

142

Chapter 14 Heaps and Priority

public int remove() {
Node b = predecessorOfBest();
int best = b.next.key;
b.next = b.next.next;
--size;
return best;
}
public int size() {
return size;
}
private Node predecessorOfBest() {
if (size==0) throw new IllegalStateException();
Node b = start;
for (Node p=b.next; p.next!=null; p = p.next)
if (p.next.key > b.next.key) b = p;
return b;
}
private static class Node {
int key;
Node next;
Node(int key, Node next) {
this.key = key;
this.next = next;
}
}
}

Chapter 15
Sorting
Exercises
15.1

a. Bubble Sort:
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
C
O
M
P
U
T
E
R
1
M
O
2
T
U
3
E
U
4
R
U
5
E
T
6
R
T
7
E
P
8
E
O
9
C
E
M
O
P
R
T
U
0

b. Selection Sort:
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
C
O
M
P
U
T
E
R
1
R
U
2
E
T
3
E
R
4
E
P
5
C
E
M
O
P
R
T
U
0

143

144

Chapter 15 Sorting
c. Insertion Sort:
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
C
O
M
P
U
T
E
R
1
M
O
2
T
U
3
E
M
O
P
T
U
4
C
E
M
O
P
R
T
U
0

d. Shell Sort:
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
C
O
M
P
U
T
E
R
1
E
M
2
M
U
3
R
T
4
E
O
5
M
O
P
6
C
E
M
O
P
R
T
U
0

e. Merge Sort:
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
C
O
M
P
U
T
E
R
1
T
U
2
M
O
E
R
T
U
3
C
E
M
O
P
R
T
U
0

f. Quick Sort:
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
C
O
M
P
U
T
E
R
1
C
2
E
O
P
3
R
U
4
C
E
M
O
P
R
T
U
0

g. Heap Sort:
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
0

1
3
5
6
7

2
4

P
R

U
C
T
E

U
R

R
P

M
O
P

C
U
C
T

Solutions

145

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]

8
9
10
11
12
13
14
15
16
17

15.2

R
C
P
C
O
C
M
C
E
C

O
R

C
P

C
O
C
M

C
E

h. Bucket Sort:
a = 'A', b 1 = 'Z', b a = 26, n = 8, x = 26/8 = 3.25:
C, O, M, P, U, T, E, R
Bucket #0 ('A' through 'C'): C
Bucket #1 ('D' through 'F'): E
Bucket #2 ('G' through 'I'):
Bucket #3 ('J' through 'L'):
Bucket #4 ('M' through 'P'): O, M, P M, O, P
Bucket #5 ('Q' through 'S'): R
Bucket #6 ('T' through 'V'): U, T T, U
Bucket #7 ('W' through 'Z'):
C, E, M, O, P, R, T, U
a. Bubble Sort:
0

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

a[8]

I
G

G
I
C

O
T

U
E

1
2

a[9] a[10] a[11]

E

4
5
6

U
R

T
R

11
12
13
14
15

U
S

10

16

E
G

E
I
I

E
M
M

E
O

T
S

146

Chapter 15 Sorting
b. Selection Sort:
0

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

a[8]

U
S

2
3

E
O

E
I

6
7
8

a[9] a[10] a[11]

E
P

S
U

T
S

C
E

G
G

c. Insertion Sort:
0

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

a[8]

I
G
C

G
I
G

O
U
T
S

U
T

1
2

T
P

U
T
R
R

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

a[8]

P
E

4
5
6
7

a[9] a[10] a[11]

d. Shell Sort:
0
1

E
P

G
C

U
S

I
G

M
I

O
M

P
P

R
R

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

a[8]

I
G

G
I

I
E
O

T
P
P

U
R
R

S
S

T
T

U
U

4
5
6
7
8
9

a[9] a[10] a[11]

S
S

e. Merge Sort:
0
1
2
3
4
5
6

a[9] a[10] a[11]

Solutions

147

f. Quick Sort:
0

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

a[8]

I
E
C

O
I

G
O

1
2
3

S
R

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

a[8]

M
S

3
4

a[9] a[10] a[11]

E
O
U
R
S

T
T

U
U

g. Heap Sort:
0
1

7
8
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

U
G
T
G
S
E
R
B
P
C
O
G
M
B
I
B
G
C
E
B
C
B

U
T

S
M

R
O

a[9] a[10] a[11]

T
I

I
B
U

G
T

G
S

E
R
M

B
P

C
O
G
M

B
I
B
G

C
E
B
C

148

15.3

Chapter 15 Sorting
h. Bucket Sort:
a = 'A', b 1 = 'Z', b a = 26, n = 12, x = 26/12 = 3.17:
B, I, G, C, O, M, P, U, T, E, R, S
Bucket #0 ('A' and 'B'):B
Bucket #1 ('C' and 'D'):C
Bucket #2 ('E' and 'F'):E
Bucket #3 ('G' and 'H'):G
Bucket #4 ('I' and 'J'):I
Bucket #5 ('K', 'L', and 'M'):M
Bucket #6 ('N' and 'O'):O
Bucket #7 ('P' and 'Q'): P
Bucket #8 ('R' and 'S'):R, S
Bucket #9 ('T' and 'U'):U, T T, U
Buckets #10 ('V' and 'W') and #11 ('X', 'Y', and 'Z') are empty
B, C, E, G, I, M, O, P, R, S, T, U
a. Bubble Sort:
0
1

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

77
44

44
77
22

22

88

99

55

33

66

55

99
33

99
66

99

77

3
4
5
6

22

44
55

7
8

88
33

55

10
11

77
33

12

77
66

77

88

22

33

33
44

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

77

44

22

88

99
66

55

33

66
99

13
14

88
66

55
55

66

77

88

99

b. Selection Sort:
0
1

33

2
3
4

55
33

5
6

22

88
77

55
22
33

44
44

55

66

77

88

99

Solutions

149

c. Insertion Sort:
0
1
2

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

77
44
22

44
77
44

22

88

99

55

33

66

22

33
33

77
55
44
44

77
55
55

88
77
66

99
88
77

99
88

99

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

77

44

22

88
66

99

55

33

66
88

3
4
5

d. Shell Sort:
0
1
2

22

77
33

77
55

33

44

22

33

44

55

66
66

77
77

88

99

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

77
44
22

44
77
44

22

88

99

55

33

66

99
55
77

66
88

99
99

5
6
7

99
66

e. Merge Sort:
0
1
2

77

22

33

44

55

55
33
66

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

77
66
55
33
22
22

44

22

88
33

99
55
66

55
77

33
99

66
88

33
33

44
44

66

77

88

99

3
4
5

f. Quick Sort:
0
1
2
3
4
5

55
55

150

Chapter 15 Sorting

g. Heap Sort:
0

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

77

44

22
55

88

99

55
22

33

66

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

15.4

99
66
88
33
77
22
66
22
55
33
44
22
33
22

99
88

77

44

77

66

66

33

99
88
77
44

22
66
22
55

33
33
22
33

44
44

55

66

77

88

99

h. Bucket Sort:
a = 0, b = 100, b a = 100, n = 8, x = 100/8 = 12.5:
77, 44, 22, 88, 99, 55, 33, 66
Bucket #0 (0 12):
Bucket #1 (13 24):22
Bucket #2 (25 37):33
Bucket #3 (38 49):44
Bucket #4 (50 62):55
Bucket #6 (63 74):66
Bucket #7 (75 87):77
Bucket #8 (88 99):88, 99
22, 33, 44, 55, 66, 77, 88, 99
a. Bubble Sort:
0

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

61

83
38

38
83
52

52

94

47

29

76

47

94
29

94
76

94

1
2
3
4
5
6

38

61

83

Solutions

151

a[0]
7

a[1]

a[2]

52

61

a[3]

a[4]

47

83
29

9
10

47

11
12

47

29

29
38

52
29
47
47

a[0]

a[1]

61

83

13
14
15
16

61
29

a[5]

a[6]

83
76

83

a[7]

61

52
52

61

76

83

94

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

38

52

94
76

47

29

76
94

47
61

76

b. Selection Sort:
0
1

29

83

3
4
5
6

47
38
29

38

47
47

52

61

76

83

94

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

61
38

38
83
61
52
47
47

52

94

47

29

76

29
29

83
61
52
47
38
38

83
61
52
52

83
61
61

94
83
76

94
83

94

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

61

83
47

38

52

94

47
83

29

76

c. Insertion Sort:
0
1
2
3
4
5

d. Shell Sort:
0
1

29
61
38

2
3

29

38
61

6
7

94
76

29

38
38

47
47

52

61

76

83
83

94

152

Chapter 15 Sorting
e. Merge Sort:
0
1

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

61
38

83
52

38
61

52
83

94

47

29

76

94
47
76

76
83

94
94

29

38

47

52

47
29
61

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

61
29

38

52

94
61

47
94

29
83

76

29

83
47
38
38

47
47

52

61

76

83

94

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

61

83

38

52
76

94

47

29

76
52

2
3
4

f. Quick Sort:
0
1
2
3

g. Heap Sort:
0
1

47

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

94
52
83
29
76
38
61
29
52
29
47
29
38
29

38

94
83

83
61
94

76

52
83

61
52
44

29
76
38
61

38

33
29
38

29
52
29
47
47

52

61

76

83

94

Solutions

15.5

153

h. Bucket Sort:
a = 0, b = 100, b a = 100, n = 8, x = 100/8 = 12.5:
61, 83, 38, 52, 94, 47, 29, 76
Bucket #0 (0 12):
Bucket #1 (13 24):
Bucket #2 (25 37):29
Bucket #3 (38 49):38, 47
Bucket #4 (50 62):61, 52 52, 61
Bucket #6 (63 74):
Bucket #7 (75 87):83, 76 76, 83
Bucket #8 (88 99):94
29, 38, 47, 52, 61, 76, 83, 94
a. Bubble Sort:
0
1

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

22
22

33
33

44
44

55
55

66
66

77
77

88
88

99
99

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

22
22

33
33

44
44

55
55

66
66

77
77

88
88

99
99

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

22
22

33
33

44
44

55
55

66
66

77
77

88
88

99
99

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

22
22

33
33

44
44

55
55

66
66

77
77

88
88

99
99

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

22
22

33
33

44
44

55
55

66
66

77
77

88
88

99
99

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

22
22

33
33

44
44

55
55

66
66

77
77

88
88

99
99

b. Selection Sort:
0
1

c. Insertion Sort:
0
1

d. Shell Sort:
0
1

e. Merge Sort:
0
1

f. Quick Sort:
0
1

154

Chapter 15 Sorting

g. Heap Sort:
0

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

22

33

44

55
99

66

77

88

99
55

88

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

99
33
88
44
77
33
66
22
55
22
44
22
33
22

99
66

44
55

33
22
99

77

33
88

44
77
55

33

33

22
55

66

22
44
22
33

44

55

h. Bucket Sort:
a = 0, b = 100, b a = 100, n = 8, x = 100/8 = 12.5:
22, 33, 44, 55, 66, 77, 88, 99
Bucket #0 (0 12):
Bucket #1 (13 24):22
Bucket #2 (25 37):33
Bucket #3 (38 49):44
Bucket #4 (50 62):55
Bucket #6 (63 74):66
Bucket #7 (75 87):77
Bucket #8 (88 99):88, 99
22, 33, 44, 55, 66, 77, 88, 99

66

77

88

99

Solutions
15.6

155

a. Bubble Sort:
0
1

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

99
88

88
99
77

77

66

55

44

33

22

99
22

99

2
3

99
66

99
55

99
44

99
33

7
8

77

88
66

10

88
55

11

88
44

12

88
33

13
14

66

15

77
55

16

77
44

17

77
33

18
19

55

20

66
44

21

66
33

22
23

44

55
33

77

66

55

22

44
22
33

44
44

55

66

77

88

99

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

99
22

88

77

66

55

44

33

22
99

66

77
77

25

33

27
28

88

55
22

24
26

66
22

77
22

88
22

b. Selection Sort:
0
1

33

2
3
4

22

33

88
44
44

55

88

99

156

Chapter 15 Sorting
c. Insertion Sort:
0
1
2
3
4
5
6
7

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

99
88
77
66
55
44
33
22

88
99
88
77
66
55
44
33

77

66

55

44

33

22

99
88
77
66
55
44

99
88
77
66
55

99
88
77
66

99
88
77

99
88

99

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

99
55

88

77

66

55
99

44

33

22

d. Shell Sort:
0
1

44

88
33

3
5

77
22

33

66

55
77

22

66

8
9

22

88

33

10

44

55

22

33

44

55

66
66

77
77

88

99

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

99
88

88
99

77

66

55

44

33

22

66

77
44

55
22

33

11
12

99

44

e. Merge Sort:
0
1
2
3
4
5

66

77

88

99

22

33

44

55

22
66

33
77

44
88

55
99

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

99
22

88

77

66

55

44

33

22
99

66

77
77

6
7

f. Quick Sort:
0
1

33

2
3
4

22

33

88
44
44

55

88

99

Solutions

157

g. Heap Sort:
0
1
2
3
4
5
6
7
8
9
10
11
12
13

a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

99
22
88
33
77
33
66
33
55
22
44
22
33
22

88

77

66

55

44

33

22
99

66

22
88
44

33
77

55

33
66

33
55
33
22
33

22
44
44

55

h. Bucket Sort:
a = 0, b = 100, b a = 100, n = 8, x = 100/8 = 12.5:
99, 88, 77, 66, 55, 44, 33, 22
Bucket #0 (0 12):
Bucket #1 (13 24):22
Bucket #2 (25 37):33
Bucket #3 (38 49):44
Bucket #4 (50 62):55
Bucket #6 (63 74):66
Bucket #7 (75 87):77
Bucket #8 (88 99):88, 99
22, 33, 44, 55, 66, 77, 88, 99

66

77

88

99

158
15.7

Chapter 15 Sorting
a. Selection Sort:
0

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

1
0

0
0

1
1

1
2
3

[9] [10] [11] [12] [13] [14] [15]

0
1

b. Insertion Sort:
0

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

1
0

0
1
0

1
2
3

1
0

1
1

0
0

5
6

1
0

[9] [10] [11] [12] [13] [14] [15]

c. Merge Sort:
0

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

1
0

0
1

1
2

0
1

[9] [10] [11] [12] [13] [14] [15]

0

0
1
1

5
6

0
1

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

1
0

0
0

1
1

0
1

d. Quick Sort:
0
1
2
3

[9] [10] [11] [12] [13] [14] [15]

0
1

Solutions

159

e. Counting Sort:
a = {0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0}, n = 16, m = 2,
c = {7, 9} c = {7, 16}

15.8

k = ai

15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

0
1
1
1
1
1
0
0
1
0
1
1
0
0
1
0

c0

c1

7
6

16

j = ck bj = k
6
15
14
13
12
11
5
4
10
3
9
8
2
1
7
0

15
14
13
12
11
5
4
10
3
9
8
2
1
7
0

0
1
1
1
1
1
0
0
1
0
1
1
0
0
1
0

b = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1}
a. Selection Sort:
0

US CA CN US
1 ES
2
AU
3
4
5
6
7
8
9
10 CN
11
12 AU CA CN CN
0

10 11 12 13 14 15 16 17 18 19

GB JA FR CN US DE JA GB US CN US IT AU ES US US
US
US
IT
US
CN US
CN
JA
GB JA
GB
IT
DE
GB
CN FR
ES
CN DE
CN DE ES FR GB GB IT JA JA US US US US US US US

160

Chapter 15 Sorting
b. Insertion Sort:
0

US CA
1 CA US
2
CN
3
4
5
6
7
8
9
10
11
12 AU CA
13 AU CA
0

10 11 12 13 14 15 16 17 18 19

CN US GB JA FR CN US DE JA GB US CN US IT AU ES US US
US
GB

US
JA
US
FR GB JA
US
CN FR GB JA
US
DE FR GB JA
US
JA
US
GB
JA
US
CN DE FR
GB
JA
US
IT
JA
US
CN DE FR
GB IT
JA
US
CN CN CN DE ES FR GB GB IT JA JA US US US US US US US

c. Merge Sort:
0

US CA CN US
1 CA US
2
GB
3
CN GB US
4
5
6
7
CN DE
8
9
10
11
11
12
13
14 AU CA CN CN
0

10 11 12 13 14 15 16 17 18 19

GB JA FR CN US DE JA GB US CN US IT AU ES US US
US
FR JA
DE US
CN DE FR JA
FR GB JA US US
GB JA
CN US
CN GB JA
AU IT
ES IT
AU CN ES GB IT JA US US
CN DE ES FR GB GB IT JA JA US US US US US US US

d. Quick Sort:
0

10 11 12 13 14 15 16 17 18 19

US CA CN US GB JA FR CN US DE JA GB US
1 ES
2 AU
CN DE CN ES FR
JA
3
CN DE
4
IT
5
GB GB IT JA
6 AU CA CN CN CN DE ES FR GB GB IT JA JA
0

CN US IT AU ES US US
US
GB
US
US
JA
US US US US US US US

Solutions

161

e. Counting Sort:
a = {US, CA, CN, US, GB, JA, FR, CN, US, DE, JA, GB, US, CN, US, IT, AU, ES, US, US},
n = 20, m = 10:

i
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

15.9

ai
US
US
ES
AU
IT
US
CN
US
GB
JA
DE
US
CN
FR
JA
GB
US
CN
CA
US

k
9
9
4
0
7
9
2
9
6
8
3
9
2
5
8
6
9
2
1
9

Key

ck

ck.

0
1
2
3
4
5
6
7
8
9

AU
CA
CN
DE
ES
FR
GB
IT
JA
US

1
1
3
1
1
1
2
1
2
7

1
2
5
6
7
8
10
11
13
20

c0

c1

c2

c3

c4

c5

c6

c7

c8

c9 j = ck bj = ai

10

11

13

20
19
18

6
0
10
17
4
16
9
12
5
15
3
7
11
8
14
2
1
13

19
18
6
0
10
17
4
16
9
12
5
15
3
7
11
8
14
2
1
13

b = {AU, CA, CN, CN, CN, DE, ES, FR, GB, GB, IT, JA, JA, US, US, US, US, US, US, US}
If t = c n2 and n = 2n, then t = c(n)2 = c(2n)2 = (4)(c n2 ) = 4t;
i.e., the time for an array of length 2n will be about 4 times as long.
a. 4(5 ms) = 20 ms
b. 4(20) ms = 80 ms
c. 4(80) ms = 320 ms
d. 4(320) ms = 1280 ms = 1.26 s

US
US
ES
AU
IT
US
CN
US
GB
JA
DE
US
CN
FR
JA
GB
US
CN
CA
US

162
15.10

15.11

15.12

15.13

Chapter 15 Sorting
If t = c n lgn and n = n2, then t = c n lgn = c (n2)lg(n2) = (2n)(c n lgn) = (2n) t;
i.e., the time for an array of length n2 will be about 2n times as long.
a. 2(200)(3 s) = 1200 s = 1.2 ms
b. 2(40,000)(1.2 ms) = 96,000 ms = 1600 s = 26 min 40 s
If t = c n and n = 2n, then t = c(n) = c(2n) = (2)(c n) = 2t ;
i.e., the time for an array of length 2n will be about twice as long.
a. 2(7 ms) = 14 ms
b. 2(14 ms) = 28 ms
c. 2(28 ms) = 56 ms
d. 2(56 ms) = 112 ms
If t = c n lgn and n = 2n,
then t = c n lgn = c (2n)lg(2n) = 2(c n lgn)(lg(2n)/lgn = 2t lg(2n)/lgn.
But lg(2n) = lg2 + lgn = 1 + lgn, so lg(2n)/lgn = (1 + lgn)/lgn = 1 + 1/lgn.
Thus, t = 2t (1 + 1/lgn).
With n = 1,000,000, 1/lgn = log 2/logn = 0.301/6 = 0.05.
Thus, t = 2t (1 + 0.05) = 2(20 ms)(1.05) = 42 ms.
Here is Listing 15.3:
void sort(int[] a) {
for (int i = a.length-1; i > 0; i--) {
3
for (int j = 0; j < i; j++)
4
if (a[j] > a[j+1]) swap(a, j, j+1);
5
// INVARIANTS: a[i] = max{a[0..i]};
6
}
7
// INVARIANT: a[i..a.length) is in ascending order;
8
}
From lines 34, we know that a[j] a[j+1] for all j < i.
Thus: a[0] a[1] a[2] ... a[i].
Therefore, a[i] = max{a[0], a[1], a[2], ..., a[i]} = max{a[0..i]}.
1
2

15.14
15.15

Continuing from the solution to Exercise 15.13:

From line 2, we see that the invariant on line 6 holds for each i > 0, including
i = a.length-1. Thus: a[0] a[1] a[2] ... a[i] ... a[a.length-1].
Algorithm. Descending Bubble Sort
1.Repeat steps 23 for i = n 1 down to 1:
2.
Repeat step 3 for j = 0 up to i 1.
3.
If a j < a j+1 , swap them.

Solutions
15.16

15.17
15.18

15.19

163

Algorithm. An Improved Bubble Sort

1.Initialize a flag to false.
2. Let i = n 1.
3. Repeat steps 4-8 while the flag is false.
4.
Set the flag to true.
5.
Repeat step 6 for j = 0 up to i 1.
6.
If a j > a j+1 , swap them and reset the flag to false.
7.
If i = 1, return.
8.
Decrement i.
With this improvement, the algorithm will terminate as soon as the inner repeat loop (steps
6-7) is able to iterate without making a swap. Consequently, in the bast case, where the list
is already in ascending order, the main loop (steps 3-8) will iterate only once, thereby running in linear time: (n).
The worst case is still (n 2 ).
Algorithm. Selection Sort
1.Repeat step 2 for i = 0 up to n 2.
2. Swap a i with min{a i ... a n1 }.
Algorithm. External Selection Sort
1.Open a new temporary file named temp for writing.
2. Open the specified file, henceforth called specFile, for reading.
3. Read through specFile to obtain its number of lines n.
4. Repeat steps 511 for i = 0 to n 2.
5.
Reset specFile to be read again from its beginning.
6.
Read the first i lines of specFile.
7.
Read the next line of specFile into a string named line.
8.
Repeat lines 910 as long as specFile has more lines:
9.
Read the next line of specFile into a string named nextLine.
10.
If nextLine alphabetically precedes line, copy it into line.
11.
Write line to the end of the temp file.
12. Copy the last line of specFile to temp.
13. Close both files.
14. Open the temp file for reading.
15. Open the specFile for writing.
16. Copy all n lines from temp to specFile.
17. Close both files.
The Indirect Insertion Sort:
1
2
3
4
5
6
7

int[] sort(int[] a, int[] k) {

int[] k = new int[a.length];
for (int i = 0; i < k.length; i++) {
k[i] = i;
for (int i = 1; i < a.length; i++) {
int ai = a[i], j = i;
for (j = i; j > 0 && a[k[j-1]] > ai; j--)

164

Chapter 15 Sorting
k[j] = k[j-1];
k[j] = ai;

8
9

10
11

15.20

The Merge Sort for Linked Lists:

1
2
3
4
5
6
7

Node sorted(Node list) {

if (list == null || list.next == null) return list;
// temporarily add a dummy head node:
Node temp = new Node(0, list);
sort(temp);
return temp.next;
}

8
9
10
11
12
13
14
15
16
17

// recursively sorts the data from p.next to q:

void sort(Node left) {
if (left.next==null || left.next.next==null) return;
Node right = new Node(0, null);
split(left, right);
sort(left);
sort(right);
merge(left, right);
}

18
19
20
21
22
23
24
25
26
27
28

// cuts left in two, returning second half in right:

void split(Node left, Node right) {
Node p=left, q=p.next;
while (q != null && q.next != null) {
p = p.next;
q = q.next.next;
}
right.next = p.next;
p.next = null;
}

29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// merges left and right into left:

void merge(Node left, Node right) {
if (right.next==null) return;
Node pp=left, p=pp.next, q=right.next;
while (p != null && q != null) {
if (p.data < q.data) {
pp = p;
p = p.next;
} else {
pp = pp.next = q;
q = q.next;
pp.next = p;
}
}

Solutions

165
pp.next = (p==null? q: p);

44
45

15.21

The Shell Sort for subarrays:

1
2
3
4
5

15.22

}
void sort(int[] a, int p, int q) {
for (int d = (q-p)/2; d > 0; d /= 2)
for (int c = p; c < p+d; c++)
iSort(a, c, d);
}

Here is the code from Listing 15.12 on page 460:

1
2
3
4
5
6
7
8

void sort(int[] a) {
for (int i = (a.length-1)/2; i >= 0; i--)
heapify(a, i, a.length);
for (int j = a.length-1; j > 0; j--) {
swap(a, 0, j);
heapify(a, 0, j);
}
}

The steps in the trace in Figure 15.11 are numbered. This line that each is executing is
shown in the following table:
Step
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Line
3:
3:
3:
5:
6:
5:
6:
5:
6:
5:
6:
5:
6:
5:

heapify() at a[3]
heapify() at a[1]
heapify() at a[0]
swap() a[0] with a[7]
heapify() at a[0]
swap() a[0] with a[6]
heapify() at a[0]
swap() a[0] with a[5]
heapify() at a[0]
swap() a[0] with a[4]
heapify() at a[0]
swap() a[0] with a[3]
heapify() at a[0]
swap() a[0] with a[2]

166
15.23

15.24

15.25

15.26

Chapter 15 Sorting

Algorithm. A Modified Shell Sort

1.Let d = 1.
2. Repeat step 3 while d < n.
3.
Set d = 3d + 1.
4. Set d = (d 1) / 3.
5. Repeat steps 67 while d > 0.
6.
Apply the insertion sort to each of the d subsequences
{a0 , ad , a2d , a3d , . . .}
{a1 , ad+1 , a2d+1 , a3d+1 , . . .}
{a2 , ad+2 , a2d+2 , a3d+2 , . . .}
:
{ad 1 , a2d 1 , a3d 1 , a4d 1 , . . .}
7.
Set d = (d 1) / 3.
a. The Insertion Sort.
b. The Selection Sort.
c. The Heap Sort.
d. The Heap Sort.
Algorithm. The Shaker Sort
1.Let p = 0 and q = n 2.
2. Repeat steps 310 forever:
3.
Repeat step 4 for i = p up to q.
4.
If a i > a i+1 , swap them.
5.
Decrement q.
6.
If p = q, return.
7.
Repeat step 8 for j = q down to p.
8.
If a j > a j+1 , swap them.
9.
Increment p.
10.
If p = q, return.
This has the same complexity as the Bubble Sort: each element must make the same number of swaps to be moved into position because only adjacent elements are swapped.
Algorithm. The Parity Transport Sort
1.Repeat steps 29 n/2 times.
2.
Let i = 0.
3.
Repeat steps 45 while i < n 2.
4.
If a i > a i+1 , swap them.
5.
Increment i by 2.
6.
Let j = 1.
7.
Repeat steps 89 while j < n 3.
8.
If a j > a j+1 , swap them.
9.
Increment j by 2.
This has the same complexity as the Bubble Sort: each element must make the same number of swaps to be moved into position because only adjacent elements are swapped.

Solutions
15.27

15.28

15.29

15.30

15.31

167

Algorithm. The Exchange Sort

1.Repeat steps 23 for i = n 1 down to 1.
2. Repeat step 3 for j = 0 up to i 1.
3.
If a j > a i , swap them.
This has the same complexity as the Selection Sort, which is better than the Bubble Sort.
Algorithm. The Binary Insertion Sort
1.Do Steps 25 for i = 1 to n1.
2.
Hold the element ai in a temporary space.
3.
Use the Binary Search to find an index j i for which ak ai when k j
and for which ak ai when j k i.
4.
Shift the subsequence {aj , ..., ai1 } up one position, into {aj+1 , ..., ai }.
5.
Copy the held value of ai into aj .
This is more efficient than the Insertion Sort because the Binary Search makes frwer comparisons than the Sequential Search. However, it the same number of data movements.
Algorithm. The Binary Tree Sort
1.Do Step 2 for i = 0 to n1.
2.
Use Algorithm 13.2 to insert the element ai into the BST T.
3. Use Algorithm 12.4 to traverse T, copying each element sequentially back
into the sequence {a0 , ..., an1 }.
The average case for this algorithm is comparable to the Heap Sort. By Formula 13.3,
insertions take about 1.39 lgn steps, so steps 12 will take about 1.39n lgn = (n lgn)
steps. But in the worst case, it becomes (n 2 ) because the BST degrades into a linked list.
That is much worse than the Heap Sort. Of course, if an AVL tree or a red-black tree
implementation is used, then this algorithm remains competetive with the Heap Sort even
in the worst case.
There are n! permutations of the a sequence of size n. Each one would require n 1 comparisons to determine whether that permutation is the correct (sorted) sequence. Thus, the
average complexity function is n n!/2. By Stirlings Formula (Formula C.10 on page 576),
this is exponential: O(2 n ).
Algorithm. The Tournament Sort
1.Allocate an auxiliary sequence {b i } of size 2n.
2. Do Step 3 for i = 0 up to n1.
3.
Copy a i into b n+i .
4. Do Steps 511 for i = n1 down to 0.
5.
Let m = n.
6.
While m > 1, repeat steps 79.
7.
Repeat step 8 for j = m/2 up to m 1.
8.
Copy the larger of b 2j and b 2j+1 into b j .
9.
Divide m by 2.
10.
Copy b0 into ai .
11.
Find the value b0 among {bn, ..., b2n1 } and change it to .

168

15.32
15.33
15.34
15.35

Chapter 15 Sorting

This is comparable to the Bubble Sort. The loop in steps 69 makes n1 comparisons and
n1 copies.
Among the ten sorting algorithms presented in this book, only the Selection Sort, the
Quick Sort, and the Heap Sort are unstable. Moreover, the Selection Sort can easily be
modified to make it stable.
The Shell Sort, Merge Sort, Quick Sort, Bucket Sort, and Counting Sort are parallelizable.
Anns program crashes because it is using the Quick Sort on a large array that contains at
least 99,000 duplicates. That array is nearly sorted already, causing the Quick Sort to run
in nearly (n 2 ) time.
The main loop of the Selection Sort iterates n 1 times. On iteration i, it finds the maximum element among the subsequence {a0, ..., ai} and then swaps it with ai . That requires
searching through all i + 1 elements of the subsequence. Thus the total number of comparisons made is C = (n 1) + (n 1) + ... + 2 + 1 = n(n 1)/2 = (n 2 ). [See Formula C.6
on page 572.]

Solutions

169

Programming Problems
15.1

package chap15.prob01;
import chap03.list08.IntArrays;
public class TestBubbleSort {
public TestBubbleSort() {
int[] a = {66, 33, 99, 88, 44, 55, 22, 77};
IntArrays.print(a);
sort(a);
}
void sort(int[] a) {
for (int i = a.length-1; i > 0; i--)
for (int j = 0; j < i; j++)
if (a[j] > a[j+1]) {
IntArrays.swap(a, j, j+1);
IntArrays.print(a);
}
}
public static void main(String[] args) {
new TestBubbleSort();
}

15.2

}
package chap15.prob02;
import chap03.list08.IntArrays;
public class TestSelectionSort {
public TestSelectionSort() {
int[] a = {66, 33, 99, 88, 44, 55, 22, 77};
IntArrays.print(a);
sort(a);
}
void sort(int[] a) {
for (int i = a.length-1; i > 0; i--) {
int m=0;
for (int j = 1; j <= i; j++) {
if (a[j] > a[m]) m = j;
}
IntArrays.swap(a, i, m);

170

Chapter 15 Sorting
IntArrays.print(a);
}
}
public static void main(String[] args) {
new TestSelectionSort();
}
}

15.3

15.4

15.5

void sort(int[] a) {
for (int i = a.length-1; i > 0; i--)
bubbleUp(a, i);
}
void bubbleUp(int[] a, int i) {
for (int j = 0; j < i; j++)
if (a[j] > a[j+1])
IntArrays.swap(a, j, j+1);
}
public TestBubbleSort() {
int[] a = IntArrays.randomInts(N, N);
System.out.println("sorted: " + IntArrays.isSorted(a));
sort(a);
System.out.println("sorted: " + IntArrays.isSorted(a));
}
package chap15.prob05;
import chap03.list08.IntArrays;
public class TestBubbleSort {
final int N = 4000;
public TestBubbleSort() {
int[] a = IntArrays.randomInts(N, N);
System.out.println("sorted: " + IntArrays.isSorted(a));
sort(a);
System.out.println("sorted: " + IntArrays.isSorted(a));
}
void sort(int[] a) {
for (int i = a.length-1; i > 0; i--)
for (int j = 0; j < i; j++)
if (a[j] > a[j+1])
IntArrays.swap(a, j, j+1);

Solutions

171
}
public static void main(String[] args) {
new TestBubbleSort();
}

15.6

15.7

void sort(int[] a) {
boolean done = false;
for (int i = a.length-1; i > 0 && !done; i--) {
done = true;
for (int j = 0; j < i; j++) {
if (a[j] > a[j+1]) {
IntArrays.swap(a, j, j+1);
done = false;
}
}
}
}
package chap15.prob07;
import chap03.list08.IntArrays;
public class TestBubbleSort {
final int N = 4000;
public TestBubbleSort() {
int[] a = IntArrays.randomInts(N, N);
System.out.println("sorted: " + IntArrays.isSorted(a));
System.out.println("sort1() time: " + sort1(a));
System.out.println("sorted: " + IntArrays.isSorted(a));
a = IntArrays.randomInts(N, N);
System.out.println("sorted: " + IntArrays.isSorted(a));
System.out.println("sort2() time: " + sort2(a));
System.out.println("sorted: " + IntArrays.isSorted(a));
}
long sort1(int[] a) {
long t1 = System.currentTimeMillis();
boolean done = false;
for (int i = a.length-1; i > 0 && !done; i--) {
done = true;
for (int j = 0; j < i; j++) {
if (a[j] > a[j+1]) {

172

Chapter 15 Sorting
IntArrays.swap(a, j, j+1);
done = false;
}
}
}
long t2 = System.currentTimeMillis();
return t2 - t1;
}
long sort2(int[] a) {
long t1 = System.currentTimeMillis();
boolean done = false;
for (int i = a.length-1; i > 0 && !done; i--) {
done = true;
for (int j = 0; j < i; j++) {
if (a[j] > a[j+1]) {
IntArrays.swap(a, j, j+1);
done = false;
}
}
}
long t2 = System.currentTimeMillis();
return t2 - t1;
}
public static void main(String[] args) {
new TestBubbleSort();
}
}

15.8

15.9

void sort(int[] a) {
sort(a, a.length);
}
void sort(int[] a, int n) {
if (n < 1) return;
for (int j = 0; j < n-1; j++)
if (a[j] > a[j+1]) IntArrays.swap(a, j, j+1);
sort(a, n-1);
}
void sort(int[] a) {
for (int i = a.length-1; i > 0; i--) {
for (int j = 0; j < i; j++) {

Solutions

173
if (a[j] > a[j+1]) IntArrays.swap(a, j, j+1);
if (!invariant1(a, j))
throw new RuntimeException("INVARIANT 1 VIOLATED");
}
if (!invariant2(a, i))
throw new RuntimeException("INVARIANT 2 VIOLATED");
}
}
boolean invariant1(int[] a, int j) {
for (int k=0; k<j; k++)
if (a[j+1] < a[k]) return false;
return true;
}

15.10

15.11

boolean invariant2(int[] a, int i) {

for (int k=0; k<i; k++)
if (a[i] < a[k]) return false;
for (int k=i; k<a.length-1; k++)
if (a[k+1] < a[k]) return false;
return true;
}
void sort(int[] a) {
for (int i = a.length-1; i > 0; i--) {
int m=0;
for (int j = 1; j <= i; j++) {
if (a[j] > a[m]) m = j;
// INVARIANT: a[m] = max{a[0], ..., a[j]};
}
IntArrays.swap(a, i, m);
// INVARIANTS: a[i] = max{a[0], ..., a[i]};
//
a[i] <= ... <= a[a.length-1];
}
}
void sort(int[] a) {
for (int i = a.length-1; i > 0; i--)
select(a, i);
}
void select(int[] a, int i) {
// moves max{a[0], ..., a[i]} into a[i]:
int m=0;

174

Chapter 15 Sorting
for (int j = 1; j <= i; j++) {
if (a[j] > a[m]) m = j;
}
IntArrays.swap(a, i, m);

15.12

15.13

15.14

15.15

}
void sort(int[] a) {
sort(a, a.length);
}
void sort(int[] a, int n) {
if (n < 2) return;
int m=0;
for (int j=1; j<n; j++)
if (a[j] > a[m]) m = j;
IntArrays.swap(a, n-1, m);
sort(a, n-1);
}
void sort(int[] a) {
for (int i=1; i<a.length; i++)
insert(a, i);
}
void insert(int[] a, int i) {
// inserts a[i] into a[0..i] leaving it in ascending order:
int ai=a[i], j=i;
for (j=i; j>0 && a[j-1]>ai; j--)
a[j] = a[j-1];
a[j] = ai;
}
void sort(int[] a) {
sort(a, a.length);
}
void sort(int[] a, int n) {
if (n < 2) return;
sort(a, n-1);
int ai=a[n-1], j=n-1;
for (j=n-1; j>0 && a[j-1]>ai; j--)
a[j] = a[j-1];
a[j] = ai;
}
package chap15.prob15;
import chap03.list08.IntArrays;
public class TestMergeSort {

Solutions

175
public TestMergeSort(int size) {
int[] a = IntArrays.randomInts(size, 100);
IntArrays.print(a);
System.out.println("sorted: " + IntArrays.isSorted(a));
sort(a, 0, a.length);
IntArrays.print(a);
System.out.println("sorted: " + IntArrays.isSorted(a));
}
void sort(int[] a, int p, int q) {
// PRECONDITION: 0 < p < q <= a.length
// POSTCONDITION: a[p..q-1] is in ascending order
if (q-p < 2) return;
int m = (p+q)/2;
sort(a, p, m);
sort(a, m, q);
merge(a, p, m, q);
}
void merge(int[] a, int p, int m, int q) {
// PRECONDITIONS: a[p..m-1] and a[m..q-1] are in ascending order;
// POSTCONDITION: a[p..q-1] is in ascending order;
if (a[m-1] <= a[m]) return; // a[p..q-1] is already sorted
int i = p, j = m, k = 0;
int[] aa = new int[q-p];
while (i < m && j < q)
if (a[i]<a[j]) aa[k++] = a[i++];
else aa[k++] = a[j++];
if (i < m) System.arraycopy(a,i,a,p+k,m-i); //shift a[i..m-1]
System.arraycopy(aa,0,a,p,k); // copy aa[0..k-1] to a[p..p+k-1];
}
public static void main(String[] args) {
for (int i=10; i<=20; i++)
new TestMergeSort(i);
}

15.16

a. void sort(int[] a, int p, int q) {

for (int i = q-1; i > p; i--)
for (int j = p; j < i; j++)
if (a[j] > a[j+1]) IntArrays.swap(a, j, j+1);
}

176

Chapter 15 Sorting
b. void sort(int[] a, int p, int q) {
for (int i = q-1; i > p; i--) {
int m=0;
for (int j = 1; j <= i; j++)
if (a[j] > a[m]) m = j;
IntArrays.swap(a, i, m);
}
}

c. void sort(int[] a, int p, int q) {

for (int i=p+1; i<q; i++) {
int ai=a[i], j=i;
for (j=i; j>p && a[j-1]>ai; j--)
a[j] = a[j-1];
a[j] = ai;
}

15.17

}
package chap15.prob17;
abstract class AbstractTester {
protected int[] a;
private java.util.Random random;
private final int N = 100;
public AbstractTester() { // initializes a[] and random
a = new int[N];
random = new java.util.Random();
for (int i=0; i<N; i++)
a[i] = 100 + random.nextInt(900);
}
public void randomize() { // randomly permutes a[]
for (int i=0; i<N; i++) {
int j = random.nextInt(N);
swap(a, i, j);
}
}
public void reverse() { // reverses the order of a[]
for (int i=0; i<N/2; i++)
swap(a, i, N-i);
}
abstract public void sort();

// sorts a[]

Solutions

177

public boolean isSorted() {

for (int i=1; i<a.length; i++)
if (a[i] < a[i-1]) return false;
return true;
}
public void swap(int[] a, int i, int j) {
int ai = a[i], aj = a[j];
if (ai==aj) return;
a[i] = aj;
a[j] = ai;
}
}

Chapter 16
Graphs
Exercises
16.1
16.2
16.3

If e is an edge between vertex i and veretex j in an undirected graph, then there is one 1
at location aij and a one 1 at location aji in the adjacency matrix. Thus, there are two 1s
for each edge.
If e is an edge between vertex i and veretex j in an undirected graph, then there is a node
to j in list i and a node to i in list j in the adjacency list. Thus, there are two nodes for
each edge.
a. n = 6
b. V = {A, B, C, D, E, F}
c. E = {AB, BC, BD, CD, CE, CF, DE, DF}
d.
x:

d(x)

e. ABCD
f. ABCEDF
g. BCEDB
h.
A

178

Solutions

179

i.
A
B
C
D
E
F
v

j.

2
3
4
4

B
1
0
1
1
0
0

C
0
1
0
1
1
1

D
0
1
1
0
1
1

E
0
0
1
1
0
0

F
0
0
1
1
1
0

A
B
C
D
E
F

0
1

16.4

A
0
1
0
0
0
0
0

a. n = 6
b. V = {A, B, C, D, E, F}
c. E = {AD, BA, BD, CB, CD, CE, CF, DE, EC, FE}
d.
x:

d(x):

e. ADEC
f. FCBADE
g. BDECB
h.
B

F
D

i.
A
B
C
D
E
F

j.

A
0
1
0
0
0
0

v
0
1
2
3
4
4

A
B
C
D
E
F

B
0
0
1
0
0
0

C
0
0
0
0
1
0

D
1
1
1
0
0
0

E
0
0
1
1
0
1

F
0
0
1
0
0
0

a
0

180
16.5

Chapter 16 Graphs

a.

K4

K5

K2

b. Each vertex of Kn has n 1 adjacent vertices. So each vertex is an endpoint of n 1

edges. There are n vertices. So there are n(n 1) edge endpoints. Each edge has two
endpoints. So the number of edges is n(n 1)/2.
c. The adjacency matrix for Kn is an n-by-n matrix with 0s on the diagonal and 1s everywhere else.
d. The adjacency list for Kn is an n-component array a[] of lists. The list at component
a[i] has n 1 nodes: one for each vertex except vertex i.
e.

Solutions

181

f.

16.6

4
2

4
2
1

1
4

2
4

1
E

182

Chapter 16 Graphs

16.7

4B
4

2
5

D7

I4

1
1

5 J

1H

16.8

a. Preorder traversal.

b. Level order traversal.

16.9

a.

A B C D E F

A
B
C
D
E
F
G

b.

0 4 0 0 0 1 2
4 0 2 0 0 0 5
0 2 0 4 0 0 1
0 0 4 0 1 0 2
0 0 0 2 0 3 4
1 0 0 0 3 0 3
2 5 1 2 4 3 0

A B C D E F G
A
B
C
D
E
F
G

c.

0 1 0 0 0 1 1
1 0 1 0 0 0 1
0 1 0 1 0 0 1
0 0 1 0 1 0 1
0 0 0 1 0 1 1
1 0 0 0 1 0 1
1 1 1 1 1 1 0

v
0
1
2
3
4
5
6

A
B
C
D
E
F
G

a
0

Solutions

Programming Problems
16.1

16.2

public Graph(String[] args) {

size = args.length;
vertices = new String[size];
size = args.length;
vertices = new String[size];
for (int i=0; i<size; i++) {
String ai = args[i];
int j=i;
while (j>0 && vertices[j-1].compareTo(ai)>0) {
vertices[j] = vertices[j-1];
--j;
}
vertices[j] = ai;
}
a = new boolean[size][size];
}
private int index(String v) {
int p=0, q=size;
while (p < q) {
int i = (p + q)/2;
if (vertices[i].equals(v)) return i;
if (vertices[i].compareTo(v) < 0) p = i;
else q = i;
}
if (vertices[p].equals(v)) return p;
return a.length;
}
public boolean equals(Object object) {
if (object == this) return true;
if (!(object instanceof Graph)) return false;
Graph that = (Graph)object;
if (that.size != this.size) return false;
String[] thisVertices = new String[size];
System.arraycopy(this.vertices, 0, thisVertices, 0, size);
Arrays.sort(thisVertices);
String[] thatVertices = new String[size];
System.arraycopy(that.vertices, 0, thatVertices, 0, size);
Arrays.sort(thatVertices);
if (!(Arrays.equals(thatVertices, thisVertices))) return false;
for (int i=0; i<size; i++) {

183

184

Chapter 16 Graphs
String vi = vertices[i];
int i1 = this.index(vi);
int i2 = that.index(vi);
for (int j=0; j<size; j++) {
String vj = vertices[i];
int j1 = this.index(vj);
int j2 = that.index(vj);
if (this.a[i1][j1] != that.a[i2][j2]) return false;
}
}
return true;

16.3

}
public class Graph {
private int size;
private List[] a; // adjacency list
private String[] v; // vertex list
public Graph(String[] args) {
size = args.length;
a = new List[size];
for (int i=0; i<size; i++)
a[i] = new List();
v = new String[size];
System.arraycopy(args, 0, v, 0, size);
}
public void add(String v, String w) {
a[index(v)].add(index(w));
a[index(w)].add(index(v));
}
public String toString() {
if (size == 0) return "{}";
StringBuffer buf = new StringBuffer("{" + v[0] + ":" + a[0]);
for (int i = 1; i < size; i++)
buf.append("," + v[i] + ":" + a[i]);
return buf + "}";
}
private int index(String vertex) {
for (int i = 0; i < size; i++)
if (vertex.equals(v[i])) return i;

Solutions

185
return a.length;
}
private class List {
String vertex;
Node edges;
public void add(int j) {
edges = new Node(j, edges);
}
public String toString() {
if (edges==null) return "";
StringBuffer buf = new StringBuffer();
for (Node p = edges; p != null; p = p.next)
buf.append(Graph.this.v[p.to]);
return buf.toString();
}
private class Node {
int to;
Node next;
Node(int to, Node next) {
this.to = to;
this.next = next;
}
}

16.4

16.5

}
}
public boolean[][] getAdjacencyMatrix() {
return a;
}
public String[] getVertices() {
return vertices;
}
public int size() {
return size;
}
public int[] degrees() {
int[] d = new int[size];
for (int i=0; i<size; i++) {
d[i]=0;

186

Chapter 16 Graphs
for (int j=0; j<size; j++)
if (a[i][j]) ++d[i];
}
return d;

16.6

16.7

16.8

16.9

}
public int[] degrees() {
int[] d = new int[size];
for (int i=0; i<size; i++) {
d[i]=0;
for (List.Node p=a[i].edges; p != null; p = p.next)
++d[i];
}
return d;
}
public boolean isComplete() {
for (int i=0; i<size; i++)
for (int j=0; j<size; j++)
if (j != i && !a[i][j]) return false;
return true;
}
public boolean isComplete() {
for (int i=0; i<size; i++) {
boolean[] e = new boolean[size];
for (List.Node p=a[i].edges; p != null; p = p.next)
e[p.to] = true;
for (int j=0; j<size; j++)
if (j != i && !e[j]) return false;
}
return true;
}
public Graph(boolean[][] aa) {
size = aa.length;
a = new List[size];
for (int i=0; i<size; i++)
a[i] = new List();
v = new String[size];
for (int i=0; i<size; i++)
v[i] = String.valueOf((char)('A'+i));
for (int i=0; i<size; i++)
for (int j=0; j<size; j++)
if (aa[i][j]) a[i].add(j);
}

Solutions
16.10

16.11

16.12

public Graph(String[] v, String[] e) {

size = v.length;
vertices = v;
a = new boolean[size][size];
for (int i=0; i<size; i++) {
StringTokenizer tok = new StringTokenizer(e[i], " ,");
while (tok.hasMoreElements()) {
int j = Integer.parseInt(tok.nextToken());
a[i][j] = true;
}
}
}
public boolean remove(String v, String w) {
int i = index(v);
if (i < 0) return false;
int j = index(w);
if (j < 0) return false;
if (!a[i][j] || !a[j][i]) return false;
a[i][j] = a[j][i] = false;
return true;
}
public boolean remove(String v, String w) {
boolean found = false;
int i = index(v);
if (i < 0) return false;
int j = index(w);
if (j < 0) return false;
List.Node p=a[i].edges;
if (p.to == j) {
a[i].edges = p.next;
found = true;
} else {
while (p.next != null) {
if (p.next.to == j) {
p.next = p.next.next;
found = true;
break;
}
p = p.next;
}
}
List.Node q=a[j].edges;

187

188

Chapter 16 Graphs
if (q.to == i) {
a[j].edges = q.next;
found = true;
} else {
while (q.next != null) {
if (q.next.to == i) {
q.next = q.next.next;
found = true;
break;
}
q = q.next;
}
}
return found;
}