StudySoup StudySoup
×

Log in to StudySoup

Math - Textbook Survival Guide
Forgot password?
Register Now
×

Join StudySoup

Get Full Access to Math - Textbook Survival Guide
Already have an account? Login here
×
Reset your password

I don't want to reset my password

Solutions for Discrete Mathematics and Its Applications | 7th Edition | ISBN: 9780073383095 | Authors: Kenneth Rosen

ISBN9780073383095

Solutions for Chapter 3.1: Cardinality of Sets

Solutions for Chapter 3.1

3.1.1E) List all the steps used by Algorithm I to find the maximum of the list 1, 8, 12, 9. 11, 2, 14, 5, 10, 4.

3.1.2E) ?2E Determine which characteristics of an algorithm described in the text (after Algorithm 1) the following procedure...

3.1.3E) ?3E Devise an algorithm that finds the sum of all the integers in a list.

3.1.4E) Describe an algorithm that takes as input a list of n integers and produces as output the largest difference obtained...

3.1.5E) Describe an algorithm that takes as input a list of n integers in nondecreasing order and produces the list of all va...

3.1.6E) Describe an algorithm that takes as input a list of n integers and finds the number of negative integers in the list.

3.1.7E) Describe an algorithm that takes as input a list of n integers and finds the location of the last even integer in the...

3.1.8E) Describe an algorithm that takes as input a list of n distinct integers and finds the location of the largest even in...

3.1.9E) A palindrome is a string that reads the same forward and backward. Describe an algorithm for determining whether a st...

3.1.11E) ?11E Describe an algorithm that interchanges the values of the variables ?x and ?y?. using only assignments. What is ...

3.1.12E) Describe an algorithm that uses only assignment statements that replaces the triple (x, y, z) with (y. z. x). What is...

3.1.13E) ?13E List all the steps used to search for 9 in the sequence 1, 3, 4, 5, 6, 8, 9, 11 using a) a linear search. b) a b...

3.1.14E) List all the steps used to search for 7 in the sequence given in Exercise 13 for both a linear search and a binary se...

3.1.15E) Describe an algorithm that inserts an integer x in the appropriate position into the list a1, a2, …, an of integers t...

3.1.16E) Describe an algorithm for finding the smallest integer in a finite sequence of natural numbers.

3.1.17E) Describe an algorithm that locates the first occurrence of the largest element in a finite list of integers, where th...

3.1.18E) Describe an algorithm that locates the last occurrence of the smallest element in a finite list of integers, where th...

3.1.19E) Describe an algorithm that produces the maximum, median, mean, and minimum of a set of three integers. (The median of...

3.1.20E) Describe an algorithm for finding both the largest and the smallest integers in a finite sequence of integers.

3.1.21E) Describe an algorithm that puts the first three terms of a sequence of integers of arbitrary length in increasing order.

3.1.22E) Describe an algorithm to find the longest word in an English sentence (where a sentence is a sequence of symbols, eit...

3.1.23E) Describe an algorithm that determines whether a function from a finite set of integers to another finite set of integ...

3.1.24E) Describe an algorithm that determines whether a function from a finite set to another finite set is one-to-one.

3.1.25E) Describe an algorithm that will count the number of 1s in a bit string by examining each bit of the string to determi...

3.1.26E) ?Change Algorithm 3 so that the binary search procedure compares \(x\) to \(a_{m}\) at each stage of the algorithm, w...

3.1.27E) The ternary search algorithm locates an element in a list of increasing integers by successively splitting the list i...

3.1.28E) Specify the steps of an algorithm that locates an element in a list of increasing integers by successively splitting ...

3.1.29E) Devise an algorithm that finds a mode in a list of nondecreasing integers. (Recall that a list of integers is nondecr...

3.1.30E) Devise an algorithm that finds all modes. (Recall that a list of integers is nondccreasing if each term of the list i...

3.1.31E) Devise an algorithm that finds the first term of a sequence of integers that equals some previous term in the sequence.

3.1.32E) In a list of elements the same elements may appear several times. A mode of such lust is an element that occurs at le...

3.1.33E) Devise an algorithm that finds the first term of a sequence of positive integers that is less than the immediately pr...

3.1.34E) ?34E Use the bubble sort to sort 6, 2.3, 1, 5, 4, showing the lists obtained at each step.

3.1.35E) ?35E Use the bubble sort to sort 3, 1,5, 7, 4. showing the lists obtained at each step.

3.1.36E) Use the bubble sort to sort d, f, k, m, a, b, showing the lists obtained at each step.

3.1.37E) Adapt the bubble sort algorithm so that it stops when no interchanges are required. Express this more efficient versi...

3.1.38E) ?38E Use the insertion sort to sort the list in Exercise 34, showing the lists obtained at each step.

3.1.39E) Use the insertion sort to sort the list in Exercise 35, showing the lists obtained at each step.

3.1.40E) Use the insertion sort to sort the list in Exercise 36, showing the lists obtained at each step.The selection sort be...

3.1.41E) Sort these lists using the selection sort.a) 3, 5, 4, 1, 2________________b) 5, 4, 3, 2, 1________________c) 1, 2, 3,...

3.1.42E) ?42E Write the selection sort algorithm in pseudocode.

3.1.43E) Describe an algorithm based on the linear search for determining the correct position in which to insert a new clemen...

3.1.44E) ?44E Describe an algorithm based on the binary search for determining the correct position in which to insert a new e...

3.1.45E) How many comparisons does the insertion sort use to sort the list 1, 2, …, n?

