Department of Computer Science
The Strand, London WC2R 2LS, UK
  Undergraduate enquiries:
Postgraduate enquiries:
Fax: 		+44 (0)20 7848 2005
+44 (0)20 7848 2588
+44 (0)20 7848 2851
 
 



Manal Mohamed 2007/8 BSc/MSci individual projects

Supervisor: Manal Mohamed

Project Titles

Note: Please come to see me during my office hours (Thursdays 14:00-16:00, room 23F), if you wish to discuss any of the project proposals below.

Projects Descriptions

MM01: Necklace Swap Rhythmic Similarity Measures

A rhythm may be represented as a cyclic binary sequence where a zero denotes a rest (silence) and a one represents a beat or note onset, for example, the clave Son would be written as the 16-bit binary sequence: [1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0]. This rhythm can also be thought as a point in a 16-dimensional space (the hyperube). The swap distance between two rhythms is the minimum number of swaps required to convert one rhythm to the other.

The aim of the project is to implement and visualise an algorithm to calculate the swap distance between to given rhythms.

MM02: Smallest Box

Finding the smallest box is an interesting problem with many applications in real life. In two dimensions, we would like to compute the smallest area rectangle that encloses a set of points.

The aim of this project is to develop a system which would support the following task. The user specifies a number of points on the plane. The hull of the set of point is then calculated. Using the calculated hull, the smallest area rectangle is then computed. Graham’s algorithm is one of the efficient algorithms for finding the hull of points.

The developed system has to have graphical interface which visualizes the computation of the proposed algorithm.

MM03: String Edit Distance

The words “computer” and “commuter” are very similar, and a change of just one letter, “p” to “m” will change the first word into the second. The word “sport” can be changed into “sort” by the deletion of the “p”, or equivalently, “sort” can be changed into “sport” by the insertion of “p”. The edit distance (also known as Levenshtein distance) is a measure of the similarity between two strings (words). Dynamic programming is used to solve the edit distance problem. Intuitively, solving the edit distance is equivalent to solving a single-source shortest path problem in Directed Acyclic Graph.

The aim of this project is to develop an educational software system which visualises the computation of both approaches for the edit distance problem.

MM04: Lowest Common Ancestor

The problem of finding a lowest common ancestor (LCA) in a tree is a basic problem in algorithmic graph theory. An LCA of vertices u and v in is an ancestor of both u and v that has no descendant which is an ancestor of u and v. This problem has been very extensively studied in the literature in the context of (rooted) trees.

The developed system has to have graphical interface which visualizes the computation of the proposed algorithm.

MM05: You Own Idea

I am ready to supervise any project based on your own ideas. Please come to see me during my office hours if you wish to discuss your project proposal.