Problem 1 of 4

A linear search checks list items one at a time from the front until it finds the target. The list is 4, 8, 15, 16, 23, 42, 7, 9 and the target is 9, which sits at the very end. Count how many items the search has to look at, and print that count.

Expected output: 8

data ← [4, 8, 15, 16, 23, 42, 7, 9]
target ← 9
count ← 0
FOR EACH item IN data
{
  count ← count + 1
  IF(item = target)
  {
    DISPLAY(count)
  }
}

Problem 2 of 4

Now a nested loop. For a list of 6 items, an algorithm compares every item against every item, including itself. Count how many comparisons that is in total, and print the count.

Expected output: 36

n ← 6
count ← 0
FOR EACH i IN [1..n]
{
  FOR EACH j IN [1..n]
  {
    count ← count + 1
  }
}
DISPLAY(count)

Problem 3 of 4

Compare the two directly. For n = 10 and then n = 100, print the number of steps a single loop takes and the number a nested loop takes. Print one line per size, in exactly this format: n=10 linear=10 quadratic=100

Expected output: n=10 linear=10 quadratic=100
n=100 linear=100 quadratic=10000

FOR EACH n IN [10, 100]
{
  linear ← n
  quadratic ← n * n
  DISPLAY("n=" + n + " linear=" + linear + " quadratic=" + quadratic)
}

Problem 4 of 4

Write from scratch. Some algorithms have to try every possible subset of their input, which takes 2 to the power of n steps. For n = 20, print the step count for a quadratic algorithm and for a subset algorithm, then print which of the two is unreasonable. Use exactly this format:
quadratic 400
subsets 1048576
subsets is unreasonable

Expected output: quadratic 400
subsets 1048576
subsets is unreasonable

n ← 20
quadratic ← n * n
subsets ← 2 ^ n
DISPLAY("quadratic " + quadratic)
DISPLAY("subsets " + subsets)
DISPLAY("subsets is unreasonable")