Let us start with the heapsort algorithm:
heap_sort(int Arr[])
{
int heap_size = n; build_maxheap(Arr);
for(int i = n; i >= 2 ; i--)
{
swap(Arr[1], Arr[i]);
heap_size = heap_size - 1;
heapify(Arr, 1, heap_size);
}
}
The build_maxheap() funnction has a standard implementation of O(n). The important part of the sorting is the for loop, which executes for n times. Inside that we have a swap method call and heapify method call. The heapify method is a standard walk through of complete binary tree. Hence, the complexity is O(log n)
T(n) = O(n) + n * O(log n) =…
Problem statement
Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size).
Solution
There can be two ways you can solve the above problem.
- Option A: The stack — efficient when pushing an item
- Option B: The stack — efficient when popping an item
In this post lets us discuss the an implementation of option A.
Exception handling: We have a ‘Stack Overflow’ exception — which can occur @ push operation in runtime to handle that case. Similarly we have a ‘Stack Underflow’ exception for pop operation. The checks depends on…
How insertion sort works?
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It works best on a nearly sorted list. It has the following characteristics
- Stable; i.e., does not change the relative order of elements with equal keys
- In-place; i.e., only requires a constant amount O(1) of additional memory space
- Online; i.e., can sort a list as it receives it
Sort an almost sorted array
Claim
Insertion sort works the most efficient when the incoming or given array is almost sorted. The runtime in those cases are linear => O(n)
Experiment
Let us actually prove the runtime is O(n)…
Data Structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. They can be broadly classified as primitive, composite/abstract/non-primitive data structures. Primitive structures are the basic units of storage like boolean, integer, float, double. These are not that significant when compared to other types. In this post we will discuss about linear data structures and how to implement them in python (with built-in data structures in python).
Non-primitive data structure
The Non-primitive data structure cannot be directly controlled by computer commands, we need to define and implement the operations supported by them. Depending…
Most of us know about existence of various OS (Operating Systems) like Linux, Windows 7/8, Mac OS. Apart from the fact that they are coming from different vendors, they are built for different purposes. Lets try to analyze it in this post. We can be broadly categorize the OS as below:
Single User and Single Task OS:
OS like MS-DOS allow single user to interact and run a single task @ given time. Mainly these Operating system are for Personal Computers (PC) and Handheld devices. …
Character encoding — Why ?
If you use anything other than the most basic English text, people may not be able to read the content you create unless you say what character encoding you used.
For example, you may intend the text to look like this:
MIPS R2000 is a RISC processor. Its ISA has fixed-width 32 bit instructions and fall into one of the following three categories: R-type, I-type, and J-type
All the Instructions — can also be grouped under following functional groups.
Arithmetic Instructions: +, -, *, / operations on std data-structures (short, int, long, float)
Logical Instructions: AND, OR, NOT, XOR operations on std data-structures (short, int, long, float)
Comparison Instructions: <, >, =, >=, <= operations on std data-structures (short, int, long, float)
Branch Instructions: Changing the PC register values — updating with target address defined in the instruction
Load, Store and…
We all know that the standard file for representing executable, shared library and object file is ELF in UNIX based systems. In this post we will not talk about ELF file formats or any details of how to load it in to memory, but about the steps kernel does after loading ELF into memory and starting the process corresponding to it.
Assuming all process related entries are made in kernel data structures and memory is allocated for it, we start the steps on how kernel load, initialize and start executing a ELF executable file.
1. Kernel reads and load multiple…
Most of the system programmer used the Timer Interrupt for various reasons especially in synchronization. Some of the including me didn’t spent much time on how exactly it works. This post is my attempt to explain my understanding on how it works?
Most of the IBM compatible PCs come with a hardware unit called Programmable Interrupt Timer (PIT — Chip 8253 and 8254) or an equivalent circuit embedded in Mother board. They have separate clock and 3 counter circuits which can be programmed to track different tasks. At the time of booting OS typically sets the frequency @ which it…
Have you ever wondered how exactly computer does all the tasks from browsing, playing games, videos, editing documents, etc… By Computers I mean every thing from mobile phones, laptops to Dedicated server class machines and even world fastest super computers. All most all of them work on same basic design done by Von Newmann popularly known as ‘Von Newmann Architecture’. Let us discuss about it on a high level in this post.
Basic characteristics of any computer:
- Computer has 4 main sub-systems: Memory, ALU (Arithmetic/Logic Unit), Control Unit, Input/Output System (I/O)
- Program is stored in memory during execution
- Program instructions are executed sequentially till a…
