Algorithms and Data Structures

Abstraction

• The process of identifying orientation properties of a material object.
• Algorithm and data structure are levels of abstraction.
• An algorithm is an abstraction of a program.
• A data structure is an abstraction of similarly typed variables in a program.

Algorithm

• An algorithm is an unambiguous sequence of clear instructions
• Algorithms solve problems in a finite amount of time and terminate or halt.

Data Structure

• Represents an abstraction of the data type provided by a language.
• Elementary data types are atomic, meaning they cannot be further decomposed.
• Structured data types can be decomposed into components.
• Data structures are the organization of components and relations (e.g., Arrays, Records, Classes).

Algorithm Efficiency

• From a practical view, algorithm efficiency is measured by how well its implementation uses computer time and space.
• Execution time differs across computers, even with the same data.
• Execution time is sensitive to the amount of data it manipulates.
• Execution time depends on the implementation, including the language compiler.
• To measure efficiency, avoid implementation concepts that affect execution time.
• Algorithm analysis determines how much computing time and space is needed.

Asymptotic Notation

• Analysis of computing time ignores machine or language-dependent factors.
• "Big O-notation" is one notation used for this type of analysis.

Big O-Notation

• Defined as F(n) = O(G(n)) if there exist positive constants n₀ and c, such that |F(n)| ≤ c * |G(n)| for all n ≥ n₀.
• F(n) is the computation time, representing the number of operations for a size n.
• G(n) is the upper bound of computation time.
• C is a constant value.
• n₀ is a positive value.

Big O-Notation Examples

• Analyzing time efficiency:
  • Loop 1: For k=1 to N/2 do Begin For j=1 to N*N do Begin End End results in F(n) = O(N³).
  • Loop 2: For K=1 to N/2 do Begin End For j=1 to N*N do Begin Endimplies F(n) = O(N²).
  • Loop 3: K=N While K ≥ 1 do Begin K = K/2 Endimplies K = log₂ N.
• Big O-notation enables classification of algorithms.

Common Computing Times

• Common computing times from fastest to slowest: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ).

Algorithm Comparison Example

• Two algorithms perform the same task on 'n' inputs; one has a computing time of Kn (K ≥ 2), and the other is n².
• Big O-notation for the first algorithm is O(n) and O(n²) for the second.
• If n < K, the second algorithm (n²) is better; if n > K, the first (Kn) is better.

Different Views of Data

• Humans think of data in terms of larger units like numbers and lists.
• Computers manipulate data in terms of ‘bits.’
• Data abstraction separates the computer's view from the human's view.

Data Abstraction

• Data abstraction separates a data type’s logical properties from its implementation.
• Programmers generally don't need to know the physical representation; they only need to know how to declare a type and what operations are allowed.

Data Encapsulation

• Data encapsulation separates the representation of data from the application using it at a logical level (information hiding).
• How operations are implemented is hidden from the user

Abstraction vs. Encapsulation

• Data abstraction deals with the outside view.
• Data encapsulation deals with the inside view.
• Goal: reduce complexity.

Abstract Data Type

• Refers to the set of all possible values (domain) of an encapsulated data 'object'.
• It also specifies the operations provided to create and manipulate the data.
• Integer is an abstract data type, with operations like add, subtract, multiply, and divide.

Data Structure

• Consists of single or multiple data types, which is useful for simple data, but usually must deal with data that have lots of parts such as lists, records etc.
• Logical properties of a collection of data described as an abstract data type.
• Concrete implementation of the described data called the data structure.

Data Structure Definition

• A collection of data elements organized for storage and retrieval.
• The implementation of composite data members is an abstract data type.

Data Structure Features

• Decomposable into component elements.
• Arrangement affects how each element is accessed.
• Arrangement and access can be encapsulated.

Example: Library

• Decomposable into books.
• Books can be arranged in various ways.
• Users don't directly access books; they request them from a librarian.
• The card catalog offers logical views (author, subject).
• Physical arrangement differs from the logical arrangement.

Data Structure Definition in a Program

• A logical arrangement of data elements.
• Set of operations for data access.