Proving an Algorithm by Induction


New member
Feb 5, 2019

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.