EE221 Assignment 12

Program 1 (30pts.)

Write an implementation for the generic algorithm that calculates the inner product for the two data collections. The information about these collections is passed by iterators to beginning and ends of the data sets. In addition an initial value of the inner product (dot product) is also passed. Because an assumption was made that the both data collections are of the same size the end iterator for the second one is skipped.

Need a hint how to test it? Look at equals and partial_sum generic algorithm implementation and their sample test programs.

Problem 2 (30pts.)

Chapter 10, Exercise 10.4: #2, #7, #10, #11, #12, Pages 563-564.  

Problem 3 (30pts.)

After numerous homework assignments in EE303 we have discovered the following behavior of P-Spice software that is used to simulate behavior of electronic circuits before they are built in the lab or synthesized as VLSI chips:

• The program was run to simulate a 100-second behavior of a circuit that has 10 elements. The execution time was about 103 seconds.
• The program was run again to simulate a 100-second behavior of another, similar circuit that has 20 elements. The execution time turned out to be about 803 seconds.
• The program was run one more time to simulate a 200-second behavior of the original 10-element circuit. The execution time was about 203 seconds.

What can you tell about the numerical complexity of the algorithm used in the program as a function of element count E in a circuit? (10pts.) And as a function of the simulated time T? (10pts.)

In your most recent homework assignment Professor Irwin asked to design and simulate a "monster-size" circuit of 100 components that are connected in several clusters that can be assume to be independent. We call this circuit of a "monster size" as you never did so huge design, and are still to find out in the future that it is actually a relatively small circuit as for real-life complexity circuits. Anyway, after attempting to isolate those clusters you concluded that you have can run the software either:

• once for the data volume of 100
• or twice, for the data volumes of 50 and 50
• or three times for data volume of 40 and 30 and 30

Assume that you would run next simulation immediately after the previous one is done, and that the overhead related to starting a new simulation can be neglected. Calculate how much time it would take to perform each set of simulations. Which choice will produce the result fastest? How much time it could take? (10pts.

You must show your work or provide valid reasoning to get any credit. If you make a mistake in the first part (complexity with respect to E(lements) and to T(ime)) but would come up with somewhat reasonable data that you use in the second part we will attempt to grade the second d part and give you a partial credit.