Contents

1. Environment Setup

2. Quiz

Resources

• Main: src/main/java/edu/emory/cs/utils/Utils.java

• Test: src/test/java/edu/emory/cs/utils/UtilsTest.java

This is an advanced programming course in Computer Science that teaches how to design efficient structures and algorithms to process big data and methods to benchmark their performance for large-scale computing. Topics cover data structures such as priority queues, binary trees, tries, and graphs and their applications in constructing algorithms such as sorting, searching, balancing, traversing, and spanning. Advanced topics such as network flow and dynamic programming are also discussed. Throughout this course, students are expected to

• Have a deep conceptual understanding of various data structures and algorithms.

• Implement their conceptual understanding in a programming language.

• Explore the most effective structures and algorithms for given tasks.

• Properly assess the quality of their implementations.

There are topical quizzes and homework assignments that require sufficient skills in Java programming, Git version control, Gradle software project management, and scientific writing. Intermediate-level Java programming is a prerequisite of this course.

• Syllabus

• Schedule

Contents

1. Abstraction

2. Implementation

3. Unit Testing

4. Quiz

Resources

• Main: src/main/java/edu/emory/cs/algebraic

• Test: src/test/java/edu/emory/cs/algebraic

References

• TIOBE Programming Community Index

• PYPL Popularity of Programming Language

Coding

Right-click on the src/main/java directory under the project and create the package edu.emory.cs.utils. Right-click on the utils package and create the Java class Utils:

• Add Utils.java to git.

• Add the following methods to the Utils class:

static public int getMiddleIndex(int beginIndex, int endIndex) {
    return beginIndex + (endIndex - beginIndex) / 2;
}

static public void main(String[] args) {
    System.out.println(getMiddleIndex(0, 10));
}

Run the program by clicking [Run -> Run]. If you see 5 on the output pane, your program runs successfully.

Testing

Open build.gradle and add the following configurations (if not already), which would allow you to perform JUnit Testing:

test {
    useJUnitPlatform()
}

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter-api:5.8.2'
    testRuntimeOnly 'org.junit.jupiter:junit-jupiter-engine:5.8.2'
}

Right-click on the src/test/java directory under the project and create the package edu.emory.cs.utils. Right-click on the utils package and create the Java class UtilsTest:

• Add UtilsTest.java to Git.

• Add the following method to the UtilsTest class. Make sure to include all imports:

package edu.emory.cs.utils;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

@Test
public void getMiddleIndexTest() {
    assertEquals(5, Utils.getMiddleIndex(0, 10));
}

Run the test by clicking [Run -> Run]. If you see the test passed, your unit test runs successfully.

Submission

1. Add the instructors as collaborators in your GitHub repository:

• Jinho Choi: jdchoi77

• Peilin Wu: qualidea1217

• Jeongrok Yu: jeongrok

• Zinc Zhao: ZincZhao

2. Commit and push the following to your GitHub repository:

• gradle/wrapper/gradle-wrapper.jar

• gradle/wrapper/gradle-wrapper.properties

• .gitignore

• build.gradle

• gradlew

• gradlew.bat

• settings.gradle

• src/main/java/edu/emory/cs/utils/Utils.java

• src/test/java/edu/emory/cs/utils/UtilsTest.java

3. Submit the URL of your GitHub repository to Canvas.

General

• Book: https://emory.gitbook.io/dsa-java/

• GitHub: https://github.com/emory-courses/dsa-java

• Time: MW 11:30AM - 12:45PM

• Location: Atwood 240

Instructors

• Jinho Choi Associate Professor of Computer Science Office Hours → MW 4PM - 5:30PM, MSC W302F

• Peilin Wu BS in Computer Science; BA in Physics and Astronomy Office Hours → TuTh 10:30AM - 12PM, MSC E308

• Jeongrok Yu BS in Computer Science and Economics Office Hours -> MW 2:30PM - 4PM, MSC E308

