General information for programming exercises

• 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 exerciseY.cpp (case sensitive, no subdirectories!) before the respective deadline.
• The program must compile on a Linux Pool machine (https://www.mi.fu-berlin.de/w/IT/ServicesStudentPools) with g++ -pedantic -Wall -ansi -O3 -o exerciseY exerciseY.cpp
• The final version of your application note also have to be checked in as PDF file exerciseY_Note.pdf

Exercise 1

Bellman-Ford Algorithm

Deadline: 05.11.2012 9:00 a.m.

• 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

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. After a single line containing only a single # symbol all directed edges are listed with their weights (double).

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

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

Hashing with Open Adressing

Deadline: 20.11.2012 8:00 p.m.

• Implement a class openAddMap that implements a hash table with the following public member functions:
  • size_t size() - returns the size (reserved slots) of the table.
  • size_t numElem() - returns the number of elements currently in the table (not including NIL markers).
  • bool insert(unsigned int) - insert a new element into the table. On success return true. If element was already in the table return false.
  • bool find(unsigned int) - search for entry in the table. If found return true otherwise false.
  • bool remove(unsigned int) - delete entry from table. If deleted return true. If element was not in the table return false.
  • openAddMap(const std::string & mode) - Constructor takes a std::string argument which is either "linear", "quadratic" or "double" and defines which probing scheme your table should implement.
• The load factor (excluding NIL slots) should always be between 25% and 75%. You can use -1u as marker for deleted slots and -2u as marker for free slots.
• The class shall be defined in a file openAddMap.h and member functions shall be defined in openAddMap.cpp.

• Visualize the distribution of items in your table for the different probing schemes. Can you observe primary/secondary clustering?
• Evaluate the number of probes you need for the probing schemes and the runtime.

Exercise 3

Skiplists

* Implement a class skipList that implements a skipList with the following public member functions:

• • size_t numElem() - returns the number of elements currently stored in the list.
  • int find(int x): report the maximal element in the list that is at most equal to x.
  • bool insert(int x) - insert x into the list. On success return true. If x was already in the list return false.
  • bool remove(int x) - delete x from list. If deleted return true. If x was not in the list return false.
  • skipList(const std::vector<int> & init) - Constructor takes a std::vector<int> argument which contains the initial elements (not sorted) to be stored in the list.
• The class shall be defined in a file skipList.h and member functions shall be defined in skipList.cpp.

• On some generated datasets with different size compare the runtime of insertions and removal and also evaluate the height and size of your lists.

Deadline: 14.12.2012 9:00 a.m.

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, ?
3	ngenov, magdaw, mairae
4	biederj, dvinzelb, ?
5	fsiemer, dianavm, ?
6	kitty05, huetrang,flekschas
7	mattesf, stillsen, chosu
8	phieler, asandra, kselm87
9	tausch, mareikem, aeckert1
10	beny, josofie, r3p10id0
11	h3nsen, meinhart, agrigore
12	meyerclp, dvo, evelynsk
13	osterlam, kruben, dps
14	tbd.