LESSON 1: Fundamentals of Data Structures and Algorithm

• DATA STRUCTURE 


  a special format for storing and organizing data.
• Two (2) types of data structure

  1. Linear
  2. Non-Linear
• Linear


  Elements are accessed in a stored sequential order but may be unsystematically.
• Non-Linear


  Elements are stored and accessed in a non-sequential order.
• ABSTRACT DATA TYPES


  a logical description of how data is viewed as well as the operations that are allowed without regard to how they will be implemented.
• Implementations of ADTs can be changed without requiring changes to the program that uses the ADTs. 
• Wall of ADT 

  • Create a list 
  • Insert an item into the list 
  • Remove an item from the list 
  • Check if the list is empty 
  • Display list content
• Two (2) parts of ADT 

  1. Public or external ADT
  2. Private or internal ADT
• Public or external ADT


  the data and the operations
• Private or internal ADT

  the representation and the implementation
• The four (4) main operations that could be defined for each ADT are: 

  1. initializing, 
  2. adding, 
  3. accessing, and 
  4. removing of data 
• Linked list


  used for storing elements where each is a separate object.
• Stack 


  an ordered list in which the last element added is the first element retrieved or removed (Last-In, First-Out)
• Queue 


  an ordered list in which the first element added is the first element retrieved or removed (First-In, FirstOut)
• Tree 


  represents a hierarchical nature of a structure in a graphical form.
• Graph 


  consists of a set of vertices (or nodes) and a set of edges (relations) between the pairs of vertices.
• Heap 


  a complete binary tree where the value of each parent node is either higher or lower than the value of its child nodes.
• Priority queue


  a special type of queue where elements are processed based on their order (natural or custom).
• Set 


  a collection of elements where each element is unique.
• Map 


  a set of ordered pairs where elements are known as keys (identifiers) and values (content).
• keys 


  identifiers
• values 


  content
• data structure

  A) array

  B) stack

  C) queue

  D) linked-list

  E) graphs

  F) trees

  
• ALGORITHM


  a step-by-step set of instructions to be executed in sequence for solving a problem.
• CHARACTERISTICS OF AN ALGO

  1. Finiteness
  2. Definiteness
  3. Input
  4. Output
  5. Uniqueness
• Finiteness 


  must terminate after a specified no. of steps
• Definiteness 


  each instruction has to be clear and unambiguous.
• Input 


  should have zero or more well-defined data given before the algo begins.
• Output 


  must have 1 or more results w/ specified relation to the input
• Uniqueness 


  the result of each step depends on the input and/or the result of the previous step.
• Elements of an algorithm:

  • Sequential operations Actions based on the state of a data structure
  • Iteration
  • Recursion
• Iteration 


  repeating an action multiple times
• Recursion 


  occurs when a function calls itself once or multiple times to solve a problem
• Algorithm design paradigms:

  • Divide and Conquer
  • Greedy and Algorithms
  • Dynamic Programming
• Divide and Conquer


  a problem is broken into smaller sub-problems
• Greedy Algorithms


  the optimal approach is always chosen in solving a problem
• Dynamic Programming


  Similar to Divide and Conquer except that the results of the sub-problems are reused for overlapping sub-problems.
• Algorithm design paradigms:

  1. Divide and Conquer
  2. Greedy Algorithms
  3. Dynamic Programming
• Divide and Conquer


  a problem is broken into smaller sub-problems
• Greedy Algorithms


  the optimal approach is always chosen in solving a problem.