• Zinc Zhao BS in Computer Science; BA in Music Office Hours → TuTh 1PM - 2:30PM, MSC E308

Grading

• 1 + 10 topical quizzes: 70%

• 3 homework assignments: 30%

• Your work is governed by the Emory Honor Code. Honor code violations (e.g., copies from any source, including colleagues and internet sites) will be referred to the Emory Honor Council.

• Excuses for exam absence/rescheduling and other serious personal events (health, family, personal related, etc.) that affect course performance must be accompanied by a letter from the Office of Undergraduate Education.

Notes

• For every topic, one quiz will be assigned to check if you keep up with the materials.

• Homework assignments assess conceptual understanding, programming ability, and analytical writing skills relevant to this course.

• All quizzes and assignments must be submitted individually. Discussions are allowed; however, your work must be original.

• Late submissions within a week will be accepted with a grading penalty of 15% and will not be accepted once the solutions are discussed in class.

Development Kit

Install the latest version of the Java SE Development Kit (JDK) on your local machine:

• The required version: 17.x.x (or higher)

Version Control

Install Git using any of the following instructions:

• Git Installation Guide by Bitbucket

• Git Installation Guide by GitHub

Run the following commands on a terminal by replacing user.email and user.name with your email address and name:

git config --global user.email "your_id@emory.edu"
git config --global user.name "Your Name"

Integrated Development Environment

Install the latest version of IntelliJ IDEA on your local machine:

• The recommended version: 2022.3.x (Ultimate Edition)

• Apply for the academic license with your school email address to use the ultimate version.

Project Management

Launch IntelliJ and create a Gradle project by clicking the [New Project] button at the top:

• Name: dsa-java

• Location: local_path/dsa-java

• Check "Create Git repository"

• Language: Java

• Build system: Gradle

• JDK: 17

• Gradle DSL: Groovy

• Uncheck "Add sample code"

• Advanced Settings:

  • GroupId: edu.emory.cs

  • ArtifactId: dsa-java

Open gradle/wrapper/gradle-wrapper.properties and make sure distributionUrl indicates the latest version of Gradle:

distributionUrl=https\://services.gradle.org/distributions/gradle-7.6-all.zip

Click [Settings - Build, Execution, Deployment] on the menu:

• Click [Build Tools - Gradle] and set Gradle JVM to 17.

• Click [Compiler - Java Compiler] and set Project bytecode version to 17.

Click [File - Project Structure] and select [Project Settings]:

• Click [Project Settings - Project] and set SDK to 17 and Project language level to SDK default.

• Click [Project Settings - Modules - Dependencies] and set Module SDK to 17.

• Go to [Platform Settings - SDKs] and select 17.

Open build.gradle and make sure sourceCompatibility and targetCompatibility are set to java version 17 (add the following configurations if they do not exist already):

compileJava {
    sourceCompatibility = JavaVersion.VERSION_17
    targetCompatibility = JavaVersion.VERSION_17
}

Lastly, check mavenCentral() is configured as a repository in your build.gradle:

repositories {
    mavenCentral()
}

GitHub Integration

To integrate the project with your GitHub repository, click [Settings]:

• Choose [Version Control - Github] on the left pane.

• Click [+] and login with your GitHub ID and password.

• If you use two-factor authentication, log in with your personal access token.

Create .gitignore under the project and add the following contents:

/.gradle/
/.idea/
/.vscode/
/build/

Click [Git - GitHub - Share Project on Github] and create a repository:

• Make sure to check private.

• Repository name: dsa-java

• Remote: origin

• Description: Data Structures and Algorithms in Java

Add all files and make the initial commit. Check if the repository is created under your GitHub account: https://github.com/your_id/dsa-java.

Contents

Resources

• Main:

• Test:

References

Class

A is a template to instantiate an .

What is the relationship between a class and an object?

Let us create a class called that we want to be a super class of all numeral types:

