Recently I ran into a problem that asks for a data structure that efficiently allocate and recycle integer id in [0, MAX_ID). Each id can be allocated again after being recycled. The data structure runs on single machine in single thread. The goal is to optimize time and memory. An intuitive solution is to use a set to track recycled ids, and use a counter to track maximum allocated id so far.
The well known recursive binary tree inorder traversal needs O(H) space where _H_ is the height of the tree.
Macros are not covered in SICP. I didn’t know how to use macro in scheme until I read Peter Norvig’s JScheme code. Only then I started to understand why “symbol” and “quote” are important to scheme. Scheme macros is similar to C macro, both transform some pattern into another. Scheme macros are more powerful because expansion/transformation happens at run time, and input/output patterns are structured scheme data that represents scheme code.
Scheme is a beautiful language. – prof Ben Leong
This is very surprising. When I was learning C, I was convinced that array size must be determined at compile time, and I never wrote a line of code that violate this. Today, my friend (a C beginner) asked me to help him to debug his code. His code contains following lines: