Understanding Recursiveness

Recursiveness

• Describes a definition where the object or concept being defined appears in the definition itself.

Applications

• It is employed is image and fractal graphics processing
• It is used during traversal and processing of non-linear data structures, like trees and graphs.

Conditions

• The functions must have self-invocation in its action block
• Control conditions should interrupt the recursive process, if trivial or base problem situations are reached.
• A well-structured recursive definition avoids infinite recursion by logically including elements that close it.

Recursive Definition of the Concept of Forest

• A forest is a set of trees that may be empty.
• A forest may contain one or more trees grouped with another forest.

Code Block Analysis

• This recursive version is simpler and more compact than a cycle-based version.
• The recursive version requires stack memory for each invocation.
• The iterative approach is more convenient.

Fractal Graphics

• Refer to a fractal figure composed of smaller versions of the original figure

Screen Coordinates

• The coordinate system's origin is in the screen's or window's upper-left corner.
• Lower-numbered rows are closer to the top edge than higher-numbered rows.

Ackermann Function

• A mathematical function defined recursively with rapid growth.
• The function accepts two non-negative integer arguments denoted as m and n.
• It returns n + 1 if m = 0.
• It returns A(m-1, 1) if m > 0 and n = 0.
• It returns A(m - 1, A(m, n - 1)) if m > 0 and n > 0.

Stack Segment

• A block of memory automatically allocated for a function upon invocation, whether recursive or not.
• Within this block, all formal parameters and local variables are created and stored before execution begins

Operation as a Stack

• The stack segment operates as a data stack with LIFO modality i.e. Last In - First Out
• The latest data is stored at the top of the stack segment.
• Internal support for function invocation, recursive or not
• It fills up as the cascade of invocations develops
• As the return process occurs, it empties
• Each recursive instance stores the return address, as well as the local variables, in the stack segment.
• As cascading recursive invocations develop, the stack segment fills up, but begins to empty as an instance finalizes.

Factorial

• Factorial of n, denoted as n!, is defined as 1 if n = 0, or n * factorial(n-1) if n > 0.

Potency

• Potency of a raised to the power of n, denoted as potencia(a, n), is defined as 1 if n = 0.
• Potencia = a * potencia(a, n-1) if n>0

Product

• The product of a and b, denoted as producto(a, b), is defined as 0 if either a or b is 0, otherwise a + producto(a, b-1).

Fibonacci

• F(n) is defined as 1 if( integer n = 1 or n = 0).
• F(n) F(n-1) + F(n-2) if (integer n>1).
• Iterative version has acceptable complexity, constant memory usage, and linear time
• Recursive version has optimal code complexity, proportional to n memory usage, and undefined time complexity

Version Comparison

• Iterative version has a linear time
• Recursive version has exponential time, where the process is of order 1.8η.

Ordering Algorithms

• Types include Simple/Direct and Compound/Improved algorithms
• Simple/Direct algorithms have poor execution time if the array size n is large, but have acceptable performance if n is small.

Simple or Direct Algorithms

• Include Direct Exchange (Bubble), Direct Selection, and Direct Insertion

Compound or Improved Algorithms

• Include Quick Sort, Heap Sort and Decreasing Increments Sort (Shellsort).

Direct Exchange (Bubble/Bubblesort)

• Compares each element with the next in n passes.
• Each pass moves larger elements towards the end of the array.
• A "cut flag" stops the process if no swaps occur in a pass, saving time.

Direct Selection

• Identifies the smallest element from the analyzed elements in n passes
• These elements are moved to the pivot position.

Direct Insertion (or Simple Insertion)

• Involves assuming the array has an initially ordered subset containing only the first element.
• Involves adding new elements to the group in n passes

Shellsort

• Algorithm improves upon Direct Insertion by creating ordered subsets with elements at distance h > 1 initially.
• The process terminates with h = 1.
• When h = 1, the algorithm becomes a simple insertion sort, guaranteeing an ordered array.
• The performance depends on the decreasing increment series selected.
• Worst-case execution time is O(n1.5).
• Subsets analyzed contain almost the same elements if the distance is decreasing.
• There is no good organization of the array before the last pass
• Decreasing increments are assumed to be in the form [5 – 3-1].

Heapsort

• Find the smallest or largest elements successively to move the value to a final location.
• The search for the smallest or largest value is very fast.
• It’s efficient in execution time for both average and worst cases.
• The heap or group of ordering is built with the vector being ordered, without the use of extra memory.

Algorithm Analysis Definition

• A branch of Computer Science focused on techniques to measure algorithmic efficiency.

Factors Influencing Efficiency

• Execution time
• Memory usage
• Source code complexity

Difference Between Worst and Average Case

• The worst case is the most unfavorable input data configuration for the algorithm.
• The average case describes a random configuration of data

Big O Notation

• Represents an upper bound on the execution time
• Expresses the performance of an algorithm
  • time
  • space
  • parameter

