Data Structure X Algorithm

★★★★★ Super tricky, wtf

★★★★☆ Can image, but still super hard

★★★☆☆ Can get the thoughts, but detail is hard

★★☆☆☆ Can solve, but needs review

★☆☆☆☆ Can solve, quite familiar

☆☆☆☆☆ Too basic...

From 15-651 lecture note of D. Sleator

A data structure is a way of representing information in a computer and a set of procedures for accessing and updating the information.

These procedures for accessing and updating the information are called the operations on the data structure.

There are two fundamentally different ways in which data structures are used.

• They are used as part of an information retrieval system,
• They are used as one component of an algorithm whose purpose is to solve some other problem.

Why do we have data structures? In the first application the purpose of the data structure is obvious, for the data structure itself is solving the problem that we want to solve.

In the second application, the reason for having data structures is not so obvious. In this case our motivation for creating them is to aid in our conception of the algorithm. By using a data structure as a component of an algorithm, we split the problem of `creating or expressing the algorithm into two parts. Once the interface between these two parts has been specified, these two components of the problem can be solved (or expressed) separately.

The interface between a data structure and the algorithm that uses it consists of two parts:

• A set of operations that allow the algorithm to access and update the data structure.
• Constraints that say how much time (or space) each operation is allowed to use in order for the algorithm to perform with the desired efficiency.