Lab 3

Overview =========

In this lab you will come up with a Divide and Conquer algorithm to solve the problem from Lab 2 (i.e., given two sorted lists, return the item at rank k when both lists are considered). You will then summarize the contexts in which you would want to use all of the three algorithms you’ve designed for this problem. For HW3 you will implement this Divide and Conquer algorithm.

Problem review

Input

• Two SortedListWithEnd. These lists can have overlapping items.
• A rank starting from 1. In any given SortedListWithEnd, the item at the start of the list has rank 1.

Output

• The item at the specified rank when both SortedListWithEnd are considered if a valid rank is entered (i.e., 1 <= rank <= total items across lists). Otherwise return null.

Step 0: Creating a markdown file for writeups

• One person in your team should visit https://demo.hedgedoc.org/new to create an empty document

• Share the URL of the document created with the others in your team (e.g., email them the link in the address bar). When someone else visits the URL, they are able to collaboratively edit the document.

• Each person should copy and paste the URL of the document into the Moodle submission box for the “Lab 1” assignment. Do this right away, even before writing in the document, so that your course account has a link to your work.

Step 1: Design a Divide and Conquer algorithm that works under some simplifying assumptions

Design a divide and conquer algorithm that works under the following simplifying assumptions:

1. The rank k that we want to find is always a power of 2.
2. Assume that k is less than the size of both lists combined.
3. The two sorted lists are of equal lengths, each of size n.

Once you’ve designed your algorithm, do the following:

1. Justify why the algorithm is correct.
2. Compute the time complexity for finding the student for one k value.
3. Compute the time complexity for finding students for x different rank values.

Once you’ve worked on these parts, check in with the instructor/ TA to make sure that the algorithm is as efficient as it can be.

Step 2: Discuss the role of the simplifying assumptions

What parts of the analysis of your algorithm do the three simplifying assumptions assumptions impact? The correctness, time complexity or both? Explain why.

Step 3: Design a more general Divide and Conquer algorithm

Modify your previous algorithm to handle situations where none of the three simplifying assumptions hold.

Once you’ve designed your algorithm, do the following:

1. Justify why the algorithm is correct.
2. Compute the time complexity for finding the student for one k value.
3. Compute the time complexity for finding students for x different rank values.

Once you’ve worked on these parts, check in with the instructor/ TA to make sure that the algorithm is as efficient as it can be.

As you are working on this part, it might help for you to breakdown the algorithm design by tackling one simplifying assumption at a time, starting with assumptions 1 and 2 before moving onto assumption 3.

Step 4: Compare the different algorithms

You’ve now designed three algorithms to solve the same task – two algorithms in lab 2, and one in this lab. Discuss what are the circumstances in which you would use one algorithm over the other.

Step 5: Submit the writeup

• Each group member should submit the same markdown file to Moodle. In the submission comment add a link to the hedgedoc file and also indicate who you worked with.

Step 6: Program Design for the algorithm in Step 3

Your team should create a plan for how to translate the algorithm for the problem into an implementation that satisfies the requirements above. Before you leave lab, your team should have the TA/instructor review as much of your plan as possible. Be very careful as you think about what inputs you are passing in to each recursive call to ensure that your code is correct and as efficient as can be

Step 9 (homework): Coding, Testing, Program Submission

The Moodle page has a link to submit your code. Please submit your FindRanksRecursive.java file only.

You do not need to submit the StudentList.java file.

Scoring

To get scores call “java ComputeScores” after compiling your source code. It will call your two functions with different instances of SortedListWithEnd and different rank values, and will check that your function returns the correct value.

Some of the tests may focus on efficiency and will check the number of get queries your code makes.

Remember the score provided by the autograder for a given assignment will make up 90% of your homework score for that assignment. The other 10% will be based on the structure of the code, test cases and comments that explain both the logic of your code and the test cases.