This course has a programming pre-requisite; we expect all students to be proficient coders. Students will need to create software programmes and/or develop spreadsheets that implement algorithms covered in this course. In some assignments, example code may be provided using languages/tools such as Matlab, Python, Excel, and Visual Basic for Applications; students will be expected to complete this code, typically in the language provided. Students are expected to draw upon their existing programming expertise to quickly adapt to any of these languages. Knowledge of common data structures such as arrays, lists, and dictionaries will be assumed.
As a minimum, we expect that you can trivially write computer code (eg in Python) for tasks such as the following:
1) Given the set X={A,B,C,D,E,F}, choose a random element from this set, i.e. choose some random y∈X.
2) Generate a vector/list that is a random ordering of X
3) Given a vector/list x=(x[1],x[2],x[3],x[4],..,x[n]), calculate f=∑ d(x[i],x[i+1]) (where i=1, 2, ..., n-1) where d(p,q)=(p-q)^2
4) Given the x above, and some j, k, form a new solution y which is the same as x except that the ordering of elements x[j], x[j+1], ..., x[k] has been reversed in y.
5) Using for loops (not built-in Python methods), combine two sets (ensuring duplicate items appear in the new set only once).
6) Assume now that the "sets" are stored in a sorted lists. Repeat step 5), showing how the lists being sorted can make the merge more efficient.
Students will be expected to confidently read and write mathematical expressions, be familiar with mathematical notation such as summations and sets (eg C=A ∪ B , D=A ∩ B , x∈C) and be confident using these to write algorithms. Student will also need a basic understanding of the two optimisation concepts of branch and bound and the Simplex algorithm; extra background reading material will be provided for students without these optimisation skills.
Students are expected to have a solid background in probability, and so be comfortable with expressions such as: P(A|B)=P(B|A)P(A)/P(B) and other basic concepts of probability.