Comments on Homework 10

General comments/advice:

Make sure you fully explain how you are using data structures e.g. for a dictionary or search tree, what are the key-value pairs?
Be suspicious if there is information that you aren't using — while it is possible that a more general solution is as efficient as you can get, you should at least think about whether what you know about the data can be exploited.

Design a dictionary data structure in which search, insertion, and deletion can all be processed in O(1) time in the worst case. You may assume the set elements are integers drawn from a finite set 1, 2, .., n, and initialization can take O(n) time.

A hashtable doesn't quite solve this — insert, search, delete in a hashtable are O(1) expected time, not O(1) worst case as required here, and good performance requires N > n but initialization is required to be O(n).

Make use of the knowledge that the elements being stored are integers 1, 2, ..., n.
Let A[1..n] be an array of real numbers. Design an algorithm to perform any sequence of the following operations:

Add(i,y) — Add the value y to the ith number.
Partial-sum(i) — Return the sum of the first i numbers, that is,

There are no insertions or deletions; the only change is to the values of the numbers. Each operation should take O(log n) steps. You may use one additional array of size n as a work space.

AVL trees are search trees. For any search tree, identify what is the key and (if there's an additional element) what is the element. This is necessary to understand how find and other operations work.

AVL trees are dynamic data structures that keep the tree balanced after insertions and deletions. Use all the information you have — there aren't any insertions or deletions in this application, so a O(log n) height tree can be built from the start and dynamic balanced trees like AVL trees are overkill. (And may be detrimental — does anything besides balance factors need to be updated during a restructuring?)

Adding i values for the partial sum is O(i) work, not O(log n). A binary tree does not automatically make all operations O(log n) — it is necessary to limit nodes visited to those along a leaf-to-root path.