71 A similar problem will occur for Java programs when the n

7.1) A similar problem will occur for Java programs when the number of milliseconds since the beginning of 1970 exceeds the capacity of a long. In what year will this occur, given that the maximum value of a long is 9,223,372,036,854,775,807? What if getTime() returned an int, which has a maximum value of 2,147,483,647? What about those UNIX/C systems which use an int to store the number of seconds since the beginning of 1970?

7.2) What is the order of the expression 3n2 + 5n + n log n?

7.3) What is the order of the expression 5n log 5n? ?

7.9) An instance of the built-in class java.lang.BigInteger represents an integer, which can be arbitrarily large. Is it safe to assume that the add() method from this class takes constant time? Explain

7.13) What is the average result of rolling a 6-sided die? We want to know the average output (not running time) of the method. We might try to do this by determining the average result of rolling a die and then squaring that. What\'s wrong with this reasoning?

7.15) All of the Stack and Queue operations, under both array-based and linked implementations, take amortized time in the same order. Which order is it?

7.14 1P*Roll a die, square the result, and return it. * k ak 2 public static int dieSquared) 3 Die die = new Die(); 4 die.roll(O; 5 return die.getTopFace die.getTopFace); 6 )

Solution

7.2) ORder of the expression 3n²+5n+nlogn

To find the order of the above expression, we must find constants c>0,n0>=1 such that

                  3n²+5n+nlogn <= cn² for all n>=n0

so, bringing cn² to the other side of the inequality, we have

(c-3)n² +5n+nlogn>=0

the above inequality holds true even though we drop nlogn term and calculate for c and n

c=3 and n₀=1

the values of c and n₀ can be anyvalues which satisfy inequality now , we found c and n₀ such that 3n²+5n+nlogn <= cn² so we can say that it is of the order O(n²)

7.3) 5nlog5n

5nlog5n<= cn

(5-c)n log5n<=0

c=5 n=1

we say that 5nlog5n is of the order O(n)

7.9) add() of two long integers

The model depends on a single parameter w, called the word size. Each memory address holds a single w-bit integer, or word. In this model, the input size n is the number of words in the input, and the running time of an algorithm is the number of operations on words. Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require O(1) time by definition.

Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time O(1). For example, we assume this when we say that comparison-based sorting is O(nlogn), but when numbers are too big to fit into registers, we normally represent them as arrays so basic operations require extra calculations per element.

Suppose we are adding two arrays of size n and m , then that is we need to insert emelemts of one array into another .

hen each insertion will take O(log (n/m)) and the overall complexity will be O(m log(n/m) ). If there exists a constant k>1 that does not depend on n or m such that n > k * m then O(log(n/m)) = O(log(n)) and we get the asymptotic complexity O(logn)

7.1)The Year 2038 problem is an issue for computing and data storage situations in which time values are stored or calculated as a signed 32-bit integer, and this number is interpreted as the number of seconds since 00:00:00 UTC on 1 January 1970 (\"the epoch\"). Such implementations cannot encode times after 03:14:07 UTC on 19 January 2038. Most 32-bit Unix-like systems store and manipulate time in this \"Unix time\" format, so the year 2038 problem is sometimes referred to as the \"Unix Millennium Bug\" by association.

Times beyond that will \"wrap around\" and be stored internally as a negative number, which these systems will interpret as having occurred on 13 December 1901 rather than 19 January 2038. This is caused by integer overflow. The counter \"runs out\" of usable bits, \"increments\" the sign bit instead, and reports a maximally negative number (continuing to count up, toward zero). Resulting erroneous calculations on such systems are likely to cause problems for users and other relying parties.

Programs that work with future dates will begin to run into problems sooner; for example a program that works with dates 20 years in the future will have to be fixed no later than 2018.

Many data structures in use today have 32-bit time representations embedded into their structure. A full list of these data structures is virtually impossible to derive but there are well-known data structures that have the Unix time problem:

Examples of systems utilizing data structures that may contain 32-bit time representations include:

Any system making use of data structures containing 32-bit time representations will present risk. The degree of risk is dependent on the mode of failure.

A solution for this cane be :

storing either milliseconds or microseconds since an epoch (typically either 1 January 1970 or 1 January 2000) in a signed 64-bit integer, providing a minimum range of 300,000 years.^[18][19] Other proposals for new time representations provide different precisions, ranges, and sizes (almost always wider than 32 bits), as well as solving other related problems, such as the handling of leap seconds. In particular, TAI64^[20] is an implementation of the Temps Atomique International standard, the current international real-time standard for defining a second and frame of reference.