Functions and Execution Times

• O(1) is constant
• O(log(n)) is logarithmic
• O(n) is linear
• O(n*log(n)) involves processing each partition without discarding.
• O(n²) is quadratic
• O(n³) is cubic
• O(2ⁿ) is exponential

Exponential Algorithms

• Must explore all combinations of solutions.
• The number of solutions increases exponentially.

Forms of Function Growth

• O(1) < O(log(n)) < O(n) < O(n*log(n)) < O(n²) < O(n³) < O(2ⁿ)

Formalization of Big O Notation

• Polynomial function in n of degree k is of order nk e.g f(n) = 5n³ + 2n² + n = O(n³).
• If f(n) = 2n+10 and g(n) = 2n, then 2n+10 = O(2n).
• logb(n) = O(log(n)).

Exhaustive Counting

• Seeks to determine an expression or formula that rigorously expresses the number of critical operations performed by an algorithm.

Asymptotic Analysis

• Aims to determine the general behavior of a function for very large values of the problem size.

Complexity Order

• Refers to a set or family of mathematical functions with similar asymptotic behavior.
• The most characteristic function of that set is the simplest.

Intractable Problems

• In complexity theory, a problem for which only algorithms with exponential execution time are known

Asymptotic Behavior of Main Sorting Algorithms

• Bubble Sort has O(n²) time in the worst case
• Direct Selection has O(n²) time in the worst case
• Direct Insertion has O(n²) time in the worst case
• Quicksort has O(n*log(n)) in the average case, and O(n²) in the worst case.
• Heapsort has O(n*log(n)) in the average case
• Shellsort has O(n1.5)

Typical Notations

• Big O represents an upper bound on execution time by providing the best upper bound
• Omega represents that execution time or memory space is occupied by an algorithm
• Theta indicates that a function f behaves above and below in the same way that multiples of another function g, meaning f can be bounded both superiorly and inferiorly by multiples of g.
• Little O is similar to O(), but considers only the stricter minor relationship.

If simple sort algorithms all have O(n²) execution time in the worst case

• Explain effective measurements if the execution times are different when facing the same array
• Big O notation rescues the most significant term in the expression that calculates performance
• Discards constants and other terms that might not coincide in the three algorithms

Shellsort Algorithm Characteristics include

• Complex to analyze performance mathematically
• Time of execution for the worst case is O(n1.5)
• An improvement of the Direct Insertion algorithm
• Consists of forming ordered subsets with elements at a distance h > 1 in the first phases, finishing with h = 1 in the last.

Linear Structures

• Includes Stacks and Queues

Structures

• Native structures come with the language (tuples, ranges, strings, lists, etc.).
• Abstract structures don't come with the language (class Book).

Structure Type

