Hussein Thompson
Abstract
This article presents an alternative visual analysis of the BUILDHEAP algorithm provided by Goodrich and Tamassia [4]. The analysis is based only on elementary properties of complete binary trees and a simple comparison of the areas of rectangles. As such, it should be accessible to a wide cross-section of students taking a typical algorithm design and analysis course.
- Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Boston, MA, 1974. Google Scholar
Digital Library
- Blaheta, D. 2009. A visual proof of amortised-linear resizable arrays. In Proceedings of the 14th Annual ACM SIGCSE Conference on Innovation and Technology in Computer Science Education (Paris, France, July 06-09, 2009). ITiCSE '09. ACM, New York, NY, 338--338. DOI= http://doi.acm.org/10.1145/1562877.1562979. Google ScholarDigital Library
- Thomas T. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990. Google ScholarDigital Library
- Goodrich, M. T. and Tamassia, R. 1998. Teaching the analysis of algorithms with visual proofs. SIGCSE Bull. 30, 1 (Mar. 1998), 207--211. DOI=http://doi.acm.org/10.1145/274790.274298. Google ScholarDigital Library
- Hammack, R. H. and Lyons, D. W., Alternating series convergence: A visual proof, Teaching Mathematics and its Applications, 25, 2 (2006) 58--60, DOI=10.1093/teamat/hri005.Google Scholar
- Udi Manber, Introduction to Algorithms: A Creative Approach. Addison-Wesley, Boston, MA, 1989. Google ScholarDigital Library
- Bruno Preiss, Data Structures and Algorithms with Object-Oriented Design Patterns in C++, Wiley, New York, NY, 1999. Google ScholarDigital Library
- Sher, D. B. 2008. A visual proof for an average case of list searching. SIGCSE Bull. 40, 2 (Jun. 2008) 74?78, DOI= http://doi.acm.org/10.1145/1383602.1383639. Google ScholarDigital Library
Index Terms
- An alternative visual analysis of the build heap algorithm
Recommendations
A visual proof of amortised-linear resizable arrays
ITiCSE '09: Proceedings of the 14th annual ACM SIGCSE conference on Innovation and technology in computer science educationWe demonstrate visually why doubling capacity is the better strategy when resizing arrays. The visual proof makes simple amortised analysis more accessible to a CS2 audience.
Analysis of the rubberband algorithm
We consider simple cube-curves in the orthogonal 3D grid of cells. The union of all cells contained in such a curve (also called the tube of this curve) is a polyhedrally bounded set. The curve's length is defined to be that of the minimum-length ...
Reducing sweep time for a nearly empty heap
POPL '00: Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesMark and sweep garbage collectors are known for using time proportional to the heap size when sweeping memory, since all objects in the heap, regardless of whether they are live or not, must be visited in order to reclaim the memory occupied by dead ...
Comments