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