nach oben

2018 | Buch

Kapitel lesen Erstes Kapitel lesen

Fundamentals of Discrete Math for Computer Science

A Problem-Solving Primer

verfasst von: Prof. Tom Jenkyns, Dr. Ben Stephenson

Verlag: Springer International Publishing

Buchreihe : Undergraduate Topics in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This clearly written textbook presents an accessible introduction to discrete mathematics for computer science students, offering the reader an enjoyable and stimulating path to improve their programming competence. The text empowers students to think critically, to be effective problem solvers, to integrate theory and practice, and to recognize the importance of abstraction. Its motivational and interactive style provokes a conversation with the reader through a questioning commentary, and supplies detailed walkthroughs of several algorithms.

This updated and enhanced new edition also includes new material on directed graphs, and on drawing and coloring graphs, in addition to more than 100 new exercises (with solutions to selected exercises).

Topics and features: assumes no prior mathematical knowledge, and discusses concepts in programming as and when they are needed; designed for both classroom use and self-study, presenting modular and self-contained chapters that follow ACM curriculum recommendations; describes mathematical processes in an algorithmic manner, often supported by a walkthrough demonstrating how the algorithm performs the desired task; includes an extensive set of exercises throughout the text, together with numerous examples, and shaded boxes highlighting key concepts; selects examples that demonstrate a practical use for the concept in question.

Students embarking on the start of their studies of computer science will find this book to be an easy-to-understand and fun-to-read primer, ideal for use in a mathematics course taken concurrently with their first programming course.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Algorithms, Numbers, and Machines

Abstract

This chapter begins with a strange algorithm, Russian Peasant Multiplication, that may or may not work correctly. (Verifying correctness is a constant theme throughout this book, and the techniques used to decide such issues are explained thoroughly later.)

The concept of an algorithm is illustrated by more examples: testing primes, factoring an integer into primes, and finding the greatest common divisor of two integers. Representation of numbers in computers is discussed, and truncation error is shown to be an unavoidable consequence of using machines to do computation.

This chapter ends with an algorithm to solve equations, that is, to find a numerical solution that is accurate to any degree one might desire. This illustrates the formal idea of the limit of a sequence in the context of how many iterations must be done by the algorithm to guarantee a specified accuracy.

Tom Jenkyns, Ben Stephenson

Chapter 2. Sets, Sequences, and Counting

Abstract

Sets and sequences are the fundamental objects of study in discrete mathematics, and this chapter provides a review of naïve set theory. Formulas for counting sequences, subsets, and permutations are developed, followed by an algorithmic method for counting when no formula applies (or is obvious). The final section looks at infinite sequences, particularly complexity functions of algorithms.

Tom Jenkyns, Ben Stephenson

Chapter 3. Boolean Expressions, Logic, and Proof

Abstract

The objective of this chapter is to explain the structure of mathematical proofs, especially proofs of correctness of algorithms. Boolean operators are defined by their truth tables. The definition of a valid argument form is intuitive and easily confirmed using a truth table. These are followed by many examples of standard and common patterns of proof: direct and indirect arguments, mathematical induction, and strong mathematical induction.

Tom Jenkyns, Ben Stephenson

Chapter 4. Searching and Sorting

Abstract

This chapter explores two very practical problems: searching and sorting. We consider Linear Search and (two versions of) Binary Search. Binary trees are used to describe the search process. Binary search is much, much better but requires sorted input. We give examples of several sorting strategies: selection sorts, exchange sorts, and partition sorts. A binary tree produces a lower bound on the number of key comparisons that must be done in a worst case and in the average case.

This chapter ends with timing comparisons and a relation between the time and number of key comparisons that anticipates the notion of order of complexity.

Tom Jenkyns, Ben Stephenson

Chapter 5. Graphs and Trees

Abstract

This chapter introduces graphs as diagrams for solving puzzles. Careful definitions specify the language of graph theory: vertices, edges, degrees, paths, circuits, Euler paths, Hamilton paths, and so on. Then our interest returns to trees, with algorithms for depth-first traversal and for breadth-first traversal.

