Data Structures and Algorithms: Introduction to Algorithmic Logic and Problem Solving

Course Information and Introductory Concepts

  • Course Title: Data Structure and Algorithm

  • Lesson: Lesson 1

  • Lecturer: Blasius K. Pinias

Definition and Fundamentals of Algorithms

  • Defining an Algorithm: An algorithm is defined as a sequence of instructions or a set of rules that are followed to complete a specific task.

  • Scope of Tasks: The task can be any activity as long as it can be described through clear instructions.

  • Alternative Definition: An algorithm is a step-by-step solution to a problem.

Structural Components of an Algorithm in Pseudocode

  • Control Flow Structure: Algorithms typically follow a standard structure encompassing declaration, input, process, and output.

  • Start and End Identifiers:

    • Every algorithm begins with the keyword BEGIN and concludes with the keyword END.

  • 1. Declaration Phase:

    • Used to define memory space for data.

    • Syntax: DECLARE variables AS data type

  • 2. Input Phase:

    • Involves gathering data from the user.

    • Commands: PROMPT "Message to ask for input" followed by GET variable.

  • 3. Process Phase:

    • This stage involves calculations, logic, and control structures.

    • IF Statement (Decision):

    • IF condition THEN (perform action) ELSE (perform alternative action) ENDIF.

    • FOR Loop (Controlled Iteration):

    • FOR counter ← start TO end STEP increment (repeated process) NEXT counter.

    • WHILE Loop (Condition-based Iteration):

    • WHILE condition DO (repeated process while condition remains true) ENDWHILE.

  • 4. Output Phase:

    • Displays the result to the user.

    • Command: DISPLAY "Message with results".

Essential Characteristics of an Algorithm

  1. Finiteness: An algorithm must be finite; it must eventually come to an end.

  2. Unambiguity: Every step must be clear and lead to only one interpretation.

  3. Detail-Oriented: An algorithm must include all finer details regardless of how trivial they may seem. Nothing should be omitted.

  4. Executability: Every algorithm must be capable of being transformed into an executable computer program.

  5. Persistence and Transferability: Use of an algorithm is not restricted to the creator; it may be used by others in the future who may not know its derivation.

  6. Correctness: When executed, an algorithm should always yield the correct solution.

  7. Presentation Formats: Algorithms are commonly presented in three formats:

    • Pseudo-code

    • Flow charts

    • Nassi-Schneiderman Diagrams

The Relationship Between Algorithms and Computer Programs

  • Purpose of the Course: The Data Structures and Algorithms course is designed to prepare students for programming by teaching them how to make a computer perform any task.

  • Mechanization of Tasks: Writing a program involves telling the computer, step-by-step, exactly what to do. The computer "executes" these steps mechanically to achieve a goal.

  • Definitions:

    • Source code: A text listing of commands formatted to be compiled or assembled into an executable program.

    • Compiler: A program or set of programs that transforms source code written in a high-level programming language (source language) into another language, usually a binary form known as object code (target language).

    • Program: A set of instructions derived from a specific algorithm, written in a specific programming language.

  • Translation Logic: A program is essentially an algorithm translated into instructions that the CPU can understand. Algorithms are only converted into programs once they have been validated.

Comprehensive Look at Pseudo-Code

  • Definition: Pseudo-code is an informal high-level description of the operating principles of a computer program or algorithm.

  • Etymology: "Pseudo" means false; therefore, pseudo-code is "false code" used as a standard for representing algorithmic logic.

  • Simple Logic Example:

    • Problem: Given two whole numbers, find their sum.

    • Pseudocode Instance:

    • START

    • Integer a, b, Sum

    • 1. Get a, b

    • 2. Sum = a + b

    • 3. Display Sum

    • END

Data Types and Data Structures

  • Data Type: A set of values sharing common characteristics that belong to the same domain.

  • Data Structure: A specific way of organizing data in a computer so it can be utilized efficiently.

