grapplingshark
New member
- Joined
- Feb 5, 2019
- Messages
- 1
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.
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.