DLS: What Every Computer Scientist Should Know About Computer History

Event details

  • When: 10th October 2017 09:30 - 16:00
  • Where: Byre Theatre
  • Series: Distinguished Lectures Series
  • Format: Distinguished lecture

What Every Computer Scientist Should Know About Computer History

Prof Ursula Martin

Distinguished Lecture Series, Semester 1, 2017-18


Professor Ursula Martin CBE FREng FRSE joined the University of Oxford as Professor of Computer Science in 2014, and is a member of the Mathematical Institute.  She holds an EPSRC Established Career Fellowship, and a Senior Research Fellowship at Wadham College. Her research, initially in algebra, logic and the use of computers to create mathematical proofs, now focuses on wider social and cultural approaches to understanding the success and impact of current and historical computer science research.

Prof Ursula Martin

Prof Ursula Marti

Before joining Oxford she worked at  Queen Mary University of London, where she was Vice-Principal for Science and Engineering (2005-2009), and Director of the impactQM project (2009-2012), an innovative knowledge transfer initiative. She serves on numerous international committees, including the Royal Society’s Diversity Committee and the UK Defence Science Advisory Council.  She worked  at the University of St Andrews from 1992 – 2002, as only its second female professor, and its first in over 50 years. She holds an MA in Mathematics from Cambridge, and a PhD in Mathematics from Warwick.


9.30 Introduction

9.35 Lecture 1:  The early history of computing: Ada Lovelace, Charles Babbage, and the history of programming

10.35 Break with Refreshments Provided

11.15 Lecture 2: Case study, Alan Turing,  Grace Hopper, and the history of getting things right

12.15 Lunch (not provided)

2.30 Welcome by the Principal, Prof Sally Mapstone

2.35 Lecture 3: What do historians of computing do, and why is it  important for computer scientists today

3.30 Close

Lecture 1. The early history of computing: Ada Lovelace, Charles Babbage, and the history of programming

IN 1843 Ada Lovelace published a remarkable paper in which she explained  Charles Babbage’s designs for his Analytical Engine. Had it been built, it would have had in principle the same capabilities  as a modern general purpose computer. Lovelace’s paper is famous for its insights into more general questions, as well as for its detailed account of how the machine performed its calculations – illustrated with a large table which is often called, incorrectly, the “first programme”.   I’ll talk about the wider context; why people were interested in computing engines; and some of the other work that was going on at the time, for example Babbage’s remarkable hardware description language. I’ll  look at different explanations for why Babbage’s ideas did not take off, and give a quick overview of what did happen over the next 100 years, before  the invention of the first digital computers.

Lecture 2. Case study, Alan Turing,  Grace Hopper, and the history of getting things right

Getting software right was a theme of programming for the days of Babbage onwards. I’ll look at the work of pioneers Alan Turing and Grace Hopper, and talk about the long interaction of computer science with logic, which has led to better programming languages, new ways to prove programmes correct, and sophisticated mathematical theories of importance in their own right.  I’ll look at the history of the age-old debate about whether computer science needs mathematics to explain its main ideas, or whether practical skills, building things and making things simple for the user are more important.

Lecture 3: What do historians of computing do, and why is it  important for computer scientists today

When people think about computer science, they think about ideas and technologies that are transforming the future – smaller faster smarter connected devices, powered by, AI, and big data – and looking at the past can be seen as a bit of a waste of time. In this lecture I’ll look at what historians do and why it is important; how we get history wrong; and in particular often miss the contribution of of women.  I’ll illustrate my talk with  my own work on Ada Lovelace’s papers, to show how  detailed historical work is needed to debunk popular myths – it is often claimed that Lovelace’s talent was  “poetical science” rather than maths, but I’ve shown that she was a gifted perceptive and knowledgeable mathematician. I’ll explain how the historian’s techniques of getting it right can help us get to grip with  topical problems like “Fake news”, and give us new ways of thinking about the future.

n-Queens Completion is NP-Complete

Peter Nightingale and Ian Gent at Falkland Palace, Wednesday, 17 August 2017.
©Stuart Nicol Photography, 2017

Ian Gent, Christopher Jefferson and Peter Nightingale have shown that a classic chess puzzle is NP-Complete. Their paper “Complexity of n-Queens Completion” was published in the Journal of Artificial Intelligence Research on August 30.

