PA2 - Balanced Books

Prof Hott’s son loves books–some days more than others. He gives each book a reading score (as a positive integer) defining how many times he’s read that book. Each time the books get put back on the shelf, they end up in a slightly different order! Maybe at some point he’ll step back from the shelf and declare “this is a good order!” and leave them, but he wants a balanced bookshelf. To help him out, we’re asking you to construct an algorithm that calculates how balanced a given ordering of books is. Given \(S\), a list of reading scores of the \(n\) books in the order they currently appear on the shelf, your job is to calculate the balance \(B\) for the entire shelf.

The balance of a shelf of books \(S\) is defined as follows. Let \(B_L\) be the number of times any book was read more than the books to its left; likewise, let \(B_R\) be the number of times any book was read more than the books to its right. Note that if all the books he read the most were at the far right of the bookshelf, \(B_L\) would be large and \(B_R\) would be small. A balanced bookshelf would have \(B_L\) and \(B_R\) values that are close to one another. We denote the balance score \(B\) for the bookshelf \(S\) as the absolute value of the difference of \(B_L\) and \(B_R\). For example, given the following shelf of books (denoted by reading score):

S = [10, 2, 8, 4, 12]

• \(B_L\) is 6, since 12 is larger than everything to its left, 4 is larger than 2, and 8 is larger than 2 (for a total of 6).
• \(B_R\) is 4, since 10 is larger than three values to its right (2, 8, 4) and 8 is larger than 4 (for a total of 4).
• The overall balance score for the bookshelf is \(B = \lvert B_L - B_R \rvert = \lvert 6 - 4 \rvert = 2\).

Requirements

Construct a divide and conquer algorithm that is given a bookshelf of books (as reading scores) and returns the absolute value of the difference of \(B_L\) and \(B_R\) for that bookshelf ordering: \(B = \lvert B_L - B_R \rvert\).

Note: you should write a second, recursive function that takes the input described below and returns something that is helpful with your recursive divide and conquer strategy. Then modify your output for the final return value we are looking for.

Input

Your program will be given, as input, an array of reading scores in the order the books appear on the current bookshelf.

Output

Your output will be the balance score, returned as a single integer value.

Running Time Requirements

The worst-case asymptotic running time of your program should belong to \(O(n \log n)\), where \(n\) is the number of books on the shelf.

Example

Given the following input to your algorithm:

[10, 2, 8, 4, 12]

You should return:

2

Submission Requirements

• Your algorithm must be written in Python 3.10.6 or Java 19.0.2 (OpenJDK)
• You must download the appropriate wrapper code based on the language you choose: Main.py and Balance.py for Python; Main.java and Balance.java for Java.
  • Java package: pa2-java.zip
  • Python package: pa2-python.zip
• Implement the compute() method in the Balance class. The compute() method should call a recursive function that you write, passing in the input we provide. The compute() method should then return a single integer. Hint: your recursive algorithm may return a different value or values!
• You may modify the Main.java or main.py files to test your algorithm, but they will not be used during grading.
• You must submit your Balance.java or Balance.py files on Gradescope. Do not submit Main.java, main.py, or any test files.
• A few other notes:
  • Your code will be run as:
    python Main.py or python3 Main.py for Python,
    or javac *.java && java Main for Java.
  • You may upload multiple Java files if you need additional classes, but do not assign packages to the files.
  • You may not use any graph packages for this assignment.
  • Please note that you are responsible for analyzing the running time of any algorithm you use and ensuring that they satisfy the runtime requirements for this assignment.

Rules on Collaboration and Outside Sources

You must follow the rules about Collaboration and Outside Sources in the syllabus.

Use of Generative AI

For PA2, you are not allowed to use generative AI tools to help you solve this problem.