School of Computing and Information Systems

comp10002 Foundations of Algorithms

Semester 2, 2018

Assignment 2

Learning Outcomes

In this project, you will demonstrate your understanding of dynamic memory and linked data structures,

and extend your skills in terms of program design, testing, and debugging. You will also learn

about graph algorithms, and implement a simple path discovery mechanism in preparation for the

more principled approaches that are introduced in comp20007 Design of Algorithms.

Background— The K¨onigsberg Bridge Problem

In the 18th century, in the town of K¨onigsberg, there were seven bridges that crossed the river Pregel.

These bridges connected two islands in the river with each other and with opposite banks. The city

council of K¨onigsberg and its citizens for a long time considered this problem: Is it possible to have a

continuous walk to cross all the seven bridges without recrossing any of them? This problem is known

as the K¨onigsberg bridge problem and belongs to the general area of graph problems. Figure 1a shows

a map of K¨onigsberg from the 18th century1, while Figure 1b gives a multigraph representation of the

K¨onigsberg problem.

Advanced Programming Techniques – Semester 2, 2018 Assignment Two (v1.0, 3 Sept 2018)

A S S I G N M E N T T W O : G E N E T I C A L G O R I T H M

A D VA N C E D P R O G R A M M I N G T E C H N I Q U E S – S E M E S T E R 2 , 2 0 1 8

SUMMARY

In this assignment, you will use your C programming skills to build a simple Genetic Algorithm.

A genetic algorithm (GA) is a heuristic search technique inspired by natural selection. A

population of candidate solutions to a problem is iteratively evolved towards an optimal

solution (as measured by an evaluation function) by:

? Evaluating the ‘fitness’ of candidate solutions according to the evaluation function

? Probabilistically selecting ‘fitter’ candidate solutions from the population to act as

‘parents’ for the next generation of candidate solutions

? Introducing constrained novelty to the new generation via operations analogous to

reproduction and mutation. (Note: the selection function will then tend to remove ‘bad’

novelty).

The course Canvas assignment 2 page has links to descriptions of the above operations.

Genetic algorithms are used in computing and industry in areas as diverse as hardware design

optimization, scheduling and machine learning. The genetic algorithm of this assignment is

applied to two problems:

minfn: determine variables to satisfy an equation

pcbmill: minimise the drill head movement (and thus the time taken to drill) of a mill

for drilling holes in a Printed Circuit Board (PCB).

The course Canvas assignment 2 page has links to specifications for minfn and pcbmill and

sample data files that they can use.

In the following sections of this document, the details of your assignment are explained. Read

them thoroughly and ask your questions from the teaching team. You are expected to

understand every requirement explained in this document and implement all of them

accordingly.