• L1: packageindicates the name of the package that this class belongs to in a hierarchy.

• L3: public is an .

What are the acceptable access-level modifiers to declare a top-level class?

Let us declare a method, add() , that is an operation expected by all numeral types:

The issue is that we cannot define the methods unless we know what specific numeral type this class should implement; in other words, it is too abstract to define those methods. Thus, we need to declare Numeral as a type of abstract class.

What are the advantages of havingNumeral as a super class of all numeral types?

There are two types of abstract classes in Java, abstract class and interface.

Can an object be instantiated by an abstract class or an interface?

Interface

• L2: abstract method

  • All methods in an interface are public that does not need to be explicitly coded.

  • Abstract methods in an interface are declared without their bodies.

Who defines the bodies of the abstract methods?

Let us create a new interface called SignedNumeral that inherits Numeral and adds two methods, flipSign() and subtract():

Can an interface inherit either an abstract class or a regular class?

• L1: extends inherits exactly one class or interface.

Can we call add() that is an abstract method without a body in the default method subtract()?

Although the logic of subtract() seems to be correct, n.flipSign() gives a compile error because n is a type of Numeral that does not include flipSign(), which is defined in SignedNumeral that is a subclass of Numeral.

What kind of a compile error does n.flipSign() cause?

Casting

The first way is to downcast the type of n to SignedNumeral, which forces the compiler to think that n can invoke the flipSign() method:

Why is a runtime error worse than a compile error?

How can downcasting cause a runtime error in the above case?

Polymorphism

The second way is to change the type of n to SignedNumeral in the parameter setting:

This seems to solve the issue. Then, what about add() defined in Numeral? Should we change its parameter type to SignedNumeral as well?

It is often the case that you do not have access to change the code in a super class unless you are the author of it. Even if you are the author, changing the code in a super class is not recommended.

Why is it not recommended to change the code in a super class?

The annotation @Override gives an error in this case because it is not considered an overriding.

What are the criteria to override a method?

When @Override is discarded, the error goes away and everything seems to be fine:

What are good use cases of method overriding and overloading?

Generics

• L1: T is a generic type that is a subtype of Numeral.

  • A generic type can be recursively defined as T extends Numeral<T>.

• L2: T is considered a viable type in this interface such that it can be used to declare add().

Can we define more than one generic type per interface or class?

The generic type T can be specified in a subclass of Numeral:

• L1: T is specified as SignedNumeral.

This would implicitly assign the parameter type of add() as follows:

The issue is that the implementation of add() may require specific features defined in the subclass that is not available in SignedNumeral. Consider the following subclass inheriting SignedNumeral:

Would the type of n being SignedNumeral an issue for the subtract() method as well?

Thus, SignedNumeral needs to define its own generic type and pass it onto Numeral:

• L1: T is a generic type inheriting SignedNumeral, that implies all subclasses of SignedNumeral.

T can be safely passed onto Numeral because if it is a subclass of SignedNumeral, it must be a subclass of Numeral, which is how T is defined in the Numeral class.

Enum

• Items must be delimited by , and ends with ;.

The items in the enum can be assigned with specific values to make them more indicative (e.g., +, -):

Why should the member field value be private in the above example?

Note that value in L8 indicates the local parameter declared in the constructor whereas value in L13 indicates the member field declared in L5.

Limit of Interface

In SignedNumeral, it would be convenient to have a member field that indicates the sign of the numeral:

• L2: All member fields of an interface are static and public.

Can you declare a member field in an interface without assigning a value?

Given the sign field, it may seem intuitive to define flipSign() as a default method:

Is there any advantage of using a ternary operator instead of using a regular if statement?

Unfortunately, this gives a compile error because sign is a constant whose value cannot be reassigned. An interface is not meant to define so many default methods, which were not even allowed before Java 8. For such explicit implementations, it is better to declare SignedNumeral as an abstract class instead.

Abstract Class

