Which topic in Discrete Mathematics is considered as a prerequisite for data structures course?

I want to read a book on data structures and algorithms, but I would like to开发者_JAVA百科 know if there is any specific topic in discrete mathematics considered very important as a prerequisite to understanding the materials presented in data structure book.

P.S I am self-taught programmer; I didn't take any computer science courses.

---

"Discrete math" is more a buzzword that contains the basics from a dozen different topics (logic, algorithms, theory of computation, number theory, digital design, etc.) all marginally related to programming. Reading a discrete mathematics book would be about the same as reading the first chapter or two of books on all these topics.

The most essential thing to understand is boolean logic, which you're probably already pretty good at if you're self-taught; algorithms are also very important. The theory of computation stuff is fairly interesting, but not really useful unless you're really into algorithms, or want to write your own parser. Number theory is good to learn if you want to get into cryptography.

You don't really need to know any of these things to read about data structures.

---

Mathematical induction is probably the single most important concept nobody has mentioned yet. It is essential for understanding and proving the properties of algorithms on trees and other inductively defined data structures.

BTW, the classic textbook on this topic is Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik.

But life is too short to read a textbook just so you can read a textbook. Dive in. If you find yourself lost, go find the background you need.

---

Some topics usually found in introductory discrete math books that come in handy in an algorithms/data structure course are:

1. Some basic probability/statistics: Useful in understanding hashing and randomized algorithms
2. Most discrete math books have a chapter on graphs and related concepts, things like topological sorting, relations, partial and total orders.
3. Set theory and formal logic: Essential tools in reasoning about the correctness and complexity of algorithms.

There are probably a few others that escape me at this moment. It's been a while since I left college.

Having said this, a good data-structure/algorithm book often has one or two introductory chapters and sections in most other chapters that are aimed at bringing the reader up to speed on some of the relevant discrete math topics. But IMO, it is better to know this stuff just to have a more thorough understanding, if you have the time and inclination. Otherwise, I don't think you will find yourself stuck if you have a good book.

PS: The topics I mention are from these two books: "Discrete and Combinatorial Mathematics: An Applied Introduction" by Grimaldi "Discrete Mathematics and its Applications" by Rosen ("Concrete Math" is way too heavy to read just for data structures)

---

Go ahead and read the data structures book, you'll be fine.

---

For data structures and algorithms I think you will mostly want to know the area of Calculus related to the computing of series limits. This, in turn, involves some knowledge of Algebra.

You need to know how to compute series limits in order to be able to compute algorithm complexity.

---

if you are interested not only in data structure but in all computer science fields, discrete math include Boolean algebra and it's application that is the basis of computer architecture and assembly language, but i don't think it's related to data structures and algorithms