Web Page for the Book: Discrete Structures with Contemporary Applications by Alexander Stanoyevitch Chapman & Hall/CRC Press (January 2011) |

PrefaceAbout the AuthorDependency ChartChapter 1: Logic and SetsSection 1.1: Logical Operators Section 1.2: Logical Quantifiers Section 1.3: Sets Chapter 2: Relations and Functions, Boolean Algebra, and Circuit Design Section 2.1: Relations and Functions Section 2.2: Equivalence Relations and Partial Orderings Section 2.3: Boolean Algebra and Circuit Design Chapter 3: The Integers, Induction, and RecursionSection 3.1: Mathematical Induction Section 3.2: Recursion Appendix: Recursive Definitions and Structural Induction Section 3.3: Some Topics in Elementary Number Theory Appendix: Probabilistic Primality Tests Chapter 4: Number SystemsSection 4.1: Representations of Integers in Different Bases Section 4.2: Modular Arithmetic and Congruences Section 4.3: Matrices Section 4.4: Floating Point Arithmetic Section 4.5: Public Key Cryptography Chapter 5: Counting Techniques, Combinatorics, and Generating Functions Section 5.1: Fundamental Principles of Counting Section 5.2: Permutations, Combinations, and the Binomial Theorem Section 5.3: Generating Functions Appendix: Application to Weighted Democracies |
Chapter 6: Discrete Probability and SimulationSection 6.1: Introduction to Discrete Probability Section 6.2: Random Numbers, Random Variables, and Basic Simulations Chapter 7: Complexity of AlgorithmsSection 7.1: Some Algorithms for Searching and Sorting Section 7.2: Growth Rates of Functions and the Complexity of Algorithms Chapter 8: Graphs, Trees, and Associated AlgorithmsSection 8.1: Graph Concepts and Properties Section 8.2: Paths Connectedness, and Distances in Graphs Section 8.3: Trees Appendix: Application of Rooted Trees to Data Compression and Coding; Huffman Codes Chapter 9: Graph Traversal and Optimization ProblemsSection 9.1: Graph Traversal Problems Section 9.2: Tree Growing and Graph Optimization Algorithms Section 9.3: Network Flows Chapter 10: Randomized Search and Optimization AlgorithmsSection 10.1: Randomized Search and Optimization: An Overview Section 10.2: Genetic Algorithms Appendix A: Pseudo Code DictionaryAppendix B: Solutions to all Exercises for the Reader Appendix C: Answers/Brief Solutions to Odd Numbered Exercises References Index of Theorems, Propositions, Lemmas, and Corollaries Index of Algorithms Index |

To see a more detailed version of the contents click on this link: Detailed TOC

To see the book's preface and dependency chart click on this link: Preface

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

**Downloading instructions:** For each of the links below, left click your mouse to view the file in your internet
browser window. To download the file in its original format, right click on the link and select a "save" or "save target" option.

Each of the links below will lead to a MS Excel file that contains the distance matrix, an optimum tour, and the optimum tour
distance for the corresponding traveling salesman problem under its name. These benchmark problems and data were obtained
using the data from the Web page TSPLIB Web Page.
The traveling salesman problem, which is introduced in Chapter 9, is one of the most difficult problems in combinatorial
optimization. It is often used as a testing ground for algorithms and programs. The TSBLIB webpage contains a substantial
collections of traveling salesman problems and optimal solutions.

Ullysses 16 City Problem

Ullysses 22 City Problem

Berlin 52 City Problem

Technical Comment: The above mentioned TSPLIB Web page did not provide the distance matrices that are included in the above Excel files.
These distance matrices were computed according to the algorithms given on the TSPLIB Web Pages. In particular, the first two are computed
using certain great circle distance algorithm from the x- and y- coordinates that were given. The third distance matrix was computed using
the usual two-dimensional distance formula. All of these distance matrices had their entries rounded to the nearest integer.

Below are links to download individual programs for an assortment of algorithms and computer exercises from the book.
The programs are written in MATLAB, which is a very user-friendly language, and many comments are included.
(NOTE: In MATLAB, comments appear after "%" symbols since anything appearing in a line after this symbol
is ignored by MATLAB.) More information on how these programs operate and how corresponding programs can be written
in any computing platform can be learned by looking at the computer implementation material appearing at the end of
each chapter.
Some programs below give reference to the computer exercise to which it corresponds.

