FIT2014
Assignment 1
1st Semester 2025
Linux tools, logic, regular expressions, induction
DUE: 11:55pm, Friday 28 March 2025 (Week 4)
Start work on this assignment early. Bring questions to Consultation and/or the Ed Forum.
Instructions
• Generative AI tools must not be used for any part of this Assignment.
You must not use generative artificial intelligence (AI) to generate any materials or content in relation to this Assignment (or any other assessment in this unit). For example, no GPT, DeepSeek, Copilot, Claude, Cohere, Gemini/Bard, etc.
• The work you submit for this Assignment must be your own individual work.
• To start work, download the workbench asgn1 .zip from Moodle. Create 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 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.
• Every PDF file submitted must also contain your name and student ID at the start.
• 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:
• the file student-id, edited to contain your name and student ID
• 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.
Initially, the asgn1 directory contains empty files (or dummy files) with the required filenames.
These must each be replaced by the files you write, as described above. Before submission, check that each of these empty files is, indeed, replaced by your own file, and that the student-id file is edited as required.
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. In Problems 1–4, you will construct an awk program to construct, for any directed graph, a logical expression that describes the conditions under which the directed graph has a normal 2-regular subgraph.
Finally, Problem 5 is about applying induction to a problem about structure and satisfiability of some Boolean expressions in Conjunctive Normal Form (CNF).
Introduction to awk
An awk program takes an input file and processes it line-by-line. 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 in the input file 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 NF,
• the function printf( ··· ),
• if statements
• for loops. For these, you will only need simple loops like
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.)
• the GNU Awk User’s Guide.
• the Wikipedia article looks ok
• the awk manpage
The following is a useful reference, but might be less suitable as an introduction, as its detailed treatment of patterns and actions (the heart of awk) comes very late, long after extensive discussion of other programming aspects:
• https://www.grymoire.com/Unix/Awk.html
Introduction to Problems 1–4
Many systems and structures can be modelled as graphs (abstract networks) or as directed graphs (in which every edge is an ordered pair of vertices, and therefore has a direction, and is shown as an arrow in diagrams).
Suppose you have a set of people who are going to give presents to each other. Each person must be allocated one other person to give a present to, in such a way that everyone receives exactly one present. But each person can only give to certain people; there will be other people that they can’t give a present to, perhaps because they don’t know enough about the other person’s tastes or interests. We can represent the people by vertices, and put a directed edge (U, w) from U to w if person U is able to give a present to person w. There are two further rules:
• You have to be allocated to someone else (i.e., not yourself). (This is a social activity!)
• The person who gives you a present has to be different to the person who you give a present to. This means that two people cannot give presents to each other. (It’s a group activity, not just about pairing off.)
Figure 1: Three digraphs, H1 , H2 , H3 . The first, H1 , and the third, H3 , have a normal 2-regular subgraph, but the middle one, H2 , does not.
Is it possible for each person to be allocated one other person to give a present to, satisfying these requirements? Sometimes it is, sometimes it isn’t. Determining whether this can be done is, in general, a nontrivial problem.
We can model this abstractly by the Normal 2-Regular Subgraph problem, which we consider here.
Throughout, we use G to denote a directed graph (also called a digraph), n denotes its number of vertices and m denotes its number of directed edges, also called arcs. V (G) denotes the set of vertices of G, and A(G) denotes the set of arcs of G.
A 2-regular subgraph of a digraph G is a set of arcs X ⊆ A(G) such that every vertex of G has exactly one arc coming into it and exactly one arc going out of it. Such a subgraph consists of a collection of directed cycles such that each vertex belongs to exactly one cycle in the collection. A 2-regular subgraph is normal if all its cycles have at least three arcs. This means it contains no loops (i.e., no arcs from a vertex to itself) and no pair (v, w), (w, v) of oppositely-directed arcs on the same two vertices.
Not every digraph has a normal 2-regular subgraph.
For example, in the digraph H1 in Figure 1, the arc set {(1, 2), (2, 5), (5, 4), (4, 3), (3, 1)} is a normal 2-regular subgraph, consisting of a single directed cycle of five arcs. But:
• {(1, 2), (2, 5), (5, 4), (4, 3)} is not a normal 2-regular subgraph, because there is no arc coming out of vertex 3, and no arc going into vertex 1. (In the present-giving context: person 3 has not been allocated someone to give a present to, and person 1 is not going to receive a present.)
• {(1, 2), (2, 5), (5, 4), (4, 3), (3, 1), (1, 3)} is not a normal 2-regular subgraph, because vertex 1 has two outgoing arcs, and also because vertex 3 has two incoming arcs.
• {(2, 5), (5, 4), (4, 2), (3, 1), (1, 3)} is not a normal 2-regular subgraph, even though every vertex has one incoming arc and one outgoing arc, because there is a cycle of length only 2.
Digraph H2 has no normal 2-regular subgraph.
In digraph H3 , the arc set {(1, 2), (2, 7), (7, 6), (6, 1), (3, 4), (4, 5), (5, 3)} is a normal 2-regular subgraph, consisting of two directed cycles, one of four arcs and another of three arcs. The arc set {(1, 2), (2, 3), (3, 4), (4, 5), (5, 7), (7, 6), (6, 1)} is another normal 2-regular subgraph, consisting of a single directed cycle of seven arcs. But the arc set {(1, 2), (2, 3), (1, 3), (4, 5), (5, 7), (7, 6), (6, 4)} is not a normal 2-regular subgraph, even though it may appear to consist of two separate “cycles” and every vertex belongs to exactly one of those cycles. The trouble is that the “cycle” (1, 2), (2, 3), (1, 3) is not a properly directed cycle. It is not enough that the other cycle, (4, 5), (5, 7), (7, 6), (6, 4), is a directed cycle; it is required that all the cycles are indeed directed cycles.
In Problems 1–4, you will complete a partly-written program in awk that constructs, for any digraph G, a Boolean expression φG in Conjunctive Normal Form, with variables vi,j (described below), such that φG captures, in logical form, the statement that G has a normal 2-regular subgraph. This assertion might be True or False, depending on G, but the requirement is that
G has a normal 2-regular subgraph ⇐⇒ you can assign truth values to the variables vi,j of φG to make φG True.
For each arc (i, j) ∈ A(G) we introduce a Boolean variable vi,j . It is our intention that each such variable represents the statement that “arc (i, j) is included in the normal 2-regular subgraph” (which might be True or False). When we write code, each variable vi,j is represented by a name in the form of a text string aibj formed by concatenating a, i, b, and j. So, for example, v1 ,3 is represented by the name a1b3.
But if all we have is all these variables, then there is nothing to control whether they are each True or False. We will need to build some logic, in the form of a CNF expression, to make this interpretation work. So, we need to encode the definition of a normal 2-regular subgraph into a CNF expression using these variables. The expression we construct must depend on the digraph.
Furthermore, it must depend only on the digraph.
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 H1 shown on the left in Figure 1, construct a CNF Boolean expression φH using the variables vi,j such that φH is True if and only if the assignment of truth values to the variables represents a normal 2-regular subgraph of H.
Now type this expression φH into a one-line text file, using our text names for the variables (i.e., a1b2, a1b3, a3b1, etc.), with the usual logical operations replaced by text versions as follows:
Put your answer in a one-line text file called prob1.txt.
We are now going to look at the general process of taking any digraph G on n vertices, and constructing a corresponding Boolean expression φG with n variables, in such a way that:
• the variables of φG correspond to arcs in G, and
• φG evaluates to True if and only if the assignment of truth values to those variables corresponds to a normal 2-regular subgraph in G.
The next part of the assignment requires you to write an awk script to automate this construction.
For the purposes of this task, every digraph is encoded in a type of adjacency list format in the following format:
• One line contains n, the number of vertices, followed by m, the number of edges, with at least one blank separating them, and possibly some blanks before and after them.
• Every other line is a vertex line and has the following format:
i : j1 j2 ··· jd
where i and j1 , j2 , . . . , jd (with d ≥ 0) are all positive integers, with the j1 , j2 , . . . , jd all being distinct. This means that the arcs going out of vertex i are (i, j1 ), (i, j2 ), . . . , (i, jd ), and this line serves as a complete list of those arcs.
• In a vertex line, we allow any positive number of spaces between numbers and on either side of the colon. So there is always space between the numbers and around the colon. There may also be some number of spaces before the first number i and after the last number jd.
• For each i in the range 1 ≤ i ≤ n, there is exactly one vertex line for vertex i.
• Lines that are not in one of the two formats above can be present but they must be ignored by your programs.
• The lines can be in any order in the file. There is no requirement that the line stating n and m be at the start, and there is no requirement that the vertex lines are listed in order of vertex number.
• For example, the digraph in Figure 1 could be represented by the six-line file on the left below, or (less neatly) by the one on the right (which has the line with n and m later on in the file, which is permitted, and it also has a spurious line of text, which is also permitted but must be ignored).
• Each digraph is represented in a file of its own. Each input file contains exactly one digraph represented in this way.
• Positive integers, for n and the vertex numbers, can have any number of digits. They must have no decimal point and no leading 0.
Problem 2. [7 marks]
Complete the partial awk script. below so that when it takes, as input, a graph G represented in the specified format in a text file, it should produce, as output, a one-line file containing the text representation of a Boolean expression φG in CNF which uses the variables we have specified and which is True if and only if the variables describe a normal 2-regular subgraph of G.
The text representation is the same as that described on p4 and used for Problem 1.
Put your answer in a file called prob2.awk.
BEGIN {
firstMatch = 1;
}
# Write a pattern-action statement that gets the number
# of vertices and stores it in the variable n.
# A single line should be sufficient.
Write pattern-action statement here
# Now, complete the pattern for detecting lines that start with
# a vertex number followed by a colon in the required format
/Write your pattern here/ {
# This action statement spans several lines .
# You will need to add code in appropriate gaps
# in order to print parts of the CNF expression.
# One printf statement is shown, but you will need several others .
# You also need to replace some specific conditions as indicated .
if (firstMatch == 1)
{
firstMatch = 0;
}
else
{
}
Write assignment statement here, setting variable v to vertex number
if (this vertex has at least one outgoing edge)
{
printf("a%db%d", v, $3);
arc[v, $3] = 1;
for (insert appropriate loop control here)
{
arc[v, $i] = 1;
}
# Here you can write your own loop to print further clauses
# if needed .
}
else
{
}
}
END {
# Outer loop goes through all vertices, and for each,
# adds clauses to deal with any directed loop at that vertex,
# Outer and inner loops together go through all pairs of distinct
# vertices, adding clauses to deal with any directed cycle of two edges.
# In these nested loops, you need to add appropriate printf statements.
for (i = 1; i <= n; i++)
{
if (arc[i,i] == 1)
{
}
for (j = i; j <= n; j++)
{
if (arc[i,j] == 1 && arc[j,i] == 1)
{
}
}
}
}
Problem 3. [3 marks]
(a) Derive an upper bound, in terms of n, for the number of calls to printf that are required to output φG.
(b) Express the upper bound for (a) in big-O notation.
Put your answers in a PDF file called prob3.pdf.
We are now going to modify the awk script so that the output it produces can be taken as input by a program for testing satisfiability.
SageMath is software for doing mathematics. It is powerful, widely used, free, open-source, and based on Python. It is already available in your Ed Workspace. You don’t need to learn SageMath for this assignment (although it’s good to be aware of what it is); you only need to follow the instructions below on how to use a specific function in SageMath for a specific task. If you’re interested, you may obtain further information, including tutorials, documentation and installation instructions, at https://www.sagemath.org .
In this part of the assignment, we just use one line of SageMath via the Linux command line in order to determine whether or not a Boolean expression in CNF is satisfiable (i.e., has an assignment of truth values to its variables that makes the expression True). Suppose we have the Boolean expression
(a V b) Λ (¬a V ¬b) Λ (¬a V b),
which we note is satisfiable because it can be made True by putting a = False and b = True. We first translate the expression into text in the way described earlier (p4), replacing ¬ ,Λ ,V by ˜ ,&, | respectively. This gives the text string
(a | b) & (˜a | ˜b) & (˜a | b).
We ask SageMath if this is satisfiable by entering the following text at the Linux command line:
$ sage -c ' print(propcalc.formula("(a | b) & ( a | b) & ( a | b)") .is_satisfiable()) ' True
You can see that SageMath outputs True on the next line to indicate that the expression is satisfiable.
In sage -c, the “-c” instructs sage to execute the subsequent (apostrophe-delimited) Sage command and output the result (to standard output) without entering the SageMath environment.
This is all you need to do to use the SageMath satisfiability test on your expression. If you want to actually enter SageMath and use it interactively, you can do so:
$ sage
sage: print(propcalc .formula("(a | b) & (~a | ~b) & (~a | b)") .is_satisfiable()) True
Again, the output True indicates satisfiability.
The SageMath satisfiability-testing function we are using here, is_satisfiable(), is the most primitive satisfiability-tester that you can use in SageMath. It determines if an expression is sat- isfiable by constructing the entire truth table for the expression and determining if any row (i.e., any truth assignment to the variables) gives the value True for the expression. For an expression with n variables, this involves listing all 2n truth assignments. This requires an amount of work that is exponential in the number of variables. So it will not be very efficient, even for modest-sized expressions. (The fact that truth tables are exponentially large, in the number of variables, is closely related to the fact that converting a Boolean expression to DNF can lead to an expression that is exponentially large in the number of variables.) SageMath also provides access to more sophisticated satisfiability-testers. They too can take exponential time in the worst case, though in practice they are much faster than is_satisfiable() (but they take some more effort to use for the first time).