Site pages

Programming

Participants

General

Task 1 - Hello World

Task 2 - Execution Time

Task 3 - Memory and Timing

Task 4 - Compilers and Timing

Task 5 - Anagrams

Task 6 - Linked LIsts

Task 7 - Polynomials

Task 8 - Queues

Task 9 - Hash tables

Task 10 - Stacks

Task 11 - Trees

Support

Miscellaneous

## Task 5.1 - RandomString

The attached archive contains code for a RandomString program which tests whether one randomly generated string is an anagram of another string. For simplicity and worst time behaviour we by default compare the string with a copy of itself. There are three algorithm stubs for this, but only one is implemented so far. The first one checks character by character whether all characters in the first string are present in the second string. You are to implement two more methods which are more efficient. Firstly, find a method which does not require additional memory to check whether two strings are anagrams of each other, but is faster then the one provided. Secondly, find a method which is allowed to use additional memory in order to do the anagram checking even faster. Any method is allowed to modify the character arrays provided. To show the difference between the three methods, upload a graph of the timings vs. the length of the string. Make sure your graph is properly labelled. Note, the string length is determined by encoding a random number of n-bits into a 36-base string (so the length of the string is given by the number of bits and the encoding indirectly).