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.