Monday, June 20, 2011

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 10

The authors define STACK and QUEUE and operations like PUSH, POP on STACKS and ENQUEUE and DEQUEUE on QUEUES. The authors also prove all the operations to take $ O(1) $ time.

The authors then define LINKED-LIST, provide a list of its variants like DOUBLY-LINKED-LIST and CIRCULAR-LINKED-LIST. The authors also provide variants on whether the list is maintained sorted or unsorted. The authors also define SEARCH, INSERT and DELETE operations on the list with running time of $ \Theta(n) $, $ O(1) $ and $ \Theta(n) $ respectively.

The authors then provide a way to implement pointers and objects in FORTRAN, a programming language which does not support their usage.

The authors then provide a way to implement binary tree using linked list. The authors also provide left-child right-sibling representation of a tree and a way to represent trees with more than two children for each node as binary trees.

No comments:

Post a Comment