Projects offered by Dr. Alexander Tiskin.
Main module website containing the syllabus, academic aims, and learning outcomes.
|
|
Projects offered by Dr. Alexander Tiskin. Main module website containing the syllabus, academic aims, and learning outcomes. |
My main area of interest is the design and analysis of algorithms. Historically, there has been a gap between algorithm theory and their practical use for real-life applications. This gap is being filled by the relatively new field of algorithm engineering, which is informed by advances in algorithm theory, and aims to provide a solid foundation for their practical implementation. Algorithm engineering requires a good understanding of the algorithms and the underlying mathematics, as well as good programming and experimental skills.
I currently offer algorithmic engineering projects in two areas of my recent research.
The Travelling Salesman Problem (TSP) is a classical combinatorial optimisation problem. It has been extensively studied both theoretically and practically. One particular area of interest is approximation algorithms for TSP. Together with Dr. Vladimir Deineko (Warwick Business School), we have designed a new algorithm that computes approximate solutions to TSP. Preliminary experiments show that our algorithm works surprisingly well on a particular set of input instances. The aim of the project is to create a high-quality implementation of the algorithm, that should be efficient, extendable and flexible; it is also desirable to have facilities for data visualisation. The project will also study existing data sets for TSP, and carry out an experimental evaluation of TSP approximation algorithms.
See also: a presentation of the algorithm [PDF presentation] [PDF handout]
Background on TSP: E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley and Sons, 1985.
A Wikipedia article on TSP. [HTML]
Algorithms on strings of characters is a rapidly developing branch of algorithm theory. The primary motivation for string algorithms comes from computational molecular biology, where strings represent genome sequences. One of the key algorithmic problems on strings is string comparison, where it is required to decide whether two input strings are similar or dissimilar. I have recently developed a new approach to string comparison, which is based on mathematical concepts and is applicable to a wide range of string-related algorithmic problems. The aim of the project is to implement algorithms based on the new approach, and to carry out an experimental study of their efficiency. The experiments should ideally be run on real-life data sets, such as genome sequences.
See also: a presentation of the method [PDF presentation] [PDF handout]
I am also offering a project entitled "Software tool for modelling the dynamics of branched neurons", to be supervised jointly with Dr. Y. Timofeeva. [Project description]
To get in touch with me, visit my contact page.
Home || Research | Publications | Teaching | CV | Contact
Last updated on 1 February 2008