Open Data Structures in Pseudocode
Subject: Computer Science and Data Structures
Author or source: Pat Morin
Updated:
Complete 326-page pseudocode edition by Pat Morin, covering lists, hash tables, search trees, heaps, graphs and B-trees with algorithm analysis and exercises.
Overview of the complete resource
Source page 1–326
This complete textbook explains how data structures store sequences, sets and graphs, and how to compare their running time and memory use. It starts with interfaces and asymptotic analysis, then develops array-based lists, linked lists, skip lists, hashing, binary trees, treaps, scapegoat trees, red-black trees, heaps, sorting, graphs, integer search structures and external-memory B-trees. The pseudocode edition is language-independent; the accompanying Carleton lectures use Java and are supplementary. Work through the implementation and analysis together, then try the chapter exercises. This is a book overview, not a page-by-page solution manual.
Original textbook: introduction preview
Source page 13
Chapter 1 Introduction Every computer science curriculum in the world includes a course on data structures and algorithms. Data structures are that important; they im- prove our quality of life and even save lives on a regular basis. Many multi-million and several multi-billion dollar companies have been built around data structures. How can this be? If we stop to think about it, we realize that we inter- act with data structures constantly. • Open a file: File system data structures are used to locate the parts of that file on disk so they can be retrieved. This isn’t easy; disks contain hundreds of millions of blocks. The contents of your file could be stored on any one of them. • Look up a contact on your phone: A data structure is used to look up a phone number in your contact list based on partial information even before you finish dialing/typing. This isn’t easy; your phone may contain information about a lot of people—everyone you have ever contacted via phone or email—and your phone doesn’t have a very fast processor or a lot of memory. • Log in to your favourite social network: The network servers use your login information to look up your account information. This isn’t easy; the most popular social networks have hundreds of mil- lions of active users. • Do a web search: The search engine uses data structures to find the web pages containing your search terms. This isn’t easy; there are 1