• L9: the default constructor with no parameter.

• L17: another constructor with the sign parameter.

• L10: this() calls the constructor in L17.

Why calling this(Sign.POSITIVE) in L10 instead of stating this.sign = Sign.POSITIVE?

• L29: abstract indicates that this is an abstract method.

Member fields and methods in an abstract class can be decorated by any modifiers, which need to be explicitly coded.

Is there anything that is not allowed in an abstract class but allowed in a regular class?

In summary, SignedNumeral includes 2 abstract methods, add() inherited from Numeral, and multiply() declared in this class.

Can you define an abstract class or an interface without declaring an abstract method?

Test: LongInteger()

Let us create a testing class called and make a for the constructors:

• L7: methods used for unit testing must be public.

• L8: tests the default constructor
• L12-15: tests the constructor with a string parameter.

• L18-19: tests the copy constructor.

When should we use import static instead of import?

When you run this test, you see a prompt similar to the followings:

Test: multiply()

Let us define another method for testing the multiply() method:

Test: compareTo()

Let us define a method for testing the compareTo() method:

Coding

• Create a class called LongIntegerQuiz under the main algebraic package that extends the LongInteger class.

• Override the addDifferentSign() method so that the add() method in LongIntegerQuiz can handle integers with different signs.

Testing

• Create the LongIntegerQuizTest class under the test algebraic package.

• Test the correctness of your LongIntegerQuiz using the unit tests.

• Add more tests for a more thorough assessment if necessary.

Quizzes

1. What is the advantage of using Generics?

2. How do you make the class you define comparable?

3. What is the advantage of overriding member methods in the Object class?

4. What kind of methods should be defined as static?

Submission

1. Commit and push everything under the following packages to your GitHub repository:

• Main: src/main/java/edu/emory/cs/algebraic

• Test: src/test/java/edu/emory/cs/algebraic

2. Submit answers to the above quizzes to Canvas.

A priority queue (PQ) is a data structure that supports the following two operations:

• add(): adds a comparable key to the PQ.

• remove(): removes the key with the highest (or lowest) priority in the PQ.

A PQ that removes the key with the highest priority is called a maximum PQ (max-PQ), and with the lowest priority is called a minimum PQ (min-PQ).

Does a priority queue need to be sorted at all time to support those two operations? What are the use cases of priority queues?

Abstract Priority Queue

Let us define AbstractPriorityQueue that is an abstract class to be inherited by all priority queues:

public abstract class AbstractPriorityQueue<T extends Comparable<T>> {
    protected final Comparator<T> priority;

    /**
     * Initializes this PQ as either a maximum or minimum PQ.
     * @param priority if {@link Comparator#naturalOrder()}, this is a max PQ;
     *                 if {@link Comparator#reverseOrder()}, this is a min PQ.
     */
    public AbstractPriorityQueue(Comparator<T> priority) {
        this.priority = priority;
    }
}

• L1: declares the generic type T that is the type of input keys to be stored in this PQ.

  • T must be comparable by its priority.

• L2: is a comparator that can compare keys of the generic type T.

  • final: must be initialized in every constructor.

  • Comparators: naturalOrder(), reverseOrder().

• L6: the javadoc {@link} hyperlinks to the specified methods.

What are comparable data types in Java? Can you define your own comparator?

Let us define three abstract methods, add(), remove(), and size() in AbstractPriorityQueue:

/**
 * Adds a comparable key to this PQ.
 * @param key the key to be added.
 */
abstract public void add(T key);

/**
 * Removes the key with the highest/lowest priority if exists.
 * @return the key with the highest/lowest priority if exists; otherwise, null.
 */
abstract public T remove();

/** @return the size of this PQ. */
abstract public int size();

Given the abstract methods, we can define the regular method isEmpty():

/** @return true if this PQ is empty; otherwise, false. */
public boolean isEmpty() {
    return size() == 0;
}

Lazy Priority Queue

