CSC 225 ASSIGNMENTs 1 to 4 solutions

Description

CSC 225 ASSIGNMENT 1 – PROGRAM and Written

1 Programming Assignment
The assignment is to design and implement an algorithm for the TripleSum225 problem. The problem is
defined as follows:
Input: An array 𝐴 of 𝑛 non-negative integers.
Output: A boolean value (true or false). If there are three indices 𝑖,𝑗, 𝑘 such that 0 ≤ 𝑖,𝑗, 𝑘 ≤
𝑛 − 1 and 𝐴[𝑖] + 𝐴[𝑗] + 𝐴[𝑘] = 225, the output will be true. If no such indices exist,
the output will be false. Note that 𝑖,𝑗 and 𝑘 do not have to be distinct.
Your task is to write a java program, stored in a file named TripleSum.java, that contains a function
TripleSum225, which takes an integer array 𝐴 as its only argument, and returns a boolean value. You may
assume that the provided array 𝐴 conforms to the specification above (that is, 𝐴 will contain only nonnegative integers).
The main function in your code should help you test your implementation by getting test data or reading it
from a file. It should also handle errors and keep track and report running times to the user. You may use
the Java template provided for your Lab 2 implementation as a starting point, just be sure that it properly
works for your code.
2 Example
The table below shows the correct output of the TripleSum225 function on various test inputs. In cases
where the output is true, a set of three elements of the array which sum to 225 is shown. Note that there
may be more than one triple of elements which sum to 225.
Input Array Result Triple
50, 100, 75, 500 true 50 + 75 + 100 = 225
150, 125, 100, 175 false (none)
1, 200, 100, 225 false (none)
50, 25, 75 true 75 + 75 + 75 = 225
225, 500, 1000 false (none)
225, 0, 1, 5000 true 0 + 0 + 225 = 225
224, 1, 2, 2, 2 false (none)
224, 1, 0, 2, 2 true 0 + 1 + 224 = 225
3 Test Datasets
A set of input files containing test data are available in the ‘Assignments’ folder under the ‘Resources’ tab
on ConneX, sorted by their size and whether or not they contain a triple which adds to 225. You should
ensure that your implementation gives the correct answer on these test files before submitting. It may also
be helpful to test your implementation on a variety of other inputs, since the posted data may not cover all
possible cases. Depending on the running time of your algorithm, it may not be able to process some of
the larger input files.
4 Evaluation Criteria
The programming assignment will be marked out of 25, based on a combination of automated testing
(using large test arrays similar to the ones posted on ConneX) and human inspection. There are several
possible algorithms for the TripleSum225 problem, with a variety of running times. For an input array
containing 𝑛 values, the simplest algorithm is (𝑛
3
) and the optimal algorithm is (𝑛). The mark for
each submission will be based on both the asymptotic worst-case running time and the ability of the
algorithm to handle inputs of different sizes. The table below shows the expectations associated with
different scores.
Score Description
0 – 5 Submission does not compile.
5 – 15 The implemented algorithm is 𝑂(𝑛
3
) or is
substantially inaccurate on the tested inputs.
15 – 20 The implemented algorithm is 𝑂(𝑛
2
𝑙𝑜𝑔 𝑛). Input
arrays of size 10,000 can be processed in under 30
seconds, but arrays of larger sizes may not be
feasible in a reasonable amount of time.
20 – 25 The implemented algorithm is 𝑂(𝑛), gives the
correct answer on all tested inputs, and can process
arrays of size 1,000,000 in under 10 seconds.
To be properly tested, every submission must compile correctly as submitted. If your submission does
not compile for any reason (even trivial mistakes like typos), it will receive at most 5 out of 25. The
best way to make sure your submission is correct is to download it from ConneX after submitting and test
it. You are not permitted to revise your submission after the due date, and late submissions will not be
accepted, so you should ensure that you have submitted the correct version of your code before the due
date. ConneX will allow you to change your submission before the due date if you notice a mistake. After
submitting your assignment, ConneX will automatically send you a confirmation email. If you do not
receive such an email, your submission was not received. If you have problems with the submission
process, send an email to the instructor before the due date.

