Aims
To introduce strategies for the design of algorithms which are efficient in terms of time and space requirements.
Learning Outcomes
On successfully completing this module you should understand the basic techniques for designing algorithms for fundamental computational problems.
Provisional Syllabus
Introduction:
Algorithms and computational complexity
Asymptotic notation
Pseudocode
Algorithm design techniques:
Divide-and-Conquer: Quicksort
Dynamic programming: matrix chain multiplication
Greedy algorithms: Huffman codes
Order statistics:
Selecting the k-th smallest element of a list - a practical method
Selecting the k-th smallest element of a list - an optimal method
Lower bound on the time complexity of computing the median
Data structures for set manipulation problems:
Fundamental operations on sets
The union-find algorithm
Partitioning
Representations of directed and undirected graphs:
Adjacency-matrix and adjacency-list representations
Breadth-first and depth-first search using adjacency lists
Computing connected components of a graph
Strongly-connected and biconnected components
Topological sorting
Algebraic algorithms:
Strassen matrix multiplication algorithm
The Four Russians boolean matrix multiplication
Winograd's algorithm
LUP decomposition of matrices
Applications of LUP decomposition
Integer and polynomial arithmetic:
Integer and polynomial multiplication and division
Greatest common divisors and Euclid's algorithm
Chinese remaindering
Aims
To understand the major concepts and problems of computational molecular biology. To appreciate the importance of these concepts in a wide diversity of practical applications. To learn which of the computational molecular biology problems have efficient algorithmic solutions and which are intractable (for example, which belong to the NP-complete complexity class). For some intractable problems, to understand how heuristic approaches to problem solutions may yield fast but only approximate solutions.
Learning Outcomes
On completing the module you should be able to design exact and efficient algorithms as well as approximation schemes and heuristics for some of the most important algorithms underlying the field of computational molecular biology, or bioinformatics. You will also be able to reason why efficient algorithms for certain problems might not be possible.
Provisional Syllabus
Basic concepts: Definitions and notions from Molecular Biology; DNA Sequence Analysis
Alignement:
Hamming and Levenshtein distances
Dynamic programming algorithm
Hirschberg's algorithm
Substitution matrices (BLOSSUM, PAM) and scoring
Seq vs Seq (Fasta, Dynamic Programming)
Seq vs Databank (BLAST)
Whole genome alignment
Multiple sequence alignment
Approximate string matching:
String matching with "don't cares"
Searching with differences
Searching with mismatches
Fragment assembly:
Shotgun sequencing
Gene detection:
Regular expressions, acceptor and donor sites
Alternative splicing
Secondary structure prediction:
RNA structure
Minimal free energy (Zuker's approach)
Protein Folding
Phylogeny:
Mapping and rearrangements
Clustering and classification techniques
2:1 degree in a suitable quantitative discipline, such as mathematics, physics, computer science, or engineering. A 2:2 honours degree may be acceptable depending on the candidate's academic background. A sound background in basic mathematics, in particular a familiarity with standard concepts of calculus, linear algebra, differential equations and elementary probability theory, will be assumed.
Please include transcripts of subjects taken in the relevant degrees and copies of all certificates and relevant qualifications mentioned in your application.
The Complex Systems Modelling MSc programme provided the perfect vessel to combine my previous pursuits, and the staff at King's provided a first-rate educational experience. The programme culminated with an individual research project which merged the concepts I had encountered in an attempt to tackle pertinent problems from the field. Studying at King's gave me the opportunity to explore new areas of research and pinpoint a subject I was passionate about. It also afforded the social benefits of a diverse student body.
King's is ideally situated in the middle of one of the most culturally diverse cities in the world, with campuses providing easy access to all that London has to offer. I had the chance to meet people from around the world in the melting pot that is the graduate student housing. Due to my experience at King's, I have decided to continue my education by pursuing a doctoral degree in complex networks. Thanks for a great year King's!
After completing my undergraduate degree in Spain, I decided to continue my studies abroad, and King's College London seemed like the perfect choice. It is a one-of-a-kind opportunity to study in a culturally enriching and international city and, what's more, I was fortunate enough to receive a departmental bursary which definitely helped me to cover my living expenses.
King's is not only one of the world's leading universities; it is also one of the few to offer an MSc programme fully devoted to Complex Systems. From the beginning, the Mathematics Department felt like home, staff were always willing to help in both academic and administrative matters. I have had the opportunity to meet students from all over the world who had very different academic backgrounds, and that made my experience even more interesting.
One of the programmes highlight is that many of the modules cover state-of-the-art topics, taught by experts in the field from the Disordered Systems Group. Moreover, the summer project is a chance to get involved and develop actual research, and I think this will be a highly distinguishing feature on my CV.
I joined the King's Disordered Systems group in January 2007, and I work on interdisciplinary applications of statistical mechanics to economics and biology, quantum integrability and other areas of interest. I obtained my first degree in Physics at the University of Barcelona and received my Ph.D in Theoretical Physics at the Katholieke Universiteit Leuven, under the supervision of Desire Bolle. Hereafter I was a postdoctoral research fellow at the University of Oxford and University of Rome.
The research activities of the King's Disordered Systems group concentrate on the analysis and development of mathematical theories and models with which to describe the statics and dynamics of disordered (or 'complex') systems in physics, biology, financial markets, and computer science. Such systems are characterised by microscopic (usually stochastic) dynamic elements with mutual interactions without global regularity; but with a significant degree of built-in competition and incompatibility, resulting in the existence of many locally stable states for the system as a whole, and a highly non-ergodic 'glassy' type of dynamics.
A postgraduate qualification in Mathematics is extremely desirable. King's graduates are highly sought after both nationally and internationally in research institutions and higher education, as well as in a wide range of professions.