Data Structures and Algorithm Complexity Concepts

Stack

An ADT useful for processing nested structures.

Dominant Term

When describing the O-notation of an algorithm we focus on this.

Binary Tree

Either the empty tree or a node that has left and right subtrees that are binary trees.

Internal Path Length

In a tree, the sum of the lengths of the paths from the root to all nodes.

In-order

A traversal order in which the nodes in a binary search tree are visited in sorted order.

Coalescing

A method to counteract the tendency toward fragmentation.

Heap

A zone of memory organized to support dynamic memory allocation of blocks of storage of differing sizes.

Trie

A tree that is insensitive to the order of insertion of the keys, but is sensitive to clustering in the spelling of the prefixes of the keys.

Extended

A binary tree that has its empty binary subtrees explicitly represented.

Complexity Class

A characterization of running times for different algorithms that share the same family of curves.

Benefit of best-fit search policy

Can reduce fragmentation.

O(n) algorithm

Will always finish before an O(n^2) algorithm only for n > n0 for some n0. For small n the lesser terms may be significant.

External Path Length

For an extended binary tree with n nodes, if the internal path length is I, then E = I + 2n.

Number of levels in a complete binary tree

For a complete binary tree with n nodes the number of levels in the tree equals floor(log2 n) + 1.

Big-O notation for organizing items in a complete binary tree

O(n).

Equation for circular queue representation

Rear = (Count + Front) % N.

Right child index in array implementation

Right child at 2i + 1 if 2i + 1 <= n.

Inorder traversal of binary search tree

Always visits the elements in the same order, regardless of the order in which the elements were inserted.

Leaves in a complete binary tree

2^(n-1) where level l is completely filled with leaves in all possible positions.

Parent index in array implementation

A[i/2] if i>1.

Arrangement of two stacks in array

S1 starts at A[0] and grows toward A[N-1]. S2 starts at A[N-1] and grows toward A[0].

Queue ADT problem solving

Useful for scenarios like shopping lines or class wait lists.

Advantages of using O() to compare algorithms

System independent, useful for algorithm comparison, constants don't matter (approximate).

Disadvantages of using O() to compare algorithms

Can't distinguish items in the same class, you throw away constants. Only true for large n; small problems might not be true.

Advantages of first-fit compared to best-fit

First-fit is faster, but may lead to larger amounts of waste.

Best situation for first-fit

Good when speed is key.

Best situation for best-fit

Best when memory is in short supply.

Ways to reduce fragmentation in free-list

Use roving pointer, use coalescing, compaction.

Usefulness of coalescing

Helps ensure that there are blocks large enough for future allocations.

Complications of coalescing

You must know memory is adjacent. The process will take some time to keep the free list sorted.