Unit information: Advanced Topics in Theoretical Computer Science (Teaching Unit) in 2020/21

Unit name	Advanced Topics in Theoretical Computer Science (Teaching Unit)
Unit code	COMSM0068
Credit points	0
Level of study	M/7
Teaching block(s)	Teaching Block 1 (weeks 1 - 12)
Unit director	Dr. Clifford
Open unit status	Not open
Pre-requisites	COMS10014 Mathematics for Computer Science A and COMS10013 Mathematics for Computer Science B or equivalent. COMS10017 Object-Oriented Programming and Algorithms I or equivalent. COMS20010 Introduction to Algorithms II. COMS30042 Advanced Algorithms.
Co-requisites	Assessment Unit COMSM0069 Advanced Topics in Theoretical Computer Science.
School/department	School of Computer Science
Faculty	Faculty of Engineering

Description including Unit Aims

This topics course exposes the students to a selection of advanced topics in theoretical computer science related to “Theory A” and complexity. These may include (but are not restricted to) time, space, circuit or communication complexity, and distributed, randomised, parameterised, streaming or approximate counting algorithms.

While results and problems of recent origin may be included in the syllabus, the instructors aim to make the material accessible to all students fulfilling the prerequisites by providing complete lecture notes and including all necessary background material.

The unit is suitable for students with a firm grasp of the basic concepts in the 2nd and 3rd year algorithms courses, and likely of interest to those planning to move into industrial or academic research.

Intended Learning Outcomes

On successful completion of this unit, students will:

1. Understand and recall elements of the state of the art in “Theory A” research.
2. Understand, recall and analyse a variety of advanced algorithms and data structures.
3. Be able to apply sophisticated design techniques to create new algorithms or new hardness proofs in different paradigms.
4. Demonstrate an understanding of the role of randomness in complexity theory and algorithm design.

Teaching Information

Teaching will be delivered through a combination of synchronous and asynchronous sessions, including lectures and self-directed exercises.

Teaching will take place over Weeks 1-7, and for students assessed by examination, consolidation and revision sessions in Weeks 11 and 12.

Assessment Information

January timed assessment.

Reading and References

• Cormen et al, Introduction to Algorithms, 3rd Edition (MIT Press, 2009) ISBN: 978-0262033848. Freely available online (as well as physical copies) via the Bristol library system.
• Dasgupta, S, Papadimitriou, CH and Vazirani, UV, Algorithms (McGraw-Hill Education, 2006) ISBN: 978-0073523408. A draft is available online.
• Excellent notes by Jeff Erickson. These are freely available.
• Mitzenmacher, M. and Upfal, E., Probability and Computing (Cambridge University Press, 2012) ISBN: 978-0511813603
• Arora, S. and Barak, B., Complexity Theory: A Modern Approach (Cambridge University Press, 2009) ISBN: 978-0521424264