Mathematics for Algorithm and Systems Analysis

Discrete mathematics is an essential tool in almost all subareas of computer science. Interesting and challenging problems in discrete mathematics arise in programming languages, computer architecture, networking, distributed systems, database systems, AI, theoretical computer science, and other areas. This textbook is the second part of the two series of book, used to teach two-quarter course sequence in discrete mathematics that includes Boolean arithmetic, combinatorics, elementary logic, induction, graph theory and finite probability in the University of California, San Diego (USCD). These courses are core undergraduate requirements for majors in Computer Science, Computer Engineering, and Mathematics-Computer Science. This text, Mathematics for Algorithm and System Analysis, was developed for the second quarter and the other text, A Short Course in Discrete Mathematics was developed for the first quarter. With appropriate students, this text could be used without the first. This book consists of four units of study (Counting and Listing — CL; Functions — Fn; Decision Trees and Recursion — DT; and Basic Concepts of Graph Theory — GT), each divided into four sections. Each section contains a representative selection of problems. These vary from basic to more difficult, including proofs for study by mathematics students or honors students. The first three sections in units CL and Fn are primarily a