William Ehlhardt (wehlhard@purdue.edu)
Scott Pillow	 (spillow@purdue.edu)

Project 2 Report:

Sample file: r1_top.txt
Max_dly:
max_dly_nodes = 38, 
max_dly = 2.517582e-08

Min_dly:
min_dly_nodes = 115, 
min_dly = 2.011987e-08

Elapsed time: 0

Sample file: r2_top.txt
Max_dly:
max_dly_nodes = 282, 
max_dly = 6.689053e-08

Min_dly:
min_dly_nodes = 583, 
min_dly = 4.958650e-08

Elapsed time: 0.01

Sample file: s1423_top.txt
Max_dly:
max_dly_nodes = 23, 
max_dly = 7.613585e-10

Min_dly:
min_dly_nodes = 1, 
min_dly = 3.951586e-10

Elapsed time: 0

Sample file: s5378_top.txt
Max_dly:
max_dly_nodes = 108, 
max_dly = 1.635932e-09

Min_dly:
min_dly_nodes = 5, 
min_dly = 8.354516e-10

Elapsed time: 0




Runtime complexity: O(n)
All the timing calculation functions are recursive traversals (usually some mix of pre- and post-order, depth-first).

Space complexity: O(n)
Since the timing functions were all depth-first tree traversals, the stack overhead for them was O(log(n)). However, we also added several "partial result" variables to each node, which adds O(n) space beyond that required to represent the original node list in memory. Although the nodes of the tree were never copied, extra fields were necessary to store data that would be used to calculate the current node's delay.

Comments:
The initial code written was O(n^2) (we think - we didn't analyze it) because each node delay value was calculated in a brute-force fashion, brainlessly comparing each node to every other node. 

The version we ended up turning in computed partial results for each node, not bothering to compute a delay value for the node unless it was a leaf node.

First of all, we traversed the tree to determine the source-to-this-node resistance for every node in the tree. In this traversal, we also determined a value Ctree for each node, where Ctree is the sum of the capacitances for the node and all its children.

Next, we traversed the tree again, this time calculating a partial sum of the C*R^2 term for each node in the tree. This was known as the node's "parent contribution", and represented the value of that term that needed to be added due to the part of the tree connected to the node through its parent pointer.

The use of partial results for each node greatly sped things up, as we could calculate a certain value once, and then store it, making future uses of that value very much faster.

Optimization:
As well as the above-mentioned optimizations that reduced the problem order to O(n), we also did some low-level optimizations that are possible with C, such as:
- Using pointers instead of array indices to represent the Parent and Child fields.
- Used algebra to speed up our various math operations (such as multiplying twice instead of calling pow())
- Minimized the branches possible in the code, which tends to result in a speedup on modern CPUs.

Contributions (William Ehlhardt):
- Unit testing.
- Repository administration and organization
- Code cleanup work
- Some by-hand tests
- Some of the report

Contributions (Scott Pillow):
- Rough outline of main
- Loading function
- By-hand tests to verify correctness
- Some of the report