Settling Multiple Debts Efficiently: An Invitation to Computing Science
Settling Multiple Debts Efficiently: An Invitation to Computing Science
Author(s): Tom VerhoeffSubject(s): Education
Published by: Vilniaus Universiteto Leidykla
Keywords: computing science education; combinatorial optimization; Balanced transportation problem; uncapacitated fixed-charge network flow; NP-completeness
Summary/Abstract: I present and solve several problems related to the settling of multiple debts. The solutions are documented in much detail, with (bright) high-school students in mind. One of the variants has a simple solution, though it is not so easy to code concisely. Another variant is an elegant NP-hard problem. The problem leads into important areas of mathematics and computing science, making it suitable as an invitation to these subjects.
Journal: Informatics in Education - An International Journal
- Issue Year: 3/2004
- Issue No: 1
- Page Range: 105-126
- Page Count: 22
- Language: English