Lecture Notes for SE 598, Data Structures and Algorithms

24 May 2000, Data Structures and Algorithms

1. data structures

   1. what do programs do

      1. model the world, or some small piece of it

   2. how do data structures help model the world

      1. data structures are the model

         1. the value held by a data structure represents some specific characteristic of the world

         2. the characteristic being modeled restricts the possible values held by a data structure

         3. notice the relation between characteristic, value, and data structures

   3. what's the problem - there are lots of characteristics

      1. do all characteristics need to be modeled

         1. no - it depends on the model

         2. no - it depends on the reason for developing the model

      2. abstraction is the process of

         1. classifying characteristics as important or unimportant

         2. throwing away (or ignoring) the unimportant characteristics

      3. correctly applying abstraction is the essence of successful programming

2. algorithms

   1. is that it - programs (that is, data structures) model the world

   2. are data structures good models of the world

      1. it depends on the reasons for developing the model

      2. generally speaking, data structures are not good models of the world

      3. data structures are unchanging, while the world is changing

   3. algorithms are the dynamic part of a program's world model

      1. an algorithm transforms data structures from one state to another state

         1. an algorithm may change the value held by a data structure

         2. an algorithm may change the data structure itself (change of world characteristics)

      2. but again, there are lots of changes in the world

         1. the reason for the model determines the important changes

         2. abstraction again - the important and unimportant changes

3. a recap

   1. 

4. so what

   1. the quality of a data structure is related to its ability to successfully model characteristics of the world

      1. is the model accurate

      2. is the model concise

      3. there are many other possibilities

   2. similarly, the quality of an algorithm is related to its ability to successfully simulate changes in the world.

   3. however, independent of any particular world model, the quality of data structures and algorithms is determined by their ability to work together well

      1. the correct data structures lead to simple and efficient algorithms

      2. the correct algorithms lead to accurate and efficient data structures

      3. the air-line seat reservation example

This page last modified on 24 May 2000.