Let us define LazyPriorityQueue whose core methods satisfy the following conditions:

• add(): takes$O(1)$to add a key to the PQ.

• remove(): takes$O(n)$ to remove the key with the highest/lowest priority from the PQ.

In other words, all the hard work is done at the last minute when it needs to remove the key.

public class LazyPriorityQueue<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
    private final List<T> keys;

    /** Initializes this as a maximum PQ. */
    public LazyPriorityQueue() {
        this(Comparator.naturalOrder());
    }

    /** @see AbstractPriorityQueue#AbstractPriorityQueue(Comparator). */
    public LazyPriorityQueue(Comparator<T> priority) {
        super(priority);
        keys = new ArrayList<>();
    }
    
    
    @Override
    public int size() {
        return keys.size();
    }
}

• L1: declares T and passes it to its super class, AbstractPriorityQueue.

• L2: defines a list to store input keys.

• L17-19: overrides the size() method.

Can you add keys to the member field keys when it is declared as final (a constant)? Why does all constructors in LazyPriorityQueue need to call the super constructor?

We then override the core methods, add() and remove():

/**
 * Appends a key to {@link #keys}.
 * @param key the key to be added.
 */
@Override
public void add(T key) {
    keys.add(key);
}

/**
 * Finds the key with the highest/lowest priority, and removes it from {@link #keys}.
 * @return the key with the highest/lowest priority if exists; otherwise, null.
 */
@Override
public T remove() {
    if (isEmpty()) return null;
    T max = Collections.max(keys, priority);
    keys.remove(max);
    return max;
}

• L6-8: appends a key to the list in $O(1)$.

• L15-20: removes a key to the list in $O(n)$.

  • L16: edge case handling.

  • L17: finds the max-key in the list using Collections.max() in $O(n)$.

  • L18: removes a key from the list in $O(n+n) = O(n)$.

Is ArrayList the best implementation of List for LazyPriorityQueue? Why does remove() in L18 cost $O(n+n)$?

Eager Priority Queues

Let us define EagerPriorityQueue whose core methods satisfy the following conditions:

• add(): takes$O(n)$to add a key to the PQ.

• remove(): takes$O(1)$ to remove the key with the highest/lowest priority from the PQ.

In other words, all the hard work is done as soon as a key is added.

What are the situations that LazyPQ is preferred over EagerPQ and vice versa?

public class EagerPriorityQueue<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
    private final List<T> keys;

    public EagerPriorityQueue() {
        this(Comparator.naturalOrder());
    }

    public EagerPriorityQueue(Comparator<T> priority) {
        super(priority);
        keys = new ArrayList<>();
    }
    
    @Override
    public int size() {
        return keys.size();
    }
}

• The implementations of the two constructors and the size() method are identical to the ones in LazyPriorityQueue.

Should we create an abstract class that implements the above code and make it as a super class of LazyPQ and EagerPQ? What level of abstraction is appropriate in object-oriented programming?

We then override the core methods, add() and remove():

/**
 * Adds a key to {@link #keys} by the priority.
 * @param key the key to be added.
 */
@Override
public void add(T key) {
    // binary search (if not found, index < 0)
    int index = Collections.binarySearch(keys, key, priority);
    // if not found, the appropriate index is {@code -(index +1)}
    if (index < 0) index = -(index + 1);
    keys.add(index, key);
}

/**
 * Remove the last key in the list.
 * @return the key with the highest priority if exists; otherwise, {@code null}.
 */
@Override
public T remove() {
    return isEmpty() ? null : keys.remove(keys.size() - 1);
}

• L6-12: inserts a key to the list in $O(n)$ .

  • L8: finds the index of the key to be inserted in the list using binary search in $O(\log n)$.

  • L10: reverse engineers the return value of Collections.binarySearch() .

  • L11: inserts the key at the index position in $O(n)$.

• L19-21: removes a key from the list in $O(1)$.

