|
Course catalogue no: |
6117CIT |
|
Course title: |
Adv Topics in Computing Science |
|
Field of Education Code |
Computer Science |
|
Program/s |
2011Bachelor of Information Technology with Honours
5107 Master of Information and Communication Technology
|
|
Status of Course within program/s or academic plan/s |
Elective, honours |
|
Credit point value |
10 |
|
Prerequisites: |
Enrolment in Honours Program
or MIT |
|
Year and semester: |
Semester 1, 2008
|
|
Course convenor |
Prof. Vladimir Estivill-Castro
|
|
Teaching team members: |
Same as Course convenor |
The major aims and objectives of the subject are to introduce the student to the dynamic research in the area of algorithmic engineering.
This course will briefly review what is meant by intractable problems, especially those that fall in the category of NP-Hard problems. The intention is to show many examples of these problems without focusing in the mathematical proofs of their intractability. The course then will discuss techniques to attempt to solve hard computational problems despite their established intractability. The course will discuss approximation algorithms, heuristics and then will focus in all the algorithmic techniques provided by parameterized complexity. In particular, we will emphasize the idea of reduction rules or pre-processing that is common to all the approaches to deal with NP-Hard problems. The course will also emphasize a hands-on approach to their implementation of methods and algorithms to solve these problems and will explore and experiment with fixed-parameter tractable algorithms. Several open problems will be discussed as the field of parameterized complexity continues to grow and its impact continues to expand. We will discuss applications to bio-informatics, to game theory and to computational geometry
Lecture 1. - Motivation and Assumed Knowledge
Lecture 2.- Motivation for Approximation Algorithms, the TSP and PTAS
Lecture 3 .- Approximation Algorithms (techniques) [Based on P. Schuurman and G. Woeginger (2001), Approximation Schemes - A Tutorial.]
Lecture 5.- The Foundations of Parameterized Complexity
Lecture 6.- Reduction to a Problem Kernel.
Lecture 7.- Bounded Search Trees.
Lecture 8.- Dynamic Programming
Lecture 9.- Crown Structures, Iterative compression and Graphs Minor Theorem.
Lecture 10.- Method of Extremal Structure
Lecture 11.- Introduction to Algorithmic Game Theory
Lecture 12.- Linear Programming, Complexity and Algorithms for 2 players
Lecture 13.- Some FPT algorithms in BioInformatics
Emphasis will be placed in generic research skills. This course will teach written communication of summaries, executive reports and literature reviews of research articles . The students will practices these writing skills. This course will also teach analysis and critical evaluation. There will be guided practice in analysing the contribution and assessing the merit of research papers. Another aspect that will be emphasized is the analysis and critical evaluation of different paradigms in Algorithmic Enginenring. Issues where students will be asked to perform such practice are a consideration of traditional description of algorothms vs. implementation.
Problem solving and decision-making will be further developed by practical problemn. Skills leading to professional effectiveness will be fostered by the debate of issues like areas of application.
This subject is Mode A - Web Supplemented. A complementary WEB-site will make available lecture notes, WEB resources and reading lists with materials to complement lectures. Thus, participation on-line is optional for the student. Enrolled students will access information additional to that available in the University's calendar or handbook. The information includes the course descriptions and study guides, examination information, assessment overview and readings. The information is used to supplement traditional forms of delivery.
There is flexibility
in choosing 5 out of 11 packages of readings and students can propose their
own package. Students can propose the topic for the application of their programming
assignment and the programming language to implement the algorithm.
1. Two (2) executive summaries or research surveys (These are assignments that involve a package of reading and summarizing activities. Reading consists of reading 3-5 research articles and analysing and evaluating as a means to preparing an executive summary or survey). They must be between 1500 amd 2000 words excluding references. Each is worth 10% each (a total of 20% for the subject). You can submit up to 4 summaries out of different packages of readings, the best 2 will be used to compute your grade. A list of readings and their packaging will be available in the WEB site. You must add a reading to each package yourself with publication date 2000 or later. You may choose to build a package of your own. In that case, all papers must be from proceedings or Conferences after 2000 or from academic journlas.
·
DUE DATE: Week 4 and 8.
2. One programming assignment for 30%. You are required to program yourself an algorithm of your choice in the programming language of your choice. But is must clearly be an algorithm for a core techniques in Algorithm enginenring for an Np-Had/Compelte problem. You must provide a report of your implementation including testing that validates to some extent, its correctness.
·
DUE DATE: Week 12
3. Weekly exercises. Compete them by the Friday of the due date and submit by e-mailing a PDF file to the course convener. Each is worth 2%
·
DUE DATE: Week
4.
Exams. There will be 1 Final exam worth 20%.
·
EXAM Period
There is no prescribed textbook.
HOWEVER, the following are additional resources.