French Flag Version française

Exercise Session 4: Greedy Algorithms

Reminders

Exercise 1: Knapsack

  1. You have a knapsack with capacity C (weight capacity) and a list of n objects of weights p[0], p[1], ... p[n-1].
    Your goal: put as many objects in your knapsack as possible, without going over its capacity.

    Implement in a file sac1.cc the function Sac1() described in file sac1.h: 
    #ifndef __SAC1_H
#define __SAC1_H

#include <vector>
using namespace std;

// We have a knapsack with capacity C, and objects of weight p[0], p[1], ...
// We want to select as many objects as possible such that the sum of their
// weights remains <= C.
// This function should return the maximum count of objects that can fit.
//
// EXAMPLE: C=12, p=[4, 7, 2, 5, 4, 1, 2, 10]
//          -> returns 4 because at most 4 objects can fit
//                (for example objects #0, #2, #4 and #6 have total weight
//                 4 + 2 + 4 + 2 = 12)
int Sac1(int C, const vector<int>& p);

#endif  // __SAC1_H
    Test: 
    rm test.tar.gz; wget --no-cache http://fabien.viger.free.fr/oc/td4/test.tar.gz
tar xf test.tar.gz
make sac1
    TO SUBMIT: sac1.cc

  2. Now, the objects are also valued (v[0], v[1], ...) and can also be taken partially:
    for each object, you can choose to put an aribtrary fraction (a number in [0, 1]) of it in the knapsack:
    you'll gain the corresponding fraction of its value, while occupying the corresponding fraction of its weight.

    Which objects (and what fraction of them) should we choose to maximize the value carried in the knapsack?

    Implement in a file sac2.cc the function Sac2() described in file sac2.h: 
    #ifndef __SAC2_H
#define __SAC2_H

#include <vector>
using namespace std;

// We have a knapsack with capacity C, and objects of weight p[0], p[1], ...
// and of values v[0], v[1], ...
// This function returns the maximum value that one can carry in the knapsack,
// assuming that each object can be taken fractionally.
//
// EXAMPLE: C=12, p=[4, 7, 2, 5, 5, 1, 10], v=[3.1, 99, 0.1, 0.2, 6.6, 0.4, 111]
// -> Must return 154.5. Explanation:
//    the optimal solution is to take object #1 whole (weight 7, value 99)
//    and half of object #6 (weight 10, value 111).
//    This yield a total weight 7*1 + 10*0.5 = 12, and
//    a total value 99*1 + 111*0.5 = 154.5.
double Sac2(int C, const vector<int>& p, const vector<double>& v);

#endif  // __SAC2_H
    Test: make sac2

    TO SUBMIT: sac2.cc

Exercise 2: Minimum Spanning Tree

  1. Implement in a file prim.cc de Prim algorithm to find a minimum spanning tree: Prim(), described in file prim.h: 
    #ifndef __PRIM_H
#define __PRIM_H

#include <vector>
using namespace std;

// Returns the weight of the minimum spanning tree for the given weighted graph:
// N is the number of nodes, and "edges" the list of edges of the graph, with
// their weights.
//
// EXAMPLE:
// N = 4, edges = [{0, 1, 23}, {1, 3, 13}, {2, 1, 6}, {3, 2, 11}, {0, 2, 41}]
//
//    .--[23]--1--[13]--.      Nodes are sont 0,1,2,3.
//  .´         |         `.    The edge weights are inside the [ ].
// 0          [6]          3
//  `.         |         .´    Minimum Spanning Tree: 23 + 6 + 11 = 40.
//    `--[41]--2--[11]--´
//
struct Edge {
  int node1;
  int node2;
  int weight;
};
int Prim(int N, const vector<Edge>& edges);

#endif  // __PRIM_H
    Test: make prim

    TO SUBMIT: prim.cc

    

Exercise 3: Vertex coloring in a graph

  1. You're a teacher, and want to give homework to your students.
    But they may plagiarize each other, instead of working.
    To avoid that, you are ready to prepare several different versions of the homework: 2 students who have 2 different versions won't be able to copy each other's work.
    You also know the social network of the students: students would only consider copy the work of a friend (i.e. directly linked in the social graph).
    What's the minimum number of versions of the homework that you'll need to create, and how shall you distribute those versions to the students, so that any two friends don't get the same version?

    Implement in a file color.cc the function Color(), described in file color.h: 
    #ifndef __COLOR_H
#define __COLOR_H

#include <vector>
#include "ugraph.h"  // You have this file, it's in test.tar.gz.

using namespace std;

// Given an undirected graph, returns a vertex coloring that uses as few colors
// as possible.
// Input: the undirected graph.
// Return value: the number of colors C of your coloring.
// Side output: "color" must contain as many elements as the number of nodes
//              in the graph, and color[i] shall be the color of node #i.
//              color[i] must be in 0..C-1, and any two nodes directly connected
//              by an edge of the graph must have different colors.
//
// NOTE: We do not expect an optimal algorithm (this is a NP-hard problem!), but
// your heuristics should be as "good" as possible, and will be graded
// accordingly. It shouldn't be too slow either: try to keep a linear or
// log-linear complexity.
int Color(const UndirectedGraph& graph,
          vector<int>* color);  // Side output. Don't forget to fill it!

#endif  // __COLOR_H
    Test: make color

    TO SUBMIT: color.cc