Courses

Karger's Algorithm

Karger's Algorithm

Karger's algorithm is a randomized algorithm to compute a minimum cut (minimum number of edges) of a connected graph.  The idea of the algorithm is based on the concept of contraction of an edge (u,v) in an undirected graph G=(V,E). Informally speaking, the contraction of an edge merges the nodes u and v into one, reducing the total number of nodes of the graph by one. All other edges connecting either u or v are "reattached" to the merged node, effectively producing a multigraph. Karger's basic algorithm iteratively contracts randomly chosen edges until only two nodes remain; those nodes represent a cut in the original graph.

By iterating this basic algorithm a sufficient number of times, a minimum cut (green dashed line) can be found with high probability.

MinCut.png

Karger's algorithm in pseudocode:

Karger_Algo.png

 

TP2 - Minimum Cut

You will find the exercise uploaded at Moodle -> TP2.

We provide some graphs in order to test your implementation of Karger's Algorithm. To start with, you can visualize the graphs using the online graphviz tool.

C++/ Python Containers

A container is a holder object that stores a collection of other objects (its elements). The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference objects with similar properties to pointers). Containers replicate structures very commonly used in programming: dynamic arrays (vector), queues (queue), stacks (stack), heaps (priority_queue), linked lists (list), trees (set), associative arrays (map)...

Many containers have several member functions in common, and share functionalities. The decision of which type of container to use for a specific need does not generally depend only on the functionality offered by the container, but also on the efficiency of some of its members (complexity). This is especially true for sequence containers, which offer different trade-offs in complexity between inserting/removing elements and accessing them.

 

C++ containers: http://www.cplusplus.com/reference/stl/

Python containers: https://docs.python.org/3/library/collections.html