| |
Description: Essentials of Discrete Mathematics is the ideal text for a one-term discrete mathematics course to serve computer science majors as well as students from a wide range of other disciplines. The material is organized around five types of mathematical thinking: logical, relational, recursive, quantitative, and analytical. This presentation results in a coherent outline that steadily builds upon mathematical sophistication. Graphs are introduced early and are referred to throughout the text, providing a richer context for examples and applications. Students will encounter algorithms near the end of the text, after they have acquired enough skills and experience to analyze them properly. The final chapter contains in-depth case studies from a variety of fields, including biology, sociology, linguistics, economics, and music. Clear and concise, Essentials of Discrete Mathematics presents a unified and complete picture of discrete mathematics that instructors can move through in a single semester.
Key features:
· One-term focus.
· Early introduction to graph theory.
· A range of exercises designed to help students think mathematically.
· Careful attention to mathematical logic and proof techniques.
· Coverage of algorithms appropriate for computer science majors, as well as students with no previous programming experience.
· A wealth of applications, including many applications from areas beyond mathematics and computer science. A course taught out of this book can serve several purposes: an introductory course for computer science majors, a course where mathematics majors learn the basics of proof techniques, or a course where students from other disciplines get a serious introduction to modern mathematics.
Contents: Chapter 1: Logical Thinking • Formal logic • Connectives and propositions • Truth tables • Logical equivalences • Exercises • Propositional logic • Tautologies and contradictions • Derivation rules • Proof sequences • Forward- backward • Exercises • Predicate logic • Predicates • Quantifiers • Translation • Negation • Two common constructions • Exercises • Logic in mathematics • The role of definitions in mathematics • Other types of mathematical statements • Counter examples • Axiomatic systems • Exercises • Methods of proof • Direct proofs • Proof by contraposition • Proof by contradictionChapter 2: Relational Thinking • Graphs • Edges and Vertices • Terminology • Modeling relationships with graphs • Exercises • Sets • Membership and containment • New sets from old • Identities • Exercises • Functions • Definition and examples • One-to-one and onto functions • New functions from old • Exercises • Relations and equivalences • Definitions and examples • Graphs of relations • Relations vs. Functions • Equivalence relations • Modular arithmetic • Exercises • Partial orderings • Definition and examples • Hasse diagrams • Topological sorting • Isomorphisms • Boolean Algebras • Exercises •Graph Theory • Graphs: Formal definitions • Isomorphisms of graphs • Degree counting • Euler paths and circuits • Hamilton paths and circuits • Trees • Exercises
Chapter 3: Recursive thinking • Recurrence relations • Definitions and examples • The Fibonacci sequence • Modeling with recurrence relations • Exercises • Closed-form solutions and induction • Guessing a closed-form solution • Polynomial sequences: Using differences • Inductively verifying a solution • Exercises • Recursive definitions • Definition and examples • Writing recursive definitions • Recursive geometry • Recursive jokes • Exercises • Proof by induction • The principle of induction • Examples • Strong induction • Structural induction • Exercises • Recursive data structures • Lists • Efficiency • Binary search trees revisited • Exercises
Chapter 4: Quantitative thinking • Basic counting techniques • Addition • Multiplication • Mixing addition and multiplication • Exercises • Selections and arrangements • Permutations: The arrangement principle • Combinations: The selection principle • The binomial theorem • Exercises • Counting with functions • One-to-one correspondence • The pigeonhole principle • The generalised pigeonhole principle • Ramsey theory • Exercises • Discrete probability • Definitions and examples • Applications • Expected value • Exercises • Counting Operations in Algorithms • Algorithms • Pseudocode • Sequences of operations • Loops • Arrays • Sorting • Exercises • Estimations • Growth of functions • Estimation targets • Properties of Big • Exercises
Chapter 5: Analytical thinking • Algorithms • More pseudocode • Preconditions and postconditions • Iterative algorithms • Functions and recursive algorithms • Exercises • Three common types of algorithms • Traversal algorithms • Greedy algorithms • Divide- and-Conquer Algorithms • Exercises • Algorithm complexity • The good, the bad and the average • Approximate complexity calculations • Exercises • Bounds of complexity • Algorithms as decisions • A lower bound • Searching an array • Sorting • P vs. NP • Exercises • Program verification • Verification vs. testing • Verifying recursive algorithms • Searching and sorting • Towers of Hanoi • Exercises • Loop invariants • Verifying iterative algorithms • Searching and sorting • Using invariants to design algorithms • ExercisesISBN - 9789380108209
|
| |
Pages : 468
|