Bitonic Sort
Posted on January 6, 2012 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra
Bitonic Sort
Bidirectional Bubble Sort
Construct a full binary tree from a pre-order list of marked nodes
Question: construct a full binary tree from a list of nodes in pre-order. The nodes are marked ‘i’ if they are inner nodes and are marked ‘l’ if they are leaf nodes.
Example given a list of nodes marked as (i, i, i, l, l, i, l, l, i, l, l), we need to construct a tree from those nodes so that the result looks like this:
Notice how all “l” nodes are leaf nodes and “i” nodes are inner nodes?
[Read More]
Andersson Trees
http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx
ArrayDeque + Stack Algorithms
Sorted Linear Hash Table
Search trees
Concurrent Skip List
Huffman Codes
Background
When we encode characters in computers, we assign each an 8-bit code based on an ASCII chart. But in most files, some characters appear more often than others. So wouldn’t it make more sense to assign shorter codes for characters that appear more often and longer codes for characters that appear less often?
This is exactly what Claude Shannon and R.M. Fano were thinking when they created the first compression algorithm in the 1950’s.
[Read More]
Convert Binary tree to double linked list in inorder traversal
Problem Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.
Example Input
[Read More]