The n-Queens puzzle is a classic chess problem: given a chessboard of size n by n, can you place n queens so that no two queens attack each other?  That is, can you place the queens with no two queens are on the same row, column, or diagonal? The n-Queens puzzle has long been known to be simple to solve:  you can solve the problem for all n except 2 and 3, and solutions for all other n can be described in a few lines.  This very simplicity has led to repeated controversy in Artificial Intelligence (AI). The n-Queens puzzle is often used as a benchmark problem, but good results on the problem can always be challenged because the problem is so simple to solve without using AI methods.

The new work follows a challenge on Facebook on New Year’s Day, 2015, when a friend of Ian’s asked him how hard n-Queens is if some queens were already placed on the board.  It turns out, this version (dating from 1850) of the puzzle is only two years younger than the more famous n-Queens problem. The picture shows Peter (left) and Ian (right) with queens on the board at positions suggested by Nauck in 1850, the squares b4 and d5.  Can you put another 6 queens on the board so that the entire board is a solution of 8-Queens?  The general version with some number of queens preplaced on an n by n board is the n-Queens Completion puzzle.


With queens at b4 and d5, can you place 6 more queens to get a solution to the 8-queens puzzle? ©Stuart Nicol Photography, 2017

Ian, Christopher and Peter have shown that the n-Queens puzzle is in fact hard, not simple.  It belongs to the complexity classes NP-Complete and #P-Complete. Other NP-Complete problems include the “travelling salesperson problem”, finding cliques in graphs, and many other important problems, from scheduling to circuit layout. This puts n-Queens Completion at the centre of the most important theoretical problem in computer science — it has long been known that either all NP-complete problems are easy, or none of them are. Most computer scientists believe that this means there is no efficient algorithm possible for solving this problem, compared to the very simple techniques long known for n-Queens.
The importance of this work is that it provides researchers with a benchmark that can be used for evaluating AI techniques. Moreover, it helps to explain why so many AI techniques have been used on the n-Queens puzzle. Most techniques do most of their work with some queens partially placed, using some form of (hopefully intelligent) trial and error. In fact it turns out that many researchers – in order to solve a simple problem – have solved it by turning the simple problem of n-Queens into the hard problem of n-Queens Completion.
It does seem that AI researchers should not use n-Queens as a benchmark, but the very closely related n-Queens Completion puzzle is a valid benchmark. As well as the theoretical results, the paper shows how example instances can be generated which appear to be hard in practice. Some caution is still needed, though. It does seem to be quite hard to generate hard instances of n-Queens Completion.
The University has also issued an article on the same paper, under the title “Simple” chess puzzle holds key to $1m prize

Seminar: Propagation and Reification: SAT and SMT in Prolog (continued)

Event details

  • When: 23rd June 2017 13:00 - 14:00
  • Where: Cole 1.33a
  • Series: AI Seminar Series
  • Format: Seminar

Jacob Howe, City University, London

Abstract: This talk will recap how a watched literal DPLL based SAT solver can be succinctly coded in 20 lines of Prolog. The focus of the talk will be the extension of this solver to an SMT solver which will be discussed with a particular focus on the case where the theory is that of rational-tree constraints, and its application in a reverse engineering problem.
[Note change of time from that previously advertised]

Best Final Year Student at Lovelace 2017

We are delighted to congratulate Iveta Dulova, who attended the 10th BCSWomen  Lovelace Colloquium, and walked away with the prize for “Best Final Year Student”. Iveta’s poster, titled “SensorCube: An end-to-end framework for conducting research via mobile sensing“, was based on her final year project supervised by Dr Juan Ye.

The event was held at Aberystwyth University on April 12, 2017. Also attending from St Andrews were Chloe Collins, competing in the second year category with the poster “Pedal to the metal – the role of technology in transportation” and Laura Brewis with her poster “What percentage of solitaire games are actually winnable?”.

It showed great commitment for these three students to undertake the lengthy trip at a busy time of semester. Like St Andrews, Aberystwyth, is a beautiful small seaside town with an excellent Computer Science department.  Iveta took a couple of photos showing off the beach and the campus.

DLS: Algorithms for healthcare-related matching problems

Event details

  • When: 31st March 2017 09:15 - 15:30
  • Where: Lower College Hall
  • Series: Distinguished Lectures Series
  • Format: Distinguished lecture

Algorithms for healthcare-related matching problems

Distinguished Lecture Series, Semester 2, 2016-7

David Manlove

School of Computing Science, University of Glasgow

Lower College Hall (with overflow simulcast in Upper College Hall)


