Lab 1

Overview

In this lab, you will design an efficient algorithm to search for some target item in a custom data structure called SortedList. If the item exists, you will return the index with the target, otherwise return -1.

Below are the relevant properties of the SortedList you will need for this lab. You can find more details about how the SortedList is implemented in Step 4 of this lab.

1. A SortedList is a finite list of items of unknown length in which all of the items are sorted in ascending order

2. This data structure has only one operation: 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
3. The data structure does not have an operation that returns the size, or the number of items in, the list.

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

Input:

• A SortedList, possibly with duplicate values.

• A target item to locate.

Output:

• If the target is present in the list, the index that contains target (an integer >= 0). If the target occurs multiple times, it is ok to return any index with the target in it.

• If the target is not present in the list, the value −1.

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: Comparing two naive algorithms

There are two naive approaches you can take to search for a target item in the SortedList data structure.

1. Linear search: For each index, starting from 0, check if the item at the index is either the target or null. If the item is target, return the index. If the item is null, return -1.

2. Find end + Binary search: For each index, starting from 0, check if the item at the index is null. Once you find null, you know the size of the list. Use the size to run the standard binary search algorithm.

Given a SortedList L with n items (although you don’t know what n is), your task is to determine which algorithm to use in two scenarios: when you are looking for just one item, and when you are looking for k different items.

In your write-up include:

• The best-case and worst-case time and space complexity for each of the two algorithms when you are looking for just one item. Make sure to include descriptions of what the best and worst case would look like.

• The best-case and worst-case time and space complexity for each of the two algorithms when you are looking for k items. Make sure to include descriptions of what the best and worst case would look like.

• The circumstances (if any) in which you would use one algorithm over the other.

Step 2: Designing a more efficient algorithm

Design, describe and analyze an algorithm that is more efficient than the two naive approaches described above. In your write-up include:

• A clear, unambiguous, human-readable prose description of the algorithm. To make the description unambiguous, you might want to include a few lines of pseudo-code. But the pseudo-code shouod be an addition to, and not a replacement of, prose description.

• An explanation or justification of correctness (why it works).

• An analysis of the time and space complexity of the algorithm when you are searching for one item and when you are searching for k items. Make sure to include descriptions of what the best and worst case would look like.

Step 3: Submit the write-up

Each member of the team should:

• Copy-paste the URL of the document into the Moodle submission box for the “Lab 1” assignment if you haven’t already.

• Go to Menu -> Download Markdown, which should produce an .md file. Save and upload that file, which will preserve the text of your answer in your course account. (Otherwise, access to the contents will be subject to the availability of a demo cloud service!)

Step 4: Understand the homework requirements

For homework, you will complete a Java implementation of the algorithm for the problem described above. You will want to work towards the details of the implementation in lab, after you’ve completed the writeup. The specification for the implementation is described below.

Starter files

Two starter files are provided:

• AmbiguousEndSearch.java: this contains a public class AmbiguousEndSearch containing a single function, which you have to complete, that should implement the search algorithm solving the problem above

• SortedList.java: this is the definition of an object that simulates the behavior of the data structure described in the problem statement above

You should not make any changes to SortedList.java; any code for your implementation should be in AmbiguousEndSearch.java or any helper files / classes.

These are both available from the Course Website (where you found the description for this lab).

Details about the SortedList data structure

The structure supports generic types, so that you can have a list of any data type that supports comparison in Java. In the declarations in the SortedList.java file, and in the descriptions below, the generic type T of items in a SortedList <T> must support comparison, and thus T is declared as follows:

public class SortedList <T extends Comparable<? super T>>

which is the standard way of saying that you can make lists of items of a type T as long as you can compare those items with each other.

Here is a description of some methods you may want to use.

• Accessing items: public T get(int index) returns:

  • the item at position index, if index is less than the number of items

  • null, if index is greater than or equal to the number of items

• Creating a new list:

  • From an array of objects: public SortedList(T arr)

    This is a constructor that takes an array of items of type T and creates a SortedList<T> from a sorted version of it. For example:

      Integer[] arr = {5, 1, 7, 2, 1, 5, 3};
      SortedList<Integer> labList = new SortedList<Integer>(arr);
    

    It’s important to note that this won’t work with an array of primitives, such as an int[].

  • From a collection of objects: public SortedList(Collection<T> c)

    This is a constructor that takes any Java collection of items of type T and creates a SortedList<T> from a sorted version of it. For example:

      ArrayList<Double> a = new ArrayList<Double>();
      a.add(3.14);
      a.add(2.718);
      a.add(1);
      a.add(0);
      SortedList<Double> labList = new SortedList<Double>(a);
    

  • A new random list of integers: public static SortedList<Integer> createRandomList(int lengthLower, int lengthHigher, int valueLower, int valueHigher)

    This is a static function of SortedList that takes four parameters:

    • The actual number of items will be a random number between lengthLower (inclusive) and lengthHigher (exclusive)

    • The values of the items will be chosen randomly between valueLower (inclusive) and valueHigher (exclusive)

    For example:

      SortedList<Integer> labList = SortedList.createRandomList(100, 200, 1000, 2000);
    

    will create a random SortedList consisting of between 100–199 numbers in the range of values 1000–1999.

Your implementation

You must implement the following function, declared in the AmbiguousEndSearch.java starter file:

public static <T extends Comparable<? super T>> int locateItem(SortedList<T> list, T target)

The parameter list is a reference to a SortedList data structure of elements of comparable type T, and the parameter target is a reference to the item to locate. You can assume that neither of these references are null.

The function should return –1 if target is not in list; otherwise, it should return the position of the item in the list.

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 AmbiguousEndSearch.java file only.

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

Scoring

To get scores call “java ComputeScores” after compiling your source code. It will call your AmbiguousEndSearch.locateItem() function with different instances of SortedList and different targets, 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.