Assignment 1 solutions
the homework for 22C:50, Summer 2004
A complete binary tree with n leaves has n-1 internal nodes for a total of 2n-1 nodes. Every node but the root has an edge leading to it, so we have 2n-2 edges.
A pair of integers would require 2 32-bit words, or 8 bytes. A string of k ASCII characters would require k bytes, so we can say, naively, that the storage for n items of this kind will be n(k+8) bytes.
But, many compilers will round up to the nearest word, so we actually use 4(ciel(k/4)) bytes for the string, where ciel(x) is the nearest integer greater than or equal to x. This means the actual requirement will be more likely to be n(4ciel(k/4)+8) bytes.
The steriotypical CPU operates by repeatedly fetching an instruction from memory and then executing it. This is called the fetch-execute cycle.