What are the worst-case complexities of add() and remove() in LazyPQ and EagerPQ in terms of assignments and comparison?

We are going to create a class called LongInteger inheriting SignedNumeral that can store an indefinite size of an integer value beyond the primitive types such as int and long.

What is so special about primitive data types in Java?

Field

Let us declare the member field digits that is an array of bytes holding the values of this integer:

public class LongInteger extends SignedNumeral<LongInteger> {
    /** The values of this integer (excluding the sign). */
    protected byte[] digits;
    ...

• L1: LongInteger is passed to specify the generic type T in SignedNumeral.

The i'th dimension of digits is the i'th least significant digit in the integer such that the integer 12345 would be stored as digits = {5, 4, 3, 2, 1}, which makes it convenient to implement the arithmetic methods, add() and multiply().

Is the array of bytes the most efficient way of storing a long integer?

Constructors

Let us define the following three constructors:

/** Creates a long integer with the default value of "0". */
public LongInteger() {
    this("0");
}

/**
 * Creates a long integer by copying the specific object.
 * @param n the object to be copied.
 */
public LongInteger(LongInteger n) {
    super(n.sign);
    digits = Arrays.copyOf(n.digits, n.digits.length);
}

/**
 * Creates a long integer with the specific sign and values.
 * @param n the sign and values to be set.
 * @see #set(String)
 */
public LongInteger(String n) {
    set(n);
}

• L2: the default constructor that initializes this integer with 0 by calling the constructor in L20.

• L10: a copy constructor that initializes this integer with n.

  • super(): calls the corresponding constructor in the super class, SignedNumeral.

  • Arrays.copyOf(): creates a new array by copying n.digits.

• L20: a constructor that initializes this integer with n by passing it to the set() method.

Do the constructors in L10 and L20 call any constructor in the super class?

Arrays.copyOf() is a static method referenced by the class type Arrays, not an object. Java provides many classes with static methods that are commonly used (e.g., Arrays, Collections).

Can you call non-static methods or fields in the body of a static method?

Method: set()

Let us define the set() method that takes a string and sets the sign and the value of this integer:

/**
 * Sets the sign and values of this integer.
 * @param n the sign and values to be set.
 * @throws NullPointerException when `n` is null.
 * @throws InvalidParameterException when `n` contains non-digit character
 *         except for the first character that can be [+-\d].
 */
public void set(String n) {
    // 'n' must not be null
    if (n == null)
        throw new NullPointerException();

    // set this.sign
    sign = switch (n.charAt(0)) {
        case '-' -> { n = n.substring(1); yield Sign.NEGATIVE; }
        case '+' -> { n = n.substring(1); yield Sign.POSITIVE; }
        default -> Sign.POSITIVE;
    };

    // set this.digits
    digits = new byte[n.length()];

    for (int i = 0, j = n.length() - 1; i < n.length(); i++, j--) {
        byte v = (byte)(n.charAt(i) - 48);
        if (0 > v || v > 9) {
            String s = String.format("%d is not a valid value", v);
            throw new InvalidParameterException(s);
        }
        digits[j] = v;
    }
}

• L1-7: javadoc comments.

  • L4: this method throws NullPointerException if n is null.

  • L5: this method throws InvalidParameterException if the format of n is invalid.

• L10-11: throws the NullPointerException.

• L14-18: checks the first character of n and sets this.sign using the switch expression.

  • String member methods: charAt(), substring().

  • yield: returns the value of this switch statement for the condition (introduced in Java 14).

• L21-30: sets the value of n to this.digits .

  • L23: for-loop can handle multiple variables such as i and j.

  • L24: gets the ASCII value of n.charAt(i).

  • L25-28: throws the InvalidParameterException if v is not a digit.

  • L29: stores the value in the reverse order.

