Data Structures & Algorithms

Data Structures

• A way of storing data in a computer for efficient use.
• Organizes data considering the items stored and their relationships.
• Allows designing efficient algorithms for data manipulation.
• Different data structures suit different applications.
• Examples:
  • B-trees for databases.
  • Hash tables for compiler implementations.

Importance of Data Structures

• Used in almost every program or software system.
• Manages huge amounts of data efficiently.
• Key to designing efficient algorithms.
• Algorithms + Data Structures = Programs

Basic Types of Data Structures

• Files
• Lists
• Arrays
• Records
• Trees
• Tables

Algorithm

• A formula or set of steps for solving a particular problem.
• Must be unambiguous and have a clear stopping point.
• Can be expressed in any language.
• Algorithms are used every day.
• Creating simple algorithms is a principal challenge in programming.

Properties of an Algorithm

• Input: Accepts zero or more inputs.
• Output: Produces at least one output.
• Finiteness: Terminates after a finite number of steps.
• Definiteness: Each step is unambiguous.
• Effectiveness: Consists of basic, realizable instructions.
• Generality: Works for a general set of inputs.

How to Represent Algorithms

• Natural languages: Too verbose.
• Formal programming languages: Too low level.
• Pseudo-code: Natural language constructs modeled after programming languages.
• Flowchart: Diagram representing an algorithm or process.

Algorithm Representation Examples

• Natural language
• Pseudo-code
• Flowchart

Data Structures and Algorithms

• Most algorithms operate on data collections, so define Collection Abstract Data Type (ADT)
• Methods:
  • Constructor / Destructor
  • Add / Edit / Delete
  • Find
  • Sort
  • ….