School of Electronics, Electrical Engineering and Computer Science

Generation and Analysis of 3-SAT benchmarks

Internships Summer 2017

Proposed Project Title:

  • Generation and Analysis of 3-SAT benchmarks

Principal Supervisor(s):
  • Generation and Analysis of 3-SAT benchmarks


Project Description:

The satisfiability problem [1] is fundamental to Computer Science because on the one hand solvers for this abstract problem can be used to solve an enormous range of practical problems such as verifying the design of processors, timetabling, or even SuDoku puzzles, while on the other hand (unlike many other problems such as sorting a list of numbers)  it is not known exactly how difficult this problem is. Regular competitions are held [2] in which solvers tackle a wide range of problem instances with the aim of determining which is the best solver and which is the most difficult problem. Some very small yet difficult problems are known [3] and the idea is to investigate these further.

This project will involve learning how to carry out experiments running many programs, gathering and analysing information about how well they have performed. It will also involve writing programs to create new benchmarks to see whether it is possible to make them even harder. The programming can use Java, C or C++ and the operating system can be MS Windows or linux (or combinations of all of these) as desired.

[1] https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

[2] www.satcompetition.org

[3] http://dx.doi.org/10.1145/2746239


Objectives:
  • To learn about experimental as well as theoretical Computer Science
  • To implement a framework for executing many programs and gathering information on their performance
  • To experiment with a new technique for creating satisfiability benchmarks

 


Academic Requirements:

The scheme is open to all EEECS Undergraduates (apart from students on the BIT degree pathway and students who are due to graduate this summer)

We welcome candidates on all pathways, including CS and SE students and SESE and EEE students who have an affinity to programming.


General Information:

Each internship will last between 6-8 weeks and will pay a weekly stipend of £200.

Accommodation and travel costs are not provided under this scheme.

Start date: To be determined in conjunction with the successful candidate

Duration: 6-8 (Weeks) (project can be adjusted to 6 or 8 weeks depending on student availability)

Location: Computer Science Building

Further information available at: http://www.qub.ac.uk/schools/eeecs/Research/


Contact details:

Supervisor Name: Ivor Spence
Address:

Queens University of Belfast
School of EEECS,
Computer Science Building,
18 Malone Road,
Belfast
BT9 5BN

Email: i.spence@qub.ac.uk
Tel: +44 (0)28 9097 1875

For further information on Research Area click on link below:

https://en.wikipedia.org/wiki/Boolean_satisfiability_problem