Old French Bible Project

A project funded by the Undergraduate Research Assistant Scheme has successfully completed the first stage of interdisciplinary work, between the Institute of Mediaeval Studies and the School of Computer Science.  The long-term aim is to digitise and analyse early French bibles.

In this pilot project, undergraduate student Gregor Haywood, under the supervision of Prof. Clive Sneddon and Dr. Mark-Jan Nederhof, explored the feasibility of large-scale OCR technology for early printed text.  Scans from a French bible from 1543 were provided by the Special Collections of the University Library.  Much of the project consisted of iterations of automatic transcription, manual correction, retraining, and evaluation of accuracy.  In addition, problems were investigated that specifically arise from taking OCR technology designed for modern printed documents and applying it on early documents. Such problems include non-standard character sets, non-standard page layout, faded or smudged ink, and torn pages.

Despite of these problems, it was demonstrated that error rates below 3% are achievable, which paves the way for a continuation of these efforts.

Funding success for characterizing the adoption of ORCID ID in academic communities

Alex Voss from the School of Computer Science and Anna Clements and Eva Borger from the University Library have been awarded funding by OCLC for a 1-year project titled “Characterizing the adoption of ORCID ID in academic communities”.

ORCID iDs are persistent digital identifiers that distinguish researchers and, through integration in key research workflows such as manuscript and grant submission, support automated linkages between individuals and their professional activities ensuring that their work is recognized and attributed.

The funded project, which began in March, expands on a pilot study carried out in 2017 by Eva as part of her MSc dissertation project, which investigated the adoption and use of ORCID iDs among researchers at the University of St Andrews and identified key use cases and new avenues for advocacy.

The team now aim to carry out similar surveys at other institutions that integrate ORCID iDs and build a bigger picture of how advocacy, institutional processes and mandates relate to the adoption of ORCID iDs in academic communities. Based on these findings, they plan to formulate recommendations on how advocacy and policies regarding ORCID iDs can be employed to maximise their value in the research process.

Alex Voss has a related MSc dissertation, Consolidating Output and Citations Data, for students interested in this particular project or research area.

If you would like to find out more about ORCID iDs at the University of St Andrews, visit their ORCID pages. For more information about the project, please contact Alex Voss at alex.voss@st-andrews.ac.uk or visit the ORCID study blog for ongoing updates.

St Andrews – University of Primorska co-tutelle in Computer Science

The University of St Andrews and Primorska are soon to agree to award a joint degree with the title of Doctor of Philosophy (on condition that the joint PhD study programme in Computer Science will gain accreditation of the Slovenian Quality Assurance Agency for Higher Education). This represents the culmination of many months of effort from Drs Matjaž Kljun, Klen Čopič Pucihar and Professor Aaron Quigley. Aaron and Matjaž first met at the UMAP conference in 2011 in Spain as mentor and mentee in the PhD doctoral program. Since then, Matjaž and Klen who undertook their PhDs in the University of Lancaster have returned to Slovenia to establish and exciting program of HCI research and development in the HICUP lab. In 2017 a program of international support (Slovenian/English) allowed them to invite Aaron to Slovenia for three weeks and this has resulted in a number of join grant submissions and the establishment of this co-tutelle program. We look forward to many years collaborating and we look forward to this new PhD student starting later this year.

VISSOFT 2018 Keynote by Professor Aaron Quigley

Aaron will be a keynote speaker at the IEEE VISSOFT 2018 conference later this year. “The sixth IEEE Working Conference on Software Visualization (VISSOFT 2018) builds upon the success of the previous four editions of VISSOFT, which in turn followed after six editions of the IEEE International Workshop on Visualizing Software for Understanding and Analysis (VISSOFT) and five editions of the ACM Symposium on Software Visualization (SOFTVIS). Software visualization is a broad research area encompassing concepts, methods, tools, and techniques that assist in a range of software engineering and software development activities. Covered aspects include the development and evaluation of approaches for visually analyzing software and software systems, including their structure, execution behaviour, and evolution.”

Mensch-und-Computer 2019 Keynote by Professor Aaron Quigley

