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:

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

Testing

Open and add the following configurations (if not already), which would allow you to perform :

Right-click on the directory under the project and create the package . Right-click on the utils package and create the Java class :

• Add UtilsTest.java to Git.

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

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

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

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

Contents

1. Environment Setup

Resources

• Main:

• Test:

General

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

• GitHub:

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

• Location: Atwood 240

Instructors

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

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

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

Grading

• 1 + 10 topical quizzes: 70%

• 3 homework assignments: 30%

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

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.

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.

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:

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

Integrated Development Environment

Install the latest version of on your local machine:

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

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

Project Management

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

• Name: dsa-java

• Location: local_path/dsa-java

• Check "Create Git repository"

Open and make sure distributionUrl indicates the latest version of Gradle:

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.

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

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

GitHub Integration

To integrate the project with your 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 .

Create under the project and add the following contents:

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

• Make sure to check private.

• Repository name: dsa-java

• Remote: origin

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

1. Abstraction

Resources

• Main:

• Test:

References

Divide & Conquer

• Divide the problem into sub-problems (recursively).

• Conquer sub-problems, which effectively solve the super problem.

Why do people ever want to use QuickSort?

Merge Sort

• Divide the input array into two sub-arrays.

• Sort each of the sub-arrays and merge them into the back.

Let us create the class inheriting AbstractSort:

• L2: holds the copy of the input array.

Let us then override the sort() method that calls the helper method:

• L4-5: increases the size of the temp array if necessary.

  • L5: unchecked type Object to T[].

What is the advantage of declaring the member field temp?

The helper method can be defined as follows:

• L11: sorts the left sub-array.

• L12: sorts the right sub-array.

• L13: merges the left and right sub-arrays.

Finally, the merge() method can be defined as follows:

• L10-11: copies the input array to the temporary array and counts the assignments.

• L14-15: no key left in the 1st half.

• L16-17

How many assignments are made for the number of keys by the above version of MergeSort?

Quick Sort

• Pick a pivot key in the input array.

• Exchange keys between the left and right partitions such that all keys in the left and right partitions are smaller or bigger than the pivot key, respectively.

• Repeat this procedure in each partition, recursively.

Let us create the class inheriting AbstractSort:

Let us then override the sort() method:

• L3: stops when the pointers are crossed.

• L6: sorts the left partition.

• L7: sorts the right partition.

The partition() method can be defined as follows:

• L5: finds the left pointer where endIndex > fst > pivot.

• L6: finds the right pointer where beginIndex < snd

Intro Sort

• Although Quick Sort is the fastest on average, the worst-case complexity is .

• sorting algorithms that guarantee faster worst-case complexities than Quick Sort: Quick Sort for random cases and a different algorithm for the worst case.

How can we determine if Quick Sort is meeting the worse-case?

Let us define the IntroSoft class inheriting QuickSort:

• L2: declares a sorting algorithm to handle the worst cases.

• L14: resets the counters for both the main and auxiliary sorting algorithms.

We then override the sort() method by passing the maximum depth to the auxiliary method:

• L9: returns as the maximum depth.

Finally, the auxiliary method sort() can be defined as follows:

• L4-5: switches to the other sorting algorithm if the depth of the partitioning exceeds the max depth.

Does the max-depth need to be set to ?

Benchmarks

The following shows runtime speeds, assignment costs, and comparison costs between several sorting algorithms for the random, best, and worst cases.

Hybrid Sort

Your task is to write a program that sorts a 2D-array of comparable keys into an 1D-array where all the keys are sorted in ascending order. Here is a sample input to your program:

Here is the expected output given the sample input:

Each row in the input array has one of the following properties:

• Sorted in ascending order (e.g., the 1st row).

• Sorted in descending order (e.g., the 2nd row).

• Mostly sorted in ascending order (e.g., the 3rd row).

• Mostly sorted in descending order (e.g., the 4th row).

• Randomly distributed (e.g., the 5th row).

The easiest way is to merge all rows in the input array into an 1D-array then sort it using . The implementation of this strategy is provided to establish the baseline: . Your goal is to design a sorting mechanism that gives a noticeable speed-up over this baseline.

