Contents: CS2
From
(Difference between revisions)
(→Linear Structures) |
m (→Data Structures and Abstract Data Types) |
||
| (48 intermediate revisions not shown) | |||
| Line 1: | Line 1: | ||
| - | + | This is an online, interactive text for exploring the concepts and topics normally taught in the ACM CS2 course. This online text as of Spring 2009 does have quite a bit of content, but is currently under development and certainly not close to complete. [[Credits to the primary content contributors]] | |
== Data Structures and Abstract Data Types == | == Data Structures and Abstract Data Types == | ||
| - | A data structure is a means of organizing data in a computer’s memory to try to optimize either the memory | + | A data structure is a means of organizing data in a computer’s memory to try to optimize either the memory usage or the time to access the data. This brings up the classic trade-off in Computer Science: the trade-off between Time and Space. In most situations today, it seems that we are primarily interested in minimizing the Time aspect. But, given smaller and smaller devices that increasingly do more (think of the evolution of the cell phone), minimizing the Space aspect can be important also. |
| - | + | <br/><br/> | |
There is sometimes a difference made between a data structure and an abstract data type (ADT). An ADT describes the public interface of a data structure: the type of data and the valid operations on the data. An ADT, however, does not consider an implementation, and this is the essential difference. | There is sometimes a difference made between a data structure and an abstract data type (ADT). An ADT describes the public interface of a data structure: the type of data and the valid operations on the data. An ADT, however, does not consider an implementation, and this is the essential difference. | ||
| + | <br/><br/> | ||
== Introduction to Computability and Complexity == | == Introduction to Computability and Complexity == | ||
*[[Computability and Complexity|Overview of computability and complexity]] <br/> | *[[Computability and Complexity|Overview of computability and complexity]] <br/> | ||
*[[Asymptotic Measures|Asymptotic Measures]] <br/> | *[[Asymptotic Measures|Asymptotic Measures]] <br/> | ||
| - | *[[ | + | *[[CS2/Empirical Measures|Empirical Measures]] <br/> |
<br/> | <br/> | ||
== Algorithms == | == Algorithms == | ||
| - | *[[Algorithms and | + | *[[Algorithms and Psuedocode|Overview of Algorithms and Psuedocode]] <br/> |
*[[Searching|Seaching]] <br/> | *[[Searching|Seaching]] <br/> | ||
*[[Sorting|Sorting]] <br/> | *[[Sorting|Sorting]] <br/> | ||
| Line 21: | Line 22: | ||
== Preliminaries of Data Organization == | == Preliminaries of Data Organization == | ||
*[[Memory Allocation|Memory Allocation]] <br/> | *[[Memory Allocation|Memory Allocation]] <br/> | ||
| - | *[[Primitive | + | *[[Primitive and Composite Structures]] <br/> |
*[[Concept of an Element (Node)|Concept of an Element (Node)]] <br/> | *[[Concept of an Element (Node)|Concept of an Element (Node)]] <br/> | ||
*[[Abstract Data Types|Abstract Data Types]] <br/> | *[[Abstract Data Types|Abstract Data Types]] <br/> | ||
| Line 27: | Line 28: | ||
== ADTs and Data Structures == | == ADTs and Data Structures == | ||
| - | |||
===Linear Structures=== | ===Linear Structures=== | ||
| - | *[[ | + | *[[Linear ADTs|Overview of Linear Abstract Data Types]] <br/> |
*[[Stacks|Stacks]] <br/> | *[[Stacks|Stacks]] <br/> | ||
*[[Queues|Queues]] <br/> | *[[Queues|Queues]] <br/> | ||
| - | <br/> | + | *[[Lists|Lists]] <br/> |
===Trees=== | ===Trees=== | ||
| - | + | *[[Tree ADTs|Overview of Tree Abstract Data Types]] | |
| - | + | *[[Binary Trees|Binary Trees]] <br/> | |
| - | + | **[[Binary Search Trees]] <br/> | |
| - | + | **[[AVL Trees]] <br/> | |
| - | + | **[[Red-Black Trees]] <br/> | |
| - | + | **[[Splay Trees]] <br/> | |
| - | + | **[[Heaps]] <br/> | |
| - | <br/> | + | *[[Multi-Way Trees]] <br/> |
| + | **[[B-Trees]] <br/> | ||
| + | **[[B+Trees]] <br/> | ||
| + | *[[General Trees]] <br/> | ||
| + | |||
===Graphs=== | ===Graphs=== | ||
| - | <br/> | + | *[[Graph ADTs|Overview of Graph Abstract Data Types]] <br/> |
| - | === | + | *[[Representing Graphs]] <br/> |
| - | + | *[[Variations of Graph ADTs]] <br/> | |
| - | + | *[[Common Graph Algorithms]] <br/> | |
| - | + | ||
| - | + | ===Unordered Collections=== | |
| + | *[[Unordered Collection ADTs|Overview of Unordered Collection Abstract Data Types]] | ||
| + | *[[Sets and MultiSets (Bags)]] <br/> | ||
| + | *[[Maps and Dictionaries]] <br/> | ||
| + | *[[Hash Tables]] <br/> | ||
<br> | <br> | ||
| + | ---- | ||
| + | {{CS2/ChapNav}} | ||
| + | ---- | ||
| + | [[Category:CS2|{{SUBPAGENAME}}]] | ||
Current revision as of 08:08, 15 January 2010
This is an online, interactive text for exploring the concepts and topics normally taught in the ACM CS2 course. This online text as of Spring 2009 does have quite a bit of content, but is currently under development and certainly not close to complete. Credits to the primary content contributors
Contents |
Data Structures and Abstract Data Types
A data structure is a means of organizing data in a computer’s memory to try to optimize either the memory usage or the time to access the data. This brings up the classic trade-off in Computer Science: the trade-off between Time and Space. In most situations today, it seems that we are primarily interested in minimizing the Time aspect. But, given smaller and smaller devices that increasingly do more (think of the evolution of the cell phone), minimizing the Space aspect can be important also.
There is sometimes a difference made between a data structure and an abstract data type (ADT). An ADT describes the public interface of a data structure: the type of data and the valid operations on the data. An ADT, however, does not consider an implementation, and this is the essential difference.
Introduction to Computability and Complexity
Algorithms
Preliminaries of Data Organization
- Memory Allocation
- Primitive and Composite Structures
- Concept of an Element (Node)
- Abstract Data Types
ADTs and Data Structures
Linear Structures
Trees
Graphs
- Overview of Graph Abstract Data Types
- Representing Graphs
- Variations of Graph ADTs
- Common Graph Algorithms
Unordered Collections
- Overview of Unordered Collection Abstract Data Types
- Sets and MultiSets (Bags)
- Maps and Dictionaries
- Hash Tables
CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs
