ramblings of a quack
ramblings of a quack
Sorting Arrays.sort() Array Type Algorithm Average Time Worst Time Space Stable In-Place Primitives (int[], double[], etc.) Dual-Pivot Quicksort O(n log n) O(n²) O(log n) ❌ No ✅ Yes Objects (String[], Integer[], custom classes) TimSort O(n log n) O(n log n) O(n) ✅ Yes ❌ No Data Structures Queue A Queue in Java is a FIFO […]
Artificial Intelligence (AI) is an umbrella term that contains a number of categories, such as Machine Learning, Robotics, Computer Vision. Broadly, it refers to developing computer applications that mimic human intelligence, such as decision making, text processing, and visual perception. Machine learning is the study of computer algorithms that allow computer programs to automatiically improve […]
A good source of information about the Secure Shell (SSH) is provided in RFC 4253. This network protocol provides a secure way to login to remote servers. This fundamental service provides a mechanism for other useful operations, such as secure file transfer. The protocol will work over an underlying transport that protects transmission errors, such […]
C++17 provides a really cool feature that allows us to unpack / decompose structures into their constituent values. This combines some syntactic sugar and automatic type deductaion to create structured bindings. The below code provides some example use cases: This produces the following output (when built with –std=c++17):
The cutest of all sorting algorithms (or at least tied with bubble sort). Has O(N^2) due to N^2/2 compares. Data movement is minimal. The running time does not depend on the input data, in the sense that it will always take the same amount of time to run, as it compares each index to all […]
In programming, graphs allow us to represent a particular class of problem that is concerned with the connections between nodes: is there way to connect two nodes via a series of other connected nodes? How many nodes are connected to any given node? What is the shortest chain of connections between two nodes? Examples of […]
Binary search is a classic search algorithm for sorted lists of elements. Below is a simple implementation. Of course, the STL provides std::binary_search() Time complexity of Binary Search: log2N Some important things to remember for the implementation: make sure to base your mid calculation with the lower bound, as below. This is because indexing is […]
Algorithm Average Worst Case Space O(n) O(n) Search O(n) O(n) Insert O(1) O(log n) Delete O(1) O(1) A simple tree data structure that typically uses an array to store values, rather than linked nodes. There are regularly two strategies with heaps, either they are a max or a min heap, where the root value is […]
Most of the information is taken from C++ Templates: The Complete Guide, by David Vandervoorde and Nicolai M. Josuttis. C++ templates allow you to write functions or classes that prescribe behavior for an arbitrary data type. Instead of duplicating code for each type that it should handle, you write the logic once and indicate that […]
Let’s write a C++ shared pointer. Shared pointers are smart pointers that ensure the freeing of memory when the last reference to it is deleted. Fundamentally, smart pointers take advantage of a class’ destructor. When an object goes out of scope, its destructor is called. When a shared pointer goes out of scope, logic in […]
