Unit information: Advanced Algorithms (Teaching Unit) in 2020/21

Unit name	Advanced Algorithms (Teaching Unit)
Unit code	COMS30042
Credit points	0
Level of study	H/6
Teaching block(s)	Teaching Block 1 (weeks 1 - 12)
Unit director	Dr. Clifford
Open unit status	Not open
Pre-requisites	COMS10017 Object-Oriented Programming and Algorithms I or equivalent. COMS20010 Algorithms II or equivalent. Solid understanding of O-notation and recurrence relations, the “greedy”, “divide-and-conquer” and “dynamic programming” paradigms of algorithm design, proof by induction and contradiction, discrete probability. Previous exposure to pseudocode. A solid understanding of arrays, linked lists, and priority queues.
Co-requisites	COMS30041 Advanced Algorithms (10 credit exam assessment unit).
School/department	School of Computer Science
Faculty	Faculty of Engineering

Description including Unit Aims

This unit gives an overview of recent advances in the design of algorithms and data structures. These fall into two broad categories.

First, we will cover algorithms and data structures for fundamental problems surrounding storing, recovering and searching within data. For these problems we will see that nearly optimal solutions are possible.

Second are optimisation problems where sometimes only exponential-time algorithms are known. We will discuss when these problems admit exact efficient solutions, and when only approximation is possible.

Intended Learning Outcomes

On successful completion of this unit, students will:

1. Be able to apply sophisticated analysis techniques to measure the time and space complexity of algorithms and also prove their correctness.
2. Demonstrate a clear understanding of a variety of advanced data structures and their applications.
3. Be aware of and able to apply standard approaches to approximating the answer to (NP-complete) problems where finding the exact answer is infeasible.

Teaching Information

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

Teaching will take place over Weeks 1-7, with consolidation and revision sessions in Weeks 11 and 12.

Assessment Information

January timed assessment (100%)

Reading and References

As well as the books listed below, there are excellent notes by Jeff Erickson that are freely available online.

• Cormen, Thomas H 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, Sonjay, Papadimitriou, Christos and Vazirani, Umesh, Algorithms (McGraw-Hill, 2006) ISBN: 978-0073523408. A draft is available online.
• Gusfield, Dan, Algorithms on Strings Trees and Sequences (Cambridge University Press, 1997) ISBN: 978-0521585194. Freely available online (as well as a physical copy) via the Bristol library system.
• Mitzenmacher, Michael and Upfal, Eli, Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Cambridge University Press, 2005) ISBN: 978-0521835404
• De Berg, Mark et al, Computational Geometry: Algorithms and Applications (Springer, 2008) ISBN: 978-3540779735
• Kleinberg, Jon and Tardos, Éva, Algorithm Design (Pearson, 2013) ISBN: 978-1292023946