Reading List

Recommended books

You should get a textbook to support your studies of the module. Two books are suggested. They are very different in style, so it is worth having a look at both books in the library. You should only have to buy one of them. Neither book is perfect, and some material will only be covered by videos and hand-out material.

Discrete Mathematics and Its Applications (by Kenneth H. Rosen)

This is a much used book, including similar modules for computing students at NTNU, HiOA, and UiB. It is very comprehensive, covering topics such as algebra, number theory, and algorithms. Some will find it too comprehensive and verbose. For instance, it defines many abstract and rarely-used structures (e.g. semi-groups) on the way to the more common ones. Interested and motivated students will find it an interesting read, but some will find it hard to filter out the essentials.

Discrete Mathematics for Computer Scientists (by Stein, Drysdale, and Bogart)

This book takes an unusual paedagogical angle in starting with examples from computing, and exploring the mathematical theory in order to solve problems in the examples. Contrary to most books which aims at a first-year module, it aims at students who have already completed some computing modules. This is a promising approach, but some will say that some of the theory and formalism is treated too lightly.

The most serious objection to this book is that the chapter on cryptography is misleading. It gives the impression that only public key cryptography can be secure. A little more detail must be added to avoid misunderstanding.

The book is tailored to computer science rather than computer engineering. It seems to assume that the student has already encountered the basics of algorithmic theory, and for an engineering degree I would like to add material on coding theory and symmetric cryptography.

The teaching most closely follows Stein et al's book, and thus this may be easier to read. However, Rosen will give you a distinctly different angle, and thus be more illuminating. The second half of the module will contain a lot of material covered by neither book, and some additional hand-outs will be provided.

Other documents

• The AES Standard. This is normally available from NIST but their web site is down due to failure to get a federal budget in the USA.
• The slightly more detailed AES proposal which subsequently became the AES standard.
• Matimatiske symbol frå Wikipedia (recommended by students)

References

The following is a list of books that I have consulted and/or considered in the preparation of a discrete maths module, with a short review and my opinions about their suitability. Each of the books has its own merits and may provide useful background reading, possibly with a different angle.

Discrete Mathematics - Mathematical Reasoning and Proof with Puzzles, Patterns, and Games (by Douglas E. Ensley and J. Winston Crawley)

This book draws its examples and motivation from puzzles and games of all sorts, and covers fundamental topics with well-known examples. It misses topics like number theory, algebra, and cryptography, but does cover most other standard topics.

Discrete Mathematics for Computing (by Rod Haggarty) 2002

This i short and concise book covering logic, set theory, functions and relations, combinatorics, and graph theory. It lacks computing topics like number theory (cryptography), algebra, and algorithmic complexity.

Essentials of Discrete Mathematics (by David J Hunter) 2012

This looks like a very interesting and well-structured book for computer science. It is structured around a number of approaches to reasoning: logical thinking, relational thinking, recursive thinking and quantitative thinking are largely independent approaches. Analytical thinking considers algorithms, building on the four first approaches. «Thinking through applications» goes closer into real-world applications.

The book mentions modular arithmetrics only briefly, and does not discuss discrete algebra and topics relating to coding and cryptography.

A Concrete Introduction to Higher Algebra (by Lindsay Childs)

This is a very good book, for mathematicians. It is less suitable for computer engineers. Most of the material is approached in abstract terms. It also does not cover algorithms and complexity, nor graph theory, but discrete algebra and reasoning (proof and induction) is covered very thoroughly and formally. It also includes coding and cryptography as case studies, but the cases come after the heavy theory.

A Beginner's Guide to Discrete Mathematics (by W.D.Wallis)

Formal and concise, this book is similar to Childs in style, but it has its focus on combinatorics and logic, rather than algebra. Thus it is a better fit with the syllabus of the module. It is a good choice for students who seek a formal and concise angle to tie up loose ends.

Mathematics of Discrete Structures for Computer Science (by Gordon J. Pace)

The title's address of `Computer Science' should not in any way be confused with any practical or applied area of computing. The focus of the book is on set theory, relations, and logic, as commonly taught as part of a theoretical computer science curriculum. The chapter on `reasoning about programs' is a particularly interesting touch, covering abstract analysis of computer programs in much more depth than the other texts.

It feels like a more advanced and abstract text than the above two. Much as I would love to read it myself, I would not recommend it for a course of computer engineering.

Advanced textbooks

Mathematics of Public Key Cryptography (by Steven Galbraith)

Specialising on the Mathematics required for Asymmetric Cryptography, this book is able to dig deep. It is suitable for advanced modules in specialised `maths and computing' degrees.