Primary Data Types

  1. Integers: The set of positive and negative whole numbers.

  2. Real (Floating Point): All possible numbers, including decimals and fractions.

  3. Characters: All possible symbols, including alphabet letters and special signs found on a keyboard.

  4. String: A group of two or more characters representing a single value.

  5. Boolean: A set containing two values representing true or false.

User-Defined Data Structures (Composite Types)

  • These can represent more than one value simultaneously.

  1. Array: A data type derived from a simple type that stores multiple values of the same domain at once.

  2. File/Record/Structure: A composite data type grouping different data values from one or more domains into a single unit.

  3. Union: A data type that holds exactly one value from a set of specified possible data types.

Variables, Constants, and Literals

  • Variable: A name for a specific memory location reserved to store a value of a specific type. Variables can change during program execution.

  • Constant: A name for a specific memory location reserved to store a value that cannot change during program execution.

  • Literal: A value written exactly as it is to be interpreted. Unlike a variable or constant, it is not a name but the value itself.

    • Example: In Integer x = 20, xx is the variable and 2020 is the literal.

Declaration and Naming Conventions

  • Declaration: The process of naming and reserving memory space for specific data types.

  • Variable Declaration Syntax: Data_Type Variable_Name (e.g., Integer X).

  • Constant Declaration Syntax:

    • Constant_name Value (e.g., Rate 2.5).

    • Typed constants: Data_type Constant_name value (e.g., String institutionName "NSEA").

Naming Rules for Identifiers

  1. Must be a single word (no spaces).

  2. If multiple words are needed, use an underscore (e.g., Integer student_age).

  3. Must start with a letter, never a number.

  4. Names must be unique within the same scope (distinct spelling).

  5. Special symbols (e.g., +, -, ', /, *) are prohibited.

  6. Names can consist of one or more alphabet letters.

  7. A number can be used only if it follows an alphabetical letter.

The Seven-Step Problem-Solving Framework

  1. Understand/Identify the Problem:

    • Read and analyze the problem statement.

    • Identify required inputs, processes, and outputs.

    • Define constraints, rules, and clarify ambiguous terms to ensure the algorithm addresses the specific problem.

  2. Outline a Solution:

    • Plan the steps before writing code.

    • Break tasks into smaller logical steps and decide on control structures.

    • Focus on three components: Input, Processes, and Output.

  3. Develop the Outline into an Algorithm:

    • Expand the outline into precise steps and order of execution.

    • Representation methods include pseudo-code, flowcharts, or Nassi-Schneidermann diagrams.

  4. Test/Validate Your Algorithm (Desk Checking):

    • Identifying major errors early for easy correction.

    • Walk through the logic with test data as a computer would, tracking variable values on paper.

  5. Transform Algorithm into a Program:

    • Start coding in a language like Python, Java, C, C++, C#, JavaScript, or PHP only after design and testing are complete.

  6. Run/Execute the Program:

    • Use a compiler or interpreter.

    • Test for syntax errors (detected at compile time) and run-time/logical errors (detected during execution).

  7. Install, Document, and Maintain the Program:

    • External Documentation: Hierarchy charts, algorithms, test results.

    • Internal Documentation: Comments coded within the program.

    • Maintenance: Making necessary changes throughout the program's life cycle.

Practical Implementation Example

  • Problem: Display all even numbers from 2 to 10 and state if each is greater than 5. Also, provide a countdown from 5 to 1.

  • Pseudocode Example:

    • BEGIN

    • // DECLARATION

    • DECLARE Num AS INTEGER

    • // FOR LOOP – display even numbers from 2 to 10

    • FOR Num = 2 TO 10 STEP 2

    • // IF STATEMENT – check if number is greater than 5

    • IF Num > 5 THEN

    • DISPLAY Num, " is greater than 5"

    • ELSE

    • DISPLAY Num, " is less than or equal to 5"

    • ENDIF

    • // WHILE LOOP – count down from 5 to 1

    • Num ← 5

    • WHILE Num >= 1 DO

    • DISPLAY "Countdown: ", Num

    • Num = Num - 1

    • ENDWHILE

    • END