How to use this book |
|
v | |
Acknowledgements |
|
viii | |
Introduction |
|
1 | (2) |
|
|
3 | (10) |
|
1A Proof by contradiction |
|
|
4 | (2) |
|
|
6 | (3) |
|
|
9 | (4) |
|
2 Divisibility and prime numbers |
|
|
13 | (20) |
|
2A Factors, multiples and remainders |
|
|
13 | (6) |
|
2B Greatest common divisor and least common multiple |
|
|
19 | (4) |
|
2C The Euclidean algorithm |
|
|
23 | (3) |
|
|
26 | (7) |
|
3 Representation of integers in different bases |
|
|
33 | (9) |
|
3A How many fingers do we need to count? |
|
|
33 | (2) |
|
3B Changing between different bases |
|
|
35 | (1) |
|
3C Arithmetic in different bases |
|
|
36 | (6) |
|
4 Linear Diophantine equations |
|
|
42 | (9) |
|
4A Examples of equations with integer solutions |
|
|
42 | (2) |
|
4B How many solutions are there? |
|
|
44 | (2) |
|
4C Finding the general solution |
|
|
46 | (1) |
|
4D Solutions subject to constraints |
|
|
47 | (4) |
|
|
51 | (16) |
|
5A Introduction: working with remainders |
|
|
51 | (2) |
|
5B Rules of modular arithmetic |
|
|
53 | (3) |
|
5C Division and linear congruences |
|
|
56 | (3) |
|
5D Chinese remainder theorem |
|
|
59 | (3) |
|
5E Fermat's little theorem |
|
|
62 | (5) |
|
|
67 | (31) |
|
6A Introduction to graphs |
|
|
67 | (2) |
|
|
69 | (10) |
|
6C Some important theorems |
|
|
79 | (6) |
|
6D Subgraphs and complements |
|
|
85 | (2) |
|
|
87 | (2) |
|
|
89 | (4) |
|
|
93 | (5) |
|
|
98 | (36) |
|
|
98 | (4) |
|
7B Minimum spanning tree: Kruskal's algorithm |
|
|
102 | (4) |
|
7C Finding the shortest path: Dijkstra's algorithm |
|
|
106 | (6) |
|
7D Travelling along all the edges: Chinese postman problem |
|
|
112 | (6) |
|
7E Visiting all the vertices: Travelling salesman problem |
|
|
118 | (16) |
|
|
134 | (15) |
|
8A Defining sequences recursively |
|
|
134 | (2) |
|
8B First order linear recurrence relations |
|
|
136 | (3) |
|
8C Second order recurrence relations |
|
|
139 | (4) |
|
8D Modelling using recurrence relations |
|
|
143 | (6) |
|
9 Summary and mixed examination practice |
|
|
149 | (9) |
Answers |
|
158 | (14) |
Glossary |
|
172 | (5) |
Index |
|
177 | |