1. Order the following list of functions by their big-Oh notation. Group together (for example, by
underlining) those functions that are big-Theta of one another. (No justification needed).
Note: log 𝑛 = log2 𝑛 unless otherwise stated.
6𝑛 log 𝑛 2
100 log log 𝑛 log2 𝑛 2
log 𝑛
2
2
𝑛
√𝑛 𝑛
0.01 1⁄𝑛 4𝑛
3⁄2
3𝑛
0.5 5𝑛 2𝑛 log2 𝑛 2
𝑛 𝑛 log4 𝑛
4
𝑛 𝑛
3 𝑛
2
log 𝑛 4
log 𝑛 √log 𝑛
Hint: When in doubt about two functions 𝑓(𝑛) and 𝑔(𝑛), consider log 𝑓(𝑛) and log 𝑔(𝑛) or
2
𝑓(𝑛)
and 2
𝑔(𝑛)
.
2. Justify the fact that if 𝑑(𝑛) is 𝑂(𝑓(𝑛)) and 𝑒(𝑛) is 𝑂(𝑔(𝑛)), then the product 𝑑(𝑛)𝑒(𝑛) is
𝑂(𝑓(𝑛)𝑔(𝑛)).
3. Show that log𝑏 𝑓(𝑛) is (log2 𝑓(𝑛)) if 𝑏 > 1 is a constant.
Hint: One of the properties of logarithms from the slide I gave you is very useful here.
4. Consider the recurrence equation,
𝑇(𝑛) = {
1 if 𝑛 = 0
𝑇(𝑛 − 1) + 2
𝑛 otherwise.
Show, by induction, that 𝑇(𝑛) = 2
𝑛+1 − 1.
5. Consider the Algorithm arrayFind, given below, which searches an array 𝐴 for an element 𝑥.
Algorithm arrayFind(𝑥, 𝐴):
Input: An element 𝑥 and an 𝑛-element array, 𝐴.
Output: The index 𝑖 such that 𝑥 = 𝐴[𝑖] or −1 if no element of 𝐴 is equal to 𝑥.
𝑖 ← 0
while 𝑖 < 𝑛 do
if 𝑥 = 𝐴[𝑖] then
return 𝑖
else
𝑖 ← 𝑖 + 1
return −1
(a) Counting assignments, comparisons, and returns only, calculate the worst-case, 𝑇(𝑛), and
best-case, 𝑇𝑏
(𝑛), running times of arrayFind.
(b) Prove by induction (loop invariants) that arrayFind is correct.

CSC 225 ASSIGNMENT 2 – PROGRAMMING and Written

1 Programming Assignment
In a sequence 𝑆 = 𝑠1, 𝑠2, … , 𝑠𝑛 of 𝑛 integers, an inversion is a pair of elements 𝑠𝑖 and 𝑠𝑗 where
𝑖 < 𝑗 (that is, 𝑠𝑖 appears before 𝑠𝑗
in the sequence) and 𝑠𝑖 > 𝑠𝑗
. For example, in the sequence
𝑆 = 2, 1, 5, 3, 4
the pairs (2,1), (5,3) and (5,4) are inversions.
The programming assignment is to implement an algorithm which counts the number of
inversions in an input sequence:
Input: An array 𝐴 of 𝑛 integers in the range 1 − 𝑛.
Output: An integer, corresponding to the number of inversions in 𝐴.
An array with 𝑛 elements may have as many as
(
𝑛
2
) =
𝑛(𝑛 − 1)
2
inversions. When the number of inversions 𝑘 may be any value between 0 and 𝑛(𝑛−1)
2
, the best
algorithm for counting inversions has running time 𝑂(𝑛 log(𝑛)). There also exists a 𝑂(𝑛 + 𝑘)
algorithm for counting inversions, which is 𝑂(𝑛
2
) when 𝑘 ∈ 𝑂(𝑛
2
).
In this assignment, we will assume that the number of inversions is at most 𝑛 (that is, 𝑘 ≤ 𝑛).
When the 𝑂(𝑛 + 𝑘) algorithm is used with such values of 𝑘, its running time is 𝑂(𝑛 + 𝑛) =
𝑂(𝑛). For full marks, your implementation must run in 𝑂(𝑛) time when 𝑘 ≤ 𝑛.
Your task is to write a java program, stored in a file named CountInversions.java that
contains a function CountInversions, which takes an integer array A as its only argument,
and returns an integer value. The main function in your code should help you test your
implementation by getting test data or reading it from a file. It should also handle errors but don’t
worry about running times.
2 Examples
The table below gives the inversion count and a list of the inversions present in several small
input arrays.
Input Array # of Inversions Inversions
1, 2, 3 0 none
1, 2, 3, 5, 4 1 (5, 4)
10, 30, 40, 20, 50 3 (30, 20), (40, 20)
4, 3, 2, 1, 5, 6 6 (4, 3), (4, 2), (4, 1), (3, 2), (3, 1), (2, 1)
5, 1, 2, 3, 4 4 (5, 1), (5, 2), (5, 3), (5, 4)
3 Test Datasets
A set of input files have been uploaded to ConneX, containing arrays of various sizes and
inversion counts. You should test your implementation on the uploaded files before submitting.
Note that an algorithm with a running time which is 𝑂(𝑛 log 𝑛) or better should be able to
process any of the files within a few seconds. The uploaded files may not cover all possible
cases, so you should test your implementation on other inputs as well.
4 Evaluation Criteria
The programming assignment will be marked out of 25, based on a combination of automated
testing (using large test arrays similar to the ones posted on ConneX) and human inspection. All
of the tested input arrays will have an inversion count 𝑘 which is at most 𝑛.
Score (/25) Description
0 – 5 Submission does not compile or does not
conform to the provided template.
5 – 15 The implemented algorithm is 𝑂(𝑛
2
) or is
substantially inaccurate on the tested inputs.
15 – 20 The implemented algorithm is 𝑂(𝑛 log 𝑛) or
contains minor errors.
20 – 25 The implemented algorithm is 𝑂(𝑛 + 𝑘) on an
array with 𝑛 elements and 𝑘 inversions, resulting
in a 𝑂(𝑛) algorithm when 𝑘 ∈ 𝑂(𝑛).
To be properly tested, every submission must compile correctly as submitted. If your submission
does not compile for any reason (even trivial mistakes like typos), it will receive at most 5 out of
25. The best way to make sure your submission is correct is to download it from ConneX after
submitting and test it. You are not permitted to revise your submission after the due date, and
late submissions will not be accepted, so you should ensure that you have submitted the correct
version of your code before the due date. ConneX will allow you to change your submission
before the due date if you notice a mistake. After submitting your assignment, ConneX will
automatically send you a confirmation email. If you do not receive such an email, your
submission was not received. If you have problems with the submission process, send an email
to the instructor before the due date.

1. Describe how to implement the stack ADT using two queues. What is the running time of the push()
and pop() methods in this case?
2. Show the various steps of Selection Sort, Bubble Sort and Insertion Sort on the example array,
𝐴 = {5, 7, 0, 3, 4, 2, 6, 1}.
3. An Array 𝐴 contains 𝑛 − 1 unique integers in the range [0, 𝑛 − 1]. That is, there is one number in
this range that is not in 𝐴. Describe in pseudo-code an 𝑂(𝑛)-time algorithm for finding that number.
You are only allowed to use 𝑂(𝑙𝑜𝑔 𝑛) bits of additional space besides the array 𝐴 itself.
4. Consider an implementation of a stack using an extendible array. That is, instead of giving up with a
“StackFullException” when the stack becomes full, we replace the current array 𝑆 of size 𝑁 with a
larger one of size 𝑓(𝑁) and continue processing the push operations. Suppose that we are given two
possible choices to increase the size of the array: (1) 𝑓(𝑁) = 𝑁 + 𝑐 (for convenience, we start
with an initial array of size 0) (2) 𝑓(𝑁) = 2𝑁 (we start with an initial array of size 1). Compare the
two strategies and decide which one is better.
To analyze the two choices, assume the following cost model: A “regular” push operation costs one
unit of time. A “special” push operation, when the current stack is full, costs 𝑓(𝑁) + 𝑁 + 1 units
of time. That is, we assume a cost of 𝑓(𝑁) units to create the new array, 𝑁 units of time to copy the
𝑁 elements and one unit of time to copy the new element.
5. Characterize each of the following recurrence equations using the master method (assuming that
𝑇(𝑛) = 𝑐 for 𝑛 < 𝑑, for constants 𝑐 > 0 and 𝑑 ≥ 1).
a. 𝑇(𝑛) = 2𝑇(𝑛/2) + log 𝑛
b. 𝑇(𝑛) = 8𝑇(𝑛/2) + 𝑛
2
c. 𝑇(𝑛) = 16𝑇(𝑛/2) + (𝑛 log 𝑛)
4
d. 𝑇(𝑛) = 7𝑇(𝑛/3) + 𝑛
e. 𝑇(𝑛) = 9𝑇(𝑛/3) + 𝑛
3
log �

CSC 225 ASSIGNMENT 3 – PROGRAMMING and Written

1 Programming Assignment
Write a program that prints out all integers of the form 𝑎
3 + 𝑏
3
, where 𝑎 and 𝑏 are integers in the
range [0, 𝑛], in sorted order while using 𝑂(𝑛) space. That is, you cannot use an array of size 𝑛
2
and then sort it.
Input: A nonnegative integer n.
Output: A sorted list of all integers of the form 𝑎
3 + 𝑏
3
, where 𝑎 and 𝑏 are integers in
the range [0, 𝑛].
For each value integer of this form you will need to keep track of three things, the integer itself,
𝑎
3 + 𝑏
3
, and the two integers used to create it, 𝑎 and 𝑏. So, let’s denote our elements with the
triples (𝑎
3 + 𝑏
3
, 𝑎, 𝑏). We do not need duplicate values (𝑎
3 + 𝑏
3 = 𝑏
3 + 𝑎
3
) so we can assume
that 𝑎 ≥ 𝑏.
Hint: You can start with the 𝑛 + 1 values, (0
3 + 0
3
, 0,0), (1
3 + 0
3
, 1,0), … , (𝑛
3 + 0
3
, 𝑛, 0). At
any given time if the current smallest element is (𝑖
3 + 𝑗
3
, 𝑖,𝑗) and 𝑗 < 𝑖, then you may print
𝑖
3 + 𝑗
3
, remove it from your data structure and add new element (𝑖
3 + (𝑗 + 1)
3
, 𝑖,𝑗 + 1).
Otherwise, you may just print it, remove it and then find the next smallest element.
Your task is to write a java program, stored in a file named SortedSumsOfCubics.java that
contains a function SortedSumsOfCubics, which takes a nonnegative integer n as its only
argument, and prints out all the integers of the form 𝑎
3 + 𝑏
3
, where 𝑎 and 𝑏 are integers in the
range [0, 𝑛], in sorted order. For example, if the input is 𝑛 = 3, the output should be,
0 1 2 8 9 16 27 28 35 54
The main function in your code should help you test your implementation by getting an integer
from input and sending it to the function above.
2 Evaluation Criteria
The programming assignment will be marked out of 25, based on a combination of automated
testing (various values for n, some very large) and human inspection.
Score (/50) Description
0 – 5 Submission does not compile or does not
conform to the provided description.
5 – 15 The implemented algorithm uses 𝑂(𝑛
2
) space or
is inaccurate. That is, the outputs are not in sorted
order or some are missed.
15 – 20 The implemented algorithm uses 𝑂(𝑛) space and
𝑂(𝑛
3
) or worse running time or minor errors.
20 – 25 The implemented algorithm uses 𝑂(𝑛) space and
𝑂(𝑛
2
log 𝑛) running time and is accurate.
To be properly tested, every submission must compile correctly as submitted. If your
submission does not compile for any reason (even trivial mistakes like typos), or was not
based on the template, it will receive at most 5 out of 25. The best way to make sure your
submission is correct is to download it from conneX after submitting and test it. You are not
permitted to revise your submission after the due date, and late submissions will not be accepted,
so you should ensure that you have submitted the correct version of your code before the due
date. conneX will allow you to change your submission before the due date if you notice a
mistake. After submitting your assignment, conneX will automatically send you a confirmation
email. If you do not receive such an email, your submission was not received. If you have
problems with the submission process, send an email to the instructor before the due date.

1. Consider a version of the deterministic quick-sort algorithm that uses the element at rank ⌊𝑛/2⌋ as
the pivot for a sequence on 𝑛 elements.
(a) What is the running time of this version on a sequence that is already sorted?
(b) Describe the kind of sequence that would cause this version of quick-sort to run in Θ(𝑛
2
)
time.
2. Illustrate the performance of the heap-sort algorithm on the following input sequence, S, by
drawing the heap tree after each insert() and removeMin() call. That is, there should be 20 trees,
each the final result of the given operation after bubbling is complete.
𝑆 = (2, 5, 16, 4, 10, 23, 39, 18, 26, 15)
3. Design algorithms for the following operations for a node v in a binary tree T:
(a) preorderNext(v): return the node visited after v in a preorder traversal of T.
(b) inorderNext(v): return the node visited after v in an inorder traversal of T.
(c) postorderNext(v): return the node visited after v in a postorder traversal of T.
What are the worst-case running times of your algorithms?
4. Define the internal path length, 𝐼(𝑇), of a tree T to be the sum of the depths of all the internal
nodes in T. Likewise, define the external path length, 𝐸(𝑇), of a tree T to be the sum of the
depths of all the external nodes in T. Show that if T is a proper binary tree with n internal nodes,
then 𝐸(𝑇) = 𝐼(𝑇) + 2𝑛.
5. Suppose we are given a sequence S of n elements, each of which is an integer in the range
[0, 𝑛
3 − 1]. Describe a simple method for sorting S in O(n) time.
Hint: Think of an alternate way of representing the elements

CSC 225 ASSIGNMENT 4 – PROGRAMMING and Written

1 Programming Assignment
The 9-puzzle consists of a square grid containing eight tiles, marked with the numbers 1 through 8. One
of the spaces in the grid is empty. The initial state of the puzzle is the configuration below:
1 2 3
4 5 6
7 8
This is considered to be the ‘solved’ state of the puzzle and is normally called the ‘goal state’. The tiles on
the board can be moved horizontally or vertically into the empty space to scramble the ordering of the
board, as in the configuration below:
4 1 3
2 6
7 5 8
The programming assignment is to implement a solver for the 9-puzzle. Your submission will read a
sequence of boards and, for each board, output a sequence of moves which solves the board.
The different configurations of the 9-puzzle and their relationships can be modeled with a graph. Each
vertex corresponds to a possible configuration of the board. Edges represent the transformations possible
by making one (legal) move. That is, if two different board configurations are connected by an edge, there
is a way to obtain one configuration from the other by making a single move. To solve a given board, tiles
are moved until the goal state is reached. The diagram below shows a small snapshot of the graph, with
the goal state framed in green.
The set of moves needed to solve a given board is represented by a path in the graph from the board to the
goal state. Therefore, a board can be solved by performing one of the two fundamental graph traversals–
DFS or BFS–on the graph and searching for a path to the goal state. Some possible board configurations
cannot be solved, such as the following:
1 2 3
4 5 6
8 7
Your task is to write class SolveNinePuzzle. The main method in your code should help you test
your implementation by entering test data or reading it from a file.
2 Input Format
9-puzzle boards are input as 3×3 tables, with the character ‘0’ representing the empty square. For
example, the board
4 1 3
2 6
7 5 8
would be represented by the input sequence
4 1 3
0 2 6
7 5 8
3 Suggested Algorithm
If 𝑣 is the vertex corresponding to the input board and 𝑢 is the vertex corresponding to the goal state, then
𝑣 is solvable if and only if a traversal (DFS or BFS) rooted at 𝑣 encounters 𝑢 (or vice-versa in fact). If 𝑢
is never encountered, then SolveNinePuzzle should return false. If 𝑢 is encountered, then the
traversal tree computed by DFS or BFS can be used to find a path from 𝑣 to 𝑢 in the graph (specifically,
by starting at 𝑢 and tracing upward through the tree until 𝑣 is reached). The implementation should print
every board encountered along this path.
The exact implementation of the SolveNinePuzzle program is up to you. However, the algorithm
outlined below is suggested for simplicity:
• Create the vertex 𝑣 of 𝐺 corresponding to the input board 𝐵.
• Create the vertex 𝑢 of 𝐺 corresponding to the goal state.
• Run DFS or BFS on 𝐺 starting at 𝑣.
• If 𝑢 is encountered by the traversal, print each board on the 𝑣 − 𝑢 path and return true.
• Otherwise, return false.
In practice, puzzles like the 9-puzzle and 16-puzzle are solved with more advanced artificial intelligence
algorithms, which are beyond the scope of this course.
An example pseudocode algorithm for solving this problem using DFS is as follows:
Algorithm ninePuzzleDFS(Board 𝐵, Board 𝐺, HashTable 𝐻, Path 𝑃):
Input: Current board 𝐵 as a 3 × 3 integer array, the goal board 𝐺 as a 3 × 3 integer array, hash table
𝐻 and some data structure holding the path so far, 𝑃.
Output: Boolean true is a path exists, and false if one does not exist.
if 𝐵 = 𝐺 then \\ 𝐺 is the goal board
print 𝑃
return true
if 𝐵 is NOT is 𝐻 then \\Vertex 𝐵 is unexplored
add 𝐵 to 𝐻
for each adjacent board, 𝐵𝑖
\\ 𝑖 = 2, 3 or 4 of them
add 𝐵𝑖
to 𝑃
ninePuzzleDFS(𝐵𝑖
,𝐺,𝐻,𝑃)
remove 𝐵𝑖
from 𝑃
return false
end
Each vertex of the underlying graph corresponds to a possible 9-puzzle board, but it can be helpful to
have vertices represented by strings or integers instead of 3×3 arrays to facilitate indexing into a hash
table. To enable this, you may use the Arrays.deepToString(int[][]) to convert the array into
a string. This will allow you to insert the vertices into the java hashing class HashSet. Note, there is no
need to actually create the graph here. We can perform graph algorithms on the vertices even though we
are storing them in a hash table because we know that every vertex has at most 4 adjacent vertices which
can be determined when needed using the given board. So, you can create an abstract version of the graph
on the fly.
4 Test Datasets
A collection of randomly generated solvable and unsolvable boards has been uploaded to conneX. Your
assignment will be tested on boards similar but not identical to the uploaded boards. You may want to
create your own collection of test boards.
5 Sample Run
The output of a model solution on the board specified above is given in the listing below. Note that there
may be multiple move sequences that solve a given board. Console input is shown in blue.
Reading board 1
4 1 3
0 2 6
7 5 8
Attempting to solve board 1…
4 1 3
0 2 6
7 5 8
0 1 3
4 2 6
7 5 8
1 0 3
4 2 6
7 5 8
1 2 3
4 0 6
7 5 8
1 2 3
4 5 6
7 0 8
1 2 3
4 5 6
7 8 0
Board 1: Solvable.
Processed 1 board.
Average Time (seconds): 0.00
6 Evaluation Criteria
The programming assignment will be marked out of 25, based on a combination of automated testing and
human inspection. The running time of the implemented algorithm should be at most 𝑂(𝑛
2
), where 𝑛 is
the number of vertices in the constructed graph 𝐺. To receive full marks, the implementation should solve
each board with the smallest number of moves possible. This can be achieved by using BFS instead of
DFS.
Score (/25) Description
0 – 5 Submission does not compile or does not
conform to the provided description.
5 – 15 The implemented algorithm is not 𝑂(𝑛
2
) or is
substantially inaccurate on the tested inputs.
15 – 20 The implemented algorithm is 𝑂(𝑛
2
) and
accurate on all the tested inputs.
20 – 25 The implemented algorithm is 𝑂(𝑛
2
), accurate
on all the tested inputs, and the sequence of
moves for each tested board is the shortest
possible length.
To be properly tested, every submission must compile correctly as submitted. If your submission does
not compile for any reason (even trivial mistakes like typos), it will receive at most 5 out of 25. The
best way to make sure your submission is correct is to download it from conneX after submitting and test
it. You are not permitted to revise your submission after the due date, and late submissions will not be
accepted, so you should ensure that you have submitted the correct version of your code before the due
date. conneX will allow you to change your submission before the due date if you notice a mistake. After
submitting your assignment, conneX will automatically send you a confirmation email. If you do not
receive such an email, your submission was not received. If you have problems with the submission
process, send an email to the instructor before the due date.

1. Let 𝐺 be the undirected graph with vertices 𝑉 = {0,1,2,3,4,5,6,7,8} and edges
𝐸 = {{0,4},{1,4},{1,5},{2,3},{2,5},{3,5},{4,5},{4,6},{4,8},{5,6},{5,7},{6,7},{6,8},{7,8}}
(a) Draw 𝐺 in such a way that no two edges cross (i.e. it is a planar graph.)
(b) Draw adjacency list representation of 𝐺.
(c) Draw adjacency matrix representation of 𝐺.
2. For the graph 𝐺 in Problem 1 assume that, in a traversal of 𝐺, the adjacent vertices of a given
vertex are returned in their numeric order.
(a) Order the vertices as they are visited in a DFS traversal starting at vertex 0.
(b) Order the vertices as they are visited in a BFS traversal starting at vertex 0.
3. Let 𝐹 = (𝑉, 𝐸) be a forest with 𝑛 vertices, 𝑚 edges and 𝑘 connected components. Prove that the
number of edges in 𝐹 is 𝑚 = 𝑛 − 𝑘.
4. Design an algorithm (in pseudocode) to determine whether a digraph has a unique topological
ordering. Your algorithm should return the ordering if a unique one exists or indicate that no
unique order exists.
5. A 2-colouring of an undirected graph with n vertices and m edges is the assignment of one of two
colours (say, black or white) to each vertex of the graph, so that no two adjacent nodes have the
same colour. So, if there is an edge (u,v) in the graph, either node u is black and v is white or vice
versa. Give an O(n + m) time algorithm (pseudocode!) to 2-colour a graph or determine that no
such colouring exists, and justify the running time. The following shows examples of graphs that
are and are not 2-colourable:
2-colourable Not 2-colourable