Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
FIT2014
Assignment 1
Linux tools, logic, regular expressions, induction
DUE: 11:55pm, Friday 18 August 2023 (Week 4)
Start work on this assignment early. Bring questions to Consultation and/or the Ed Forum.
Instructions
Please read these instructions carefully before you attempt the assessment:
• To begin working on the assignment, download the workbench asgn1.zip from Moodle. Cre-
ate a new Ed Workspace and upload this file, letting Ed automatically extract it. Edit the
student-id file to contain your name and student ID. Refer to Lab 0 for a reminder on how
to do these tasks.
• The workbench provides locations and names for all solution files. These will be empty, needing
replacement. Do not add or remove files from the workbench.
• Solutions to written questions must be submitted as PDF documents. You can create a PDF
file by scanning your legible (use a pen, write carefully, etc.) hand-written solutions, or by
directly typing up your solutions on a computer. If you type your solutions, be sure to create
a PDF file. There will be a penalty if you submit any other file format (such as a Word
document). Refer to Lab 0 for a reminder on how to upload your PDF to the Ed workspace
and replace the placeholder that was supplied with the workbench.
• Before you attempt any problem—or seek help on how to do it—be sure to read and understand
the question, as well as any accompanying code.
• When you have finished your work, download the Ed workspace as a zip file by clicking on
“Download All” in the file manager panel. You must submit this zip file to Moodle by
the deadline given above. To aid the marking process, you must adhere to all naming
conventions that appear in the assignment materials, including files, directories, code, and
mathematics. Not doing so will cause your submission to incur a one-day late-penalty (in
addition to any other late-penalties you might have). Be sure to check your work carefully.
Your submission must include:
• a one-line text file, prob1.txt, with your solution to Problem 1;
• an awk script, prob2.awk, for Problem 2;
• a PDF file prob3.pdf with your solution to Problem 3;
• an awk script, prob4.awk, for Problem 4;
• a file prob5.pdf with your solution to Problem 5.
Introduction to the Assignment
In Lab 0, you met the stream editor sed, which detects and replaces certain types of patterns in
text, processing one line at a time. These patterns are actually specified by regular expressions.
In this assignment, you will use awk which does some similar things and a lot more. It is a simple
programming language that is widely used in Unix/Linux systems and also uses regular expressions.
1
In Problems 1–4, you will construct an awk program to construct, for any graph, a logical expression
that describes the conditions under which the graph is 3-colourable.
Finally, Problem 5 is about applying induction to a problem about structure and satisfiability of
some Boolean expressions in Conjunctive Normal Form.
Introduction to awk
In an awk program, each line has the form
/pattern / { action }
where the pattern is a regular expression (or certain other special patterns) and the action is an
instruction that specifies what to do with any line that contains a match for the pattern. The action
(and the {. . . } around it) can be omitted, in which case any line that matches the pattern is printed.
Once you have written your program, it does not need to be compiled. It can be executed di-
rectly, by using the awk command in Linux:
$ awk -f programName inputFileName
Your program is then executed on an input file in the following way.
// Initially, we’re at the start of the input file, and haven’t read any of it yet.
If the program has a line with the special pattern BEGIN, then
do the action specified for this pattern.
Main loop, going through the input file:
{
inputLine := next line of input file
Go to the start of the program.
Inner loop, going through the program:
{
programLine := next line of program (but ignore any BEGIN and END lines)
if inputLine contains a string that matches the pattern in programLine, then
if there is an action specified in the programLine, then
{
do this action
}
else
just print inputLine // it goes to standard output
}
}
If the program has a line with the special pattern END, then
do the action specified for this pattern.
Any output is sent to standard output.
You should read about the basics of awk, including
• the way it represents regular expressions,
• the variables $1, $2, etc., and NR,
• the function printf(· · · ),
• for loops. For these, you will only need simple loops like
2
for (i = 1; i <= n; i++)
{
⟨body of loop⟩
}
This particular loop executes the body of the loop once for each i = 1, 2, . . . , n (unless the body
of the loop changes the variable i somehow, in which case the behaviour may be different, but
you should not need to do that). You can nest loops, so the body of the loop can be another
loop. It’s also ok to write loops more compactly,
for (i = 1; i <= n; i++) { ⟨body of loop⟩ }
although you should ensure it’s still clearly readable.
Any of the following sources should be a reasonable place to start:
• A. V. Aho, B. W. Kernighan and P. J. Weinberger, The AWK Programming Language,
Addison-Wesley, New York, 1988.
(The first few sections of Chapter 1 should have most of what you need, but be aware also of
the regular expression specification on p28.)
• https://www.grymoire.com/Unix/Awk.html
• the Wikipedia article looks ok
• the awk manpage
• the GNU Awk User’s Guide.
Introduction to Problems 1–4
Many systems and structures can be modelled as graphs (abstract networks). Many problems on
these structures require allocation of some scarce resources to the objects in a network in such a way
that objects that are close together do not share the same resource. For example, in timetabling,
two classes with some students in common should not be scheduled in the same timeslot; in commu-
nications networks, two neighbouring cellphone towers should not be assigned the same transmission
frequency (to minimise interference). This wide family of problems, drawn from many different do-
mains, can be modelled abstractly by graph colouring. To keep things simple for the assignment,
we will only use a few colours, but in real applications the numbers of colours used can be very large.
Throughout, we use G to denote a graph, n denotes its number of vertices and m denotes its
number of edges.
A 3-colouring of a graph G is a function f : V (G) → {Red,White,Black} such that adjacent
vertices are given different colours by f . Here, V (G) denotes the set of vertices of G. A graph is
3-colourable if it has a 3-colouring.
For example, the graph in Figure 1(a) is 3-colourable, and an actual 3-colouring is shown for it.
Note that a 3-colouring does not have to use all three available colours. The graph in Figure 1(b)
is shown with a 2-colouring, using just the colours Black and White, so it is 2-colourable. It is also
3-colourable, since every 2-colouring is also a 3-colouring.
The graph in Figure 1(c) is not 3-colourable. Study it carefully and check that this assertion is
correct.
In Problems 1–4, you will write a program in awk that constructs, for any graph G, a Boolean
expression φG in Conjunctive Normal Form that captures, in logical form, the statement that G is
3-colourable. This assertion might be True or False, depending on G, but the requirement is that
G is 3-colourable ⇐⇒ you can assign truth values to the variables of φG to make it True.
For each vertex i ∈ V (G) and each colour c ∈ {Red,White,Black}, we introduce a Boolean
variable vi,c. It is our intention that this represents the statement that “vertex i gets colour c”
(which might be True or False). So, for example, we want the variable v2,Red to represent the
3
1Red
2
White
3
Black
4
Red
(a)
1
White
2
Black
3
Black
4
White
(b) (c)
Figure 1: Three graphs. (a) A 3-colourable graph, with a 3-colouring. (b) Another 3-colourable
graph. This one is also 2-colourable. It is shown with a 2-colouring, which is also a 3-colouring. (c)
A non-3-colourable graph.
statement “vertex 2 gets colour Red”. But we will need to build some logic, in the form of a CNF
expression, to make this interpretation work.
When we write code, each variable vi,c is represented by a name in the form of a text string vic
formed by concatenating v, i and c. So, for example, v2,Red is represented by the name v2Red.
If all we have is all these variables, then there is nothing to control whether they are each True or
False. Their values might not bear any relation to their intended meaning. For example, we might
have v4,Red = True and v4,Black = True, meaning that vertex 4 gets two colours instead of one. Or
we might have v1,Red = v1,White = v1,Black = False, meaning that vertex 1 gets no colour at all. Or
we might violate the constraint that adjacent vertices get different colours: if vertices 2 and 3 are
adjacent, and v2,Red = v3,Red = True, then the interpretation is that both these vertices get colour
Red even though they are adjacent, which breaks the rules.
So, we need to encode the definition of 3-colourability into a CNF expression using these variables.
The expression we construct must depend on the graph. Furthermore, it must depend only on the
graph. Think of the graph as uncoloured: you cannot assume that any vertex gets any specific
colour.
We begin with a specific example (Problem 1) and then move on to general graphs (Problems 2–4).
Problem 1. [2 marks]
For the graph H shown on the right (Fig. 2), construct a Boolean
expression φH using the variables vi,c which is True if and only if the
assignment of truth values to the variables represents a 3-colouring
of H.