Tasks

• Create a class inheriting under the package .

• Override the sort() method and evaluate your program for robustness and runtime speeds using :

Submission

• Commit and push everything under the package.

• Submit hw1.pdf to Canvas.

Notes

• You are not allowed to:

  • Use any implementation that is not written by you nor provided by this course.

  • Call any sorting methods built-in Java or 3rd-party libraries.

Results

Baseline: 20697

• Cannot run: 7

• Extremely slow: 6

• Code not found: 1

Coding

Shell Sort: Hibbard

Abstract Binary Node

Let us create an abstract class, :

• L1: defines two generic types, T for the type of the key and N is for the type of the binary node.

• L8: calls the setKey() method to assign the value of key in L2

Let us define boolean methods for the member fields:

What is the input parameter node is null for the isLeftChild() and isRightChild() methods?

Let us then define getters to access the member fields:

We can also define helper methods inferred by the getters:

• L9: this needs to be casted to N since the input parameter of isLeftChild() is N.

Is it safe to downcast this to N?

Finally, let us define setters and their helper methods:

• L5,10: sets node to be a child of this in two steps:

  • L6,11: replaces the parent of node with this

Binary Node

Let us define the class inheriting AbstractBinaryNode:

• L1: defines only 1 generic type T for the comparable key and passes itself for the generic type N to theAbstractBinaryNode class.

Is there any abstract method from AbstractBinaryNode to be defined in BinaryNode?

Abstract Binary Search Tree

Let us define an abstract class, :

• L1: defines two generic types, T for the type of the key and N is for the type of the binary node.

• L4: initializes the member field root to null.

Why does Java not allow a generic type to be instantiated (e.g., node = new N())?

Let us define searching methods:

What are the worst-case complexities of findNode(), findMinNode(), and findMaxNode()?

Let us define the add() method:

• L5: creates a node with the key to be the root if this tree does not include any node.

• L7: finds the appropriate location for the key and creates the node.

What does the add() method above do when the input key already exists in the tree?

Let us define the remove() method:

• L6: removes a node with two children using the Hibbard algorithm.

• L7: removes a node with no or one child

The removeSelf() method makes the node's only child as the child of its parent and removes it:

• L6: finds the child of node.

• L7: replaces node with its child.

The removeHibbard() method finds a node that can be the parent of the left- and the right-children of node and makes it a child of its parent:

Which nodes are guaranteed to be the parent of those left- and right- children?

The following demonstrates how the above removeHibbard() method works:

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

Binary Search Tree

Let us define the BinarySearchTree inheriting AbstractBinarySearchTree:

Unlike comparison-based algorithms in Sections 3.2 and 3.3, distribution-based sorting algorithms do not make comparisons between keys in the input array; instead, they distribute keys into ordered buckets and merge keys in the buckets.

Bucket Sort

Let us create an abstract class, AbstractBucketSort inheriting AbstractSort:

• L2: declares a list of buckets where each bucket is represented by a .

• L6: does not pass any comparator to AbstractSort since no comparison is needed.

• L7: creates a pre-defined number of buckets.

What kind of input keys can work with distribution-based sorting algorithms?

We then define a helper method sort():

• L7: bucketIndex is a function that takes a comparable key and returns the appropriate bucket index of the key.

• L9-10: adds the keys within the range in the input array to the buckets.

How many assignments are made by the sort() method in BucketSort?

Integer Bucket Sort

Let us create the IntegerBucketSort class inheriting BucketSort that sorts integers within a specific range in ascending order:

• L2: takes the smallest integer in the range.

• L8: passes the number of buckets, max - min, to be initialized to the super constructor.\

We then override the sort() method:

• L3: passes a lambda expression that takes key and returns key - MIN indicating the index of the bucket that key should be assigned to.

Is it possible to implement DoubleBucketSort that can handle double instead of integer keys?

Radix Sort

Let us create an abstract class, RadixSort, inheriting BucketSort<Integer>:

• L3: creates 10 buckets to sort any range of integers.

• L6: returns the order of the most significant digit in the input array.

