3
Introduction to Computer Science
Assignment 3
Exercise 1
Design and implement a program in C, that given a sequence s = [e0, e1, . . . , en−1] of numbers, and a number x, it checks whether there exists a subset of the elements in s whose sum equals x. This problem must be solved recursively, i.e., the function that checks whether there is a subset whose sum leads to x must be a recursive function. As an example, if the sequence is s = [−73, 30, 44, 23,−40,−92, 87] and the value is 20, the function must return false (zero), since no subset of the sequence has sum 20. On the other hand, if for the same sequence, the value we consider is 27, the function must return true (one), since 44 + (−40) + 23 = 27.
Your task is to extend the partial implementation in file sum exists.c, with a recursive implementation of function sum exists(seq, lower, upper, n). Follow the comments that accompany the function to have more precise details of what this function must implement.
The main function in the file receives a seed and the value x from the command line, it generates a random sequence using the seed, and then checks whether the generated sequence contains elements whose sum is x, using the function you have to implement. You can use the overall implementation to test your solution. You may fully disregard efficiency for this exercise, and concentrate on functional correctness, as well as code clarity.
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_SIZE 20
#define MAX_VALUE 100
/*
* checks if there exists a subset of the elements of the array seq,
* between positions lower and upper-1, whose sum results in n.
*/
int sum_exists(int seq[], int lower, int upper, int n) {
//TODO Implement this function. Replace the return line below with your implementation
//We do it recursively to substract some elements in the sequence from n
//Base case: if the sum is 0, means it exists
if (n == 0)
return TRUE;
//Base case: if we traverse any element in sequence but n is still not 0, then it doesn't exist
if (lower >= upper)
return FALSE;
//Recursive case: one possibility: the current element is in the sum of n
if (sum_exists(seq, lower + 1, upper, n - seq[lower]))
return TRUE;
//Recursive case: another possibility: the current element is not in the sum of n
if (sum_exists(seq, lower + 1, upper, n))
return TRUE;
//If above possibilities are not satisfied, then it doesn't exist
return FALSE;
}
/**
* Prints the contents of an array, from position lower to position upper-1.
*/
void print_array(int array[], int lower, int upper) {
printf("{ ");
for (int i = lower; i < upper; i++) {
printf("%d ", array[i]);
}
printf("}\n");
}
/**
* Generates a random sequence of size at most MAX_SIZE, and checks if there exists a subset of
* the elements of the sequence that sum up a given number.
* It receives the inputs from the command line:
* - seed: is the seed for random generation.
* - n: is the number to check against the sum of elements of the random sequence.
*/
int main(int argc, char* argv[]) {
if (argc != 3) {
printf("Usage: ./sum_exists seed n\n");
}
else {
int seed = atoi(argv[1]);
int n = atoi(argv[2]);
srand(seed);
int size = rand() % (MAX_SIZE + 1);
int sequence[size];
for (int i = 0; i < size; i++) {
sequence[i] = rand() % 2 == 0 ? rand() % MAX_VALUE : -1 * (rand() % MAX_VALUE);
}
print_array(sequence, 0, size);
printf("value is %d\n", n);
printf("%s\n", sum_exists(sequence, 0, size, n)? "YES" : "No");
}
}
Exercise 2
Design and implement a program in C, that given a sequence s = [e0, e1, . . . , en−1] of numbers, computes and prints out the longest subsequence of s that is strictly increasingly sorted. For instance, if the sequence is s = [−73,−73, 30, 44, 23,−40,−92, 87], then the longest strictly increasing subsequence is [−73, 30, 44]. This problem can be solved iteratively or recursively.
Your task is to extend the partial implementation in file strictly increasing subsequence.c, with an implementation of function strictly increasing subsequence(seq, lower, upper, result). Follow the comments that accompany the function to have more precise details of what this function must implement.
The main function in the file receives a seed from the command line, it generates a random sequence using the seed, and then computes and prints the longest strictly increasing subsequence of the generated sequence, using the function you have to implement. You can use the overall implementation to test your solution. You may fully disregard efficiency for this exercise, and concentrate on functional correctness, as well as code clarity.
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_SIZE 20
#define MAX_VALUE 100
/*
* Computes the longest strictly increasingly sorted subsequence of seq, between
* between positions lower and upper-1, whose sum results in n.
*/
//This function calculate the length of strictly increasing sequence from start_position
int calculate_length(int seq[], int start_position, int upper) {
int length = 1;
for(int i = start_position; i + 1 < upper && seq[i+1] > seq[i]; i++) {
//if i+1 still in the range and sequence is still increasing, then length++
length++;
}
return length;
}
void strictly_increasing_subsequence(int seq[], int lower, int upper, int result[]) {
//TODO Implement this function.
int max_length = 1;// the max length of sequence satisfied
int max_lower = 0; //the corresponding lower position called max_lower
//calculate each length of strictly increasing sequence starting from lower to upper
for(int i = lower; i < upper; i++) {
if(calculate_length(seq, i, upper) > max_length) {
max_length = calculate_length(seq, i, upper);
max_lower = i;
}
}
//store the max in the result
result[0] = max_lower;
result[1] = max_lower + max_length;
}
/**
* Prints the contents of an array, from position lower to position upper-1.
*/
void print_array(int array[], int lower, int upper) {
printf("{ ");
for (int i = lower; i < upper; i++) {
printf("%d ", array[i]);
}
printf("}\n");
}
/**
* Generates a random sequence of size at most MAX_SIZE, and computes the longest
* strictly increasingly sorted subsequence in the generated sequence. The program
* prints out the result.
* This programs receives the seed for random generation from the command line.
*/
int main(int argc, char* argv[]) {
if (argc != 2) {
printf("Usage: ./strictly_increasing_subsequence seed\n");
}
else {
int seed = atoi(argv[1]);
srand(seed);
int size = rand() % (MAX_SIZE + 1);
int sequence[size];
for (int i = 0; i < size; i++) {
sequence[i] = rand() % 2 == 0 ? rand() % MAX_VALUE : -1 * (rand() % MAX_VALUE);
}
printf("Sequence: ");
print_array(sequence, 0, size);
int result[2];
strictly_increasing_subsequence(sequence, 0, size, result);
printf("Longest strictly increasing subsequence:: ");
print_array(sequence, result[0], result[1]);
}
}