School of Computing and Information Systems
comp10002 Foundations of Algorithms
Semester 2, 2018
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