General information for programming exercises

• Each group gets access to a svn directory at https://svn.imp.fu-berlin.de/agbio/AlgorithmsWS13/GroupX
• The solution to each exercise has to be checked in a subdirectory exerciseY/ case sensitive) before the respective deadline.
• The program must compile on a Linux Pool machine (https://www.mi.fu-berlin.de/w/IT/ServicesStudentPools) with make exerciseY (sample makefile will be given, compiler flags -pedantic -Wall -ansi -O3 have to be set)
• The final version of your application note also have to be checked in to the subdirectory as PDF file exerciseY_Note.pdf
• Test data and makefile template are available in: https://svn.imp.fu-berlin.de/agbio/AlgorithmsWS13/data
• Do NOT check in test data again in your group directory!

Useful links

• http://www.cplusplus.com/reference/
• http://www.mi.fu-berlin.de/w/ABI/CppIntroWS12

Exercise 1

Bellman-Ford Algorithm

Deadline: 30.10.2013 9:00 a.m.(files in svn at that time count)

Code Review: 01.11.2013 during exercise

• Write a C++ program that:
  • reads a file containing the structure and weights of a directed graph (Format will be specified)
  • computes the shortest path from some specified node s to some other node t or returns infeasible if the graph contains negative weight cycles.

• Test your program on the given test Dataset (will be added)
• Write a short application note (no more than 1-2 pages) where you describe your implementation and present some runtime results.

Format specifications (Test files can be found in the svn repository)

Input

As input format we use the Trivial Graph Format (TGF) which is defined as follows:

0 someString0

1 someString1

2 someString2

3 someString3

#

0 1 weight

1 2 weight

1 3 weight

3 2 weight

First all node identifier (int) and associated node names (arbitrary strings - we limit to single words) are listed. You can expect them to be 0..|V|-1 in increasing order. After a single line containing only a single # symbol all directed edges are listed with their weights (double, at most 3 fractional digits).

Your program shall be called as:

./exercise1 graph.tgf sourceId targetId

sourceId and targetId are the node identifiers (not the names!) of the source and target node for the shortest path search.

Output (Must be exactly as below! No additional output or typos!)

If no path form source to target exists your program shall generate the single output no path

If the graph contains negative weight cycles your program shall generate the single output infeasible

Otherwise your program shall return two lines of output first the length of the shortest path P, then the path itself e.g.

134.5

sourceId idP2 idP3 idP4 … targetId

Exercise 2

Ford Fulkerson Algorithm

Deadline: 13.11.2013 9:00 a.m.(files in svn at that time count)

Code Review: 15.11.2013 during exercise

• Write a C++ program that:
  • reads a file containing the structure and capacities of a directed flow network
  • computes the value of a maximum flow from some specified node s to some other node t.

• Test your program on the given test Dataset (will be added)
• Write a short application note (no more than 1-2 pages) where you describe your implementation and present some runtime results.

Format specifications (Test files can be found in the svn repository)

Input

As input format we use the Trivial Graph Format (TGF) from exercise 1. Now the weights of the edges represent their capacities and you can expect them to be positive integer numbers.

Output

The output is simple one number specifying the value of the maximum flow

Call

Your program shall be called as:

./exercise2 network.tgf sourceId sinkId

sourceId and sinkId are the node identifiers (not the names!) of the source and sink node for maximum flow computation.

Exercise 3

Dictionary

Deadline: 27.11.2013 9:00 a.m.(files in svn at that time count)

Code Review: 29.11.2013 during exercise

• Implement a class dictionary with the following public member functions:
  • size_t numElem() - returns the number of elements currently stored in the list.
  • std::pair<bool,int> find(int x): returns (true,x) if x is contained in the dictionary, otherwise
    • (skip list): (false,y) with y the maximal element in the list (including the artificial-infinity Element) that is at most equal to x.
    • (hash table): (false,x)
  • bool insert(int x) - insert x. On success return true. If x was already in the dictionary return false.
  • bool remove(int x) - delete x. If deleted return true. If x was not in the dictionary return false.
  • dictionary(const std::vector<int> & init) - Constructor takes a std::vector<int> argument which contains the initial elements (not sorted) to be stored in the dictionary.
  • string implType() - return either "skiplist" or "hashtable" depending on your underlying implementation.
  • The class shall be defined in a file dictionary.h and member functions shall be defined in dictionary.cpp.

• You can choose to implement your dictionary by either using a skip list or a perfect hashing scheme as presented in the lecture (extended to non static hashing - be creative).

• On some generated datasets with different size compare the runtime of insertions and removal and find.
• Evaluate the size (and height for skip list) of your dictionary.

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