Complexity Exercises

This is a basic project designed to give you a chance to play with some of the concepts we’ve talked about so far, including psuedocode and complexity.

Repo link: https://github.falmouth.ac.uk/Games-Academy/comp101-samples

Getting started

This is a basic project designed to give you a chance to play with some of the concepts we’ve talked about so far, including psuedocode and complexity.

It’s also a good introduction to datatypes, but we’ll look at that more in the future.

clone this repository locally, you can fork it if you wish
look in the complexity project, you should see a 'Solutions' file with method stubs. These are the methods you need to implement for this workshop
Where possible, I’ve provided textual descriptions or psudocode for the algorithms we’re exploring

There is also a test suite to see if your solutions do what they are meant to do. I’ve also included a few advanced/evil test cases to see how your program handles unexpected inputs. These are commented out.

Once you have implemented your solutions, we can then start exploring the complexity of what you have built.

Escape Hatch Try to implement this without referring to example code (other than psuedocode), there are complete solutions available if you are really struggling.

Testing Complexity

Now you have your algorithms implemented, we’re going to have a look at the effects of the complexity we spoke about in the workshop.

First, we’re going to test Linear vs Binary Search. Look in program.cs, you will see a few lines commented out:

program.cs

//var result = ListStuff.BinarySearch(myList, myList[ ^2 ]);
var result = ListStuff.LinearFind(myList, myList[^2]);

Uncomment the LinearFind result. The code will no longer compile because it’s now invalid. There are two (reasonable) ways to fix this, implement one of them. You shouldn’t need to alter any code outside of this function to achive this.

Hat Syntax

Did you notice that in the previous two lines, there was some strange syntax you will likley not have encountered before. The statement myList[^2] means, take the second element from the end of the list.

To me it looks like XOR, but that’s probably a me problem. I only found out that’s a thing when writing the code and the IDE telling me off for what I wrote originally. There is always more to learn when programming!

How would you accomplish this in Python?
How would you write this without using the strange-hat syntax? (what line would I have written originally)

Binary Search

We have two possible approaches for our search code. Linear search is the one we’ve been using up till now. This searches from the begining of the list to the end, element by element. We have another option we talked about in the session. Binary Search. We’ll now experiment with it to see how it performs vs linear search, and when it might not be the best option.

Example 1. Linear vs Binary Search

Comment out the linear search approach from above, and try out the binary search approach instead.

What do you notice as the number of elements increases? What impact do we notice on performance?

You might want to kill (stop) the linear search version when it gets to the 10,000,000 element one…

Click here to check answer

Linear search is linear (ie, O(n)), it must search each item until it finds the one we care about
Binary search is log(n), as each 'iteration' it can skip half the remaining items

We’ve been searching the list for an element near the end of the list. This is the 'worst case' for linear search, as we need to search through almost the entire list before we find what we’re looking for.

Try altering the search, alter the [^2] to find a different item from the list:

Try searching for an third-from-last item in the list
Try searching for the third item in the list
Try searching for the item in the exact middle of the list (or one close to it)

Assumptions

Binary search relies on an assumption, about the input data. We will now violate this assumption to see what happens. Do you know what this assumption is?

Details

Binary search assumes the input data is ordered. We’re going to mess up the order of the numbers in the list so it isn’t anymore.

Use the shuffle method to shuffle the input data. Re-run the previous task (altering the [^2] to see what it now reports about our list).

Extention Task

There is one other assumption we’re making which makes (this) implementation of binary search quite fast. What might this assumption be? (hint what order do we access the elements in?)

Try modifying the code to test your assumption. There is a class implementing LinkedList in C#, but this does not implement the IList interface. We’re therefore going to have to alter the method arguments.

Exploring Futher: Dynamic Arrays

How do you remove an item from an Array? What if it’s in the middle? What about the begining? I’ve seen production code which makes a mistake about this and results in O(n) behaviour when it could be O(1)!

We are generally not allowed 'gaps' in our arrays: * we’re not talking about null, that’s technically not a gap * We’re also not talking about inputs which are are undefined - they exist we just don’t care about the value).

An array of size N must contain N elements, and they must be contiguous. It’s fairly common to have an array which is really larger than it is, but we 'pretend' it’s smaller. There are operating system reasons for doing this that are beyond the scope of COMP101, but there are also reasons we’d want to do it in our code.

For this section, assume we have an array with a real size (can store n elements, we’ll call this capacity), we’ll also assume we have a series of elements which actually contain data we care about, which can be less or equal to n values, we’ll call this the size. We can shrink the 'fake' size by modifying this size.

Removing from arrays

When we remove an element from the end of the list, we can 'pretend' the array is simply one shorter. However, if we want to remove an element from elsewhere in the list, we end up with a gap. How do we fix this? We need to move the 'gap' to the end, then we can 'pretend' the array is one shorter.

If we don’t care about the order, we swap the element to be removed with the last element
If we care about the order, we need to shuffle each element down the list until the gap is at the end

Q: What is the worst case? (ie, When must we move the most number of elements).

Adding elements

The same is true for adding elements to an array.

In general, it’s fast to add/remove from the end of a list (or 'faking it' with an array and a size parameter). It’s very slow to do the opposite (removing from the start of a list), why might this be?

(very) Advanced try implementing these approaches using an array (or multiple arrays) and a size parameter.

Looking Further

COMP290 (Computer Science students) look at benchmarking next year
Games students explore complexity in COMP280

Last updated 0001-01-01