# Proving an Algorithm by Induction

#### grapplingshark

##### New member
Hello,

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.