Q1 Teaching Assignment
CSC373 Fall’20 Tutorial 5 Mon. Oct. 13, 2020
Suppose there are m courses: c1,…,cm. For each j ∈ {1,…,m}, course cj has sj sections. There are n professors: p1,…,pn. For each i ∈ {1,…,n}, professor pi has a teaching load of li, and has a preference for a subset of courses Ai ⊆ {c1, . . . , cm}.
Your goal is to find a feasible assignment of professors to courses such that:
• each professor pi is assigned exactly li courses,
• each course cj assigned to exactly sj professors,
• no professor is assigned a course that they do not prefer, • no professor teaches multiple sections of the same course.
Reduce this problem to the network flow problem. Justify that your reduction is correct. What is the worst-case running time of the na ̈ıve Ford-Fulkerson algorithm on the network you created?
Q2 Mobile Computing
Suppose there are n mobile computing clients in a certain town. Each client i ∈ {1, . . . , n} is located at a given point (xci,yic), and must be connected to exactly one of m “base stations”. We are also given the coordinates (xbj,yjb) of each base station j ∈ {1,…,m}.
There is a “range parameter” r: a client can only be connected to a base station within a Euclidean distance of r. There is also a “load parameter” L: no more than L clients can be connected to any single base station.
Reduce this problem to the network flow problem. Justify that your reduction is correct. What is the worst-case running time of the na ̈ıve Ford-Fulkerson algorithm on the network you created?
Q3 (In-Tutorial Exercise) Midterm Rehearsal
Perform the following actions in the last 20 minutes of the tutorial. If you encounter any difficulties, ask the TA for help.
1. Take a blank sheet of paper / start a LaTeX document / open a blank page in a notetaking app on your tablet. Use the mode of answering questions that you plan to use in the actual midterm next week.
2. Write down your name and student number.
3. Create a PDF (e.g. by scanning the sheet of paper).
1
4. Go to MarkUs → Rehearsal Midterm 1, and upload the PDF.
Take a note of the total time required for this. In the midterm next week, you will certainly need more time than this as you will have to scan multiple sheets of paper. Please use the extra 10 minutes provided for scanning and uploading.
2