3.1.46E) How many comparisons does the insertion sort use to sort the list n, n – 1, … 2, 1?The binary insertion sort is a var...

3.1.47E) Show all the steps used by the binary insertion sort to son the list 3, 2, 4, 5, 1, 6.

3.1.48E) Compare the number of comparisons used by the insertion sort and the binary insertion sort to sort the list 7, 4, 3, ...

3.1.49E) Express the binary insertion sort in pseudocode.

3.1.50E) The binary insertion sort is a variation of the insertion sort that uses a binary search technique (sec Exercise 44) ...

3.1.51E) When a list of elements is in close to the correct order, would it be better to use an insertion sort or its variatio...

3.1.52E) ?52E Use the greedy algorithm to make change using quarters, dimes, nickels, and pennies for a) 87 cents. b) 49 cents...

3.1.53E) Use the greedy algorithm to make change using quarters, dimes, nickels, and pennies fora) 51 cents.________________b)...

3.1.54E) Use the greedy algorithm to make change using quarters, dimes, and pennies (but no nickels) for each of the amounts g...

3.1.55E) Use the greedy algorithm to make change using quarters. dimes, and pennies (but no nickels) for each of the amounts g...

3.1.57E) Use Algorithm 7 to schedule the largest number of talks in a lecture hall from a proposed set of talks, if the starti...

3.1.58E) Show that a greedy algorithm that schedules talks in a lecture hall, as described in Example 7. by selecting at each ...

3.1.59E) ?a) Devise a greedy algorithm that determines the fewest lecture halls needed to accommodate \(n\) talks given the st...

3.1.60E) Suppose we have three men m1, m2, and m3 and three women w1, w2, and w3. Furthermore, suppose that the preference ran...

3.1.61E) Write the deferred acceptance algorithm in pseudocode.

3.1.62E) Show that the deferred acceptance algorithm terminates.

3.1.63E) Show that the deferred acceptance always terminates with a stable assignment.

3.1.65E) Show that the following problem is solvable. Given two programs with their inputs and the knowledge that exactly one ...

3.1.66E) Show that the problem of deciding whether a specific program with a specific input baits is solvable.

Summary of Chapter 3.1: Cardinality of Sets

The concepts developed in this section have important applications to computer science. A function is called uncomputable if no computer program can be written to find all its values, even with unlimited time and memory.

This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. Chapter 3.1: Cardinality of Sets includes 63 full step-by-step solutions. This expansive textbook survival guide covers the following chapters and their solutions. Since 63 problems in chapter 3.1: Cardinality of Sets have been answered, more than 892784 students have viewed full step-by-step solutions from this chapter.

Key Math Terms and definitions covered in this textbook
  • Big formula for n by n determinants.

    Det(A) is a sum of n! terms. For each term: Multiply one entry from each row and column of A: rows in order 1, ... , nand column order given by a permutation P. Each of the n! P 's has a + or - sign.

  • Characteristic equation det(A - AI) = O.

    The n roots are the eigenvalues of A.

  • Cholesky factorization

    A = CTC = (L.J]))(L.J]))T for positive definite A.

  • Column space C (A) =

    space of all combinations of the columns of A.

  • Cyclic shift

    S. Permutation with S21 = 1, S32 = 1, ... , finally SIn = 1. Its eigenvalues are the nth roots e2lrik/n of 1; eigenvectors are columns of the Fourier matrix F.

  • Diagonalization

    A = S-1 AS. A = eigenvalue matrix and S = eigenvector matrix of A. A must have n independent eigenvectors to make S invertible. All Ak = SA k S-I.

  • Distributive Law

    A(B + C) = AB + AC. Add then multiply, or mUltiply then add.

  • Fast Fourier Transform (FFT).

    A factorization of the Fourier matrix Fn into e = log2 n matrices Si times a permutation. Each Si needs only nl2 multiplications, so Fnx and Fn-1c can be computed with ne/2 multiplications. Revolutionary.

  • Full row rank r = m.

    Independent rows, at least one solution to Ax = b, column space is all of Rm. Full rank means full column rank or full row rank.

  • Gauss-Jordan method.

    Invert A by row operations on [A I] to reach [I A-I].

  • Hermitian matrix A H = AT = A.

    Complex analog a j i = aU of a symmetric matrix.

  • Hessenberg matrix H.

    Triangular matrix with one extra nonzero adjacent diagonal.

  • Linear transformation T.

    Each vector V in the input space transforms to T (v) in the output space, and linearity requires T(cv + dw) = c T(v) + d T(w). Examples: Matrix multiplication A v, differentiation and integration in function space.

  • Polar decomposition A = Q H.

    Orthogonal Q times positive (semi)definite H.

  • Positive definite matrix A.

    Symmetric matrix with positive eigenvalues and positive pivots. Definition: x T Ax > 0 unless x = O. Then A = LDLT with diag(D» O.

  • Rank r (A)

    = number of pivots = dimension of column space = dimension of row space.

  • Singular Value Decomposition

    (SVD) A = U:E VT = (orthogonal) ( diag)( orthogonal) First r columns of U and V are orthonormal bases of C (A) and C (AT), AVi = O'iUi with singular value O'i > O. Last columns are orthonormal bases of nullspaces.

  • Solvable system Ax = b.

    The right side b is in the column space of A.

  • Transpose matrix AT.

    Entries AL = Ajj. AT is n by In, AT A is square, symmetric, positive semidefinite. The transposes of AB and A-I are BT AT and (AT)-I.

  • Tridiagonal matrix T: tij = 0 if Ii - j I > 1.

    T- 1 has rank 1 above and below diagonal.

Textbook Survival Guides