Professor Aaron Quigley will be a keynote speaker at the Mensch-und-Computer conference 2019 in Hamburg Germany in September of 2019. This series of symposia takes place each year in different German-speaking countries. This is one of the largest HCI conferences in Europe each year with over 700 delegates from industry and academia. Usability Professionals and Scientists come together in a multi-track program with long papers, short contributions, demos, tutorials and workshops. Submissions are possible in German and English.

Adriana Wilde (St Andrews): Rising to challenges in assessment, feedback and encouraging gender diversity in computing (School Seminar)

Abstract

This talk is in two parts, in the first of which Adriana will focus on her experiences in assessment and feedback in large classes, and in the second part on her work in encouraging gender diversity in computer science.

The focus of the first part will be on her involvement in redesigning an undergraduate module on HCI, where the methods of assessment used were no suitable for increasingly larger classes (up to 160 students). Redesign decisions needed to preserve the validity and reliability of the assessment whilst respecting the need for timely feedback. Adriana will specifically talk about the exam and coursework, and how learning activities in the module were aligned to the assessment, through the use of PeerWise for student-authored MCQs, and the use of video for assessment to foster creativity and application of knowledge. During the talk, there will be an opportunity for discussion on the challenges then encountered.

A (shorter) second part of the talk will present her experiences in supporting women in computing, starting with a very small-scale intervention with staff and students at her previous institution, and concluding with her engagement at the Early Career Women’s Network in St Andrews.

Event details

  • When: 23rd January 2018 14:00 - 15:00
  • Where: Cole 1.33a
  • Series: School Seminar Series
  • Format: Seminar

PhD viva success: Adam Barwell

Congratulations to Adam Barwell, who successfully defended his thesis yesterday. Adam’s thesis was supervised by Professor Kevin Hammond. He is pictured with second supervisor Dr Christopher Brown, Internal examiner Dr Susmit Sarkar and external examiner Professor Susan Eisenbach from Imperial College, London.

iVoLVER receives Best Demo Jury Award at ACM ISS

The iVoLVER system, created by Gonzalo Méndez and Miguel Nacenta from the SACHI group at the School of Computer Science, University of St Andrews, received Best Demo Jury Award at the ACM Interactive Surfaces and Spaces (ACM ISS) conference last week.

ACM ISS 2017, took place in Brighton, UK and selects a different location each year, with Tokyo, Japan selected as next year’s destination. The conference is a premier venue for research that studies how people interact in smart spaces and surfaces and how to design and engineer solutions for novel interfaces.

iVoLVER is a web-based visual programming environment that enables anyone to transform visualizations that they find in-the-wild (e.g., in a poster or a newspaper) into new visualizations that are more useful for them. Congratulations to the iVoLVER team. You can try out the open source iVoLVER prototype using a browser.

An example iVoLVER interface

Best Demo Jury Award

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

Update, 2021

Over the years since we published this research, many people have approached us having solved the n queens puzzle, either for one n like 8 or 1000, or having written an algorithm to solve it for different sizes.  Unfortunately this is not a major result in Computer Science and does not make one eligible to claim the $1M Clay prize. Many have been disappointed by this so we want to clarify why  this is the case. 

It is true that work on this problem could potentially result in the award but only if some exceptionally difficult conditions are met.

  • EITHER prove mathematically that NO possible algorithm could solve the n queens completion problem in polynomial time;
  • OR prove that there is an algorithm which is guaranteed to solve every instance of the n queens completion problem in polynomial time. Note that in this case the algorithm has to work on the completion version of the problem studied in our paper, not placing queens on an empty board; the algorithm has to give the correct answer on every possible instance given to it; and there has to be a mathematical proof that the algorithm’s runtime is bounded above by some polynomial in the size of the board.  However fast a given algorithm runs when tested, this is not sufficient because there are an infinite number of possible tests available, so a mathematical proof is required.
  • AND in either case, prove this at a level that is published in a respected academic source and is widely accepted by research experts as correct.

We are delighted that our work has led so many people to be interested in the problem of solving problems like the n queens puzzle that fascinates us.  But we also apologise for any impression we gave, unintentionally, that a solution to the n queens puzzle could lead to the award of the prize except under the extremely strenuous conditions listed above.

Ian Gent, 10 May 2021

Original Post from 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, 2017.

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

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

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