LSD Radix Sort

Let us create the LSDRadixSort class inheriting RadixSort that sorts the integer keys from the least significant digit (LSD) to the most significant digit (MSD):

• L5: iterates from LSD to MSD.

• L7: the lambda expression returns the bucket index, the value in the 'th significant digit.

Benchmarks

The followings compare runtime speeds between advanced sorting algorithms where the input arrays consist of random integer keys:

A binary search tree gives the worst-case complexity of $O(n)$for searching a key when it is not balanced, where $n$ is the number of nodes in the tree:

To ensure the complexity, it needs to be balanced at all time (or at most time).

Rotation

There are 4 cases of unbalanced trees to be considered:

• Left linear [3, 2, 1]

• Right linear [1, 2, 3]

• Left zig-zag

These cases can be balanced by performing rotations as follows:

What should happen to the subtrees (red/orange/green/blue triangles) after the rotations?

Abstract Balanced Binary Search Tree

Let us create an abstract class that inherits the abstract class AbstractBinarySearchTree:

Where does node end up being after the rotations?

The followings demonstrate how the rotateLeft() method works:

Let us override the add() and remove() methods that call the abstract method balance():

• L3: calls the add() method in the super class, AbstractBinarySearchTree.

• L4: performs balancing on node that is just added.

What are the worst-case complexities of the add() and remove() methods above?

Overview

A trie is a tree where each node has:

• 0-to-many children,

• A key whose type is character,

• A value that can be any type of object, and

• An end-state that indicates if the node and its ancestors together represent the end of a certain word.

Let us consider the following list of strings:

Given the strings as keys, a binary search tree can be constructed as follows using a balancing algorithm:

How many character comparisons does it need to make to search a string in a balanced BST?

With the same list of strings, a trie can be constructed as follows:

• 1st cell: key (a character).

• 2nd cell: value (the index of the string that the node represents).

• 3rd cell: end-state (T for true, F for false).

What is the worst-case complexity of searching a string in a trie?

Let L be a list of country names in String where spaces are allowed (e.g., "United States", "South Korea"). Consider a trie where all country names in L and their unique IDs are put as key-value pairs as follows:

Implementation

• Create the class under the package that inherits by passing Integer as the generic type.

• Update the getEntities() method that takes an input string and returns the list of , where each entity consists of the begin index (inclusive) and end index (exclusive) of the first and the last characters of the corresponding country name respectively as well as the ID of the country name.

Report

• Write a report that briefly describe your approach and explains the worst-case complexity of your approach, and save it as quiz5.pdf.

Notes

• Substring matching of country names is not required. If your dictionary has "United States" as a country name and the input string contains "United Nation", the "United" should not be matched as a country name.

• Substring matching within input words are expected. If your dictionary has "America" as a country name and the input contains "American", the first 7 characters, "America"

Trie Node

Let us define a class, TrieNode:

• L1: the generic type T represents the type of value in L6.

• L2: is used to store the children.

• L4: true if this node represents the last character of a certain word; otherwise, false.

• L9: gives the complexity for searching a key.

What other types of maps are implemented in Java?

Let us define getter methods:

• L10: returns the map consisting of children's characters as keys and their nodes as values.

Is there any risk of returning this.children in L11?

Let us then define setter methods:

• L7: returns the previously assigned value of this node.

• L13: returns the child with the specific key if exists; otherwise, a new child with the key.

What does the removeChild() method return if key does not exist in this node?

Finally, let us define checker methods:

• L1: returns true if this node represents the last character of a certain word; false.

Trie

Let us create the class, :

• L1: defines a generic type T that can be any type.

• L5: initializes the root with the null character.

Let us define the find() method that takes a specific key in string and returns the node corresponding the last character of the key:

• L5: iterates through every character in the string.

• L6: finds the node whose key is the current character.

• L7

Given the find() method, let us define the get() method that takes a string key and returns the value of the node corresponding to the key in this trie:

• L3: checks if both the key exists and the key is a word.

We then define the put() method that inserts a key-value pair to the trie:

• L4-5: iterates through all characters in the key and adds children as necessary.

