General information for programming exercises

  • We will continue working in the repository from the Algorithms lecture. To discriminate the exercise files we append an _opti. So the first exercise becomes exercise_opti1.
  • Each group gets access to a svn directory at (Enter your login names in the table below)
  • The solution to each exercise has to be checked in as a file named exercise_optiY.cpp (case sensitive, no subdirectories!) before the respective deadline.
  • The final version of your application note also have to be checked in as PDF file exercise_optiY_Note.pdf

Exercise 1

Flux Balance Analysis

Deadline: 16.1.2013, 9:00 a.m.

Write a program that:
  • reads in a metabolic network in SBML format
  • reads a second argument that is either BIOMASS or BLOCKED
  • reads a third argument that is the output filename.
  • depending on the given argument either:
    • computes flux distribution that maximizes the biomass production and fulfills the steady state assumption. The network will contain a reaction named "Biomass" whose rate has to be maximized.
    • determines for every reaction whether it is blocked or not. We say a reaction is blocked if it cannot have a non-zero (> zeroTolerance_ value defined in ClpSimplex class) rate in a steady state.
  • Output format:
    • in BIOMASS mode:
      • every line contains <reaction_id> <rate>
      • the first line contains the Biomass reaction, the remaining reactions are ordered according to their index in the SBMLParser
    • in BLOCKED mode write one line for each blocked reaction:
      • every line contains <reaction_id>
      • blocked reactions are ordered according to their index in the SBMLParser

related links:

Exercise 2

Shortest path with pairwise vertex scores

Deadline: 30.1.2013, 9:00 a.m.

Write a program that:
  • reads in a weighted directed graph and pairwise vertex scores.
  • computes a shortest s-t path with the additional constraint that for every pair of nodes contained in the path, their pairwise vertex score is added to the weight of the path.
  • weights and scores are nonnegative
  • Input format:
    • We use (almost) the same format (TGF) as in Exercise 1 in the algorithms lecture
      • First all node identifier (int) and associated node names (arbitrary strings - we limit to single words) are listed.
      • After a single line containing only a single # symbol all directed edges are listed with their weights (double).
      • After a single line containing only a single # symbol all nonzero pairwise scores are listed in the same format.
  • Output format:
      • If no path form source to target exists your program shall generate the single output no path
      • Otherwise your program shall return two lines of output first the length of the shortest path (with pairwise scores) P, then the path itself e.g.
        sourceId idP2 idP3 idP4 … targetId
  • Program call:
    Your program shall be called as:
    ./exercise_opti2 graph.tgf sourceId targetId

Exercise 3


Deadline: 1.3.2013, 9:00 a.m.

Write a program to solve Sudoku puzzles using Gecode. A Sudoku puzzle consists of a n*n by n*n array of squares. In a valid solution:
  • each square contains one of the numbers 1, 2, . . . , n*n (typically n = 3).
  • each row contains all the different numbers.
  • each column contains all the different numbers.
  • and each major n by n block contains all the different numbers.

  • Input format:
    • textfile containing the Sudoku matrix where every non-zero field entry is the fixed value for that square. You can find a selection of Sudoku instances at:
  • Output format:
    • textfile in the same format containing a feasible solution to the sudoku puzzle.
    • if no feasible solution exists the textile contains a single line saying infeasible
  • Program call:
    Your program shall be called as:
    ./exercise_opti3 <input file>  <output file>

  • You find a very nice documentation of how to use Gecode at:
  • You find the Gecode sources together with small example and Makefile template in the svn (data/optimization3/)

Point scheme

For each exercise you can score 4 Points, 3 for the program and 1 for the application note. For the program:
3 Pts = program runs without errors
2 Pts = program contains small errors
1 Pts = program contains critical errors
0 Pts = no program submitted

Requirements: You have to reach at least 75% of the points summed for all programming exercises


Enter your login names to the corresponding groups. Form groups of three!

Group Login Names
1 scmr, digga, hlaubish
2 lisasous, lyla, shalini6
3 ngenov, magdaw, mairae
4 biederj, dvinzelb, dianavm
5 ---
6 kitty05, huetrang,flekschas
7 mattesf, stillsen, chosu
8 phieler, asandra, kselm87
9 tausch, mareikem, aeckert1
10 beny, josofie, r3p10id0
11 agrigore
12 meyerclp, dvo, evelynsk
13 osterlam, kruben, dps
14 h3nsen, meinhart
This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Foswiki? Send feedback