Distinguished Lecture Series 2017: Professor Ursula Martin

On October 10th, we were delighted to welcome back Professor Ursula Martin from the University of Oxford, to deliver the semester one distinguished lecture series in the Byre Theatre. Earlier in her career Prof Martin was professor of Computer Science here, and in fact only the second female professor in the history of the University of St Andrews.

The lectures covered numerous aspects of the history of computing. A particular highlight was to hear about Ada Lovelace’s early work, on Ada Lovelace day. As a trained mathematician and computer scientist who has studied her papers in detail, Ursula has discovered new insights about Ada’s education and work with Charles Babbage. She also focussed on aspects of computing history that are often ignored, such as history of computing in countries other than the USA or UK. Another aspect was how, even today, the contribution of women in history is often ignored, which Ursula herself has been able to correct in some cases.

The well received lectures centred around what every computer scientist should know about computer history. Professor Martin is pictured at various stages throughout the lectures and with Head of School, Prof Simon Dobson, DLS Coordinator, Prof Ian Gent and Principal and Vice-Chancellor, Prof Sally Mapstone. Read more about Professor Martin and the individual lectures in what every computer scientist should know about computer history. Recordings of each lecture can be viewed at the end of this post.

Images courtesy of Ryo Yanagida.

Lecture 1- The Early History of Computing: Ada Lovelace, Charles Babbage and the early history of programming.

Lecture 2 – Case Study, Alan Turing, Grace Hopper, and the history of programming.

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

Computer Science hosts J.P. Morgan

Following on from a successful visit last year, J.P. Morgan returned to the School of Computer Science last week, to promote tech careers, internships and other student opportunities.

Staff from the company and CS students are pictured viewing project challenges and their solutions highlighted in their technology showcase whilst discussing future career openings and enjoying the complimentary pizza.

J.P. Morgan is a popular destination for our graduates demonstrated by four Alumni (Maria McParland, Nada Kartouch, Conner Somerville and Peter Cockroft) who were part of the team representing the company at the successful event.

School achieves Athena SWAN Bronze Award

Athena SWAN Bronze Award Logo

We are delighted to announced that the School of Computer Science has achieved an Athena SWAN Bronze Award, as recognition of our commitment to advancing gender equality.

Almost all teaching staff contributed to the application for the award, as well as many other staff in all categories, research students, masters students, and undergraduates. In congratulating staff, Simon Dobson as Head of School said:

It really does have all our fingerprints on it. The award reflects the fact that we’ve identified things that we wanted to change and have planned how to make them happen: from now on they’ll all just be “how things are” rather than part of an external process.

Gala Malbasic: Young Software Engineer of the Year 2017

Congratulations to Gala Malbasic who won Young Software Engineer of the Year 2017. The awards organised by ScotlandIS were presented at the ScotSoft Awards Dinner yesterday evening. The Young Software Engineer of the Year awards are awarded to the best undergraduate software projects from students studying computer science and software engineering in Scotland.

Gala’s project, Leap Up: The Keyboard Renaissance, set out to to make keyboard interaction faster and less complicated and involved creating a hardware prototype, using software to ensure optimal sensor performance and implemented a large gesture set for use within the system prototype. The final year project was supervised by Professor Aaron Quigley.

Judged against the level of innovation planning & organisation, technical difficulty, commercial and/or social relevance, quality of engineering quality of presentation and level of knowledge & previous research, Judges considered Gala’s project to be exceptional.

As overall winner, Gala received a cheque for £2500 from Sopra Steria, and a trophy from ScotlandIS.

Watch Gala describing her project on YouTube.

Read more about the awards at FutureScot: Women sweep the board at Scottish software engineering awards

Photos courtesy of Aaron Quigley.

Computer Science Ball 2017

Postgraduate students, led by Paul Dobra, organised the first ever CS Ball in August. The celebration coincided with finishing summer dissertations and the annual poster and demo session. The school sponsored Smurfalicious Blue Ball proved very popular and sold out of tickets earlier in August. The theme was blue and the location was The old Manor Hotel, in Lundin Links. The evening comprised of champagne, dinner and a Ceilidh till midnight. Students are pictured enjoying the 3 course dinner and fully embracing the spirit of a Cèilidh. We look forward to seeing them at December Graduation.

Images courtesy of Paul Dobra, Ula Rustamova, Nick Tikhonov, and Xu Zhu.
– Main Organisers: Paul Dobra & Shyam Reyal
– Promotion (online): Yin Noe, Nouchali Reyal
– Promotion (offline): Gillian Baird, Fiona George, Midhat Un Nisa
– Material Design: Yin Noe
– Photography: Ula Rustamova and Nick Tikhonov
– Decorations: Fiona George, Midhat Un Nisa, Anke Shi, Masha Nedjalkova, Sihan Li
– Electronics / Multimedia / Drone: Xu Zhu
– Music for Disco: Blair Fyfe


Gala Malbasic: Finalist in Scottish Software Engineer of the Year

Congratulations to St Andrews student Gala Malbasic, who has been selected as one of the finalists in the Young Software Engineer of the Year Award 2017.

The Young Software Engineer of the Year Awards are given for the best undergraduate software projects completed by students studying computer science and software engineering in Scotland.

Gala graduated in Computer Science from St Andrews earlier this year, her Major Software Project – Leap Up: The New Keyboard Renaissance, incorporated novel uses of the Leap Motion sensor and was supervised by Professor Aaron Quigley.

Previous finalists and prize winners have included,
Simone Ivan Conte, Sam Elliott,Thomas Grimes, Alistair Scott, Craig Paul, Angus MacDonald, Ben Catherall and Graeme Bell. The number of finalists is further testament to the quality of talented students graduating from the School of Computer Science at St Andrews.

The winners of this year’s award will be announced on 5th October 2017!

Computer Science Orientation and Welcome 2017

After advising and induction events, staff and students are pictured enjoying a welcome reception and orientation activities, coordinated by Uta Hinrichs. The annual orientation gaming session proved as popular as ever and offered retro classic digital games and traditional board games. The gaming session was closely followed by a well attended welcome reception for the consumption of Twiglets and Irn Bru.

Ott: Effective Tool Support for the Working Semanticist

ACM SIGPLAN has judged Ott: Effective Tool Support for the Working Semanticist, by Peter Sewell, Francesco Zappa Nardelli, Scott Owens, Gilles Peskine, Thomas Ridge, Susmit Sarkar, and Rok Strniša, to be the recipient of the Most Influential ICFP Paper Award for 2017. From the citation:

“Over the past ten years, ICFP researchers have benefitted tremendously from the open-source tool and the effective design space exploration that it promotes.”

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