| |
| |
| |
| Preparing for the Journey | |
| |
| |
| Where Are We Going? Blending Mathematics, Science, and Engineering | |
| |
| |
| The Search for Enduring Principles in Computer Science | |
| |
| |
| Principles of Software System Structure | |
| |
| |
| Efficiency and Tradeoffs | |
| |
| |
| Software Engineering Principles | |
| |
| |
| Our Approach to Mathematics | |
| |
| |
| Some Notes on Programming Notation | |
| |
| |
| Preview of Coming Attractions | |
| |
| |
| |
| Linked Data Representations | |
| |
| |
| What are Pointers? | |
| |
| |
| The Basic Intuition | |
| |
| |
| Pointers in C—The Rudiments | |
| |
| |
| Pointer Diagramming Notation | |
| |
| |
| Linear Linked Lists | |
| |
| |
| Other Linked Data Structures | |
| |
| |
| |
| Introduction to Recursion | |
| |
| |
| Thinking Recursively | |
| |
| |
| Common Pitfall—Infinite Regresses | |
| |
| |
| Quantitative Aspects of Recursive Algorithms | |
| |
| |
| |
| Modularity and Data Abstraction | |
| |
| |
| Modularity and Information Hiding in Program Design | |
| |
| |
| |
| Introduction to Software Engineering Concepts | |
| |
| |
| Top-Down Programming By Stepwise Refinement | |
| |
| |
| Proving Programs Correct | |
| |
| |
| Transforming and Optimizing Programs | |
| |
| |
| Testing Programs | |
| |
| |
| The Philosophy of Measurement and Tuning | |
| |
| |
| Software Reuse and Bottom-up Programming | |
| |
| |
| Program Structuring and Documentation | |
| |
| |
| |
| Introduction to Analysis of Algorithms | |
| |
| |
| What Do We Use for a Yardstick? | |
| |
| |
| The Intuition Behind O-Notation | |
| |
| |
| O-Notation—Definition and Manipulation | |
| |
| |
| Analyzing Simple Algorithms | |
| |
| |
| What O-Notation Doesn't Tell You | |
| |
| |
| |
| Linear Data Structures—Stacks and Queues | |
| |
| |
| Some Background on Stacks | |
| |
| |
| ADTs for Stacks and Queues | |
| |
| |
| Using the Stack ADT to Check for Balanced Parentheses | |
| |
| |
| Using the Stack ADT to Evaluate Postfix Expressions | |
| |
| |
| Implementing the Stack ADT | |
| |
| |
| How C Implements Recursive Function Calls Using Stacks | |
| |
| |
| Implementations of the Queue ADT | |
| |
| |
| More Queue Applications | |
| |
| |
| |
| Lists, Strings, and Dynamic Memory Allocation | |
| |
| |
| Lists | |
| |
| |
| Generalized Lists | |
| |
| |
| Applications of Generalized Lists | |
| |
| |
| Strings | |
| |
| |
| Dynamic Memory Allocation | |
| |
| |
| |
| Trees | |
| |
| |
| Basic Concepts and Terminology | |
| |
| |
| Binary Trees | |
| |
| |
| A Sequential Binary Tree Representation | |
| |
| |
| An Application—Heaps and Priority Queues | |
| |
| |
| Traversing Binary Trees | |
| |
| |
| Binary Search Trees | |
| |
| |
| AVL Trees and Their Performance | |
| |
| |
| Two-Three Trees | |
| |
| |
| Tries | |
| |
| |
| An Application—Huffman Codes | |
| |
| |
| |
| Graphs | |
| |
| |
| Basic Concepts and Terminology | |
| |
| |
| Graph Representations | |
| |
| |
| Graph Searching | |
| |
| |
| Topological Ordering | |
| |
| |
| Shortest Paths | |
| |
| |
| Task Networks | |
| |
| |
| Useful Background on Graphs | |
| |
| |
| |
| Hashing and the Table ADT | |
| |
| |
| The Table ADT | |
| |
| |
| Introduction to Hashing by Simple Examples | |
| |
| |
| Collisions, Load Factors, and Clusters | |
| |
| |
| Algorithms for Hashing by Open Addressing | |
| |
| |
| Choosing a Hash function | |
| |
| |
| Comparison of Searching Methods Using the Table ADT | |
| |
| |
| |
| External Collections of Data | |
| |
| |
| Characteristics of External Storage Devices | |
| |
| |
| Techniques That Don't Work Well | |
| |
| |
| Techniques That Work Well | |
| |
| |
| Information Retrieval and Databases | |
| |
| |
| |
| Sorting | |
| |
| |
| Laying Some Groundwork | |
| |
| |
| Priority Queue Sorting Methods | |
| |
| |
| Divide-and-Conquer Methods | |
| |
| |
| Methods That Insert Keys and Keep Them Sorted <B | |