INTRO TO DATA STRUCTURE AND ALGORITHM

DATA STRUCTURE AND ALGORITHM

  • Author: Marisol D. Payra

PRE-REQUISITES

  1. Basic Knowledge in Programming

    • Arrays

    • Loops

    • Conditional Statements

    • Functions and Methods

    • Object-Oriented Programming (Optional)

  2. Specific IDE for your Programming Language

WHAT IS DATA AND INFORMATION

  • Data: A collection of numbers, symbols, and characters that is raw and unorganized.

  • Information: An organized collection of data that is arranged meaningfully.

WHAT IS DATA STRUCTURE

  • A data structure represents data and the operations allowed on that data.

  • It serves as a way to store and organize data to facilitate access and modifications.

  • Data structures represent logical relationships between data elements related to a specific problem solution.

  • They consider time and space efficiency for operations on data.

SUBJECT APPROACH

THEORIES AND ALGORITHM

  1. Analyze data structures and algorithms via real-life scenarios to comprehend data flow.

  2. Implementation: Use specific programming languages to apply these data structures.

WHY DO WE NEED DATA STRUCTURE

  • Efficiently store data in specific situations.

  • Utilize resources productively.

REAL SCENARIO EXAMPLES

  • Stored Alphabetically: Efficient searching technique.

SUPERMARKET EXAMPLE

  • Pet Food Categories:

    • 14 + 13 (Pet Supplies: 2, 11)

    • Stored categorically for efficient searching.

VARIABLES

  • Temporary storage for data, which is stored in RAM.

ARRAY/COLLECTIONS

  • A data structure containing a group of values/variables accessed via an index.

  • Typically contain values of the same data type.

  • Commonly used to organize data for sorting or searching.

PROGRAMMING APPLICATION: ARRAY IN C++ (WITHOUT SORTING)

  • Example Code:

    string rooms[4] = {"RM-103", "RM-104", "RM-101", "RM-102"};

  • Assume it takes 1 second for each element to be read when searching.

SEARCHING IN UNSORTED ARRAY

  • Searching for "RM-101" by iterating through the array may take:

    • Found after 3 seconds.

PROGRAMMING APPLICATION: ARRAY IN C++ (WITH SORTING)

  • Example Code:

    string rooms[4] = {"RM-101", "RM-102", "RM-103", "RM-104"};

  • Searching for "RM-103" by iterating from the end.

  • Found after 2 seconds.

CONCLUSION

  • The main goal of data structures and algorithms is to minimize the time spent in searching, sorting, and writing data.

WHAT IS ALGORITHM

  • A set of instructions designed to perform a specific task.

  • In programming, it can range from simple math operations to complex algorithms.

  • Algorithms differ from actual implementations.

CHARACTERISTICS OF ALGORITHM

  • Input: 0 or more inputs.

  • Output: 1 or more outputs.

  • Unambiguity: Clear and simple instructions.

  • Finiteness: Limited instructions.

  • Effectiveness: Relevant impact on every step.

ALGORITHM FLOW

  • Input ➔ Process ➔ Output

SIMPLE SAMPLE OF ALGORITHM

Cooking Noodles (Pancit Canton):

  1. Boil water.

  2. Put noodles in boiling water.

  3. Prepare sauce on a plate.

  4. Drain boiling water.

  5. Mix noodles with sauce.

  6. Stir to ensure noodles are covered.

  7. Serve Pancit Canton.

ALGORITHM THAT ADDS TWO NUMBERS

  1. Declare num1, num2, and sum.

  2. Input num1 and num2.

  3. Read num1 and num2.

  4. Process: sum = num1 + num2.

  5. Output sum.

PROGRAM IMPLEMENTATION USING C++

  • Create a program to add two numbers:

    #include <iostream>
using namespace std;
int main() {
    int num1, sum;
    cout << "Num 1:";
    cin >> num1;
    cout << "Num 2:";
    cin >> num2;
    sum = num1 + num2;
    cout << "Sum: " << sum;
    return 0;
}

DATA STRUCTURE AND ALGORITHM

  • Data structures are a set of algorithms that organize data in a certain way.

ALGORITHMS COMPLEXITY

  • Time Complexity: Time needed for the algorithm to complete.

  • Space Complexity: Memory used by the algorithm during its process.

SPACE COMPLEXITY

  1. Instruction Space: Size of executable files varies with code lines.

  2. Data Space: Size needed to store variables and constants.

  3. Environmental Space: Size for storing environment information to resume functions.

BASIC DATA STRUCTURES

  • Linear Data Structures: Store data in a sequence.

  • Non-Linear Data Structures: Data is not stored in sequence.

Examples of Basic Data Structures

  • Linear Data Structures: Arrays, Linked Lists, Stacks, Queues.

  • Non-Linear Data Structures: Trees, Graphs, Hash Tables.

LINEAR DATA STRUCTURE

  • Data arranged sequentially.

  • Easy to implement but not very efficient.

TYPES OF LINEAR DATA STRUCTURE

  • Static Data Structure: Fixed memory size; easy to access but wastes memory.

  • Dynamic Data Structure: Dynamic size; updated during runtime, efficient in space.

NON-LINEAR DATA STRUCTURE

  • Data that branches out; not sequential.

  • Examples include Trees and Graphs.