Computer Laboratory

Course pages 2014–15

Research Students Lectures

Taken by: MPhil ACS, Part III
Code: RSL
Hours: 4

Aims

To give Computer Laboratory research students the opportunity to design and give a lecture on a topic of particular interest to them to a friendly audience. Bring your sandwiches.

Lecture 1: Advait Sarkar Applied Probabilistic Algorithms for Big Data Analysis

28 October 2014, Room SW01, 13:00

Introductory algorithms courses encourage us to think of computers as perfect machines that calculate exact answers. We typically design programs to provide exactly this type of perfection. However, it is possible to construct efficient algorithms by relaxing the zero error constraint. The demand for space and time resources can be drastically reduced in exchange of a small, quantifiable probability of error.

In this lecture, we will follow the journey of MildlyInappropriateCatAppreciationSociety.com and its competitors as they try to tackle some of the problems of managing large amounts of cat-related data. Motivated by examples and terrible cat puns, you will learn 5 probabilistic techniques that allow you do things such as:

  • efficiently test whether an item is already present in a gigantic distributed database
  • efficiently count the number of distinct items in said big database
  • efficiently tabulate the frequencies of different items in said big database

You will learn these techniques and their error bounds in sufficient detail that you will be able to implement them once the lecture is finished. They can all be implemented in a few dozen lines of code!

Lecture 2: Daniel Thomas Using public-key cryptography in practice

4 November 2014, Room SW01, 13:00

Public-key cryptography is vital to the security of computer systems we use every day. How does it work? How can we use it to ensure our personal security integrity, confidentiality and privacy? In this lecture I will give an overview of how it works and what we can and do use it for. You should learn what technologies are available to you, what they might achieve and why they work. We will cover concepts including trapdoor functions, identity, trust and perfect forward secrecy. We will cover applications including GPG /PGP, DNSSEC , monkeysphere and OTR.

Course materials: https://www.cl.cam.ac.uk/~drt24/lecturing/rsl-public-key/

Lecture 3: Michael Gale Programming in Haskell

11 November 2014, Room SW01, 13:00

Haskell is a non-strict, purely functional programming language. That means programs may never be evaluated and can't have “side-effects” (e.g. displaying text on screen or receiving user input). Does that mean Haskell is useless? On the contrary! In this lecture, we will learn everything needed to support the following claim: every programmer should learn Haskell! It is both fun and challenging as it requires us to rethink our approach to writing programs and results in a deeper understanding of programming in general. No prior knowledge of the language is required.

Coursework

None

Practical work

None

Assessment

There may be a fun test set at the end of Michaelmas for which prizes will be awarded to the students providing the best answers.