Task 1 Merge Sort

▪ Implement the following methods in the MergeSort.java:

1. Method mergeSort()

This method uses divide-and-conquer to sort an array. It must use merge() method

2. Method merge()

This method merges two sorted subarrays Reference: Lecture 5 Algorithms Part I, slide 20

How to test your code?

Use the MergeSortTest.java file to check whether your implementation passes the test cases or not. It may be used as an indicator that your code is working correctly. Please be aware that we will use additional test cases to verify and assess your code.

What is tracker class?

The tracker.java is used for marking purpose to track divide-and-conquer calls. Do not modify any code associated with the tracker. Otherwise, you will be penalized for violation.

Task 2 Karatsuba Multiplication

▪ Implement the following method in the MultiplicationAlgorithm.java: 1. Method KMultiply()

This method uses Karatsuba multiplication to compute the product x times y.

x and y are two n-digit input numbers Reference: Lecture 5 Algorithms Part I, slide 49

How to test your code?

Use the KMultiplyTest.java file to check whether your implementation passes the test cases or not. It may be used as an indicator that your code is working correctly. Please be aware that we will use additional test cases to verify and assess your code.

What is tracker class?

The tracker.java is used for marking purpose to track divide-and-conquer calls. Do not modify any code associated with the tracker. Otherwise, you will be penalized for violation.

Task 3 Edit Distance

▪ Implement the following method in the EditDistance.java:

1. Method minDistance()

This method computes the minimal total cost of a sequence of character edits between two strings.

The costs of character edits are defined in EditCost enum.

Do not modify the character edit costs. Otherwise, your answers will not be marked correctly. Reference: Lecture 7 Algorithms Part III, slides 10-14

How to test your code?

Use the EditDistanceTest.java file to check whether your implementation passes the test cases or not. It may be used as an indicator that your code is working correctly. Please be aware that we will use additional test cases to verify and assess your code.