MSc/PGDip Computer Science: Research Investigation CourseworkFrom 1 Jan 2006, this version of this document is no longer kept up-to-date. For a more up-to-date version, readers should consult hades.dcs.bbk.ac.uk/intranet/courses/cs/research.html.The research investigation forms an important component of the Part 2 coursework. Each of the lecturers teaching a second-year course has proposed one (or possibly more than one) topic connected with the material that they have been teaching, and has suggested some initial reading. There is a topic in Database, another in Software Engineering, and so on. (Details are appended to this note.) Each student will choose just one of these topics. Starting with the suggested reading but following pointers to other literature as they find out more about the subject, students will carry out a small project of desk research into their chosen topic. Sources include the following:
Having conducted their desk research, students will present their findings in an essay. This essay will, to some extent, summarise the material that has been gathered, but it should be more than just a summary. Students should approach the task in a critical frame of mind, evaluating the contributions presented in the literature, showing the relationships between them, and coming to their own conclusions. The text of the essay must be the students' own, expressed in their own words. Quotations should be few and brief and must be clearly acknowledged as quotations, with full references given in the manner of an academic journal. All the essays will be submitted to an on-line plagiarism detector. This will compare your essay with millions of documents on the web, including essays submitted by other students, and will highlight any passages that appear to come from an existing source. Any student who has copied without acknowledgement risks failing all of the Part 2 coursework, being disqualified from the MSc (i.e. being restricted to the PGDip), or even having their studies terminated.
The essay should be between 3000 and 5000 words in length. It should
be submitted as an email attachment to Gilda Change the above next year to: The contents of the submitted file should begin with the student's name, the module to which the topic relates ("Neural Networks", "Operating Systems" or whatever) and the title of the essay, followed by: "The text of this essay is my own, except where explicitly indicated. I give my permission for this essay to be submitted to the JISC Plagiarism Detection Service." The deadline is Tuesday 3 May 2005, the beginning of the second week of the summer term. This date has been chosen to enable students to devote some of the Easter vacation to the research, but to prevent them from eating into their revision time in the weeks immediately before the exams.
Algorithms and programmingExplain what it means to say that a problem is NP-complete. Illustrate this by selecting and discussing a suitable scheduling problem, and briefly discuss an NP-complete problem from a different problem domain. Brief descriptions of NP-completeness are given in the books referenced below. Other material is available on the web and in most books on algorithms. Weiss M A Data Structures and Algorithm Analysis in C++ Addison-Wesley (2nd edition, 1999) ISBN 0-201-36122-1 Sedgewick R Algorithms in C++ Addison-Wesley (3rd edition, 1998) ISBN 0-201-35088-2 Cryptography
Database ManagementHandling Incomplete and Imprecise Information in Relational DatabasesUse of null values has long been the standard SQL mechanism for representing incomplete information in relational databases. Researchers have investigated a number of approaches for more comprehensively capturing incomplete and imprecise information than is possible with the simple notion of a null value. A survey of approaches upto the mid-90s can be found in Sections 3.1 and 3.2 of Current Approaches to Handling Imperfect Information in Data and Knowledge Bases though of course work in the area has continued. Write an essay which explains the approaches to handling incomplete and imprecise information in relational database management systems and critically discusses the strengths and weaknesses of each. Illustrate your discussion with examples of ways in which incomplete and imprecise information techniques could be usefully applied to the familiar Suppliers-Parts-Projects database. Explain the changes that are needed to relational algebra/SQL, if any, to support each of the approaches discussed. You should limit your essay to only those approaches which extend conventional relational databases supporting relational algebra/SQL. You do not need to consider approaches to handling incomplete and imprecise information in object-oriented or deductive databases.
NetworksIEEE 802.11 Alphabet SoupThe Institute of Electrical and Electronic Engineers (IEEE) works on a very wide range of standards. Of particular interest to us is working group 802, LAN/MAN standards. IEEE 802This consists of 22 working groups from 802.1 (Higher layer LAN protocols) through 802.22 (Wireless Regional Area Network). Of particular interest to us is 802.11 (Wireless LAN). IEEE 802.11Early development on Wireless LANs (WLANs), also often referred to as Wireless Fidelity (WiFi), included industry-specific and proprietary protocols. At the end of the 1990s these were replaced by open standards with responsibility taken on by IEEE working group 802.11. A number of standards have been published, some of which are widely deployed.
Investigate these various standards by comparing their raw data rates (e.g. as specified above) and in their availability within computer networking products. In particular track the progress of 802.11n (Higher throughput improvements). Some suppliers are "jumping the gun" by offering 802.11n compatible products before the standard has been completed. Investigate these, and other standards-enhanced products. References
Neural networksMulti-Agent Reinforcement Learning as applied to General Sum Games: discuss, criticise, highlight novel aspects and identify specific areas where further research is neededThe general subject of games and reinforcement learning has received considerable attention in the last 5 years. In addition, there has been considerable work on multi-agent reinforcement learning in the last decade. Pointers to References:Multi-agent Reinforcement Learning: A Critical Survey. Y. Shoham, T. Grenager and R. Powers. (can be downloaded through the publications of Y. Shoham:
Sandholm TW, Crites RH (1996) Multiagent reinforcement learning in the Iterated Prisoner's Dilemma, BIOSYSTEMS 37 (1-2), 147-166. J. Hu and M. P. Wellman. Multiagent reinforcement learning: Theoretical framework and an algorithm. In 15th Intl Conference on Machine Learning, pages 242--250, 1998. Through the work of the following people who made significant contributions to this research area:
Object-oriented programming
Operating systems
Representing and querying data on the webSchema Languages for XMLA number of languages, other than DTDs and the XML schema definition language (XSDL) used in the module on representing and querying data on the web, have been proposed for defining document types. Some of the more theoretical of these include extended context-free grammars and regular tree grammars, while some of the more practical include RelaxNG and Schematron. Others include DSD (Document Structure Description), XDR (XML-Data Reduced), SOX (Schema for Object-Oriented XML) and still more. Write a critical survey that compares at least three of these languages, at most one of which can be either DTDs or XSDL. The survey should motivate why you chose the three languages and should compare them in terms of their expressive power, ease-of-use, efficiency of implementation and/or any other factors you consider appropriate. The survey should not include detailed descriptions of the languages, but should rather focus on their relative strengths and weaknesses, using examples to illustrate these. Some initial references are: Software EngineeringSoftware engineering has traditionally focused on building robust, reliable, fault-tolerant and efficient systems running on mainframes, personal workstations, LANs or the Internet. The proliferation of small sensing and computing devices has sparked interest into a new paradigm for embedded data processing and wireless data propagation, known as ubiquitous or pervasive computing. Write an essay in which you survey recent work on ubiquitous computing. Discuss how the limited resources of small devices (e.g. limited computation power, small memory size, unreliable and intermittent connectivity, limited bandwidth, small battery life), as well as the new application requirements, challenge traditional practices and design principles of software engineering. Explain to what extent the challenges pointed out have been addressed in existing ubiquitous computing systems. |