Except for Chapters 3, 4, and 6, the M-files and code snippets have been tested to work for MATLAB only.
Any program that has a single link "MATLAB/Octave/FreeMat" can be used
with either platform (and this is the case for most of the programs).
In a few cases some small changes were needed to make the MATLAB program run on FreeMat,
and for such programs there are separate links "MATLAB" and "FreeMat" for the corresponding programs.
When using FreeMat, a few programs require
some auxilliary programs to run; there are only five of these, and a zipped folder containing
them all can by downloaded using this link:
Auxilliary Programs for FreeMat

The programs can either be individually downloaded from the inventory list below, or more simply, the following link will allow you to download
a zip file of the entire suite of MATLAB programs

Download Entire MATLAB Discrete Structures Program Suite

To view individual files below, left click your mouse to view the file in your internet browser window.
To download the file in its original format, right click on the link and select a "save"
or "save target" option.
Even if you have never used MATLAB/Octave/FreeMat before; these programs are easy to use.
For information on how to obtain MATLAB or FreeMat and
how to set up these programs for use, refer to the following

MATLAB/Octave/FreeMat information page

The following link will allow you to download a text file that contains sample uses of all of the programs.

Program Input/Output Demos

This document can serve as a brief users manual.

- Prime Factorization (Brute-force) (Computer Exercise 3.3.2) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Program for Finding the Next Prime After an Inputted Integer (Computer Exercise 3.3.3) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Division Algorithm (Computer Exercise 3.3.4) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Euclidean Algoirthm (Computer Exercise 3.3.6) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Euler φ Function (Computer Exercise 3.3.7) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Inverse of Euler φ Function MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Program for Computing Orders (Computer Exercise 3.3.8) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Fermat's Primality Test Program (Appendix to Section 3.3) MATLAB text file MATLAB M-file FreeMat text file FreeMat M-file
- Enhanced Miller-Rabin Primality Test Program (Appendix to Section 3.3) MATLAB text file MATLAB M-file FreeMat text file FreeMat M-file
- Program for GCD with Symbolic Functionality text file (Symbolic) MATLAB M-file
- Program for Modular Inverses with Symbolic Functionality text file (Symbolic) MATLAB M-file
- Program for Fast Modular Exponentiation with Symbolic Functionality text file (Symbolic) MATLAB M-file
- Fermat's Primality Test Program with Symbolic Functionality text file (Symbolic) MATLAB M-file

- Bit String (or Binary Vector) to Integer Equivalent (Computer Exercise 4.1.1) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Base b Vector to Integer Equivalent (Computer Exercise 4.1.5) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Integer to Binary Vector (Computer Exercise 4.1.6) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Integer to Base b Vector (Computer Exercise 4.1.9) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Program for Base b Addition (Computer Exercise 4.1.12) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Program for Base b Subtraction (Computer Exercise 4.1.13) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Program for Base b Multiplication (Computer Exercise 4.1.18) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Extended Euclidean Algorithm (Computer Exercise 4.2.2) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Program for Computing Modular Inverses MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- ISBN-13 Checker Program (Computer Exercise 4.2.5) MATLAB text file MATLAB M-file FreeMat text file FreeMat M-file
- Program for Fast Modular Exponentiation (Computer Exercise 4.2.7) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Program for Inverting Modular Integer Matrices (Computer Exercise 4.3.11) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Hill Cipher Encryption (Computer Exercise 4.3.12) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Hill Cipher Decryption (Computer Exercise 4.3.13) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Hill Encoding Matrix Generator (Computer Exercise 4.3.15) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Diffie-Hellman Key Exchange (Computer Exercise 4.5.1) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- RSA Encryption (Computer Exercise 4.5.3) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- RSA Decryption (Computer Exercise 4.5.4) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- El Gamal Encryption (Computer Exercise 4.5.8) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- El Gamal Decryption (Computer Exercise 4.5.9) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Knapsack Problem (Brute-Force) (Computer Exercise 4.5.10) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Program for Super-Increasing Knapsack Problem (Computer Exercise 4.5.12) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Merkle-Hellman Encryption (Computer Exercise 4.5.13) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file
- Merkle-Hellman Decryption (Computer Exercise 4.5.14) MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file

- Random Integer Generator Program MATLAB/Octave/FreeMat text file MATLAB/Octave/FreeMat M-file

