Let $f(x,y,z)$ be a continuous function defined on a closed and bounded region
$V \subset \mathbb{R}^3$. The triple integral of $f$ over $V$ is defined as
The order of integration may be changed whenever convenient.
#
2. Explanation
Think of a double integral as adding up tiny rectangles to find the area of a region.
A triple integral does the same thing in three dimensions — it adds up tiny
boxes (small volumes) to find:
Volume of a solid
Mass (if density is given)
Center of mass
Physical quantities in engineering
Imagine breaking a solid object into many very small cubes.
If we add up the value of the function at each cube times its small volume,
we get the triple integral.
If we integrate just $1$, we simply get the volume:
A triple integral allows us to measure quantities distributed throughout
a three-dimensional region. It generalizes area (double integrals)
to volume and physical applications in space.
Double integration extends the concept of a single integral to functions of two variables, $$f(x, y)$$. Geometrically, it represents the volume under a surface within a given region $$D$$.
Weighted sampling is a sampling technique where each item is
assigned a weight, and the probability of selecting that item is
proportional to its weight.
Higher weight $\Rightarrow$ higher chance of being selected
Lower weight $\Rightarrow$ lower chance (but usually not zero)
Weighted sampling is a sampling technique where each item is
assigned a weight, and the probability of selecting that item is
proportional to its weight.
Higher weight → higher chance of being selected
Lower weight → lower chance (but usually not zero)
Randomized Algorithms:An algorithm that uses random numbers to decide what to do next
anywhere in its logic is called a Randomized Algorithm.
For example, in
Randomized Quick Sort, we use a random number to pick the next pivot (or
we randomly shuffle the array)
Type of Randomized Algorithms
1. Las Vegas: A Las Vegas algorithm is an algorithm which uses
randomness, but gives guarantees that the solution obtained for given
problem is correct.
Advantage: Always produce a correct answer. Randomness affects the running time, not correctness. Expected running time is finite and analyzed probabilistically.
A
randomized quick-sort algorithm where we randomly choose pivot is an
example of Las-Vegas algorithm. The algorithm always sorts the array.
The advantage we get with randomization is, there is no pattern for
which the quick sort causes worst case (unlike choosing fixed pivot like
a corner element causes worst case for sorted input)
Disadvantage: Time complexity of these algorithms is based on a random value and time complexity is evaluated as expected value.
Quick Short: This is a method to partition the array in place such that all elements to the left of
the pivot element are smaller, while all elements to the right of the
pivot are greater than the pivot. Then we recursively call the same
procedure for left and right subarrays.
There are two types of algorithm for random pivoting. Lomuto Partitioning and Hoare Partitioning.
Algorithm for random pivoting using Lomuto Partitioning
partition(arr[], lo, hi) pivot = arr[hi] i = lo // place for swapping for j := lo to hi – 1 do if arr[j] <= pivot then swap arr[i] with arr[j] i = i + 1 swap arr[i] with arr[hi] return i partition_r(arr[], lo, hi) r = Random Number from lo to hi Swap arr[r] and arr[hi] return partition(arr, lo, hi) quicksort(arr[], lo, hi) if lo < hi p = partition_r(arr, lo, hi) quicksort(arr, lo , p-1) quicksort(arr, p+1, hi)
# Python implementation QuickSort using # Lomuto's partition Scheme.
import random
''' The function which implements QuickSort. arr :- array to be sorted. start :- starting index of the array. stop :- ending index of the array. ''' def quicksort(arr, start , stop): if(start < stop):
# pivotindex is the index where the pivot lies in the array pivotindex = partitionrand(arr,\ start, stop)
# At this stage the array is partially sorted around the pivot.
# Separately sorting the left half of the array and the right
# half of the array. quicksort(arr , start , pivotindex-1) quicksort(arr, pivotindex + 1, stop)
# This function generates random pivot swaps the first element with the pivot # and calls the partition function. def partitionrand(arr , start, stop):
# Generating a random number between the starting index of the array
# and the ending index of the array. randpivot = random.randrange(start, stop)
# Swapping the starting element of the array and the pivot arr[start], arr[randpivot] = \ arr[randpivot], arr[start] return partition(arr, start, stop)
''' This function takes the first element as pivot, places the pivot element at the correct position in the sorted array. All the elements are re-arranged according to the pivot, the elements smaller than the pivot is places on the left and the elements greater than the pivot is placed to the right of pivot. ''' def partition(arr,start,stop): pivot = start # pivot
# a variable to memorize where the i = start + 1
# partition in the array starts from. for j in range(start + 1, stop + 1):
# if the current element is smaller # or equal to pivot, shift it to the # left side of the partition. if arr[j] <= arr[pivot]: arr[i] , arr[j] = arr[j] , arr[i] i = i + 1 arr[pivot] , arr[i - 1] =\ arr[i - 1] , arr[pivot] pivot = i - 1 return (pivot)
Algorithm for random pivoting using using Hoare's partition Scheme.
partition(arr[], lo, hi) pivot = arr[lo] i = lo - 1 // Initialize left index j = hi + 1 // Initialize right index while(True) // Find a value in left side greater than pivot do i = i + 1 while arr[i] < pivot // Find a value in right side smaller than pivot do j = j - 1 while arr[j] > pivot if i >= j then return j else swap arr[i] with arr[j] end while partition_r(arr[], lo, hi) r = Random number from lo to hi Swap arr[r] and arr[lo] return partition(arr, lo, hi) quicksort(arr[], lo, hi) if lo < hi p = partition_r(arr, lo, hi) quicksort(arr, lo, p) quicksort(arr, p+1, hi)
# Python implementation QuickSort using Hoare's partition Scheme.
import random
''' The function which implements randomised QuickSort, using Haore's partition scheme. arr :- array to be sorted. start :- starting index of the array. stop :- ending index of the array. ''' def quicksort(arr, start, stop): if(start < stop):
# pivotindex is the index where # the pivot lies in the array pivotindex = partitionrand(arr,\ start, stop)
# At this stage the array is # partially sorted around the pivot. # separately sorting the left half of # the array and the right # half of the array. quicksort(arr , start , pivotindex) quicksort(arr, pivotindex + 1, stop)
# This function generates random pivot, # swaps the first element with the pivot # and calls the partition function. def partitionrand(arr , start, stop):
# Generating a random number between # the starting index of the array and # the ending index of the array. randpivot = random.randrange(start, stop)
# Swapping the starting element of # the array and the pivot arr[start], arr[randpivot] =\ arr[randpivot], arr[start] return partition(arr, start, stop)
''' This function takes the first element as pivot, places the pivot element at the correct position in the sorted array. All the elements are re-arranged according to the pivot, the elements smaller than the pivot is places on the left and the elements greater than the pivot is placed to the right of pivot. ''' def partition(arr,start,stop): pivot = start # pivot i = start - 1 j = stop + 1 while True: while True: i = i + 1 if arr[i] >= arr[pivot]: break while True: j = j - 1 if arr[j] <= arr[pivot]: break if i >= j: return j arr[i] , arr[j] = arr[j] , arr[i]
# Driver Code if __name__ == "__main__": array = [
2.Monte Carlo Algorithms:A random algorithm is Monte-Carlo algorithms if it can give the wrong answer sometimes.
Running time is typically fixed or bounded.
Output may be incorrect with a small probability.
Often
used when approximate answers are acceptable or when error probability
can be made tiny. These algorithms are used for solving physical
simulation system and mathematical system.
The Monte-Carlo methods are used in places where
deterministic algorithms take a lot time. Monte-Carlo integration is
the most common application of Monte-Carlo algorithm. There are various
methods used for integration by using Monte-Carlo methods such as,
i) Direct sampling methods which includes the stratified sampling, recursive stratified sampling, importance sampling. ii) Random walk Monte-Carlo algorithm which is used to find out the integration for given problem. iii) Gibbs sampling.
Applications of Randomized Algorithms
Randomized algorithms have huge applications in Cryptography.
Load Balancing.
Number-Theoretic Applications: Primality Testing.
Data Structures: Hashing, Sorting, Searching, Order Statistics and Computational Geometry.
Algebraic identities: Polynomial and Matrix identity verification. Interactive proof systems.
Mathematical
programming: Faster algorithms for linear programming, Rounding linear
program solutions to integer program solutions
Counting and Enumeration: Matrix permanent Counting combinatorial structures.
Parallel and distributed computing: Deadlock avoidance distributed consensus.
Probabilistic
existence proofs: Show that a combinatorial object arises with non-zero
probability among objects drawn from a suitable probability space.
Derandomization: First devise a randomized algorithm then argue that it can be derandomized to yield a deterministic algorithm.
Consider a function of two variables
$$
z = f(x, y)
$$
This function represents a surface in three-dimensional space.
Each point on the surface corresponds to a particular value of $x$ and $y$.
The red point represents a point on the surface corresponding to the
values $(x, y)$.
Small Changes in Variables
Suppose the independent variables $x$ and $y$ change by small amounts
$dx$ and $dy$. These small changes cause a change in $z$, denoted by $dz$.
The movement along the $x$-direction by $dx$ and along the $y$-direction
by $dy$ together produce a total change in the value of $z$.
=============================
Total Change in z
The total change in $z$ is the combined effect of the change due to $x$
and the change due to $y$.
Mathematically, it is given by:
When a dependent variable depends on more than one independent variable,
its change depends on the changes in all those variables.
In such cases, we use the concept of Total Derivative.
If a function is given by
$$
z = f(x, y)
$$
where $x$ and $y$ are independent variables, then a small change in $z$
due to small changes in $x$ and $y$ is called the total differential.
The total differential of $z$ is denoted by $dz$ and is defined as:
$$
dz = \frac{\partial z}{\partial x}\,dx
+ \frac{\partial z}{\partial y}\,dy
$$
Total derivatives are widely used in error analysis, approximation,
thermodynamics, and engineering applications.
If $z = x^2y + y^2x$, find the total differential $dz$ and hence find the
approximate change in $z$ when $x$ changes from 1 to 1.02 and $y$ changes
from 2 to 2.01.
If $z = x^2 + y^2$, find the total differential and hence obtain the
approximate error in $z$ when the errors in $x$ and $y$ are $\delta x$
and $\delta y$ respectively.
Solution:
$$
dz = 2x\,dx + 2y\,dy
$$
Approximate error:
$$
\delta z = 2x\,\delta x + 2y\,\delta y
$$
Question 10
Find the total derivative of $z = x^2y^2$ and hence find the rate of
change of $z$ with respect to $t$, given $x = \sin t$ and $y = \cos t$.
