|
Chapter 1 Making sense of numbers |
|
|
2 | (38) |
|
Introduction A brief journey through different number systems |
|
|
3 | (1) |
|
1.1 Number systems and bases |
|
|
4 | (9) |
|
1.2 Integers, prime numbers, factors and divisors |
|
|
13 | (17) |
|
|
|
20 | (1) |
|
Linear Diophantine equations |
|
|
21 | (5) |
|
|
|
26 | (4) |
|
1.3 Strong mathematical induction |
|
|
30 | (3) |
|
1.4 The Fundamental Theorem of Arithmetic and least common multiples |
|
|
33 | (7) |
|
|
|
37 | (3) |
|
Chapter 2 Modular arithmetic and its applications |
|
|
40 | (36) |
|
Introduction From Gauss to cryptography |
|
|
41 | (1) |
|
|
|
42 | (6) |
|
2.2 Modular inverses and linear congruences |
|
|
48 | (5) |
|
2.3 The Pigeonhole Principle |
|
|
53 | (4) |
|
2.4 The Chinese Remainder Theorem or systems of linear congruences |
|
|
57 | (7) |
|
2.5 Using cycles for powers modulo n and Fermat's Little Theorem |
|
|
64 | (12) |
|
|
|
72 | (4) |
|
Chapter 3 Recursive patterns |
|
|
76 | (26) |
|
Introduction Modelling and solving problems using sequences |
|
|
77 | (1) |
|
|
|
78 | (5) |
|
3.2 Solution of first-degree linear recurrence relations and applications to counting problems |
|
|
83 | (6) |
|
3.3 Modelling with first-degree recurrence relations |
|
|
89 | (5) |
|
|
|
89 | (1) |
|
|
|
90 | (1) |
|
Investments and compound interest |
|
|
91 | (1) |
|
Games and probability problems |
|
|
92 | (2) |
|
3.4 Second-degree linear homogeneous recurrence relations with constant coefficients |
|
|
94 | (8) |
|
|
|
99 | (3) |
|
Chapter 4 From folk puzzles to a new branch of mathematics |
|
|
102 | (38) |
|
Introduction Introduction to graph theory |
|
|
103 | (1) |
|
4.1 Terminology and classification of graphs |
|
|
104 | (4) |
|
What is a graph and what are its elements? |
|
|
104 | (4) |
|
4.2 Classification of graphs |
|
|
108 | (7) |
|
|
|
108 | (1) |
|
|
|
109 | (1) |
|
|
|
109 | (1) |
|
|
|
110 | (1) |
|
|
|
111 | (1) |
|
|
|
112 | (1) |
|
|
|
113 | (2) |
|
4.3 Different representations of the same graph |
|
|
115 | (3) |
|
|
|
118 | (8) |
|
|
|
119 | (1) |
|
|
|
119 | (1) |
|
Euler relation for planar graphs |
|
|
120 | (4) |
|
Real life application -- The soccer ball |
|
|
124 | (2) |
|
|
|
126 | (3) |
|
4.6 Eulerian circuits and trails |
|
|
129 | (11) |
|
|
|
133 | (7) |
|
Chapter 5 Applications of Graph Theory |
|
|
140 | (25) |
|
Introduction Further algorithms and methods |
|
|
141 | (1) |
|
5.1 Graph algorithms: Kruskal's and Dijkstra's |
|
|
142 | (7) |
|
Minimum Connector Problems |
|
|
142 | (4) |
|
|
|
146 | (1) |
|
|
|
147 | (1) |
|
Limitation of Dijkstra's Algorithm |
|
|
148 | (1) |
|
5.2 Chinese postman problem |
|
|
149 | (4) |
|
Chinese Postman algorithm |
|
|
151 | (2) |
|
5.3 Travelling Salesman Problem |
|
|
153 | (12) |
|
The Nearest Neighbour Algorithm for upper bound |
|
|
154 | (1) |
|
Deleted vertex algorithm for lower bound |
|
|
155 | (5) |
|
|
|
160 | (5) |
| Answers |
|
165 | (12) |
| Index |
|
177 | |
