Notes in Data Structures and Algorithms

To Subscribe, use this Key

Status	Last Update	Fields
Published	10/15/2024	Algorithmic performance is often the deciding factor between what is {{c1::feasible}} and what is {{c2::impossible}} in computing.
Published	10/15/2024	{{c1::Insertion sort}} works by building a sorted array one element at a time, inserting each new element into its correct position.
Published	10/15/2024	The running time of an algorithm depends on the {{c1::size}} and {{c2::order}} of the input data.
Published	10/15/2024	The asymptotic upper bound, denoted by {{c1::Big O notation}}, describes the worst-case growth rate of an algorithm.
Published	10/15/2024	In best-case scenarios, insertion sort has a {{c1::linear}} time complexity, while in worst-case scenarios, it has {{c2::quadratic}} time complexity.
Published	10/15/2024	{{c1::Merge sort}} is an example of a divide-and-conquer algorithm, where the problem is recursively divided into smaller subproblems.
Published	10/15/2024	The running time of merge sort in the worst case is {{c1::\( O(n \log n) \)}}, making it more efficient than insertion sort for large datasets.
Published	10/15/2024	{{c1::Roots}} of an equation are the values of \( x \) that make the equation equal to zero, also called the {{c2::zeros}} of the equation.
Published	10/15/2024	The {{c1::incremental search}} method involves checking intervals of a function to find where it changes sign, indicating a root.
Published	10/15/2024	{{c1::Bracketing methods}} use two initial guesses that enclose the root, ensuring the root lies between them.
Published	10/15/2024	{{c1::Graphical methods}} can provide rough estimates of roots but are often too imprecise for scientific and engineering applications.
Published	10/15/2024	A major limitation of the {{c1::trial and error}} method for finding roots is its inefficiency and randomness.
Published	10/15/2024	Roots frequently occur in engineering applications such as solving equations related to {{c1::mass balance}} or {{c2::force balance}}.
Published	10/15/2024	In root-finding problems, {{c1::optimization}} seeks the maximum or minimum value of a function by solving for the points where the derivative equals …
Published	10/15/2024	The incremental search method is based on the principle that if a function changes {{c1::sign}} between two points, there must be a root between them.
Published	10/15/2024	One issue with incremental search is the choice of {{c1::increment length}}: if it is too small, the search is slow; if too large, roots may be missed…
Published	10/15/2024	{{c1::Open methods}} for root search require one or more starting values but do not require {{c2::bracketing the root}}.
Published	10/15/2024	The {{c1::Newton-Raphson method}} is one of the most widely used open methods for finding roots of a function.
Published	10/15/2024	The Newton-Raphson method is derived from the formula {{c1::\( x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)} \)}}.
Published	10/15/2024	One problem with the Newton-Raphson method is that it can diverge if the initial guess is near a point where the derivative is {{c1::zero}}.
Published	10/15/2024	The {{c1::secant method}} is a root-finding technique that does not require the calculation of the derivative, unlike Newton-Raphson.
Published	10/15/2024	In the secant method, the derivative is approximated using {{c1::two previous points}}.
Published	10/15/2024	The secant method formula is {{c1::\( x_{i+1} = x_i - \frac{f(x_i)(x_i - x_{i-1})}{f(x_i) - f(x_{i-1})} \)}}.
Published	10/15/2024	The {{c1::modified secant method}} estimates the derivative by applying a small perturbation to the independent variable.
Published	10/15/2024	A potential problem with the Newton-Raphson method is that it may oscillate if the initial guess is near a {{c1::local maximum or minimum}}.
Published	10/15/2024	The convergence of Newton-Raphson depends on the function and the {{c1::initial guess}}; it may not converge for all functions.
Published	10/15/2024	{{c1::Optimization}} deals with finding the maximum or minimum of a function that depends on one or more variables.
Published	10/15/2024	In optimization, a {{c1::global optimum}} represents the best solution, while a {{c2::local optimum}} is better than its immediate neighbors but may n…
Published	10/15/2024	The {{c1::golden-section search}} is a bracketing method for finding the minimum of a one-dimensional function.
Published	10/15/2024	The MATLAB function {{c1::fminbnd}} combines the golden-section search and parabolic interpolation to find the minimum of a one-dimensional function.
Published	10/15/2024	{{c1::Multi-dimensional optimization}} involves finding the minimum of a function that depends on more than one variable.
Published	10/15/2024	The MATLAB function {{c1::fminsearch}} is used to find the minimum of a multi-dimensional function.
Published	10/15/2024	In numerical optimization, MATLAB's {{c1::surf}} and {{c2::contour}} plots are useful for visualizing multi-dimensional functions and estimating their…
Published	10/15/2024	Optimization problems are similar to root-location methods in that both involve {{c1::guessing}} and searching for a point on a function.
Published	10/15/2024	Many fundamental equations in engineering and science are based on {{c1::conservation laws}} such as mass, energy, and momentum.
Published	10/15/2024	A system of linear equations can be represented in matrix form as {{c1::\( A x = b \)}}, where \( A \) is the matrix of coefficients, \( x \) is the v…
Published	10/15/2024	A {{c1::square matrix}} has an equal number of rows and columns and is important for solving linear systems with a unique solution.
Published	10/15/2024	In matrix algebra, the inverse of a matrix \( A \), denoted by \( A^{-1} \), is used to solve the system of equations as {{c1::\( x = A^{-1} b \)}}.
Published	10/15/2024	In MATLAB, the most efficient way to solve a system of linear equations is using the left-division operator, {{c1::A\b}}.
Published	10/15/2024	The {{c1::Gauss elimination}} method systematically eliminates unknowns to solve a system of linear equations.
Published	10/15/2024	The Gauss elimination process has two phases: {{c1::elimination of unknowns}} and {{c2::back substitution}}.
Published	10/15/2024	A matrix is called {{c1::symmetric}} if the elements in the matrix satisfy \( a_{ij} = a_{ji} \).
Published	10/15/2024	An {{c1::identity matrix}} is a square matrix where all elements on the main diagonal are equal to 1, and all off-diagonal elements are zero.
Published	10/15/2024	In Gauss elimination, the total number of floating-point operations for a system of equations with \( n \) unknowns is approximately {{c1::\( \frac{2n…
Published	10/15/2024	{{c1::Numerical integration}} involves approximating the value of a definite integral when the function cannot be integrated analytically.
Published	10/15/2024	The {{c1::trapezoidal rule}} approximates the integral of a function by calculating the area of a trapezoid under the function's curve.
Published	10/15/2024	The formula for the trapezoidal rule is {{c1::\( I = \frac{b - a}{2} \left[ f(a) + f(b) \right] \)}}.
Published	10/15/2024	The error in the trapezoidal rule can be estimated as {{c1::\( E_t = -\frac{(b - a)^3}{12} f''(\xi) \)}} where \( \xi \) is in the interval \( [a, b] …
Published	10/15/2024	The {{c1::composite trapezoidal rule}} improves accuracy by dividing the integration interval into multiple segments and applying the trapezoidal rule…
Published	10/15/2024	{{c1::Simpson’s 1/3 rule}} uses a second-order polynomial to approximate the integral of a function over an interval.
Published	10/15/2024	The formula for Simpson’s 1/3 rule is {{c1::\( I = \frac{h}{3} \left[ f(x_0) + 4f(x_1) + f(x_2) \right] \)}}, where \( h = \frac{b - a}{2} \).
Published	10/15/2024	{{c1::Simpson’s 3/8 rule}} is used for integrating a function by fitting a third-order polynomial through four points.
Published	10/15/2024	The error in Simpson's 1/3 rule is proportional to the {{c1::fourth derivative}} of the function, making it more accurate than the trapezoidal rule.
Published	10/15/2024	The MATLAB function {{c1::trapz}} computes the integral using the trapezoidal rule, while {{c2::cumtrapz}} computes the cumulative integral.
Published	10/15/2024	{{c1::Gauss quadrature}} is a method of numerical integration that chooses the base points to minimize the error, unlike the trapezoidal rule which us…
Published	10/15/2024	{{c1::Adaptive quadrature}} adjusts the step size automatically, using small steps in regions where the function changes rapidly and larger steps else…
Published	10/15/2024	In MATLAB, the function {{c1::integral}} is used for numerical integration with global adaptive quadrature.
Published	10/15/2024	{{c1::Multiple integrals}} extend the concept of integration to functions of two or more variables, such as \( \int \int f(x, y) \, dx \, dy \).
Published	10/15/2024	The {{c1::double integral}} of a function over a rectangular region can be computed using the MATLAB function {{c2::integral2}}.
Published	10/15/2024	{{c1::Composite Simpson’s rule}} divides the interval into smaller segments and applies Simpson’s rule to each segment for improved accuracy.
Published	10/15/2024	The mean value of a continuous function over an interval is computed as {{c1::\( \frac{1}{b - a} \int_a^b f(x) \, dx \)}}.
Published	10/15/2024	The {{c1::trapezoidal rule}} can be applied to data with unequal segments by summing the areas of trapezoids for each segment.
Published	10/15/2024	{{c1::Numerical differentiation}} is used to estimate the derivative of a function using discrete data points.
Published	10/15/2024	A {{c1::finite difference}} is a mathematical expression of the form \( \frac{f(x_{i+1}) - f(x_i)}{x_{i+1} - x_i} \) used to approximate derivatives.
Published	10/15/2024	The {{c1::forward difference}} approximation of a derivative uses the function values at the current and next points.
Published	10/15/2024	The {{c1::backward difference}} approximation of a derivative uses the function values at the current and previous points.
Published	10/15/2024	The {{c1::centered difference}} formula for numerical differentiation uses the values of the function at both neighboring points, providing better acc…
Published	10/15/2024	{{c1::Partial derivatives}} are used when a function depends on more than one variable, and they represent the rate of change with respect to one vari…
Published	10/15/2024	In MATLAB, the {{c1::diff}} function can be used to compute differences between adjacent elements in a vector, which can approximate derivatives.
Published	10/15/2024	The {{c1::gradient}} function in MATLAB computes numerical derivatives for both vectors and matrices, making it useful for evaluating partial derivati…
Published	10/15/2024	Numerical differentiation tends to amplify errors in the data, especially in the presence of {{c1::noise}}.
Published	10/15/2024	The {{c1::Taylor series}} expansion is a key tool for approximating functions and analyzing truncation errors in numerical differentiation.
Published	10/15/2024	In MATLAB, the {{c1::xlsread}} function is used to read data from Excel files, which can then be used for numerical analysis.
Published	10/15/2024	The {{c1::trapezoidal rule}} is a numerical method used to approximate the integral of a function by calculating the area of trapezoids under the curv…
Published	10/15/2024	To plot position and velocity data in MATLAB, the {{c1::plot}} function is used to visualize the trajectory of an object in an XY-plane.
Published	10/15/2024	Numerical differentiation can be used to estimate the {{c1::acceleration}} of an object by differentiating velocity data.
Published	10/15/2024	In MATLAB, the {{c1::smoothdata}} function can be used to apply a moving average filter and reduce noise in the data.
Published	10/15/2024	To compute the distance traveled by an object, you need to integrate the {{c1::velocity}} data over time using numerical integration techniques.
Published	10/15/2024	In numerical differentiation, filtering the velocity data before differentiating can lead to more accurate estimates of {{c1::acceleration}}.
Published	10/15/2024	The {{c1::cumulative integral}} of a function can be computed using MATLAB’s {{c2::cumtrapz}} function, which applies the trapezoidal rule iteratively…
Published	10/15/2024	In the context of motion, the {{c1::maximum speed}} of an object can be determined by identifying the maximum value in the velocity data.
Published	10/15/2024	{{c1::Least-squares regression}} is a method for fitting a curve to a set of data points by minimizing the sum of the squared residuals.
Published	10/15/2024	In {{c1::linear regression}}, the goal is to fit a straight line to a set of paired observations, minimizing the error between the line and the data p…
Published	10/15/2024	The residual error is the difference between the observed value and the value predicted by the {{c1::regression model}}.
Published	10/15/2024	The criteria for the best fit in least-squares regression is to minimize the sum of the {{c1::squared residuals}}.
Published	10/15/2024	{{c1::Polynomial regression}} extends the idea of line fitting to higher-order polynomials, allowing for more complex relationships between variables.
Published	10/15/2024	{{c1::Multiple linear regression}} models the relationship between one dependent variable and two or more independent variables.
Published	10/15/2024	In nonlinear regression, the relationship between variables is modeled by a {{c1::nonlinear function}} that depends on the parameters being estimated.
Published	10/15/2024	The {{c1::Gauss-Newton method}} is an iterative algorithm for nonlinear regression that uses the Taylor series expansion to linearize the model around…
Published	10/15/2024	{{c1::General linear least squares}} allows for the fitting of complex models where the parameters appear linearly, even if the basis functions are no…
Published	10/15/2024	In MATLAB, the function {{c1::fmincon}} can be used to perform constrained optimization, which is useful in nonlinear regression when certain paramete…
Published	10/15/2024	{{c1::Interpolation}} is the process of estimating unknown values within the range of known data points.
Published	10/15/2024	The {{c1::polynomial interpolation}} method uses an \(n\)-th order polynomial to fit \(n+1\) data points.
Published	10/15/2024	In {{c1::Newton’s divided-difference interpolation}}, the interpolation polynomial is built recursively based on divided differences.
Published	10/15/2024	In {{c1::Lagrange interpolation}}, a polynomial is constructed by combining basis polynomials that pass through each data point.
Published	10/15/2024	{{c1::Quadratic interpolation}} uses three data points to fit a second-order polynomial to approximate the function.
Published	10/15/2024	{{c1::Spline interpolation}} connects subsets of data points with lower-order polynomials to avoid oscillations in higher-order polynomial fits.
Published	10/15/2024	A {{c1::linear spline}} connects two data points with a straight line, providing a continuous but not smooth approximation.
Published	10/15/2024	{{c1::Quadratic splines}} are second-order polynomials used to provide smooth transitions between data points by ensuring continuity in the first deri…
Published	10/15/2024	A {{c1::cubic spline}} is a third-order polynomial that ensures smoothness in both the first and second derivatives between data points.
Published	10/15/2024	Higher-order polynomials tend to exhibit wild {{c1::oscillations}} between points, making lower-order splines more stable for interpolation.
Published	10/15/2024	{{c1::Fourier series}} represents a periodic function as a sum of sine and cosine terms, each with different frequencies and amplitudes.
Published	10/15/2024	The {{c1::fundamental frequency}} of a periodic function is the reciprocal of its period: \( f = \frac{1}{T} \).
Published	10/15/2024	The general form of a cosine function used in Fourier approximation is {{c1::\( A \cos(\omega t + \phi) \)}}, where \(A\) is amplitude and \(\phi…
Published	10/15/2024	{{c1::Harmonics}} are integer multiples of the fundamental frequency, contributing to the shape of the periodic function.
Published	10/15/2024	The {{c1::continuous Fourier series}} is used to represent continuous periodic functions, where the coefficients are determined using integrals.
Published	10/15/2024	The {{c1::discrete Fourier series}} is used for analyzing periodic discrete signals, often sampled at regular intervals.
Published	10/15/2024	In {{c1::Fourier approximation}}, the coefficients \( A_0, A_1, B_1 \) are determined to minimize the difference between the function and its Fourier …
Published	10/15/2024	The Fourier series of a periodic function contains both {{c1::sine}} and {{c2::cosine}} components, with different amplitudes and phases.
Published	10/15/2024	The {{c1::complex form}} of the Fourier series represents the series using complex exponentials \( e^{j\omega t} \).
Published	10/15/2024	The {{c1::Fourier transform}} is applied to non-periodic functions to decompose them into their frequency components.
Published	10/15/2024	A {{c1::linked list}} is a data structure where objects are arranged in a linear order, determined by pointers in each object rather than array indice…
Published	10/15/2024	In a {{c1::doubly linked list}}, each element has two pointers: one to the next element and one to the previous element.
Published	10/15/2024	A {{c1::binary tree}} is a hierarchical data structure where each node has at most two children, referred to as the left and right children.
Published	10/15/2024	The {{c1::binary search tree}} property ensures that for each node, the keys in the left subtree are less than the node's key, and the keys in the rig…
Published	10/15/2024	An {{c1::inorder tree walk}} visits the nodes of a {{c4::binary search tree}} in {{c5::sorted}} order by traversing the {{c2::left subtree}}, {{c3::th…
Published	10/15/2024	The {{c1::A* search algorithm}} is used in grid-based environments to find the shortest path, combining heuristics with path cost.
Published	10/15/2024	In a binary tree, the {{c1::root}} is the topmost node, and the children of each node are called {{c2::left}} and {{c3::right}} children.
Published	10/15/2024	The {{c1::TREE-SEARCH}} function is used to find a node with a given key in a binary search tree, with a time complexity of \( O(h) \), where \( h \) …
Published	10/15/2024	The {{c1::TREE-SUCCESSOR}} function returns the node with the smallest key greater than a given node's key in a binary search tree.
Published	10/15/2024	In a binary search tree, the {{c1::TREE-MINIMUM}} function finds the node with the smallest key by traversing the left children until reaching a leaf …
Published	10/15/2024	A {{c1::graph}} is a data structure consisting of vertices (nodes) connected by edges, used to represent relationships between entities.
Published	10/15/2024	In an {{c1::adjacency list}} representation, each vertex stores a {{c2::list of adjacent vertices}}, making it space-efficient for sparse graphs.
Published	10/15/2024	In an {{c1::adjacency matrix}}, the presence or absence of an edge between vertices \(i\) and \(j\) is represented by 1 or 0, respectively.
Published	10/15/2024	{{c1::Dijkstra's algorithm}} is a shortest-path algorithm for weighted graphs where all edge weights are nonnegative.
Published	10/15/2024	{{c1::Breadth-first search (BFS)}} explores the vertices of a graph level by level, discovering all vertices at a certain distance from the start befo…
Published	10/15/2024	{{c1::Depth-first search (DFS)}} explores as far as possible along a branch of the graph before backtracking to explore other branches.
Published	10/15/2024	In a directed graph, the edges have a direction, indicating the flow from one vertex to another, whereas in an {{c1::undirected graph}}, the edges hav…
Published	10/15/2024	In a {{c1::weighted graph}}, each edge has an associated numerical weight, representing costs, distances, or other metrics.
Published	10/15/2024	An {{c1::adjacency matrix}} uses \( O(V^2) \) memory, while an adjacency list uses \( O(V + E) \), where \(V\) is the number of vertices and \(E\) is …
Status	Last Update	Fields