Lecutre 36 (Sherriff) - Algorithm Design 2

Lecture Date: Monday, April 13

Okay, computer scientists! I’ve got two new algorithms for you! Let’s see if we can code them up and figure out what the complexity is!

I call them yolosearch and yolosort.

Here’s the pseudocode for yolosearch:

1
2
3
while(I haven't picked the number I'm looking for yet) {
  pick a number at random from the list
}

We can even do advancedyolosearch!

1
2
3
4
5
6
7
8
make a copy of my list

while(I haven't picked the number I'm looking for yet) {
  pick a number at random from the list
  if it's not the number {
      delete it from the list
  }
}

There’s a slight problem with this algorithm. Every time we delete something from the list, all the indices change… so if we are looking for a particular index, this doesn’t work. If we are looking for a particular item from the list, it works fine.

What’s the complexity of these two searching algorithms? How do we know? Can we code them up?

Let’s take a look at yolosort now:

1
2
3
while(the list isn't in order) {
  shuffle the list
}

How about this one? What’s the complexity? How can we code it up? How long will it take to run?