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 https://svn.imp.fu-berlin.de/agbio/AlgorithmsWS12/GroupX (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:

• http://www.coin-or.org/Clp/userguide/index.html (API of the coin-or Clp lp-solver)

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.
      134.5
sourceId idP2 idP3 idP4 ... targetId
• Program call:
  Your program shall be called as:
  ./exercise_opti2 graph.tgf sourceId targetId

Exercise 3

Sudoku

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: http://lipas.uwasa.fi/~timan/sudoku/
• 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: http://www.gecode.org/documentation.html
• 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

Groups

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