Exam 3 Review

  1. IO vocabulary:
  2. Record
  3. Field
  4. Delimiter
  5. Parse
  6. Token
  1. Formatting with fprintf.
  2. Syntax for fprintf.
  3. Escape character for formatting output.
  4. Right and left justify.
  5. Field size.
  6. Precision specifier.
  7. Conversion characters.
  8. Write an fprinf statement to print a string in variable x, right justified from the 25th column on a page.
  9. Write an fprintf statement to print the value in scientific notation left justified with two digits to the right of the decimal.
  10. Show what is printed in each column of a page with:

fprintf( ‘%10s\n%10.3f\n%-10.2E\n’, ‘Matlab’, 3.14, 6.02e23 );

fprintf( ‘%5.1f%5.1f’, 2.1, 3.2 );

  1. Use nested loops using exactly three fprintf statements to output the figure shown here:

&

&

  1. Data stored in the vectors x and y are shown to have a linear relationship when viewed on a scatter diagram. Write Matlab statements to solve for the slope and y-intercept of the best fitting line:
  1. Consider the system of linear equations: . Explain how if a small error, is added to the input data,; the result may not be close to the desired solution for .
  1. Estimate the number of operations for each problem and write the order of operations using big-O notation, O(h) :
  2. sum(x); % Iterative algorithm where x has n values.
  3. fibI(n); % Iterative algorithm where n is the n-th Fibonacci number.
  4. factorial(n); % Iterative algorithm where the return value is n!.
  5. for ( k=1 : 1 : n )

a(k) = b(k)*sqrt(b(k))-c*a(k); % how many visits here?

end

  1. for ( k=1 : 1 : n )

for ( h=1 : 1 : k )

b(k) = x*b(k) + a(k,h)*c(h); % how many visits here?

end

end

  1. for ( k=1 : n )

for ( h=1 : m )

for ( a=1 : p )

b(k,h,a) = 2*b(k,h,a) + c(k,h,a); % how many visits?

end

end

end

  1. The following code fragment is

for ( k=1 : sqrt(n) )

for ( h=1 : m )

B = myAlogorithm( A, n, m ) % how many visits?

end

end

What is the big-O order for the function myAlogorithm?

  1. Explain stable sort compared to an unstable sort.
  1. What three criteria are used for determining an appropriate sorting algorithm?
  1. What are the three properties required for a recursive algorithm to work correctly?
  1. Write a function to recursively compute factorial.
  1. Write a function to recursively compute the nth Fibonacci number.
  1. Write a recursive function to return the reverse the order of an input vector.
  2. While testing a new simulation algorithm, you discover that 500 data records completes in 24.99 seconds. You double the number of records and the same test takes 100.001 seconds. Your boss asks you to run a large simulation for a client with 10000 records. Assuming you can start the simulation within the next hour, how long will it take to complete if the algorithm is and m must be a whole number?
  1. Fill in the following table. Show the approximate growth rate of the execution times depending on the complexity of the algorithm.

n / O(n) / / / /
1000 / 4 sec / 3sec / 1 sec / 5 sec / 2 sec
2000
4000
  1. The condition number for a dense matrix is 97. How many digits of precision are expected to be lost when inverting the matrix? If four digits of precision are needed for the solution, is it acceptable to use single precision 32 bit IEEE floating point arithmetic?
  1. You are working with a vendor provided solver program. The precision of the solver is a function of input value h, and error the error is . A test run with known solution shows the computed result has an error of 8.e-005. When you cut the value of h in half, the computed error is 1.e-005. Determine the order of precision for the solver program by finding m in the expression.
  1. You have developed a new algorithm which takes 100 seconds to complete 1024 records (1024=) . The computational growth rate for your new algorithm is proportional to , where h is the number of records. How long will it take to complete 1,048,576 records (1,048,576=) using your new algorithm? Give your answer in seconds. Note that .
  1. Numerical techniques like Simpson’s Rule and the Trapezoid Rule involve dividing the area under the curve into strips. The strips under the curve all have an equal length base represented as h. As h approaches zero, our estimate for the integral approaches the true solution. Assume the Trapezoid Rule is second order accurate, O(), (the error is proportional to ). If we reduce the size of h by a factor of 8, what will happen to the error in our integral estimate?
  1. Let A be an n-by-n matrix. List reasons why solving the system of equations, for the unknownsmight be difficult or impossible.
  1. Let A be an n-by-n matrix. Explain why it’s important to know the condition number of matrix A before attempting to solve the system of equationsfor the unknowns.
  2. What is the difference between a recursive function and a function using iteration?
  1. How is the inv function used in Matlab?
  1. What can be said about changing the order of operations on a calculation using a computer? Example: A*B + A*C == A*(B + C)
  1. Write a function to generate a square Hilbert matrix (see lab 13 for a definition of a Hilbert matrix).
  1. Let x and y be vectors each containing n data items.The variable r represents the linear correlation coefficient for the data contained in x and y. Write a single Matlab statement that includes the Matlab sum function (don’t use any loops!) to compute r using the formula shown here:

Note: = sum( x )

  1. Use nested loops using exactly two fprintf statements (each printing exactly one character) to output the separate figures shown here:

and separately

  1. Define cache in the context of computer hardware.
  1. A cpu processor has 4 cores and has a clock rating of 3.5 GHz. If this processor requires 5 cycles per instruction and 14 instructions per division operation, how many division operations can be computed in one second given all 4 cores can work independently?
  1. What is the difference between volatile and non-volatile memory?
  1. What is the difference between SDRAM and SRAM?
  1. Describe differences between DDR3 SDRAM and DDR2 SDRAM?
  1. What is a motherboard in the context of computer hardware?
  1. Describe the topology for disk storage. Draw a diagram.
  1. What are the metrics for disk performance?
  1. What is RAID in the context of disk storage?
  1. What is RAID-0?
  1. What is RAID-1?
  1. What is RAID-5?
  1. Describe how parity is implemented in a RAID-5 system.
  1. What are the factors used to determine overall disk IO speed?
  1. Draw a diagram of each of these physical network topologies: bus, ring, star, mesh, compound.
  1. What is the difference between a level-2 network switch and a level-3 network switch?
  1. What is Ethernet? Describe the wired Ethernet protocol using a switch. CSMA/CD
  1. What is the 802.11_ Project? Describe the wireless handshake for the 802.11 protocol using ACK, RTS, CTS in your description.
  1. Why is a wired network faster than a wireless network under the same demand? CSMA/CA
  1. What is TCP/IP?