Algorithms arise in numerous everyday appPicture of David Manlovelications – in this series of lectures I will describe how algorithms can be used to solve matching problems having applications in healthcare settings.  I will begin by outlining how algorithms can be designed to cope with computationally hard problems.  I will then describe algorithms developed at the University of Glasgow that have been used by the NHS to solve two particular matching problems.  These problems correspond to the annual assignment of junior doctors to Scottish hospitals, and finding “kidney exchanges” between kidney patients and their incompatible donors in the UK.
Continue reading

Seminar: Jacob Howe on Propagation and Reification

Event details

  • When: 15th December 2016 14:00 - 15:00
  • Where: Cole 1.33a
  • Format: Seminar

Jacob Howe, Senior Lecturer at City University London, and sabbatical visitor, will be giving a seminar to the AI Research Group at 2pm on Thursday 15th December in JC 1.33a.

The title and abstract are:

Propagation and Reification: SAT and SMT in Prolog

This talk will describe how a watched literal DPLL based Satisfiability (SAT)
solver can be succinctly coded in 20 lines of Prolog. The extension of
this solver to an Satisfiability Modulo Theories (SMT) solver will be discussed with a particular focus on
the case where the theory is that of rational-tree constraints, and its
application in a reverse engineering problem.

Seminar: Alice Toniolo on Computational Argumentation

Event details

  • When: 1st December 2016 14:00 - 15:00
  • Where: Cole 1.33a
  • Format: Seminar

Alice Toniolo, a new lecturer in Computer Science at St Andrews, will be giving a seminar to the Artificial Intelligence Research Group on Thursday 1st December 2016, 2pm, in JC 1.33a. All are welcome.

Computational argumentation: an overview of current reasoning and dialogue models and their applications

Abstract: Argumentation is the process of arriving at a decision for a controversial standpoint. Computational models of argumentation aim to imitate the human decision-making process by modelling reason for or against certain decisions and extract justifiable options. This talk will draw from philosophical studies to present the core concepts of argumentation theory in AI through a range of abstract, logical and dialogical models. I will focus on the potential of argumentation-based models employed by software agents to support reasoning and dialogue in the presence of incomplete, inconsistent and uncertain information. An application of argumentation-based reasoning is presented in the context of intelligence analysis. The agent-based tool discussed, called CISpaces (Collaborative Intelligence Spaces), employs argumentation to help analysts make sense of information in collaboration and provenance to establish the credibility of hypotheses.

Computer Science Student Reps 2016


We are delighted to congratulate the student representatives for 2016/7, elected by their peers. Reps play a very important part in the life of the school by providing a healthy communication channel between staff and the students they represent, and also by chairing and running the Staff-Student Consultative Committee, amongst many other roles.

The reps are shown outside the Jack Cole Building in November 2016, and are (from left to right)

  • Juris Bogusevs (1st year)
  • Seamus Bonner (1st year, library)
  • Keno Schwalb (3rd year, careers)
  • Christa-Awa Kollen (welfare)
  • Vika Anisimova (4th year)
  • Anastasiia Izmailova (2nd year, social)
  • Masha Nedjalkova (masters, careers, minutes)
  • Fearn Bishop (postgraduate research)
  • Robin Nabel (school president)

Many thanks to the reps for arranging this photo (taken by Alex Bain who can be seen in the reflection), which should help staff and students put faces to the names.

Thanks to everyone who volunteered to be a student rep.



Welcome to new 2016 PhD Students


The School is very happy to welcome its new group of PhD students who have started in 2016. Shown outside the Jack Cole Building on 13 October 2016 are:

(Back row, left to right) Fahrurrozi Rahman; Xue Guo; Teng Yu; Yanbei Chen; Guilherme Soares Carneiro; Yasir Alguwaifli; and Xu Zhu.

(Front row, left to right) Mun See Chang; Zahida Almuallem; Esme Benssassi; Sidi Zhan; and the Director of Postgraduate Research, Miguel Nacenta.

Absent from the photo are Dawand Sulaiman and Saad Attieh.

Two more Internship Opportunities

Two new internships for summer 2016 are available in the Artificial Intelligence Research Group.
Internship 1: “What did I just do and how can I do it again?”
Supervisors: Ian Gent & Chris Jefferson
Internship 2: “Mixed Integer Programming Backend for Savile Row”
Supervisors: Chris Jefferson & Peter Nightingale

The deadline for applying is Wednesday 4th May 2016.

More details in this pdf: Computer Science Internship Summer 2016