  • L27: String.format() is a static method in String.

When should we use throw statements over try..catch blocks for error handling and vice versa?

Method: add()

Let us override the add() method that calls two helper methods:

@Override
public void add(LongInteger n) {
    if (sign == n.sign)
        addSameSign(n);
    else
        addDifferentSign(n);
}

• L3-4: adds n to this integer that has the same sign by calling addSameSign().

• L5-6: adds n to this integer that has a different sign by calling addDifferentSign().

The following shows an implementation of addSameSign() based on the simple arithmetic:

/**
 * Adds the specific integer that has the same sign as this integer.
 * @param n the integer to be added with the same sign.
 */
protected void addSameSign(LongInteger n) {
    // copy this integer to result[]
    int m = Math.max(digits.length, n.digits.length);
    byte[] result = new byte[m + 1];
    System.arraycopy(digits, 0, result, 0, digits.length);

    // add n to result
    for (int i = 0; i < n.digits.length; i++) {
        if (i < n.digits.length)
            result[i] += n.digits[i];
        if (result[i] >= 10) {
            result[i] -= 10;
            result[i + 1] += 1;
        }
    }

    // set this.digits
    digits = result[m] == 0 ? Arrays.copyOf(result, m) : result;
}

• L7-9: creates the byte array result by copying values in this integer.

  • L8: the dimension of result can be 1 more than m after the addition.

  • Static methods: Math.max(), System.arraycopy().

• L12-19: adds n to results (if exists) from the least significant digit.

  • L15-18: pass a carry to the next digit.

• L22: trims the most significant digit if it is 0.

What are tradeoffs to make the size of result to be m instead of m+1 and vice versa?

The following shows addDifferentSign() that throws UnsupportedOperationException:

/**
 * Adds the specific integer that has a different sign from this integer.
 * @param n the integer to be added with a different sign
 */
protected void addDifferentSign(LongInteger n) {
    throw new UnsupportedOperationException();
}

The implementation of addDifferentSign() is quite similar to addSameSign() although it involves a few more logics. We will leave this as an exercise.

Method: multiply()

Let us override the multiply() method:

@Override
public void multiply(LongInteger n) {
    // set this.sign
    sign = (sign == n.sign) ? Sign.POSITIVE : Sign.NEGATIVE;

    // multiply this and n and save it to result
    byte[] result = new byte[digits.length + n.digits.length];
    for (int i = 0; i < digits.length; i++) {
        for (int j = 0; j < n.digits.length; j++) {
            int k = i + j, prod = digits[i] * n.digits[j];
            result[k] += prod;
            result[k + 1] += result[k] / 10;
            result[k] %= 10;
        }
    }

    // set this.digits
    int m; for (m = result.length - 1; m > 0; m--)
        if (result[m] != 0) break;
    digits = ++m < result.length ? Arrays.copyOf(result, m) : result;
}

• L4: sets the sign after the multiplication.

• L7-15: multiplies n to this integer:

  • L7: the max-dimension of results is digits.length + n.digits.length.

  • L12-13: pass a carry to the next digit.

• L18-20: trims the most significant digit iteratively if it is 0.

