#### grapplingshark

##### New member

- Joined
- Feb 5, 2019

- Messages
- 1

I am in a course mixing some computer science subjects with discrete math. I am having a problem with a two part question. I'll post the question, and then my answer so far.

The following sets are defined:

β π = {πππ π π‘π’ππππ‘π }

β πΆ = {πππ πππ’ππ ππ }

β π = {(π , π) | (π , π) β π Γ πΆ πππ π π‘π’ππππ‘ π ππ π‘πππππ πππ’ππ π π}

Problem (2.5 points). Write an iteration pseudocode for a function SAC(C,R) that returns aset of students who are taking all courses in C, assuming R is a student-course relation definedabove. Use induction to prove that your algorithm is correct.Hint: prove that at each step of your iteration, the return set contains students taking all coursesprocessed so far.

Here's my pseudocode:

SAR(C,R) {

S = {} // initialize set of all students taking all courses - the result and return value

S1 = S // S assumed to be global or somehow accessible to this function as per guidance on Piazza

C1 = C

R1 = R

// Iterate over all student and, for each student, check if they are in all classes

while(S1 != empty set) {

s1 = <next from S1>

SC = s1 X C // generate every set of this particular student and all courses

// If the new set is a subset of R1, then they're taking all courses; add them to the return set

if (SC is a subset of R1) {

S = S + s

}

}

return S;

}

I am not sure that this is correct, although it seems correct. I cannot figure out how to prove this by induction. Does anyone have any suggestions about how to start this by induction? I have spent literally hours trying to figure this out on my own, but I can't seem to find (or recognize!) any examples of using induction to prove a looping algorithm is correct. If anyone has any suggestions, I would really appreciate it.