Engineering Computation Workshop 10 === ###### tags: `comp20005` `workshop` `c` --- ## Problem Solving & Simulation Plan: 1. Problem Solving (Harder Exam Questions) + Grok 2. Simulation + Grok 3. Assignment 2 --- ### Building a solution **subset sum**: Given a set of non-negative integers `A`, and a value sum `k`, determine if there is a subset of the given set with sum equal to given sum `k`. `A = [3, 34, 4, 12, 5, 2], k=9` --- ### Building a solution `A = [3, 34, 4, 12, 5, 2], k=9` True -> we can take `[4,5]` --- ### Building a solution `A = [3, 34, 4, 12, 5, 2], k=30` --- ### Building a solution `A = [3, 34, 4, 12, 5, 2], k=30` False -> No possible subset is = k --- ### Building a solution Lets brainstorm a possible general solution to this problem. [2-3mins] --- ### Building a solution What if we just make up groups and consider every single possible subset of A, computing its sum - then check if it equals k? e.g. (note there will be $2^n$ subsets.. 8 here) ``` A = [5,2,3] [5,2,3]=10, [5,3]=8, [5,2]=7 [2,3]=5, [5]=5, [2]=2, [3]=3, []=0 ``` --- ### Building a solution Awesome! That should work. But just how do we go about getting every subset of a set in c? `Hint: Think about two options: Recursion or Iteration (loops)` --- ### Building a solution hmm building subsets is kinda tricky with a head on approach - lets try and simplify it. We know that we are going to want $2^n$ subsets, so a conventtional iterative approach might be a bit tricky to reason about. However using recursion it actually becomes a lot easier... --- ### Building a solution Consider this function (useless function btw) ```cpp int r(int n, int s, int t) { if (n==1) return s == t; return r(n-1, s*n, t) || r(n-1, s, t) } ``` --- ### Building a solution Whats it doing? --- ### Building a solution It's checking all the possible subsets of numbers [1,n-1] to see if their product = n. Meaning that if no possible subset does, that number is semi-prime (it doesn't consider multiplying by the same number so 4 would be considered semi-prime because 2x2 doesn't occur) --- ### Building a solution Visualisation: for r(4,1,5) - checking if 5 is a semi-prime number  --- ### Building a solution Note that in the above graph there are 8 bottom nodes (leaves). Since we are stopping at 1 and we passed in 4 it follows that we have checked $2^{n-1}$ = (8) --- ### Building a solution So it looks like that if we have two recursive calls - we match the $2^n$ subsets (logically it makes sense since we are doubling the number of calls each time) --- ### Building a solution Recursive ``` A=set,k=sum,n=size(A),s=current_size (relative) subset(A, k, n, s) k == 0: return True s == 0: return False e = A[s-1] return subset(A,k-e,n,s-1) or subset(A,k,n,s-1) ``` --- ### Building a solution ```cpp int subset(A, k, n, s) { if (k == 0) return 1; // check if sum == 0 (we found it!) if (s == 0) return 0; // check base case (we have run out of numbers) int e = A[s-1]; // element to either include or ignore return subset(A,k-e,n,s-1) || subset(A,k,n,s-1); } ``` --- ### Building A Solution Grok 9.07 --- ### Building A Solution We can consider every single sub_array - there are $\frac{n(n+1)}{2}$ Using two for loops --- ### Building A Solution ```cpp int max_subarray_a(int *A, int n){ int best, l, r, cur; best = 0; l = 0; r = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j <= i; ++j) { cur = sum_seq(A, j, i); if (cur > best) { best = cur; l = j; r = i; } } } report_array(A, l, r); return best; } ``` --- ### Building A Solution ```cpp int max_subarray_b(int *A, int n) { int sums[n], best, l, r; best = A[0]; l = 0; r = 0; sums[0] = A[0]; for (int i=1; i<n; ++i) sums[i] = sums[i-1] + A[i]; for (int i=0;i<n;++i) { for (int j=0;j<i;++j){ if (sums[i] - sums[j] > best) { l = j; r = i; best = sums[i] - sums[j]; } } } report_array(A, l+1, r); return best; } ``` --- ### Building A Solution ```cpp int max_subarray_c(int *A, int n) { int sums[n], best, l, r; best = A[0]; l = 0; r = 0; sums[0] = A[0]; for (int i=1;i<n;++i) { if (sums[i-1] + A[i] > A[i]) { sums[i] = sums[i-1] + A[i]; if (sums[i] >= best) { best = sums[i]; r = i; } } else { sums[i] = A[i]; if (sums[i] >= best) { best = sums[i]; l = i; r = i; } } } report_array(A, l, r); return best; } ``` --- ### Building A Solution ```cpp int max_subarray_d(int *A, int n) { int best, local, l, r; best = A[0]; local = A[0]; l = 0; r = 0; for (int i=1;i<n;++i) { if (local + A[i] > A[i]) { local += A[i]; if (local >= best) { best = local; r = i; } } else { local = A[i]; if (local >= best) { best = local; l = i; r = i; } } } report_array(A, l, r); return best; } ``` --- ### Simulation 1. We want to simulate a physics event (rockets/planets etc) or probability events 2. It's all about the implementation - translating what's written to code 3. If time is involved, you usually have an outer loop with small increments representing time - you recalculate all the variables each iteration. Likewise if its a game - you simulate each turn as the outer loop. --- ### Simulation Simple Case: Identify the key variables: One mass travels towards the other in a frictionless environment - assume perfect elasticity of collisions. We want to calculate how many times the two masses collide. You are given the initially moving masses velocity and both masses weight.  ---