Think about correctness (20 points) in class we discussed the interval scheduling problem: given a set i of jobs [s, e], where s is the start time and e > s is the end time, select a subset s of i containing a maximal number of non-overlapping jobs. (if you missed class that day, you can find examples and more discussion of this problem in section 1.2 of the text by skeina, available online through the isu library.) here is a proposed algorithm to solve this problem: start with an empty set s while i is nonempty find the job j such that the midpoint (s e) / 2 is earliest remove j from i remove all jobs from i that overlap j add j to the solution s decide whether the algorithm is correct. if you believe it is correct, give an informal explanation for why it works. if you believe it is incorrect, provide a test case on which it fails (counterexample).

When making changes to optimize part of a processor, it is often the case that speeding up one type of instruction comes at the cost of slowing down something else. for example, if we put in a complicated fast floating-point unit, that takes space, and something might have to be moved farther away from the middle to accommodate it, adding an extra cycle in delay to reach that unit. the basic amdahl's law equation does not take into account this trade-off. a. if the new fast floating-point unit speeds up floating-point operations by, on average, 2ă—, and floating-point operations take 20% of the original program's execution time, what is the overall speedup (ignoring the penalty to any other instructions)? b. now assume that speeding up the floating-point unit slowed down data cache accesses, resulting in a 1.5ă— slowdown (or 2/3 speedup). data cache accesses consume 10% of the execution time. what is the overall speedup now? c. after implementing the new floating-point operations, what percentage of execution time is spent on floating-point operations? what percentage is spent on data cache accesses?

Johnson enterprises uses a computer to handle its sales invoices. lately, business has been so good that it takes an extra 3 hours per night, plus every third saturday, to keep up with the volume of sales invoices. management is considering updating its computer with a faster model that would eliminate all of the overtime processing.

Write a program that reads in a series of lines of input character by character (using the library function the first line of the input contains an integer which specifies the number of remaining lines of input, each of which contains a floating point number. the integer value on the first line can be read with (the library function) but all of the following lines can only be read with each line, after the first, contains a single floating point value, with up to four digits before the decimal point, and up to four digits following the decimal point, but there is not necessarily a decimal point in each number; i.e., it may appear to be an integer, but the digits should be read by your program, and the number should be converted to a corresponding floating point number. for instance, suppose the following input: 5 3.1255 20.25 0.875 1921.50 31 the required output is: − each of the input floating point values, printed on a separate line with four digits of precision, using printf(); − on the last line of the output, the string “total: ” followed by the sum of the input values, printed with printf() to 4 digits of precision. for example, the total of the sample input given above is 1976.7505, so the required output for this input would be: 3.1255 20.2500 0.8750 1921.5000 31.0000 total: 1976.7505 do not concern yourself with small differences in the total due to rounding, as the grader will not deduct points for this. constraints: − you are not allowed to use arrays on this portion of the lab assignment. − there is no maximum number of lines allowable. it all depends upon the first value of input. since you aren’t saving anything, it doesn’t matter. − you can assume that input will not contain more than 4 digits before or after the decimal point. you do not need to error check for this condition. -you must use getchar() to read in the floating point values one character at a time (i.e. do not use -you must declare and use your floating point values as a double to minimize rounding errors. -only use printf() to output the floating point numbers and the total (do not use − be sure your directions to the user are clear so they are sure to enter the input data correctly.