Algorithms for constructing a minimum connector and finding shortest paths joining two specified vertices are given for edge-weighted graphs. Finally, for directed graphs, we give Dijkstra’s Algorithm for shortest dipaths and the Floyd-Warshall Algorithm for the distance matrix.

Tom Jenkyns, Ben Stephenson

Chapter 6. Directed Graphs

Abstract

This chapter gives a number of algorithms that apply to directed graphs, though many ideas and algorithms for undirected graphs apply to digraphs (and vice versa). The first is an algorithm to orient the edges of an undirected graph to produce a strongly-connected digraph. Then we consider acyclic digraphs, showing how they may be “topologically sorted”, and how to use Dynamic Programming to count the number of dipaths from a to b, and find a shortest or a longest dipath from a to b. Dijkstra’s Algorithm grows a tree of shortest dipaths from a “single source”, and the Floyd-Warshall Algorithm solves the “all-pairs” shortest dipath problem. Next we consider commodity Flow Networks. The Max-flow/Min-cut Theorem is proved by the action of the Ford-Fulkerson algorithm which finds a feasible flow, and gives it a “certificate of optimality” by producing a cut whose capacity equals the value of that flow. The final section shows that matching problems in bipartite graphs can be converted to flow problems and proves several classic results, including Hall’s Marriage Theorem.

Tom Jenkyns, Ben Stephenson

Chapter 7. Relations: Especially on (Integer) Sequences

Abstract

The two objectives of this chapter are (1) to provide an ordering of sequences of objects so they can be sorted, like individual numbers, and so any finite set of them can be generated in a natural order from the first to the last, and (2) to provide a mechanism for classifying complexity functions by their rates of growth.

Relations in general are defined, then equivalence relations, then order relations.

Relations on sequences of numbers are given, in particular Lexicographic-Order. Relations on infinite sequences of real numbers (including complexity functions of algorithms) are then covered with Big-Oh, Big-Theta, and Little-Oh notation.

Tom Jenkyns, Ben Stephenson

Chapter 8. Sequences and Series

Abstract

Examples of sequences defined by recurrence equations are given and solved. Then, we provide the general method for solving all first-order recurrence equations. The Fibonacci sequence is explored in some depth, followed by the general method for solving second-order recurrence equations. This chapter ends with Zeno’s paradoxes and the formal definition of convergence of infinite series.

Tom Jenkyns, Ben Stephenson

Chapter 9. Generating Sequences and Subsets

Abstract

Algorithms are devised to generate lists of objects in Lexicographic-Order: k-sequences on {1..n}, all nonempty subsets of {1..n}, k-subsets of {1..n}, full permutations, and k-permutations on {1..n}. We include calculations of average-case complexity because in each case the average cost is less than 2 or 3 operations no matter how big k and n are.

Tom Jenkyns, Ben Stephenson

Chapter 10. Discrete Probability and Average-Case Complexity

Abstract

Discrete probability is introduced as a method to estimate average cases, not to predict individual outcomes from a process subject to chance or unpredictability, like flipping a coin or rolling a die.

Basic definitions are given for the fundamental concepts: an experiment, a sample space, a probability function, events, independent events, conditional probability, random variables, and the expected value of a random variable. Expected value generalizes average value and is used for calculating the average-case complexity of algorithms.

Standard distributions, which are good models of many real-world processes including computer applications, are treated in some detail. These include the uniform distribution, the binomial distribution, and the geometric distribution.

This chapter ends with a proof that the average-case complexity of QuickSort is O(nlgn).

Tom Jenkyns, Ben Stephenson

Chapter 10. Turing Machines

Abstract

This final chapter returns to the topic of the first chapter: What is an algorithm?

We give Alan Turing’s answer to that question and end our story with a disappointing result: namely, that we can prove that there is no algorithm that can solve the halting problem. But this result assures us that machines cannot replace human minds with their creativity and ingenuity.

Tom Jenkyns, Ben Stephenson

Backmatter

Titel: Fundamentals of Discrete Math for Computer Science
verfasst von: Prof. Tom Jenkyns
Dr. Ben Stephenson
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-70151-6
Print ISBN: 978-3-319-70150-9
DOI: https://doi.org/10.1007/978-3-319-70151-6