What is the minimum number of colours to colour the graph shown below?
(D-Problems discussed on Friday, 12-Aug-2016)
(Q-Problems due on Tuesday, 16-Aug-2016, 5:00pm in COM1-03-17)
Practice Problems: (not graded)
I have included a number of practice problems for you to try out.
These problems will help you to "ease into" the materials
covered in the course. (If you have difficulties with these
practice problems, it usually mean you are not following the
lectures -- please quickly see your classmates
or the instructor for help.)
T1-PP1: [Simple Graph Colouring]
What is the minimum number of colours to colour the graph shown below?
T1-PP2: [Frequency Assignment]
Do the "TAKE HOME Activity" on Frequency Assignment given
in the handout.
T1-D1: [e-Greeting Cards] (Do this before the tutorial on Friday!)
(a) Search for an e-greeting card web-site
and send a greeting card (maybe for "an interesting and rewarding semester") to yourself and to me.
Also browse around a few of these web-sites to learn about the
other services that are provided by these web-sites.
(Note: The NUS e-card site is at
http://www.nus.edu.sg/ecards/.
Use online search for others.)
(b) Compare a few different e-greeting card web-sites.
List out some attributes that you may want to compare them with.
How does the different sites fare with respect to your
chosen attributes?
T1-D2: (Getting the Scratch Software Framework)
In UIT2201, we (students and instructor) embark
on an interesting and fun journey -- using the Scratch
(http://scratch.mit.edu)
software framework to learn about algorithms and for course project.
(a) Your first task is to download the Scratch software (version 1.4 or version 2.0 offline)
and install it on your laptop/desktop. (Ver 2.0 does not require download.)
(b) Read the simple free how-to guide and download
some of the (numerous) free Scratch programs (all from the same web-site) and test them out.
(c) If you see a particularly cool Scratch program, do post on the UIT2201 IVLE Discussion Forum. Say a little bit about it, what makes you like it, etc.
T1-D3: [Tourist Problem -- one place only]
Consider the special case of the Tourist Problem v1.0
in which each tourist only want to visit one place
(of course, different tourists may want to visit different places).
Give a very simple (no brainer)
method to schedule the buses for this special case.
How many days does it take to complete the schedule?
Does it matter how many tourist there are?
T1-D4: [Tourist Problem -- conflict generation]
In the Tourist Problem example, Aaron wants to visit three places
SZG, BG, JB.
In the graph model, the three places are modeled as three vertices.
In addition, three edges are introduced into the graph to
represent the conflicts among these vertices.
(a) If a tourist (call him X) wants to visit 6 different places,
how many edges will be introduced into the graph to represent
the conflicts?
(b) What if X wants to visit m places (where m is some integer)?
T1-D5: [Job Scheduling Problem]
In this problem, you are given a list of 10 jobs --
J1, J2,.., J10.
The kth job
Jk = [s, e]
has a start time s
and an end time e (for k=1,2,..,10).
An instance of this problem with J1,. . ., J10 is shown
in the diagram below. Each job is represented by an
interval with start and end times.
|
J1 = [00,03],
J2 = [11,19],
J3 = [14,20], J4 = [02,06], J5 = [08,12], J6 = [06,10], J7 = [01,04], J8 = [12,16], J9 = [15,19], J10 = [04,09], |
|
You have a list of workers, and you want to assign these jobs to a minimum number of workers. Each worker can do any number of jobs as long as the jobs do not overlap in time. (For this problem, you can assume that a worker can start on a new job immediately after finishing a previous job. So, jobs J7 and J10 can be assigned to the same worker, if necessary.)
We want to use the method of graph colouring to solve this job scheduling problem --
like how we use a conflict graph model to solve the tourist problem in the lectures.
To do that, we first model this job scheduling problem using a conflict graph.
In this conflict graph, each node represents (models) a job.
Now you need to figure out the rest of the steps.
(a) Explain carefully how the edges in the conflict graph are defined.
(Think: When is there a conflict between two jobs?)
(b) Draw the conflict graph for this job scheduling instance.
(c) What is the minimum number of workers needed to complete all the jobs?
T1-Q1: (10 points) [Origami and Computing]
Algorithms have often been compared with Origami
-- the art of paper folding.
(a) For this problem, you should do a paper folding of an object
of your choice --- choose an interesting, creative one,
but it should involve more than 25 basic folding steps.
You are to submit the finished product (the folded origami piece).
(Of course, you can do more than one, if you like.)
(b) Along with the finished product, please also submit the instructions
for folding it onto IVLE folder called "T1-Q1-Origami".
(If the instructions are from a book, snap a picture,
if it is web-page, save it as a document (pdf or ps file).
If you do not know how to save as pdf or ps file, then snap a picture
and save as file.) If it is youtube video, just list the url.
(Hint: If you are not yet an origami person,
go online to search for origami instructions or
find an origami book in the library.
There are plenty available.)
T1-Q2: [Tourist Problem] Another instance.
Solve the following instance of the Tourist Problem, where
the are 8 tourists and the places they want to visit are given below.
| Tourist | Places to Visit | Tourist | Places to Visit | |
|---|---|---|---|---|
| | BG, CG, SZG | | JB, SZG | |
| | JG, SZG, CG | | BG, JB | |
| | SZG, OR, JG | | VC, OR | |
| | OR, VC, SI | | JB |
(a) Draw the conflict graph G for this Tourist Problem instance.
(b) Give a coloring of the conflict graph G that uses the minimum number of colours.
(c) Hence, give a scheduling of buses to the tourist attractions. How many days are needed.
T1-Q3: [Job Scheduling Problem] Another instance.
Re-do Problem T1-D5 with the following instance of the Job Scheduling Problem,
with 9 jobs.
| J1 = [1, 4], | J2 = [2, 4], | J3 = [3, 8], | J4 = [5, 7], | J5 = [6, 10], | |||||
| J6 = [7, 12], | J7 = [8, 13], | J8 = [10, 15], | J9 = [12, 16], | J10 = [14, 18], | |||||
T1-Q4: (10 points) [Tourist Problem. The Good and the Bad]
Suppose that the entire UIT2201 class are the tourists
in the Tourist Problem v1.0 (covered in the lectures).
Assume there are 30 students in the class.
Suppose that each of you must visit exactly two places,
but you are all free to choose whichever two places you like.
(a) (The Good) You all want to help the tour company finish scheduling all
the trips as soon as possible (ASAP).
And so all 30 of you conspire together and
work out a strategy to choose the places
in such a way that it will take
the minimum number of days to schedule all the trips.
What is the minimum number of days needed to complete all the trips?
And how should the students choose the places?
.
(In general, coffee-awards recognize excellent efforts [in many forms] by the students.
They can be redeemed at any time. Coffee can be changed to other drinks as well.)
A1: [Continued from Problem T1-Q4]
(b) (The Bad) Now, suppose that you all want to force the tour company
finish scheduling all the trips as late as possible (ALAP).
So, all 30 of you conspire together and
work out a strategy to choose the places
in such a way that it will take
the maximum number of days to schedule all the trips.
What is the maximum number of days that you can "impose"
on the tour company?
And how should the students choose the places?