tailieunhanh - Lecture NotesCMSC 420CMSC 420: Data Structures1 Spring 2001

The defining feature of modern computers which distinguishes them from all other machines is that they can be programmed. That is to say that some type of instructions (the program) can be given to the computer, and it will process them. Modern computers based on the von Neumann architecture often have machine code in the form of an imperative programming language. | Lecture Notes CMSC 420 CMSC 420 Data Structures1 Spring 2001 Dave Mount Lecture 1 Course Introduction and Background Tuesday Jan 30 2001 Algorithms and Data Structures The study of data structures and the algorithms that manipulate them is among the most fundamental topics in computer science. Most of what computer systems spend their time doing is storing accessing and manipulating data in one form or another. Some examples from computer science include Networking Suppose you need to multicast a message from one source node to many other machines on the network. Along what paths should the message be sent and how can this set of paths be determined from the network s structure Information Retrieval How does a search engine like Google store the contents of the Web so that the few pages that are most relevant to a given query can be extracted quickly Compilers You need to store a set of variable names along with their associated types. Given an assignment between two variables we need to look them up in a symbol table determine their types and determine whether it is possible to cast from one type to the other say because one is a subtype of the other . Computer Graphics You are designing a virtual reality system for an architectural building walk-through. Given the location of the viewer what portions of the architectural design are visible to the viewer In many areas of computer science much of the content deals with the questions of how to store access and manipulate the data of importance for that area. In this course we will deal with the first two tasks of storage and access at a very general level. The last issue of manipulation is further subdivided into two areas manipulation of numeric or floating point data which is the subject of numerical analysis and the manipulation of discrete data which is the subject of discrete algorithm design. An good understanding of data structures is fundamental to all of these areas. What is a data structure Whenever we .