- Program for the Linear Search Algorithm (Computer Exercise 7.1.1) MATLAB text file MATLAB M-file
- Program for the Binary Search Algorithm (Computer Exercise 7.1.2) MATLAB text file MATLAB M-file
- Program for the Bubble Sort Algorithm (Computer Exercise 7.1.6) MATLAB text file MATLAB M-file
- Program for Random Generation of Unsorted Lists (Computer Exercises 7.1.9) MATLAB text file MATLAB M-file

- Recursive Program for Graphic Sequence Determination Algorithm with Brief Output (Computer Exercise 8.1.3) MATLAB text file MATLAB M-file
- Recursive Program for Graphic Sequence Determination Algorithm with Full Output (Computer Exercise 8.1.4) MATLAB text file MATLAB M-file
- Edge List to Adjacency Matrix (Computer Exercise 8.1.9) MATLAB text file MATLAB M-file
- Brute-Force Graph Isomorphism Checker (Computer Exercise 8.1.17) MATLAB text file MATLAB M-file
- Children List to Parent List (Computer Exercise 8.3.1) MATLAB text file MATLAB M-file
- Parent List to Depth List (Computer Exercise 8.3.2) MATLAB text file MATLAB M-file
- Descendant Finder (Computer Exercise 8.3.3) MATLAB text file MATLAB M-file
- Rooted Tree to Children Subtrees (Computer Exercise 8.3.5) MATLAB text file MATLAB M-file
- PreOrder Algorithm (Computer Exercise 8.3.6) MATLAB text file MATLAB M-file
- PreOrder Recursive Algorithm (Computer Exercise 8.3.6) MATLAB text file MATLAB M-file
- InOrder Algorithm (Computer Exercise 8.3.7) MATLAB text file MATLAB M-file
- PostOrder Algorithm (Computer Exercise 8.3.8) MATLAB text file MATLAB M-file

- Program for Determining the Set of “Unused” Edges within an Iteration of the Tree Growing Meta-Algorithm 9.4 for Graphs (Computer Exercise 9.2.1) MATLAB text file MATLAB M-file
- Program for Updating the Boundary Edges Set (BdyEdges) in Algorithm 9.4 for Graphs with Edge Indices (Computer Exercise 9.2.3) MATLAB text file MATLAB M-file
- Program for Prim’s Algorithm 9.5 for Minimum Spanning Trees (Computer Exercise 9.2.4) MATLAB text file MATLAB M-file
- Program for Dijkstra’s Algorithm 9.6 for Computing Minimum Distances in Edge-Weighted Graphs (Computer Exercise 9.2.5) MATLAB text file MATLAB M-file
- Program for Dijkstra’s Algorithm 9.6 for Computing Minimum Distances in Edge-Weighted Digraphs (Computer Exercise 9.2.6) MATLAB text file MATLAB M-file
- Program for the Depth-First Search Algorithm 9.7 for Graphs (Computer Exercise 9.2.7) MATLAB text file MATLAB M-file
- Program for the Breadth-First Search Algorithm 9.8 for Graphs (Computer Exercise 9.2.8) MATLAB text file MATLAB M-file
- Random TSP Generator (Computer Exercise 9.2.10) MATLAB text file MATLAB M-file
- Brute-Force Algorithm for the Traveling Salesman Problem (Computer Exercise 9.2.11) MATLAB text file MATLAB M-file
- Nearest Neighbor Algorithm for the Traveling Salesman Problem (Computer Exercise 9.2.11) MATLAB text file MATLAB M-file
- Nearest Insertion Algorithm for the Traveling Salesman Problem (Computer Exercise 9.2.11) MATLAB text file MATLAB M-file
- Cheapest Insertion Algorithm for the Traveling Salesman Problem (Computer Exercise 9.2.11) MATLAB text file MATLAB M-file
- Program for the Edmonds–Karp Adaptation of the Ford–Fulkerson Maximum Flow Algorithm 9.13 (Computer Exercise 9.3.5) MATLAB text file MATLAB M-file
- Program for the Edmonds–Karp Adaptation of the Ford–Fulkerson Maximum Flow Algorithm 9.13 With Full Output (Computer Exercise 9.3.5) MATLAB text file MATLAB M-file

- Mating Pool Generation Program for Genetic Algorithms (EFR 10.3) MATLAB text file MATLAB M-file
- Crossover Operator Program for Genetic Algorithms MATLAB text file MATLAB M-file
- Mutation Operator Program for Genetic Algorithms MATLAB text file MATLAB M-file