Close
Register
Close Window

DSA Coursenotes

Chapter 0 Week 1

Show Source |    | About   «  0.1. Course Introduction   ::   Contents   ::   0.3. Project 1 Design  »

0.2. Data Structures and Algorithm Analysis Introduction

0.2.1. Introduction

0.2.1.1. Course Introduction

Content Goals for this Course

  • Reinforce the concept that costs and benefits exist for every data structure.

  • Learn the commonly used data structures.
    • These form a programmer’s basic data structure “toolkit”.

  • Understand how to measure the cost of a data structure or program.
    • These techniques also allow you to judge the merits of new data structures that you or others might invent.

0.2.1.2. Costs and Benefits

  • Each data structure has costs and benefits.
    • Rarely is one data structure better than another in all situations.

    • We talk about a lot of data structures and algorithms that have stood the test of time.

  • Any data structure requires:
    • space for each data item it stores,

    • time to perform each basic operation,

    • programming effort.

  • Only after a careful analysis of problem characteristics can we know the best data structure for a task.

0.2.1.3. Data Structure: Definition

  • A data structure is the physical implementation of an ADT.
    • Each operation associated with the ADT is implemented by one or more subroutines in the implementation.

  • Data structure usually refers to an organization for data in main memory.

  • File structure: an organization for data on peripheral storage, such as a disk drive.

0.2.1.4. Logical vs. Physical Form

  • Data items have both a logical and a physical form.

  • Logical form: definition of the data item as an ADT.

    • Ex: Integers in mathematical sense: operators +, -

  • Physical form: implementation of the data item within a data structure.

    • Ex: 32/64 bit integers, overflow.

0.2.1.5. Logical vs. Physical Form (2)

   «  0.1. Course Introduction   ::   Contents   ::   0.3. Project 1 Design  »

nsf
Close Window