Algorithms

Table of Contents Quick Facts Introduction Implementation Exercises Quick Facts Time Complexity: \(O(\lg n)\) Space Complexity: \(O(n)\) Introduction Besides being the primary data structure for Heapsort, a heap is also used to implement a priority queue. A priority queue is a key-value data structure in which the keys are used to determine the priority of each element in the queue. There are two variants, maximum and minimum, and they support the following operations:

Table of Contents Maintaining the Heap Property Building the Heap Heapsort Running time is \(O(n \lg n)\). Sorts in place, only a constant number of elements needed in addition to the input. Manages data with a heap. A binary heap can be represented as a binary tree, but is stored as an array. The root is the first element of the array. The left subnode for the element at index \(i\) is located at \(2i\) and the right subnode is located at \(2i + 1\). This assumes a 1-based indexing.

Table of Contents Example: Merge Sort Example: Matrix Multiplication Example: Median Finding Example: Cormen et al. Exercise 4.5-2 In the study of Divide and Conquer Algorithms, a recurrence tree can be used to determine the runtime complexity. These notes focus on the master theorem, a blueprint for solving any recurrence of the form \[ T(n) = aT(n/b) + f(n). \] \(n\) is the size of the problem, \(a \geq 1\) is the number of subproblems, \(b > 1\) is the factor by which the problem size is reduced, and \(f(n)\) is the cost of the work done outside of the recursive calls. Each recurrence is solved in \(T(n/b)\) time, and \(f(n)\) would include the cost of dividing and recombining the problem. The full theorem as described in Introduction to Algorithms is restated below (Cormen et al. 2022).

Table of Contents Definition Solving Recurrences Example: Merge Sort Example: Multiplying Square Matrices Example: Convex Hull Example: Median Search Definition Divide and conquer algorithms are a class of algorithms that solve a problem by breaking it into smaller subproblems, solving the subproblems recursively, and then combining the solutions to the subproblems to form a solution to the original problem. Problems that can be solved in this manner are typically highly parallelizable. These notes investigate a few examples of classic divide and conquer algorithms and their analysis.

Table of Contents Definition Finding the Minimum Spanning Tree Kruskal’s Algorithm Prim’s Algorithm Minimum spanning trees are undirected graphs that connect all of the vertices such that there are no redundant edges and the total weight is minimized. They are useful for finding the shortest path between two points in a graph. Useful application of MSTs include network design: it is useful to know the least expensive path with respect to either latency or resource cost for telecommunications networks, transportation networks, or electrical grids. approximation algorithms: MSTs can be used to approximate the solution to the traveling salesman problem. clustering: MSTs can be used to cluster data points in a graph. image segmentation: MSTs can be used to segment images into smaller regions. Definition Let \(G\) be a connected, undirected graph with edges \(E\), vertices \(V\), and edge weights \(w\). A minimum spanning tree is a subset \(T \subseteq E\) that connects all of the vertices such that the total weight is minimized. The original graph \(G\) is shown below.

Table of Contents Definition Bellman-Ford Shortest Paths on a DAG Dijkstra’s Algorithm When you hear the term shortest path, you may think of the shortest physical distance between your current location and wherever it is you’re going. Finding the most optimal route via GPS is one of the most widely used mobile applications. Physical paths are not the only types we may wish to find a shortest path for. Other examples include:

Table of Contents Binary Search Trees Operations Analysis A $n$-ary tree is a graph-based data structure in which each node has up to \(n\) subnodes. It is supported by the following operations (not exclusive): Search Insert Delete Tree-based data structures are defined by the following properties. The size of a tree \(T\) is determined by the total number of nodes in \(T\). The root of a tree \(T\) is the starting point of \(T\). A leaf node of a tree \(T\) is a node that has no sub-nodes. The height of a tree is determined by the length of the shortest path between the root of \(T\) and the lowest leaf node of \(T\). If we limit the number of subnodes each node may have to 2, the structure becomes known as a binary tree. Limiting the structure in this way is of interest to us because of the efficiency benefits seen in operations applied to binary trees. If we narrow the scope of these trees further, we can define a binary search tree whose search operation, as the name might suggest, runs in \(\Theta(lg n)\) worst-case time.

Table of Contents The notation of complexity analysis Formal Definition of Asymptotic Notation Common Functions The notation of complexity analysis $O$-notation $O$-notation, often referred to as “Big Oh” notation, describes an upper bound on the behavior of a function. It really means that the function will not grow faster than the a given rate. This rate is typically the highest-order term in the function, and is often referred to as the “dominant term” or “dominant function”.

Table of Contents Introduction to Algorithms Insertion Sort Example: Sorting Numbers Correctness Worst-Case Analysis Best-Case Analysis Rate of Growth Example: Analysis of Selection Sort Introduction to Algorithms One of the major goals of computer science is to solve important problems. In order to do that, we must be able to express those solutions both mathematically and in a way that can be executed by a computer. Further, those solutions need to be aware of the resources that are available to them. It does us no good to come up with a solution that could never be run by current hardware or executed in a reasonable amount of time.

Table of Contents Introduction Epipolar Geometry Calibration with Known Intrinsic Parameters and World Points Estimating Depth Introduction Binocular vision permits depth perception. It is an important part of many tasks such as robotic vision, pose estimation, and scene understanding. The goal of steropsis is to reconstruct a 3D representation of the world given correspondences between two or more cameras. The process of computing these correspondences assumes two or more cameras with known intrinsic and extrinsic parameters. Methods exist to estimate the required transformation parameters using points based on matching image features. If some set of points which a fixed coordinate system is known, such as a calibration pattern, the problem becomes even simpler. Knowing the exact world point as it is projected in all image planes is essentially a ground truth.