Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

# 1. Optimizing the gaps

Consider the following optimization problem. You are a developer. There are n lots on a street, and for each lot there is a reward (which may be negative) for building a house on that lot. However, the town has strict rules on how big or small the gap between two houses (expressed in terms of empty lots) can be. So it may be that you need to keep at least 1 and at most 3 empty lots between any two houses you build. At the end of the street, only the maximum gap comes into play; you can't have a gap larger than the maximum gap between the last house and the end, but you can have a gap smaller than the minimum gap.

Your job is to write a program gaps that computes the maximum possible total reward you can obtain. Your program should take the minimum and maximum gaps as arguments and the list of rewards as a sequence of white-space separated integer values suitable for parsing with scanf, terminated by end-of-file. Your program should print the value of the maximum total reward and a summary string that shows the positions that are included, with a '0' character for any position that is not marked and a '1' for any position that is marked.

For example, suppose that the houses have rewards 1 2 3 4 5 6 7 and that the minimum gap is 1 and the maximum gap is 3. Then the optimal placement is 1 3 5 7 with total reward 16. Your program computing this result might look like this:

```\$ echo 1 2 3 4 5 6 7 | ./gaps 1 3
16
1010101```

Alternatively, perhaps you are penalized for building houses (but must do so anyway). We could model this as a negative reward vector -1 -2 -3 -4 -5 -6 -7. If the minimum gap is 1 and the maximum gap is 3 as before, the optimal solution is to build just the house in the middle, leaving a permitted gap of 3 on either side:

```\$ echo -1 -2 -3 -4 -5 -6 -7 | ./gaps 1 3
-4
0001000```

If we reduce the maximum gap to 2, then the optimum is to take the -2 and the -5, with a gap of 2 between them and a gap of 2 on the right side of -5:

```\$ echo -1 -2 -3 -4 -5 -6 -7 | ./gaps 1 2
-7
0100100```

It's easy to see this because if we move the house at -5 to the right, our costs go up, and -2 is the least painful house to build if we want to prevent a gap of more than 2 empty lots to the left of -5.

Here's a longer input that shows how an optimal solution can run into both the minimum and maximum gap value:

```\$ echo 1 2 3 4 5 6 -7 -8 -9 -10 -11 -12 -13 -14 15 | ./gaps 1 4
17
010101000100001```

For complicated inputs, it may be harder to figure out the optimum value by hand, and for large inputs, it will be expensive to try all possibilities. We recommend attacking the problem using DynamicProgramming.

# 2. Submitting your assignment

Submit your source files using /c/cs223/bin/submit 9 as usual. If the only file you need is called gaps.c, you do not need to submit anything else; otherwise, you should submit a Makefile as well. You can run /c/cs223/bin/testit 9 public to check your submitted file using the public test script in /c/cs223/Hwk9/test.public, which may or may not resemble the final test script.

# 3. Sample solution

```   1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <assert.h>
4 #include <limits.h>
5 #include <string.h>
6
7 static int
8 max(int x, int y)
9 {
10     if(x > y) {
11         return x;
12     } else {
13         return y;
14     }
15 }
16
17 /* Find value of optimal choice placement of marks
18  * such that there are no regions between marks
19  * with less than minGap empty spots
20  * and none with more than maxGap empty spots.
21  *
22  * Returns malloc'd string describing placement '0' = no mark '1' = mark.
23  * Caller should free this.
24  *
25  * Puts value in *value.
26  */
27 char *
28 bestPlacement(int n, const int *reward, int minGap, int maxGap, int *value)
29 {
30     int *best;     /* best[i] is best value for any prefix ending with a mark on i */
31     int *prev;     /* prev[i] is previous mark (or INT_MIN if no previous mark) for best sequence */
32     char *summary; /* summary string to return */
33     int i;
34     int j;
35     int prevValue;
36     int last;      /* last value taken, or INT_MIN if no values taken */
37
38     assert(minGap <= maxGap);
39
40     best = malloc(n * sizeof(*best));
41     assert(best);
42
43     prev = malloc(n * sizeof(*prev));
44     assert(prev);
45
46     for(i = 0; i < n; i++) {
47         prev[i] = INT_MIN;
48         if(i <= maxGap) {
49             /* could have i all by itself */
50             best[i] = reward[i];
51         } else {
52             /* start here and work up */
53             /* prev[i] will be overwritten later */
54             best[i] = INT_MIN;
55         }
56
57         /* consider all possible previous marks */
58         for(j = i-minGap-1; j >= 0 && j >= i - maxGap - 1; j--) {
59             prevValue = best[j] + reward[i];
60             if(prevValue > best[i]) {
61                 best[i] = prevValue;
62                 prev[i] = j;
63             }
64         }
65     }
66
67     /* last mark must be no earlier than n - maxGap - 1 */
68     /* if maxGap >= n, we might have no marks at all */
69     last = INT_MIN;
70     if(maxGap < n) {
71         *value = INT_MIN;
72     } else {
73         *value = 0;
74     }
75
76     for(i = max(0, n - maxGap - 1); i < n; i++) {
77         if(best[i] > *value) {
78             *value = best[i];
79             last = i;
80         }
81     }
82
83     /* construct output string */
84     summary = malloc(n+1);
85
86     assert(summary);
87
88     memset(summary, '0', n);
89     summary[n] = '\0';
90
91     for(i = last; i != INT_MIN; i = prev[i]) {
92         summary[i] = '1';
93     }
94
95     free(best);
96     free(prev);
97
98     return summary;
99 }
100
101 #define INITIAL_REWARD_SIZE (32)
102
103 int
104 main(int argc, char **argv)
105 {
106     int minGap;   /* minimum gap */
107     int maxGap;   /* maximum gap */
108     int *reward;  /* array of rewards */
109     int n;        /* number of values in reward */
110     int size;     /* size of reward */
111     int nextVal;  /* for reading in next value */
112     char *summary; /* summary string */
113     int value;    /* value */
114
115     if(argc != 3) {
116         fprintf(stderr, "Usage: %s minGap maxGap\n", argv[0]);
117         return 1;
118     }
119
120     minGap = atoi(argv[1]);
121     maxGap = atoi(argv[2]);
122
123     size = INITIAL_REWARD_SIZE;
124     reward = malloc(size * sizeof(*reward));
125
126     n = 0;
127
128     while(scanf("%d", &nextVal) == 1) {
129         if(n >= size) {
130             size *= 2;
131             reward = realloc(reward, size * sizeof(*reward));
132         }
133
134         reward[n++] = nextVal;
135     }
136
137     summary = bestPlacement(n, reward, minGap, maxGap, &value);
138
139     printf("%d\n", value);
140     puts(summary);
141
142     free(reward);
143     free(summary);
144
145     return 0;
146 }
```
gaps.c

2014-06-17 11:58