• Linear data is stacks and queues
• It includes a unique immediate successor element (or none if it's the last)
  • and a unique immediate predecessor element (or none if it's the first).
• Non-linear includes trees and graphs
• Elements may have more than one immediate successor or predecessor

Abstraction Mechanism Decomposition Includes

• Data Abstraction seeks to capture the most relevant data set to represent an abstract type.
• Functional Abstraction seeks to determine the relevant set of processes to implement given functions

Stacks

• Linear structure where elements are stacked on top of each other from the first
• The last element inserted is at the top
• A sequence of data is processed in the reverse order of its input
• LIFO (Last In – First Out) - last in, first out

Queues

• Linear structure in which elements are organized behind each other
• They exist at the beginning and/or end
• Inserting an element add() means new components end up last in the queue.
• Removing an element remove() means only the first one can be eliminated.
• Data sequence is processed int he same order that it entered
• FIFO (First In – First Out) means first in, first out

Class of Stacks and class of Queues

• It goes over how to implement both of these using pseudo code

Non-Linear Structures: Binary Search Trees

• Data structure that can be empty or contain an element/ node known as the tree root.
• Two subsets of elements can be detached from the root node, if the root node exists, displaying these characteristics:

1. Both subsets have an empty intersection.
2. Both subsets are binary trees.

• They are designated as left subtree and right subtree.

Main Terms

• Links/Arcs are references or pointers, variables to contain a memory location or array indices.
• Given a node x, the two nodes connected to it with two arcs are called sons of x.
• Arcs determine a node's parent

Node Rules

• In a binary tree, no node can have more than one parent.
• Every node can have two sons, one son, or no son.
• Level is the number of arcs that must be followed to reach the given node, counting from the root arc.
• Height is the number of the tree's maximum level.
• Search includes comparing by level to find a key
• The search algorithm is O(log(n)) in the worst-case scenario, if the arc’s height h is O(log(n)).
• If the arc is a diagonal or a level n zigzag, worst-case scenario will be O(n).
• Show algorithm execution time in the worst-case is O(log(n)), just if minimum tree heigh h = O(log(n)).

Binary Tree Traversal

• While traversing the tree, a stack may be used that allows the LIFO storage of nodal directions.
• When you need to restore that node direction after processing one of its sons, it will be directly accessible at the top of the stack.

Preorder

• Each node is visited upon first arrival
• Each node of the arc will be touched 3 times when traversing
• Recorrido: { 1, 5, 13, 18, 15, 3, 20 }

Entroreden

• Each node will be visited after the left side
• Recorrido: { 13, 5, 18, 1, 3, 15, 20 }

Postorden

• Each node is visited when it returns on the right side
• Recorrido: { 13, 18, 5, 3, 20, 15, 1 }

Arc Construction Requirements

• In order to build a arc you need 2:
  • Preorden and entroorden
  • Postorden and entroorden

Conditions needed to take the Recorrido in preorden from a Binary search arc with a number in order minor to major?

• Only if the arc is diagonal
• Only if is diagonal with every node

What happen if the add section changes the condition that the root to the right may be bigger or equal?

• The arc will have a diagonal structure with null left links if all the roots that may be equal links insert on it
• Two or more equal claves are separated by 2 links

Unbalanced search arc

• On this arcs the seeking time will be the worst is going to O(n)

Balanced search arc

• Arcs binary are going to be the minimal if his height is the minimal as possible with the mount de nodes

Non-Linear Structures: Graphs

• Graph is a non-linear data structure, consisting of a set of n nodes and a set of m arcs.
• An arc connects any two vertices.
• A graph can have subgraphs not connected by arcs
• A graph can have isolated nodes with no incident arcs.
• A vertex may exist, but may not be necessarily either a start or end point for any arc.
• Two nodes a and b of a graph (directed or not) can have multiple paths of different lengths that unite them.
• Two vertices are said to be adjacent if an arc joins them, regardless of the direction of that arc.

Path Definition of Graphs

• The distance between A and B is k if there’s a sequence of k arcs to get from A ending at B
• If there's a path linking a vertex back into itself, a cycle exists, the graph is cyclic

Characteristics of Graphs

• Grade is the amount of arcs that have to be touched to get them
• Entre Grade - Entry grade is and amount of arcs so you come upon at the end that is directed
• Fuera Grade - Outside Grade is an arcs amount so you come upon at the end that is directed

Types of graphs include

• Directed graphs
• Non-directed graphs
• Weighted graphs

Directed Graphs

• The arcs indicate relations between nodes
• Every arc's sense has 2 points
  • A start node
  • A arrival node
• Some graph types include sociograms, pipeline systems, and university carreer modeling.

Non-Directed Graphs

• The arc connects the 2 vertices
• It can be understood when you can use the graph both direction
• Model the route plan between cities/locations

Weighted Graphs

• Each arc has an associated value, weight.

Matrix Implementation of Graphs

• For a graph where the rows represent the path's starting vertices, and the columns represent the arc's ending vertices.
• For a directed graph, the matrix is symmetrical where each time the arc has (A, B) the matrix is also going to (B, A).
• The matrix it's in the diagonally area where and matrix ady[x][y] is always the value, that is always the one in ady[y][x]
• Reflexive Matrix: Every vertex has itself
• Transitive Matrix: Every auto cycle.

Weighted Graph

• A matrix has to point to an object where that represents what's needed for the arc.
• A way to implements a chart in a matrix form.

Divide and Conquer

• Quicksort algorithm to speed up Bubblesort

Quicksort Algorithm

• It speeds up quick the number
• Charles Antony Richard Hoare created it
• Quickshort does the change quicker

Basic Algorithm

• First pass is the central element or Pivot is taken, the element between these are reorganized
• Second Pass: Re-pass
• Third Pass: Are back again - Re-pass

Average Case

• The Altura is an Algorithm: O(n*log(n).
• The run time is O(n*(log(n)).

Worst Case

• O(n*log(n))
• Always select the pivot from the menor that has.

Keys to Avoid

• Calculate the average that's between the elements.

Pivot Note

• Don't use element zero.
• Because it might be in the peores algorithm and it might turn the almost case in to the "Ordered".

Divide and Conquer Main Code with the Run Time

• Shows the O formula

Calculate the Average

• Shows a example in code on how to calculate.
• Wilhelm Ackerman studied at the Göttingen university
• Fibonnaci's real name is Leonardo Pisano.

Resolution Strategies of Problems

• A collection of techniques that can help find a problem solution
• Results are not guaranteed
• A problem can be solved with multi- resolution strategies

Force Brutal

• Applied with direct intuitive ideals, a simple way to coding
• It might get a good amount of memory
• Problem in travel, Algorithm in Ordenation

Recursive

• The property lets an process invoke itself or multiples times as part of an solution - Image processing, Fractal chart

Backtracking(Going back)

• Solution on how to test and error
• Algorithm in chess or sudoku
• In optimizing the combination

Algorithms avid

• This algorithm applies by an heuristics