Graph
A graph G consists of a set of the nonnegative number of vertices and a set of the nonnegative number of edges that connect two distinct vertices. It provides the ultimate flexibility to represent structure of data.
In this article, I will show two ways to how to represent a graph on a computer.
read moreSearching Arrays and Peak Finding
Searching (un)sorted array
Sequential search
When searching unsorted array for some element, only what we can do is sequential search, which we take elements in the array one by one and check if it's the one we are searching for.
Binary Heap
Heap
Heap is complete, partially ordered binary tree. Complete means every node at a depth of the tree has subtree that each height differs at most by 1. Partially ordered means that the a element stored in the tree is less than or equal only to its ancestors and greater than or equal only to its descendants, or the other way around.
read moreBinary Search Tree
Dictionary
Search is surely the most frequenly performed action by computers. Let's consider a simple dictionary ADT that represent data structure that can do search and store information.
Dictionary ADT
Partition-Based Sorting
Sorting based on partition of an array
Sorting algorithms more efficient than the one by transpositions exploit the divide and conquer principle.
Shellsort
Shellsort utilizes the near best cases behaviour of insertion sort. It partition the array and then sort the subarray using insertion sort. Then it make subarrays with smaller gap, meaning fewer and longer subarray.
read moreTransposition Sorting
Sorting by transposition
The simplest sorting algorithms use transposition to sort an array of data. Three major algorithms in this type are insertion sort, bubble sort, selection sort. I also write about heapsort that is an algothm that apply the principle behind the selection sort more efficiently. I will show sample implementations of these algorithms and then analyze the performances.
read moreQueues and Deques
Queues
Like stack, queue is a data structure that have ADT restricted compared with one of list. Queue can perform the operation that append an element at the rear of the queue and remove and return the element at the front. There is a data structure containing queue as a special case and it is called deque (double-ended queue). Deque can perform adding an element at the front of the queue and removing at the rear as well as all operations queue can.
read moreStacks and imitating recursion
Stacks
Stack is a data structure that can perform a part of the operation that lists can. We can take only the last element appended to the stack. The operation taking out the element is called "pop", and appending the element is called "push". It sounds like there is no use for stacks, however, stacks can perform those operations more efficiently than lists. This is another kind of tradeoff we saw for lists. Analogous to lists, stacks can be implemented as array-based and linked-stack. And the implementations are quite simple.
read moreLists
List
Note: This is the first post in this blog.
I will investigate basic data structures and algorithms to understand how they can be implemented and how the implementation affect their performance. The contents is mainly based on Data Structures and Algorithm Analysis (https://people.cs.vt.edu/shaffer/Book/). In the book the implementations are written in Java, however, I will use Scala instead. Also, my own analyses are added to the contennts. Enough talking, let's begin.
read more