Plan
School of Computing and Information Systems COMP90038 Algorithms and Complexity Tutorial Week 3
6–10 August 2018
Last week’s lecture discussed asymptotics and the mathematical analysis of algorithms; this week’s lectures will be about brute force methods and recursion.
This week’s questions 12–14 are combinatorics-style puzzles. Good problem-solving fun, but not essential.
The exercises
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?
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.
9. Here we consider a function first_occ, such that first_occ(d, s) returns the first position (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.
10. Gaussian elimination, the classical algorithm for solving systems of n linear equations in n unknowns, requires about 1n3 multiplications, which is the algorithm’s basic operation.
3
(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?
11. For each of the following pairs of functions, indicate whether the components have the same order of growth, and if not, which grows faster.
(a) n(n + 1) and 2000n2 (c) log2 n and lnn
(e) 2n−1 and 2n
(b) 100n2 and 0.01n3 (d) log2 n and log2 n2 (f) (n−1)! and n!
Here ! is the factorial function, and log2 n is the way we usually write (log2 n)2.
12. Eight balls of equal size are on the table. Seven of them weigh the same, but one is slightly heavier. You have a balance scale that can compare weights. How can you find the heavier ball using only two weighings?
13. There are 18 gloves in a drawer: 4 pairs of red gloves, 3 pairs of yellow, and 2 pairs of green. You select gloves in the dark, which means you cannot assess colour nor left/right-handedness. You can check the gloves only after the selection has been made. What is the smallest number of gloves you need to pick to have at least one matching pair in the best case? In the worst case?
14. After washing 5 distinct pairs of socks, you discover that two socks are missing. Hence you are left with 4 complete pairs in the best case, and 3 in the worst case. What is the probability of the best case scenario?