Useful links
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)
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)
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