# CS代考 The exercises – cscodehelp代写

The exercises
School of Computing and Information Systems COMP90038 Algorithms and Complexity
7. One way of representing an undirected graph G is using an adjacency matrix. This is an n × n matrix, where n is the number of nodes in G. In this matrix, we label the rows and the columns with the names of G’s nodes. For a pair (x, y) of nodes, the matrix has a 1 in the (x,y) entry if G has an edge connecting x and y; otherwise the entry has a 0. (As the graph is undirected, this is somewhat redundant: (x, y) and (y, x) will always be identical.) A complete graphs is one in which x and y are connected, for all x, y with x ̸= y. We don’t exclude the possibility of a loop, that is, an edge connecting a node to itself, although loops are rare.
How can you tell from its matrix whether an undirected graph
(a) is complete? (b) has a loop?
(c) has an isolated node?
(a) All elements (except those on the main diagonal) are 1. (b) Some element on the main diagonal is 1.
(c) Some row (and hence some column) has all zeros.
8. Design an algorithm to check whether two given words are anagrams, that is, whether one can be obtained from the other by permuting its letters. For example, garner and ranger are anagrams.
Answer: Note that we cannot just say “for each letter in the first word, check that it occurs in the second, and vice versa.” (Why not?)
A nice solution sorts the letters in each word and simply compares the two results. This solution scales well, that is, has good performance even as the words involved grow longer.
9. Hereweconsiderafunctionfirst_occ,suchthatfirst_occ(d,s)returnsthefirstposition (in string s) which holds any symbol from the collection d (and returns -1 if there is no such position). For simplicity let us assume both arguments are given as strings. For example, first_occ(”aeiou”, s) means “find the first vowel in s.” For s = ”zzzzzzzzzzzz” this should return -1, and for s = ”Phlogiston”, it should return 3 (assuming we count from 0).
Assuming strings are held in arrays, design an algorithm for this and find its complexity as a function of the lengths of d and s.
Suppose we know that the set of possible symbols that may be used in d has cardinality 256. Can you find a way of utilising this to speed up your algorithm? Hint: Find a way that requires only one scan through d and only one through s.

Answer: Let m be the length of d and let n be the length of s. The obvious algorithm is to scan through s and, for each symbol x met, go through d to see if that was a symbol we were looking for. In the worst case, when no symbols from d are in s, this means making mn comparisons. (We could also structure the search the other way round: for each element of d, find its first occurrence, and then, based on that, decide which occurrence was the earliest of them all; this also leads to mn comparisons in the worst case.)
Knowing that there are 256 possible symbols that may be used in d allows us to introduce an array first, indexed by the symbols. (If we are talking ASCII characters then, conve- niently, the indices run from 0 to 255.) Initialise this array so all its elements are, say, -1. Now scan through s. For each symbol x in s, if first[x] is -1, replace it with x’s position. Note that we have not considered d at all so far; we have only recorded, in first, where the first occurrence of each symbol is (and left the value as -1 for each symbol that isn’t in s).
Now all we need is a single scan through d, to find the value of first[x] for each symbol x in d. As we find these, we keep the smallest such value. It this value is -1, none of the symbols from d was found in s. Otherwise the value is the first occurrence of a symbol from d.
The complexity in this case is n + m. For most reasonable values of m and n, this is smaller than mn, so we have a better algorithm, even taking the overhead of maintaining first into account. Essentially we have traded in some space (the array first) to gain some time. This kind of time/space trade-off is a familiar theme in algorithm design.
10. Gaussian elimination, the classical algorithm for solving systems of n linear equations in n unknowns, requires about 31 n3 multiplications, which is the algorithm’s basic operation.
(a) How much longer should we expect Gaussian elimination to spend on 1000 equations, compared with 500 equations?
(b) You plan to buy a computer that is 1000 times faster than what you currently have. By what factor will the new computer increase the size of systems solvable in the same amount of time as on the old computer?
(a) The answer is: 8 times longer, and it does not depend on the particular numbers of equations given in the question. We need 13(2n)3 operations for 2n equations and
13 13(2n)3 8n3
3n operationsforn. Theratiois 13n3 = n3 =8.
(b) If the new machine needs tnew units of time for a job, the old one needs told = 1000 tnew units. Let m be the number of equations handled by the new machine in the time the old machine handles n. The new machine handles m in time 31 m3 and n in time 13n3. So we have
Solving for m we get
So we can now solve systems that are 10 times larger.
13m3 = 1000 · 13n3 m = √3 1000 n3 = 10n