• Trie Problems
• Trie explanation
• Trie Code
• Infix to Postfix
• Postfix to Infix
  • Evaluate Postfix expression
• Tree Problems
  • Find BST is balanced or not
  • Find Binary Tree is BST or not
  • BST - Recursive Inorder Traversal
  • BST - Iterative Inorder Traversal
  • BST - Morris Inorder Traversal

This article is about Trie and Trees data structure.

trie

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.

Read more

• Recusion problems
  • Factorial
  • Total BunnyEars
  • Even/Odd BunnyEars
  • Triangle
  • Sum of Digits
  • Count no 7
  • Count X in String
  • Count Hi
  • Change XY String
  • Change PI
  • No X in String
  • No Star in String
  • Substring
  • String permutation non repeating
  • Power (x, n)

This article is all about recusion.

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, in which it refers to a method of defining functions in which the function being defined is applied within its own definition. Specifically this defines an infinite number of instances (function values), using a finite expression that for some instances may refer to other instances, but in such a way that no loop or infinite chain of references can occur. The term is also used more generally to describe a process of repeating objects in a self-similar way.

Read more

• Merge Sort
• Table based comparison
• Merge sort code
• Quick sort code
• References

Merge Sort

Merge sort follows divide-and-conquer approach.

 
 MERGE-SORT(A, p, r) // A is array of numbers
 {                   // p is starting index of array
                     // r is last index of array
     if p < r
     then q <- ⌊(p + r)⌋ / 2;  
         MERGE-SORT(A, p, q)
         MERGE-SORT(A, q + 1, r)
         MERGE(A, p, q, r)
}

• Dictionary of algorithms
• Sorting Visualization
• Sorting Wiki Summary
• Sorting algorithms
• Comparisons based sorting
• Online sorts
• Stable sorts
• Time complexity chart

This article talks about Sorting, Sorting techniques/algorithms in computer science

Let’s start with Wikipedia entry about sorting

sorting algorithm

A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists; it is also often useful for canonicalizing data and for producing human-readable output. More formally, the output must satisfy two conditions:

Read more

• Basics
• Bitwise Operators
• Bit Fields
• Problems
  • How set a single bit in a byte?
  • How to unset single bit in a byte?
  • One function to set and unset
  • Unset range of bits
  • Set range of bits
• Recomended readings

Recently, I have realized that no matter how much C, C++ or other high level languages you know it all comes down to bit and bytes view of program.
I started realizing that after all it’s not that easy to actually think and write in bit/byte manipulation. This is my attempt to learn and be more comfortable about thinking in bit/bytes.

• Addition
• Subtraction
• Multiplication
• Negative Binary numbers
• Credits

Addition

 0 + 0 → 0
 0 + 1 → 1
 1 + 0 → 1
 1 + 1 → 0, carry 1
 
  For e.g
 
     1 1 1 1 1    (carried digits)
       0 1 1 0 1
+     1 0 1 1 1
    -------------
=   1 0 0 1 0 0 = 36

• Synchronization Primitives
• Summary of Synchronization Primitives
• Per-CPU variables
• Atomic Operations
• Optimization Barriers & Memory Barriers
• Semaphores
• Spin Locks
  • Read/Write Spin Locks
• SeqLocks
• Read Copy Update (RCU)

As we have discussed earlier about process synchronization, lets discuss about process synchronization primitives offered in Linux Kernel.

This blog is summary of this article

Synchronization Primitives

1. Per-CPU variables
2. Atomic Operation
3. Memory barrier
4. Spin Lock
5. Semaphore
6. SeqLocks
7. Local Interrupt disabling
8. Local softirq disabling
9. Read-Copy-Update

• What is a Process?
• 3 Issues with Sharing
• Carl’s Jr. Restaurant
• Algorithmic approach
• Software Primitives
• Semaphores
• Locks
• Concurrent Programming Construct
• Condition Variables
• Producer-Consumer Problem
• Recommended reading

What is a Process?

Operating system(OS) objective is to keep as many as of the computer resources as busy as possible. It is used to keep track of all the things an OS must remember about the state of user program.

Process is like a box, a complete entity in itself which does a step by step task written in program. More formally it is called program in execution.

Lets consider a very basic operating system with very least complexity. This operating system can run only one process at a time. Since, only one process is working at a time, it may happen that all the resources occupied by process will not be used at the same time.

Print bit values in a byte

Recently, I have been working on interesting piece of code whose crux is to create a array of pointer addresses. Each entry in this array is address pointing to memory location.

For example
Container array contains char addresses. Here, 100 is memory address where char value resides.

Address 100

Sometimes char data type is used as a package of 8 bits not as a valid char value.