Computer Science Large Practical (2014—2015)

Course Description

The Computer Science Large Practical exposes students to the problems that arise with the design and implementation of large scale computer systems, and to methods of coping with such problems. Students will gain experience in how to:

Further details can be obtained by visiting the drps page for the course.




There is no exam for this course, assessment is 100% based on the assigned coursework.


The coursework will be detailed further in the lectures.

The coursework handout is available here.

Example coursework input will appear in the Coursework Examples tab above.

General University and School of Informatics rules for course work


There are two parts, the deadlines are:



The coursework handout is available here.

The slides for the first lecture are available here.

The slides for the second lecture are available here.

The slides for the third lecture are available here.

The slides for the forth lecture are available here.

The slides for the fifth lecture are available here.

The slides for the sixth lecture are available here.

The slides for the seventh lecture are available here.

Several input examples have been posted to the "Coursework Examples" section.

The slides for the final lecture are available here.


Can I submit both an early submission version and a version for the end deadline and have the marks for whichever is highest?
No. Before the early submission deadline you have to choose whether or not you are going to hope for a mark above 90% now, or have an extra week to accumulate more marks up to 90%. The submission marked will be the latest one made before the deadline. Hence if you submit both before and after the early submission deadline, only the last submission will be marked and it will be capped to 90%.
What is the proposed maximum number of bins in a given area?
It is foreseeable that the number of bins in an area may limit e.g. the possibility of performing exhaustive search to find an optimal route. For this practical we will assume the number of bins in an area is specified as an uint16_t value, i.e. the maximum number is 65,535.
How long does it take to service (empty) a lorry at the waste processing facility?
While in practice it usual takes longer to empty a lorry than to service a single bin, to make things simpler we will consider these service times to be equal.
Can a lorry receive an updated route from the depot while in service, as a bin's occupancy threshold may be reached after the lorry's departure?
No. While this scenario is foreseeable, we will assume lorries are assigned routes only prior to their departure from the waste processing facility.
The occupancy of some bins may increase as a lorry traverses a planned route and as a consequence the lorry may not be able to service all assigned bins due to capacity constraints. How should the lorry proceed in situations like this?
How you deal with such events is a design choice you should make. You can either i) conservatively assign fewer bins on a single run, to avoid capacity problems, ii) return following the planned route without servicing other bins in that run if this happens, iii) compute the shortest path from the current bin and return to the depot, or iv) implement a combination of these or other similar strategies. Just make sure you explain your choice in the final report and comment your code appropriately.
What is the occupancy of the bins at the start of a simulation?
You can preload the bins at start time with a volume equivalent to a random value between zero and half the occupancy threshold.
How do I log overflows and how do I compute the percentage of overflowed bins?
It is reasonable to consider that an overflow occurs every time a bag is disposed at a bin that has reached its maximum capacity. It is also appropriate to log such events. On the other hand, when computing statistics, it may be more relevant to determine the percentage of bins that have overflowed. That is you should compute the ratio of the number of bins that overflowed at least once between two scheduled services, to the total number of bins.
How much does the written report weight?
The written report accounts for 25% of the final assessment.
What should I do if a lorry misses a schedule due to a lengthy previous journey?
You can schedule right away and try to catch the next planned slot. Be aware that this may occur in a cascade fashion.

Slides and Lecture Log

Slides for upcoming lectures should appear here before the lecture and will remain once the lecture has been given. Slides are subject to some minor modifications at any time prior to the start of the lecture.

Introduction - 19th September

Slides are available here. I finished at the coursework handout slide here.

I gave an overview of the course and discussed the requirements for the practical. I emphasised that these slides should not be seen as a substitute for reading and comprehending the coursework handout.

Simulator Components - 26th September

Slides are available here. I finished with clarifications at this slide.

I discussed the properties of the simulator, explained the exponential distribution, and introduced practical aspects of sampling from a probability distribution, with particular emphasis on pseudo-random number generation. I answered questions raised previously in class and offline.

Route Planning & Graphs - 3rd October

Slides are available here. I finished with a summary about choosing route planning algorithms.

I explained how service areas, bin locations and the distances between them can be modelled with weighted graphs. I reviewed fundamental graph theory concepts and discussed several heuristics that solve minimum cost Hamiltonian circuit problems.

Code Structuring & Coding Strategy - 10th October

Slides are available here. I finished with concluding remarks about refactoring and coding strategy here.

I discussed good code structuring practices, refactoring, janitorial work, and development approaches.

Memory Management. Code Optimisation. CSLP Assessment. - 17th October

Slides are available here. I finished with final points about the assessment here.

I discussed memory management aspects in C and common mistakes. I gave a few tips on code benchmarking and profiling. I discussed in detail the CSLP assessment criteria.

Array & string handling. Optimising compilation. - 24th October

Slides are available here. I finished with a discussion about IDEs here.

I discussed memory allocation/deallocation for matrices and structures, and a set of functions useful for manipulating strings. I explained compilation and linking, optimising compilation, as well as the pros and cons of working with multiple source code files.

Performance Evaluation - 31th October

Slides are available here. I finished with clarifications on metrics relevant to the CSLP. here.

I talked about the typical steps involved in the design and implementation of a system/process. I explained several concepts pertaining to performance evaluation and common evaluation methodologies. I discussed summary statistics, including standard deviation and confidence intervals. I revisited the metrics relevant to the CSLP assignment.

Review of Part One - 7th November

Slides are available here.

Example Input for the Main Coursework

An example input with two areas of different sizes, where bins are laid out on a grid structure, is available here.

An input script containing the description of a single area with some bins poorly connected is available here.

An example of invalid input exposing multiple issues is available here.

Last Updated: 6th November 2014 --- Paul Patras

Home : Teaching : Courses 

Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail:
Please contact our webadmin with any comments or corrections. Logging and Cookies
Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh