Korean

Table of Contents:

• Introduction
• Data structures
  • Array
  • Graph
  • Tree
• Topics
  • Dynamic programming
  • Greedy
  • Mathematics
  • Primitive type
  • Search
  • Sort
  • String
• Problem solving
• References

This repository is an implementation of algorithms, data structures, and problem solving. These are written in C++, Python, and Java, and each language uses the following test framework: Google Test(C++), pytest(Python), JUnit(Java).

Additionally, each project is configured in the following environments:

• C++ project: based on CMake project and uses GNU Scientific Library (GSL)
• Python project: uses NumPy and SciPy
• Java project: based on Spring Boot project and uses Java Microbenchmark Harness (JMH)

• Advancing through an array: c++(test) | Advance through the array to the last index.
• Arbitrary precision operation - increment an arbitrary-precision integer (PlusOne): c++(test) | Add one to the number represented by the vector.
• Arbitrary precision operation - add two arbitrary-precision integers (StringAddition): c++(test) | Add two numbers represented by strings.
• Arbitrary precision operation - multiply two arbitrary-precision integers (Multiply): c++(test) | Multiply two numbers represented by vectors.
• Delete duplicates from a sorted array (DeleteDuplicates): c++(test) | Delete duplicate elements in the array.
• Delete duplicates from a sorted array (DeleteDuplicateElements): c++(test) | Delete duplicate elements in the array.
• Delete specific elements from a sorted array (DeleteSpecificElements): c++(test) | Delete specific elements in the array.
• Dutch national flags problem: c++
• Enumerate prime numbers: c++(test) | Enumerate prime numbers in the range.
• Order elements in an array by even and odd (EvenOdd): c++ | Order even and odd numbers in the array.
• Order elements in an array by specified order (Rearrange): c++ | Rearrange arrays to have a specific order.
• Random data sampling - offline (OfflineRandomSampling): c++(test) | Randomly select k elements from the array.
• Random data sampling - compute permutation (ComputeRandomPermutation): c++(test) | Compute permutation of the array generated by random sampling.
• Replace elements - replace and remove (ReplaceAndRemoveString1): c++(test) | Replace element and remove element in the array. Keep the array size.
• Replace elements - replace and remove (ReplaceAndRemoveString2): c++(test) | Replace element and remove element in the array
• Replace elements - telex encoding (TelexEncoding): c++(test) | Telex encoding for punctuation marks.
• Stock trading - buy and sell a stock once (BuyAndSellStockOnceBruteForce, BuyAndSellStockOnce): c++(test)
• Stock trading - buy and sell a stock twice (BuyAndSellStockTwice): c++(test)

• Bellman-Ford algorithm: c++(test) | Bellman-Ford algorithm is a shortest path algorithm for a single source. It finds the shortest path from a source vertex to all other vertices in a weighted graph. This includes cases where the weight is negative.
• Breadth-first search (BFS): c++(test) | BFS is a search algorithm that traverses a graph layer by layer.
• Depth-first search (DFS): c++(test) | DFS is a search algorithm that traverses a graph by exploring as far as possible along each branch before backtracking.
• Dijkstra's algorithm: c++(test) | Dijkstra's algorithm is a graph search algorithm that finds the shortest path between two vertices in a graph. This is limited to cases where the weight is not negative.

• B-tree: c++(test) | B-tree is a self-balancing data structure which can have many child nodes. It is commonly used in auxiliary storage devices and database system. B-tree has the following properties: 1) Nodes have lower and upper bounds on the number of keys they can contain. (represent using degree $t$) 2) Every node other than the root must have at least $t-1$ keys. 3) Every node may contain at most $2t-1$ keys.
• Binary search tree: c++(test) | In binary search tree, all internal nodes are stored in ordered state. If y is a child of x and y is a node in the left subtree, then $y.key \leq x.key$, and if y is a node in the right subtree, then $y.key \geq x.key$.

Properties of Trees

• A tree with $n$ vertices has $n-1$ edges.
• A full $m$-ary tree with $i$ internal vertices contains $n = mi + 1$ vertices. (cf. vertices $n$ = internal vertices $i$ + leaves $l$)
• A full $m$-ary tree with
  • $(i)$ $n$ vertices has $i = (n - 1)∕m$ internal vertices and $l = [(m - 1)n + 1]∕m$ leaves,
  • $(ii)$ $i$ internal vertices has $n = mi + 1$ vertices and $l = (m - 1)i + 1$ leaves,
  • $(iii)$ $l$ leaves has $n = (ml - 1)∕(m - 1)$ vertices and $i = (l - 1)∕(m - 1)$ internal vertices.
• There are at most $m^h$ leaves in an $m$-ary tree of height $h$. $(l = m^h)$
  • If an $m$-ary tree of height $h$ has $l$ leaves, then $h \geq \lceil \log_{m}{l} \rceil$.
  • If the $m$-ary tree is full and balanced, then $h = \lceil \log_{m}{l} \rceil$.

Tree traversal in binary tree

• Preorder traversal (root, left, right): best choice for applications where internal vertices must be explored before leaves.
• Inorder traversal (left, root, right): best choice for applications where internal vertices must be explored in-order.
• Postorder traversal (left, right, root): best choice for applications where leaves need to be explored before internal vertices.

• Fibonacci number: c++(test) | Fibonacci sequence is a sequence of numbers where each number is the sum of the two preceding numbers. Fibonacci number is $n$th number in the sequence. The Fibonacci sequence is defined as follows:
  • $F_0 = 0$
  • $F_1 = 1$
  • $F_n = F_{n-1} + F_{n-2}$ (for $n > 1$)
• Longest common subsequence: c++(test)
• Rod cutting: c++(test) | Rod cutting is a problem of cutting a rod into pieces of a given length to determine the maximum profit.

• Activity selection: c++(test) | Activity selection problem using greedy algorithm or recursive approach. This is similar to the Interval scheduling problem.
• Cashier's change: python(test) | Cashier's change problem is that finds the minimum number of coins required to make change for a given amount of money.
• Huffman code: c++(test) | Huffman code constructs optimal prefix codes. This is always represented by a full binary tree.
• Interval scheduling: python(test) | Interval scheduling problem is that finds the minimum number of intervals required to schedule a set of activities(lectures).

• Base expansion (base $b$ expansion of $n$): python(test) | Constructing the base $b$ expansion of an integer $n$. Such as binary, octal, decimal, hexadecimal expansion, etc.
• Binary operation (addition): python(test)
• Combination: c++(test) | Find the number of ways to choose $k$ items from $n$ items.
• Greatest common divisor (GCD): python(test) | Find the greatest common divisor of two numbers.
• Least common multiple (LCM): python(test) | Find the least common multiple of two numbers.
• Matrix multiplication: python(test) | This is the product of two matrices.
• Miller-Rabin primality test: c++(test) | Miller-Rabin primality test is a mathematical algorithm that finds whether a given number is prime.
• Permutation (Permutation): c++(test) | Find the permutation of a set of items.
• Permutation (ApplyPermutationWithAdditionalSpace, ApplyPermutationBySwap): c++(test) | Permute the elements of an array
• Permutation (InversePermutation): c++(test)
• Permutation (NextPermutation/PreviousPermutation): c++(test) | Compute the next/previous permutation.
• Permutation (KthPermutation): c++(test) | Compute the k-th permutation.

• Arithmetic operation (Multiply/Divide): c++(test) | Calculate the product/fraction of two numbers without using arithmetic operators.
• Computing parity of word (CountBits): c++(test) | Count the number of bits that are set to 1.
• Computing parity of word (Parity): c++(test) | Compute parity of word.
• Computing parity of word (ParityDropLowestBits): c++(test) | Compute parity by dropping the lowest set bit.
• Computing parity of word (ParityLookupTable): c++(test) | Compute parity by caching the results.
• Generate random number: c++ | Generate a random number in a range with equal probability.
• Integer palindrome: c++ | Check if a number is a palindrome.
• Power operation: c++(test) | Compute repeated squaring $x^y$.
• Rectangle intersection: c++(test) | Check if two rectangles intersect.
• Reverse digits: c++ | Reverse the digits of a given integer.
• Swap bit: c++(test) | Swap the bits at indices $i$ and $j$.

• Binary search: python(test) | Binary search is a search algorithm that finds the position of a target value within a sorted array.
• Linear search: python(test) | Linear search is a search algorithm that compares x successively with each term of the list until a match is found.

• Bubble sort

java(test)

• Bucket sort

java(test)

• Counting sort

java(test)

• Heap sort

java(test)

• Insertion sort

c++(test), java(test)

one of the fastest algorithms for sorting very small arrays (around 10 elements)

• Merge sort

java(test)

divide and conquer algorithm

• Quick sort

java(test)

divide and conquer algorithm

• Selection sort

c++(test), java(test)

• Convert string (IntToString, StringToInt): c++(test) | Convert integer to string and vice versa.
• IP address validation: c++(test) | Validate IPv4 address that is in the form of "x.x.x.x" where x is a number between 0 and 255.
• Look and say problem: c++(test)
• Naive string search: python(test)
• Palindrome: c++(test) | Check if a string is palindromic.
• Print sine wave pattern string (SineWaveString and PrintSineWaveString): c++(test) | Print a string in sine wave pattern.
• Roman number (VerifyRomanString): c++(test) | Verify if a string is a valid roman number.
• Roman number (RomanStringToInteger): c++(test) | Convert a roman number to integer.
• Run-length encoding (RLE): c++(test) | Run-length encoding is a simple form of data compression in which runs of data are stored as a single data value and count.
• Spreadsheet column decoding/encoding (DecodingSheetColumnId/EncodingSheetColumnId): c++ | Convert a spreadsheet column id to integer and vice versa.

• Interval subset sum: c++(test)

• Introduction to Algorithms, 3rd Edition, by CLRS
• Discrete Mathematics and Its Applications, 8th Edition, by Kenneth H. Rosen
• Cracking the Coding Interview, 6th Edition, by Gayle Laakmann McDowell
• Elements of Programming Interviews, 2nd Edition, by Adnan Aziz, Tsung-Hsien Lee and Amit Prakash