Lab 2

Problem

In this lab, you will design an efficient algorithm to find the item at rank k within two custom list data structures SortedListWithEnd. This data structure, like SortedList from Lab 1 is a finite list of items, where the items can be of any type which can be compared to each other. All of the items in a SortedListWithEnd are sorted in ascending order. This data structure has two operations:

1. get(index) which runs in O(1) time. This operation returns:
   • the item at the position index, if index is less than the number of items in the list OR
   • null, if index is greater than or equal to the number of items in the list

2. size() which runs in O(1) time and returns the size of the list.

3. getCount() returns the number of times you’ve queried into any SortedListWithEnd. This can be used to ensure that your algorithm has the right time complexity.

4. add(item) adds a student to the end of the StudentList. You only want to use this if you know that item you are adding is greater than the current item at the end of the list – otherwise this operation would violate the sorted property of the list.

Your goal is to design an algorithm that can genereate the correct answer while minimizing the total number of get queries.

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.

Overview

In this lab, you will come up with two algorithms to solve the task under different constraints. Then, for HW2 you will implement these two algorithms in Java. The class for SortedListWithEnd is already provided. You need to just write the code for the two find_item functions in the FindRanks.java file.

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 an algorithm that solves the task using only constant space

For the first constraint, you need to find the item at the provided rank using only constant space — i.e., you are not allowed to create any data structures that scale up with the number of students or with the rank. Let m be the size of list1, n, the size of list 2 and rank the specific rank you are looking for.

Once you have an idea for an algorithm, do the following:

1. Justify why the algorithm is correct.
2. Compute the best case and worst case time complexity for finding the student for one rank value. Describe what the best and worst case input might look like.
3. Compute the best case and worst case time complexity for finding students for k different rank values. Describe what the best and worst case input might look like.

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: Design an algorithm that solves the task using one additional SortedListWithEnd

For the second constraint, you are allowed to use just one additional SortedListWithEnd with O(m+n) space complexity, where m is the size of the first list and n is the size of the second list. In other words, SortedListWithEnd is allowed to scale linearly with the total number of items across both lists

Once you have an idea for an algorithm, do the following:

1. Justify why the algorithm is correct.
2. Compute the best case and worst case time complexity for finding the item for one rank value. Describe what the best and worst case input might look like.
3. Compute the best case and worse time complexity for finding items for k different rank values. Describe what the best and worst case input might look like.
4. Discuss: what are the contexts in which you would want to use this algorithm over the previous algorithm you came up with?

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 3: Submit the writeup

• Create one markdown file per group with all of the required details outlined in the previous section. (You can use https://demo.hedgedoc.org/new if that worked for you last time)

• Each group member should submit the same markdown file to Moodle. In the submission comment indicate who you worked with.

Step 4: Understanding the program requirements

Once you are done submitting the writeup, spend some time understanding the requirements for the Java implementation of these algorithms.

Starter Files

Two starter files are provided:

• SortedListWithEnd.java which is the class with all the methods for the list data structure you will be working with. You can create a SortedListWithEnd in one of two ways: you can create it from an ArrayList of items (in which case the resulting StudentList will be sorted). Alternatively you can initialize an empty SortedListWithEnd and add items to this using the add(item) operation. As a reminder, when you are using add(item) you want to ensure that the item you are adding is greater than the current item at the end of the list – otherwise this operation would violate the sorted property of the list.

• FindRanks.java is the only file you will have to edit. You will write two functions. find_item1 refers to the algorithm desiged using the first constraint, and find_item2 refers to the algorithm designed using the second constraint. Make sure to comment your code and add test cases.

Additionally, you are also provided with ComputeScores.java which is an autograder that makes up 90% of your grade.

Remember: ComputeScores cannot (and should not) replace any testing that you do on your own!

Step 5 (ideally complete in lab): Program Design

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.

This program-design plan should be an outline of your implementation. It should consist of:

• function / method declarations

• for each function, a function-level comment that describes its purpose, explaining:

  • the meaning or role of each input parameter

  • relevant assumptions about the inputs or state of the program

  • a clear description of the output and/or any side effects of the function

  This should basically resemble the Javadoc that you find for the Java API.

• aim to keep functions simple, short, and easy to test, and avoid redundancy

• within each function, a pseudocode outline for that function’s purpose

  • elaborate or expand on every nontrivial loop or conditional

  • make notes about anything requiring more investigation (e.g., “look up how to compare generic items in Java”)

Step 6 (homework, next week): Coding, Testing, Program Submission

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

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

Scoring

To get scores call “java ComputeScores” after compiling your source code. It will call your two functions with different instances of StudentList 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.

Please note: Code that doesn’t compile and run, or code that times out, will receive a zero score.

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.