- 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:
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 |