  • L20: ++m increments m before the comparison.

What is the worst-case complexity of the multiply() method?

Method: main()

Let us create a runnable class called LongIntegerRun that contains the main method:

Can we define the main method in LongInteger instead without creating LongIntegerRun?

public class LongIntegerRun {
    static public void main(String[] args) {
        System.out.println(args);
    }
}

• L2: the parameter args is passed from the command line.

Why does the main method need to be static?

This prints something like the following:

[Ljava.lang.String;@d716361

• [: one-dimensional array.

• L: the element of this array is an object.

• java.lang.String: the type of object.

• d716361: the hash code of this array in hexadecimal.

What is the hash code of an object?

Every object implicitly inherits Object that defines a few member methods including toString(), which gets called automatically by the println() method to retrieve the string representation of this object. We can use the helper method Arrays.toString() that gives a more readable representation:

static public void main(String[] args) {
    System.out.println(Arrays.toString(args));
}

How is the Arrays.toString() method implemented?

Since no argument is passed to the main method at the moment, this prints an empty array:

[]

If you set the arguments to 123 -456 using the [Run - Edit Configurations - Program arguments]setting, it prints the following array:

[123, -456]

Given those two arguments, we can create two integers:

static public void main(String[] args) {    
    LongInteger a = new LongInteger(args[0]);
    LongInteger b = new LongInteger(args[1]);
    
    System.out.println(a);
    System.out.println(b);
}

This prints something like the following, which are returned by a.toString():

edu.emory.cs.algebraic.LongInteger@4d7e1886
edu.emory.cs.algebraic.LongInteger@3cd1a2f1

How is the toString() method implemented in the Object class?

Method: toString()

To print a more readable representation, we need to override the toString() method in LongInteger:

public class LongInteger extends SignedNumeral<LongInteger> {
    ...
    @Override
    public String toString() {
        StringBuilder build = new StringBuilder();
        if (sign == Sign.NEGATIVE) build.append("-");
        for (int i = digits.length - 1; i >= 0; i--)
            build.append(digits[i]);
        return build.toString();
    }
    ...

• L5: StringBuilder provides an efficient way of concatenating different data types into one string.

What are the advantages of using StringBuilder instead of concatenating values with the + operator as follows:

Copy

String s = "";
if (sign == Sign.NEGATIVE) s += "-";
for (int i = digits.length - 1; i >= 0; i--)
    s += digits[i];
return s;

Given the overridden method, the above main method now prints the following:

123
-456

What are the advantages of overriding toString() instead of creating a new method with the same code, and calling the new method to get the string representation of LongInteger?

Method: compareTo()

Java does not allow operator overloading, so it is not possible to use logical operators to compare the two integers above, a and b:

boolean c = a < b;  // gives a compile error

In fact, any object that is comparable must inherit the interface Comparable as follows:

public class LongInteger extends SignedNumeral<LongInteger> 
                         implements Comparable<LongInteger> {
...
}

• L2: LongInteger is passed to Comparable as a generic type.

Is extends always used to inherit a class whereas implements is used to inherit an interface?

The Comparable interface contains one abstract method called compareTo() that returns a negative value if this object is smaller than n, a positive value if this object is greater than n, and zero if this object equals to n. The compareTo() method must be overridden by the LongInteger class:

@Override
public int compareTo(LongInteger n) {
    if (isPositive())
        return n.isNegative() ? 1 : compareAbs(n);
    else
        return n.isPositive() ? -1 : -compareAbs(n);
}

The compareAbs() method compares the absolute values of this and n:

/**
 * @param n the object to be compared.
 * @return a negative integer, zero, or a positive integer as the absolute value of this object is
 * less than, equal to, or greater than the absolute value of the specified object.
 */
public int compareAbs(LongInteger n) {
    int diff = digits.length - n.digits.length;

    if (diff == 0) {
        for (int i = digits.length - 1; i >= 0; i--) {
            diff = digits[i] - n.digits[i];
            if (diff != 0) break;
        }
    }

    return diff;
}

• L7: if digits has more dimensions, its absolute value is greater.

• L10-13: compares the significant digits iteratively.

Is it safe to use the same variable i to iterate both digits and n.digits?

Once LongInteger properly inherits Comparable by overriding compareTo(), objects instantiated by this class can be compared using many built-in methods.

static public void main(String[] args) {
    List<LongInteger> list = new ArrayList<>();
    
    list.add(new LongInteger("78"));
    list.add(new LongInteger("-45"));
    list.add(new LongInteger("0"));
    list.add(new LongInteger("6"));
    list.add(new LongInteger("-0"));
    list.add(new LongInteger("-123"));
    
    list.sort(Comparator.naturalOrder());
    System.out.println(list);

    list.sort(Comparator.reverseOrder());
    System.out.println(list);
}