THINK FIRST·CODE LATER

← All labs

The longest increasing run: Θ(n²) or Θ(n)?

Problem

In a string, an increasing run is a block of consecutive characters in which each character is greater than the one before ("abcd" in "xabcdab"). Write LongestRun, which reads words until the end of the input and, for each, finds the longest increasing run (the first one in case of a tie) twice, counting the character comparisons:

  1. every start — from each position, extend the run as far as it goes;
  2. one pass — walk through the string once, remembering where the current run began.

Print the run, its position and length, the two counts, and whether the two methods agree. For the input

welcome abcdefghijklmnopqrstuvwxyz zyxwvutsrq aabbccdd x

the program prints

welcome: longest increasing run "el" at index 1, length 2
  comparisons: 8 (every start) versus 6 (one pass); same answer: true
abcdefghijklmnopqrstuvwxyz: longest increasing run "abcdefghijklmnopqrstuvwxyz" at index 0, length 26
  comparisons: 325 (every start) versus 25 (one pass); same answer: true
zyxwvutsrq: longest increasing run "z" at index 0, length 1
  comparisons: 9 (every start) versus 9 (one pass); same answer: true
aabbccdd: longest increasing run "ab" at index 1, length 2
  comparisons: 10 (every start) versus 7 (one pass); same answer: true
x: longest increasing run "x" at index 0, length 1
  comparisons: 0 (every start) versus 0 (one pass); same answer: true

Which input makes the first method quadratic? Which one makes it as fast as the second?

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d6-7-data-1.txt

welcome abcdefghijklmnopqrstuvwxyz zyxwvutsrq aabbccdd x
What your program must print for d6-7-data-1.txt
welcome: longest increasing run "el" at index 1, length 2
  comparisons: 8 (every start) versus 6 (one pass); same answer: true
abcdefghijklmnopqrstuvwxyz: longest increasing run "abcdefghijklmnopqrstuvwxyz" at index 0, length 26
  comparisons: 325 (every start) versus 25 (one pass); same answer: true
zyxwvutsrq: longest increasing run "z" at index 0, length 1
  comparisons: 9 (every start) versus 9 (one pass); same answer: true
aabbccdd: longest increasing run "ab" at index 1, length 2
  comparisons: 10 (every start) versus 7 (one pass); same answer: true
x: longest increasing run "x" at index 0, length 1
  comparisons: 0 (every start) versus 0 (one pass); same answer: true

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d6-7-data-1.txt

Windows PowerShell does not understand <:

Get-Content d6-7-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.