Data Structures And Algorithms In C++ 2nd Edition Michael T. Goodrich, Roberto Tamassia, David M. Mount - Solutions

Describe the output for the following sequence of deque operations:insertFront(3), insertBack(8), insertBack(9), insertFront(5), removeFront(), eraseBack(), first(), insertBack(7), removeFront(), last(), eraseBack().
Implement a program that can input an expression in postfix notation (see Exercise C-5.8) and output its value.Data from in Exercise C-5.8Postfix notation is an unambiguous way of writing an arithmetic expression without parentheses. It is defined so that if “(exp1) ◦ (exp2)” is a normal
Which of the following is not a valid C++ variable name? (There may be more than one.)a. I think i am validb. I may have 2 many digits 2 be validc. I start and end with underscoresd. I Have A Dollar $igne. I AM LONG AND HAVE NO LOWER CASE LETTERS
A common punishment for school children is to write out the same sentence multiple times. Write a C++ stand-alone program that will write out the following sentence one hundred times: “I will always use object oriented design.” Your program should number each of the sentences and it should
Write a short C++ function that takes an array of int values and determines if there is a pair of numbers in the array whose product is even.
Write a C++ program that, when given a starting day (Sunday through Saturday) as a string, and a four-digit year, prints a calendar for that year. Each month should contain the name of the month, centered over the dates for that month and a line containing the names of the days of the week, running
Write a pseudo-code description of a method for finding the smallest and largest numbers in an array of integers and compare that to a C++ function that would do the same thing.
Write a C++ function that takes an STL vector of int values and determines if all the numbers are different from each other (that is, they are distinct).
Give a C++ definition of a struct called Pair that consists of two members. The first is an integer called first, and the second is a double called second.
Write a C++ function that takes an STL vector of int values and prints all the odd values in the vector.
What are the contents of string s after executing the following statements.string s = "abc";string t = "cde";s += s + t[1] + s;
Write a C++ function that takes an array containing the set of all integers in the range 1 to 52 and shuffles it into random order. Use the built-in function rand, which returns a pseudo-random integer each time it is called. Your function should output each possible order with equal probability.
Consider the expression y + 2 * z ++ < 3 - w / 5. Add parentheses to show the precise order of evaluation given the C++ rules for operator precedence.
Write a short C++ program that outputs all possible strings formed by using each of the characters ’a’, ’b’, ’c’, ’d’, ’e’, and ’f’ exactly once.
Consider the following attempt to allocate a 10-element array of pointers to doubles and initialize the associated double values to 0.0. Rewrite the following (incorrect) code to do this correctly.double* dp[10] for (int i = 0; i < 10; i++) dp[i] = 0.0;
Write a short C++ program that takes all the lines input to standard input and writes them to standard output in reverse order. That is, each line is output in the correct order, but the ordering of the lines is reversed.
Write a short C++ function that takes an integer n and returns the sum of all the integers smaller than n.
Write a short C++ program that takes two arguments of type STL vector< double>, a and b, and returns the element-by-element product of a and b. That is, it returns a vector c of the same length such that c[i] = a[i] ·b[i].
Write a short C++ function, is Multiple, that takes two positive long values, n and m, and returns true if and only if n is a multiple of m, that is, n = mi for some integer i.
Write a C++ class Vector2, that stores the (x,y) coordinates of a two dimensional vector, where x and y are of type double. Show how to override various C++ operators in order to implement the addition of two vectors (producing a vector result), the multiplication of a scalar times a vector
Write a C++ function print Array(A, m, n) that prints an m × n two dimensional array A of integers, declared to be “int** A,” to the standard output. Each of the m rows should appear on a separate line.
Write an efficient C++ function that takes any integer value i and returns 2i, as a long value. Your function should not multiply 2 by itself i times; there are much faster ways of computing 2i.
The greatest common divisor, or GCD, of two positive integers n and m is the largest number j, such that n and m are both multiples of j. Euclid proposed a simple algorithm for computing GCD(n,m), where n > m, which is based on a concept known as the Chinese Remainder Theorem. The main idea of
What (if anything) is different about the behavior of the following two functions f and g that increment a variable and print its value?void f(int x){ std::cout << ++x; } void g(int& x){ std::cout << ++x; }
Write a C++ class, Flower, that has three member variables of type string, int, and float, which respectively represent the name of the flower, its number of pedals, and price. Your class must include a constructor method that initializes each variable to an appropriate value, and your class should
Modify the CreditCard class from Code Fragment 1.3 to check that the price argument passed to function charge It and the payment argument passed to function make Payment are positive.Data from in Fragment 1.3The file CreditCard.cpp, which contains the definition of the out-of-class member functions
Modify the CreditCard class from Code Fragment 1.2 to charge interest on each payment.Data from in Fragment 1.2A typical C++ program includes many different header files, which often include other header files. As a result, the same header file may be expanded many times. Such repeated header
Modify the CreditCard class from Code Fragment 1.2 to charge a late fee for any payment that is past its due date.Data from in Fragment 1.2A typical C++ program includes many different header files, which often include other header files. As a result, the same header file may be expanded many
Modify the CreditCard class from Code Fragment 1.2 to include modifier functions that allow a user to modify internal variables in a CreditCard class in a controlled manner.Data from in Fragment 1.2A typical C++ program includes many different header files, which often include other header files.
Modify the declaration of the first for loop in the Test class in Code Fragment 1.4 so that its charges will eventually cause exactly one of the three credit cards to go over its credit limit. Which credit card is it?Data from in Fragment 1.4Let us start with the second line. The #define statement
Write a C++ class, All Kinds, that has three member variables of type int, long, and float, respectively. Each class must include a constructor function that initializes each variable to a nonzero value, and each class should include functions for setting the value of each type, getting the value
Write a short C++ function, is Multiple, that takes two long values, n and m, and returns true if and only if n is a multiple of m, that is, n = m· i for some integer i.
Write a short C++ function, is Two Power, that takes an int i and returns true if and only if i is a power of 2. Do not use multiplication or division, however.
Write a short C++ function that takes an integer n and returns the sum of all the integers smaller than n.
Write a short C++ function that takes an integer n and returns the sum of all the odd integers smaller than n.
Write a short C++ function that takes a positive double value x and returns the number of times we can divide x by 2 before we get a number less than 2.
Give an example of a C++ program that outputs its source code when it is run. Such a program is called a quine.
Write a C++ program that can take a positive integer greater than 2 as input and write out the number of times one must repeatedly divide this number by 2 before getting a value less than 2.
Suppose you are on the design team for a new e-book reader. What are the primary classes and functions that the C++ software for your reader will need? You should include an inheritance diagram for this code, but you don’t need to write any actual code. Your software architecture should at least
Write a C++ program that “makes change.” Your program should input two numbers, one that is a monetary amount charged and the other that is a monetary amount given. It should return the number of each kind of bill and coin to give back as change for the difference between the amounts given and
Give three examples of life-critical software applications.
Most modern C++ compilers have optimizers that can detect simple cases when it is logically impossible for certain statements in a program to ever be executed. In such cases, the compiler warns the programmer about the useless code. Write a short C++ function that contains code for which it is
Design a class Line that implements a line, which is represented by the formula y = ax+b. Your class should store a and b as double member variables. Write a member function intersect(ℓ) that returns the x coordinate at which this line intersects line ℓ. If the two lines are parallel, then your
Describe a component from a text-editor GUI (other than an “edit” menu) and the member functions that it encapsulates.
Write a C++ class that is derived from the Progression class to produce a progression where each value is the absolute value of the difference between the previous two values. You should include a default constructor that starts with 2 and 200 as the first two values and a parametric constructor
Write a C++ program that has a Polygon interface that has abstract functions, area(), and perimeter(). Implement classes for Triangle, Quadrilateral, Pentagon, Hexagon, and Octagon, which implement this interface, with the obvious meanings for the area() and perimeter() functions. Also implement
Draw a class inheritance diagram for the following set of classes.• Class Goat extends Object and adds a member variable tail and functions milk and jump.• Class Pig extends Object and adds a member variable nose and functions eat and wallow.• Class Horse extends Object and adds member
Write a C++ class that is derived from the Progression class to produce a progression where each value is the square root of the previous value.You should include a default constructor that starts with 65,536 as the first value and a parametric constructor that starts with a specified (double)
Write a C++ program that inputs a document and then outputs a bar-chart plot of the frequencies of each alphabet character that appears in that document.
A derived class’s constructor explicitly invokes its base class’s constructor, but a derived class’s destructor cannot invoke its base class’s destructor. Why does this apparent asymmetry make sense?
Write a C++ program that inputs a list of words separated by whitespace, and outputs how many times each word appears in the list. You need not worry about efficiency at this point, however, as this topic is something that will be addressed later in this book.
Write a set of C++ classes that can simulate an Internet application, where one party, Alice, is periodically creating a set of packets that she wants to send to Bob. The Internet process is continually checking if Alice has any packets to send, and if so, it delivers them to Bob’s computer, and
Write a C++ program that can input any polynomial in standard algebraic notation and outputs the first derivative of that polynomial.
Consider the inheritance of classes from Exercise R-2.6, and let d be an object variable of type Horse. If d refers to an actual object of type Equestrian, can it be cast to the class Racer? Why or why not?Data from in Exercise R-2.6Draw a class inheritance diagram for the following set of
Consider the following code fragment:class Object{ public: virtual void printMe() = 0; };class Place : public Object{ public: virtual void printMe() { cout << "Buy it.\n"; } };class Region : public Place{ public: virtual void printMe() { cout << "Box it.\n"; } };class State : public
Generalize the Person-Student class hierarchy to include classes Faculty, Under graduate Student, Graduate Student, Professor, Instructor. Explain the inheritance structure of these classes, and derive some appropriate member variables for each class.
Give an example of a C++ code fragment that performs an array reference that is possibly out of bounds, and if it is out of bounds, the program catches that exception and prints an appropriate error message.
Write a short C++ function that counts the number of vowels in a given character string.
Write a short C++ function that removes all the punctuation from a string s storing a sentence. For example, this operation would transform the string "Let’s try, Mike." to "Lets try Mike".
Write a short C++ program that creates a Pair class that can store two objects declared as generic types. Demonstrate this program by creating and printing Pair objects that contain five different kinds of pairs, such as and .
In the Tic-Tac-Toe example, we used 1 for player X and −1 for player O. Explain how to modify the program’s counting trick to decide the winner if we had used 1 for player X and 4 for player O instead. Could we use any combination of values a and b for the two players? Explain.
Write a C++ function that takes two three-dimensional integer arrays and adds them component wise.
Modify the implementation of class Scores so that at most ⌈maxEnt/2⌉ of the scores can come from any one single player.
Give C++ code for performing add(e) and remove(i) functions for game entries stored in an array a, as in class Scores in Section 3.1.1, except this time, don’t maintain the game entries in order. Assume that we still need to keep n entries stored in indices 0 to n−1. Try to implement the add
Suppose that two entries of an array A are equal to each other. After running the insertion-sort algorithm of Code Fragment 3.7, will they appear in the same relative order in the final sorted order or in reverse order? Explain your answer.Data from in Fragment 3.7Algorithmic description of the
Write a C++ program for a matrix class that can add and multiply arbitrary two-dimensional arrays of integers. Do this by overloading the addition (“+”) and multiplication (“*”) operators.
Give a C++ code fragment that, given a n×n matrix M of type float, replaces M with its transpose. Try to do this without the use of a temporary matrix.
Perform the previous project but use a linked list that is both circularly linked and doubly linked.
Add a function size() to our C++ implementation of a singly link list. Can you design this function so that it runs in O(1) time?
Write a program that can perform encryption and decryption using an arbitrary substitution cipher. In this case, the encryption array is a random shuffling of the letters in the alphabet. Your program should generate a random encryption array, its corresponding decryption array, and use these to
Give an algorithm for finding the penultimate (second to last) node in a singly linked list where the last element is indicated by a null next link.
Write a program that can solve instances of the Tower of Hanoi problem (from Exercise C-3.12).Data from in Exercise C-3.12In the Towers of Hanoi puzzle, we are given a platform with three pegs, a, b, and c, sticking out of it. On peg a is a stack of n disks, each larger than the next, so that the
Describe a nonrecursive function for finding, by link hopping, the middle node of a doubly linked list with header and trailer sentinels. What is the running time of this function?
Draw the recursion trace for the execution of function ReverseArray(A,0,4) (Code Fragment 3.39) on array A = {4,3,6,2,5}.
Draw the recursion trace for the execution of function Puzzle Solve(3,S,U) (Code Fragment 3.44), where S is empty and U = {a,b,c,d}.Code Fragment 3.44Solving a combinatorial puzzle by enumerating and testing all possible configurations. In Figure 3.21, we show a recursion trace of a call to
Write a short C++ function that repeatedly selects and removes a random entry from an n-element array until the array holds no more entries. Assume that you have access to a function random(k), which returns a random integer in the range from 0 to k.
Write a short recursive C++ function that finds the minimum and maximum values in an array of int values without using any loops.
Write a short C++ function to count the number of nodes in a circularly linked list.
Write a short recursive C++ function that will rearrange an array of int values so that all the even values appear before all the odd values.
Write a short recursive C++ function that takes a character string s and outputs its reverse. So for example, the reverse of "pots&pans" would be "snap&stop".
Write a short recursive C++ function that determines if a string s is a palindrome, that is, it is equal to its reverse. For example, "racecar" and "gohangasalamiimalasagnahog" are palindromes.
Use recursion to write a C++ function for determining if a string s has more vowels than consonants.
Suppose you are given two circularly linked lists, L and M, that is, two lists of nodes such that each node has a nonnull next node. Describe a fast algorithm for telling if L and M are really the same list of nodes but with different (cursor) starting points.
Give a pseudo-code description of the O(n)-time algorithm for computing the power function p(x,n). Also, draw the recursion trace of this algorithm for the computation of p(2,5).
Give a C++ description of Algorithm Power for computing the power function p(x,n) (Code Fragment 4.4).Data from in Fragment 4.4Computing the power function using linear recursion.To analyze the running time of the algorithm, we observe that each recursive call of function Power(x,n) divides the
Perform an experimental analysis to test the hypothesis that the STL function, sort, runs in O(nlog n) time on average.
Draw the recursion trace of the Power algorithm (Code Fragment 4.4, which computes the power function p(x,n)) for computing p(2,9).Data from in Fragment 4.4Computing the power function using linear recursion.To analyze the running time of the algorithm, we observe that each recursive call of
Perform an experimental analysis to determine the largest value of n for each of the three algorithms given in the chapter for solving the element uniqueness problem such that the given algorithm runs in one minute or less.
Suppose you are given an n-element array A containing distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if such a pair exists. What is the running time of your algorithm?
Given an n-element unsorted array A of n integers and an integer k, describe a recursive algorithm for rearranging the elements in A so that all elements less than or equal to k come before any elements larger than k. What is the running time of your algorithm?
Graph the functions 8n, 4nlog n, 2n2, n3, and 2n using a logarithmic scale for the x- and y-axes. That is, if the function is ∫ (n) is y, plot this as a point with x-coordinate at logn and y-coordinate at logy.
Show that if d(n) is O( ∫ (n)) and e(n) is O(g(n)), then d(n) +e(n) is O( ∫ (n)+g(n)). Algorithm Ex1(A): Input: An array A storing n ≥ 1 integers. Output: The sum of the elements in A. S← A[0] for i 1 to n - 1 do s+s+A[i] return s Algorithm Ex2(A): Input: An array A storing n> 1
For each function ∫ (n) and time t in the following table, determine the largest size n of a problem P that can be solved in time t if the algorithm for solving P takes ∫ (n) microseconds (one entry is already completed). logn n nlogn n² 2" 1 Second ~10300000 1 Hour 1 Month 1 Century
What is the sum of all the even numbers from 0 to 2n, for any positive integer n?
Show that the summation n ₁ [log₂ i] is O(nlogn).
Order the following functions by asymptotic growth rate.4nlog n+2n 210 2log n3n+100log n 4n 2nn2 +10n n3 nlog n
Consider the Fibonacci function, F(n) (see Proposition 4.20). Show by induction that F(n) is Ω((3/2)n).
Show that if d(n) is O( ∫ (n)) and e(n) is O(g(n)), then d(n)−e(n) is not necessarily O( ∫ (n)−g(n)).
Show that (n+1)5 is O(n5).
Show that 2n+1 is O(2n).

Showing 400 - 500 of 502

Data Structures And Algorithms In C++ 2nd Edition Michael T. Goodrich, Roberto Tamassia, David M. Mount - Solutions

Step by Step Answers