• L7: sets the end state of the node corresponding the last character to true.

What does node.addChild(c) return if the child with the key c already exists?

The following demonstrates how the put() method works:

Finally, let us define the remove() method that removes all appropriate nodes corresponding to the key:

• L2: retrieves the node corresponding to the last character in the key.

• L4: returns false the key does not exist or the key is not a word.

The following demonstrates how the remove() method works:

Auto-Complete

Most virtual keyboards provide the option of auto-complete, which gives a list of candidate words that you wish to type given a prefix you enter. For instance, when you type "sh", it gives a list of candidate words such as "she", "shell", "ship", etc.

If you select a word from the candidates, it should learn your selection as the top candidate for that prefix. For instance, if you select "ship" from the example above, the next time you enter the same prefix "sh", it should give a list of candidates where the first item is "ship" instead of "she".

Your task is to write a program that gives a list of candidate words for any prefix and learns the selected candidates.

Tasks

• Create a class called under the package:

  • This class extends the abstract class , which extends .

  • The value type of the generic T

Extra credit

• Create a class called under the package.

• Feel free to change the generic type, representing the value type of each TrieNode, to anything other than List<String> (List<something else>).

Notes

• Do not change the dictionary file. If you find anything peculiar about the dictionary file, please let me know so everyone works on the same copy of the dictionary file.

• Please test your program yourself. We will evaluate your program using our unit tests and measure the performance (both speed and accuracy).

• Take a look at if you are not familiar with methods in the standard library.

A disjoint set enables to be join sets efficiently. There are two methods implemented in this structure, inSameSet() and union().

In the following example, each key in {0, 1, 2, 3, 4} is initially in its own set:

inSameSet(1, 3) checks if the keys 1 and 3 are in the same set:

Coding

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

Test: LongInteger()

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

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

What is so special about primitive data types in Java?

Selection-based Sort

Selection-based sorting algorithms take the following steps:

• For each key where and

Contents

Abstract Sort

Let us create an abstract class :

• L2-4

Class

A is a template to instantiate an .

What is the relationship between a class and an object?

Let us create a class called

A binary heap is a PQ that takesfor both add() and remove(), where keys are stored in a balanced binary tree in which every node has a higher priority than its children (when used as a max-PQ).

When should we use a binary heap over a lazy PQ or an eager PQ?

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.

Coding

• Create a class called under the main package that extends the abstract class .

Contents

Auxiliary Method

Let us create and define testRobustnessAux() that checks the robustness of any PQ inheriting AbstractPriorityQueue:

Time

Let us define a static nested class Time under that stores runtimes for the add() and remove() methods in any PQ:

Contents

Red-Black trees preserve the balance at most time by satisfying the following conditions:

• Every node is either red or black.

• The root and all leaves (null) are black.

Interpretation

• Explain how the remove() method works in the class:

Contents

AVL (Adelson-Velsky and Landis) trees preserve the balance at all time by keeping track of the height of every node through a balance factor.

AVL Node

Let us create the class inheriting AbstractBinaryNode:

Contents

Implementation

• Create the class under the package.

Types of Graphs

There are several types of graphs:

Can we represent undirected graphs using an implementation of directed graphs?

Let us create the class:

• L2: the size of subset (-1 implies 1 ID, -2 implies 2 IDs, and so on).

The task of topological sorting is to sort vertices in a linear order such that for each vertex, all target vertices associated with its incoming edges must appear prior to it.

By Incoming Scores

The followings demonstrate how to perform a topological sort by incoming scores, where the incoming score of a vertex is define as the sum of all source vertices:

Complexity

Explain the worst-case complexities of the following algorithms in terms of V and E according to our implementations:

• Prim's algorithm

• Kruskal's algorithm

• Chu-Liu-Edmonds' algorithm

Comparison

Provide an example of a graph where Prim's and Kruskal's algorithms find different minimum spanning trees from the same graph and explain how these trees are found. If you cannot find an example, explain why these algorithms always find the same minimum spanning tree given the same graph.

Report

Write a report quiz7.pdf that includes the complexity and comparison analyses.