Questions and Answers of Practical Introduction To Data Structures

Imagine that you are a programmer who must write a function to sort an array of about 1000 integers from lowest value to highest value. Write down at least five approaches to sorting the array. Do
Think of an algorithm to find the maximum value in an (unsorted) array. Now, think of an algorithm to find the second largest value in the array. Which is harder to implement? Which takes more time
An unsorted list of integers allows for constant-time insert simply by adding a new integer at the end of the list. Unfortunately, searching for the integer with key value X requires a sequential
For each relation below, explain why the relation does or does not satisfy each of the properties reflexive, symmetric, antisymmetric, and transitive.(a) "isBrotherOf" on the set of
For each of the following relations, either prove that it is an equivalence relation or prove that it is not an equivalence relation.(a) For integers a and b, a ≡ b if and only if a + b is
State whether each of the following relations is a partial ordering, and explain why or why not.(a) "isFatherOf" on the set of people.(b) "isAncestorOf" on the set of people.(c) "isOlderThan" on
How many total orderings can be defined on a set with n elements? Explain your answer.
Define an ADT for a set of integers (remember that a set has no concept of duplicate elements, and has no concept of order). Your ADT should consist of the functions that can be performed on a set to
Define an ADT for a bag of integers (remember that a bag may contain duplicates, and has no concept of order). Your ADT should consist of the functions that can be performed on a bag to control its
Define an ADT for a sequence of integers (remember that a sequence may contain duplicates, and supports the concept of position for its elements).Your ADT should consist of the functions that can be
An investor places $30,000 into a stock fund. 10 years later the account has a value of $69,000. Using logarithms and anti-logarithms, present a formula for calculating the average annual rate of
Rewrite the factorial function of Section 2.5 without using recursion.
Rewrite the for loop for the random permutation generator of Section 2.2 as a recursive function.
Here is a simple recursive function to compute the Fibonacci sequence:This algorithm turns out to be very slow, calling Fibr a total of Fib(n) times. Contrast this with the following iterative
Write a recursive function to solve a generalization of the Towers of Hanoi problem where each ring may begin on any pole so long as no ring sits on top of a smaller ring.
Consider the following function:This function makes progress towards the base case on every recursive call. In theory (that is, if double variables acted like true real numbers), would this function
Write a function to print all of the permutations for the elements of an array containing n distinct integer values.
Write a recursive algorithm to print all of the subsets for the set of the first n positive integers.
The Largest Common Factor (LCF) for two positive integers n and m is the largest integer that divides both n and m evenly. LCF(n, m) is at least one, and at most m, assuming that n ≥ m. Over two
Prove by contradiction that the number of primes is infinite.
(a) Use induction to show that n^2 - n is always even. (b) Give a direct proof in one or two sentences that n^2 - n is always even. (c) Show that n^3 - n is always divisible by three. (d) Is n^5 - n
Explain why n n-1 =(n-i+1) =(n - i). i=1 i=0 i=1
Prove Equation 2.2 using mathematical induction. n i=1 = 2n +3n+ n 6 = n(2n + 1)(n+1) 6 (2.2)
Prove Equation 2.6 using mathematical induction. n 1 2 i=1 || 1 I 1 2n (2.6)
Prove Equation 2.7 using mathematical induction. n i=0 2 = 2n+1 -1. (2.7)
Find a closed-form solution and prove (using induction) that your solution is correct for the summation n 3 i=1 2
Prove that the sum of the first n even numbers is n^2 + n(a) Indirectly by assuming that the sum of the first n odd numbers is n^2.(b) Directly by mathematical induction.
Give a closed-form formula for the summation where a is an integer between 1 and n. =al
Prove that Fib(n) < (5/3)^n.
Prove, for n ≥ 1, that A i=1 3 n (n + 1) 4
For this problem, you will consider arrangements of infinite lines in the plane such that three or more lines never intersect at a single point.(a) Give a recurrence relation that expresses the
Prove (using induction) that the recurrence T(n) = T(n − 1) + n; T(1) = 1 has as its closed-form solution T(n) = n(n + 1)/2.
Expand the following recurrence to help you find a closed-form solution, and then use induction to prove your answer is correct. T(n) = 2T(n − 1) + 1 for n > 0; T(0) = 0.
Expand the following recurrence to help you find a closed-form solution, and then use induction to prove your answer is correct. T(n) = T(n − 1) + 3n + 1 for n > 0; T(0) = 1.
Assume that an n-bit integer (represented by standard binary notation) takes any value in the range 0 to 2^n − 1 with equal probability. (a) For each bit position, what is the probability of its
What is the total volume of your body in liters (or, if you prefer, gallons)?
An art historian has a database of 20,000 full-screen color images.(a) About how much space will this require? How many CD-ROMs would be required to store the database? (A CD-ROM holds about 600MB of
How many cubic miles of water flow out of the mouth of the Mississippi River each day? DO NOT look up the answer or any supplemental facts. Be sure to describe all assumptions made in arriving at
When buying a home mortgage, you often have the option of paying some money in advance (called “discount points”) to get a lower interest rate. Assume that you have the choice between two 15-year
When you build a new house, you sometimes get a “construction loan” which is a temporary line of credit out of which you pay construction costs as they occur. At the end of the construction
Here are some questions that test your working knowledge of how fast computers operate. Is disk drive access time normally measured in milliseconds (thousandths of a second) or microseconds
Does your home contain enough books to total one million pages? How many total pages are stored in your school library building?
How many words are in this book?
How many hours are one million seconds? How many days? Answer these questions doing all arithmetic in your head.
How many cities and towns are there in the United States?
How many steps would it take to walk from Boston to San Francisco?
A man begins a car trip to visit his in-laws. The total distance is 60 miles, and he starts off at a speed of 60 miles per hour. After driving exactly 1 mile, he loses some of his enthusiasm for the

Showing 400 - 500 of 447

1
2
3
4
5