Aspects of sci, tech, wonders & nature: Data Structures

Dijkstra's Algorithm Implementation in Java

Share this post!

 Vote this!

Dijkstra's Algorithm is a graph-search algorithm that finds the shortest path between two Vertices on a weighted Graph. For Dijkstra's algorithm, we assume that all distances are positive.

So how exactly does this algorithm work? Basically, we initialize all the distances to infinity, except for the root Vertex which is initialized to 0. We then traverse the Graph from the starting point towards the end point. When we hit a Node, we evaluate the cumulative distance to that Node, which means the distance recorded at the previous Node plus to the distance to the current Node. So if we have A-->B weighted at 5 and B-->C weighted at C, B would record the distance 5, and C would record the distance 8. The reason we initialize to infinity is that the first time we hit that Node, everything will be less than infinity so the first distance will be stored at that Node. more...

The Halting Problem In Computer Science

Share this post!

 Vote this!

One of the most interesting non-programming parts of computer science is the study of what can (and cannot) be computed. For instance, take the question, "does this program complete?" I.e., will it not go into an infinite loop. How would you answer this question, given an arbitrary piece of code? You could try running it. But what if it takes a long time? How long are you willing to wait? Think about whether there is a general solution to this problem -- a method that you could apply to any piece of C code in order to demonstrate that it will eventually come to a stop.

Let's say that you discovered such a solution. It's a program that takes two arguments: the code for a program, and its input. This solution returns true if the program halts on the given input, and false if the program runs forever. Let's call this program DOES-HALT. We can use DOES-HALT as follows: more...

Understanding Different Base Systems

Share this post!

 Vote this!

This essay is targeted at new students of computer programming or computer science who want to understand how base two (binary), base eight (octal), and base sixteen (hexadecimal) work.
First of all, it's important to realize that each of these base systems is just another way of writing down the same number. When you convert a number between different bases, it should still have the same value. In this essay, when I want to refer to the actual value of a number (regardless of its base), I'll do it in base 10 because that's what most people are used to.

It's generally easiest to understand the concept of different bases by looking at base 10. When we have a number in base 10, each digit can be referred to as the ones digit, tens digit, the hundreds digit, the thousands digit, or so forth. For instance, in the number 432, 4 is the hundreds digit, 3 is the tens digit, and 2 is the ones digit. more...

Huffman Encoding Compression Algorithm

Share this post!

 Vote this!

The Huffman encoding algorithm is an optimal compression algorithm when only the frequency of individual letters are used to compress the data. (There are better algorithms that can use more structure of the file than just letter frequencies.) The idea behind the algorithm is that if you have some letters that are more frequent than others, it makes sense to use fewer bits to encode those letters than to encode the less frequent letters.
For instance, take the following phrase: "ADA ATE APPLE". There are 4 As, 1 D, 1 T, 2 Es, 2 Ps, 1 L, and 2 spaces. There are a few ways that might be reasonable ways of encoding this phrase using letter frequencies. First, notice that there are only a very few letters that show up here. It would be silly to use chars, with eights bits apiece, to encode each character of the string. In fact, given that there are only seven characters, we could get away with using three bits for each character! If we decided to simply take that route, that would require using 14 * 3 bits, for a total of 42 bits more...

Prim's Algorithm for Computing Minimum Spanning Trees

Share this post!

 Vote this!

The idea behind minimum spanning trees is simple: given a graph with weighted edges, find a tree of edges with the minimum total weight. What is a spanning tree? A graph that satisfies these three properties: connected, acyclic, and consisting of |V| - 1 edges. (In fact, any two of the three conditions imply the third condition.) What this means in practice is that a spanning tree is a collection of edges that connect any two nodes via a single path. It's probably easiest to understand a tree using the definition that a tree is both connected and acyclic; think about binary trees--every node in the tree is reachable, so it's connected, and there are no cycles because you can't go back up the tree. more...

Dynamic Programming with an example of all-pairs shortest paths

Share this post!

 Vote this!

Dynamic programming is a powerful technique for solving problems that might otherwise appear to be extremely difficult to solve in polynomial time. Algorithms built on the dynamic programming paradigm are used in many areas of CS, including many examples in AI (from solving planning problems to voice recognition).
Dynamic programming works by solving subproblems and using the results of those subproblems to more quickly calculate the solution to a larger problem. Unlike the divide-and-conquer paradigm (which also uses the idea of solving subproblems), dynamic programming typically involves solving all possible subproblems rather than a small portion. more...

Dijkstra's Algorithm For Shortest Paths

Share this post!

 Vote this!

Graphs are useful for representing many problems in computer science and in the real world. Applications of graph representations range from the seemingly simple, finding out whether a node is reachable from another node, to the extremely complex, such as finding a route that visits each node and minimizes the total time (the "travelling salesman" problem). A common, but solvable problem is that of problem of simple path finding. Generally, the task is determining the shortest path from a given node to any other node on the graph.

Graphs are useful for representing many problems in computer science and in the real world. Applications of graph representations range from the seemingly simple, finding out whether a node is reachable from another node, to the extremely complex, such as finding a route that visits each node and minimizes the total time (the "travelling salesman" problem). A common, but solvable problem is that of problem of simple path finding. Generally, the task is determining the shortest path from a given node to any other node on the graph. more...

XOR Encryption Algorithm Explained

Share this post!

 Vote this!

Exclusive-OR encryption, while not a public-key system such as RSA, is almost unbreakable through brute force methods. It is susceptible to patterns, but this weakness can be avoided through first compressing the file (so as to remove patterns). Exclusive-or encryption requires that both encryptor and decryptor have access to the encryption key, but the encryption algorithm, while extremely simple, is nearly unbreakable. Exclusive-OR encryption works by using the boolean algebra function exclusive-OR (XOR). XOR is a binary operator (meaning that it takes two arguments - similar to the addition sign, for example). By its name, exclusive-OR, it is easy to infer (correctly, no less) that it will return true if one, and only one, of the two operators is true. The truth table is as follows: more...

Explaining Sorting Algorithms

Share this post!

 Vote this!

Have an array you need to put in order? Keeping business records and want to sort them by ID number or last name of client? Then you'll need a sorting algorithm. To understand the more complex and efficient sorting algorithms, it's important to first understand the simpler, but slower algorithms. In this article, you'll learn about bubble sort, including a modified bubble sort that's slightly more efficient; insertion sort; and selection sort. Any of these sorting algorithms are good enough for most small tasks, though if you were going to process a large amount of data, you would want to choose one of the sorting algorithms listed on the advanced sorting page.

Bubble sort

The simplest sorting algorithm is bubble sort. The bubble sort works by iterating down an array to be sorted from the first element to the last, comparing each pair of elements and switching their positions if necessary. This process is repeated as many times as necessary, until the array is sorted. Since the worst case scenario is that the array is in reverse order, and that the first element in sorted array is the last element in the starting array, the most exchanges that will be necessary is equal to the length of the array. Here is a simple example: more...

FURTHER READING

Selection sort and Insertion sort

Heap Sort

Merge Sort

Quicksort

Radix Sort a special case sorting algorithm

Sorting Algorithm Comparison

Share this post!

 Vote this!

Sorting algorithms are an important part of managing data. At Cprogramming.com, we offer tutorials for understanding the most important and common sorting techniques. Each algorithm has particular strengths and weaknesses and in many cases the best thing to do is just use the built-in sorting function qsort. For times when this isn't an option or you just need a quick and dirty sorting algorithm, there are a variety of choices.
Most sorting algorithms work by comparing the data being sorted. In some cases, it may be desirable to sort a large chunk of data (for instance, a struct containing a name and address) based on only a portion of that data. The piece of data actually used to determine the sorted order is called the key.

Sorting algorithms are usually judged by their efficiency. In this case, efficiency refers to the algorithmic efficiency as the size of the input grows large and is generally based on the number of elements to sort. Most of the algorithms in use have an algorithmic efficiency of either O(n^2) or O(n*log(n)). more...

Linked List In Java : Complete Tutorial

Share this post!

 Vote this!

Linked Lists are an alternative to ArrayLists that Computer Scientists have come up with. While an ArrayList uses an array internally to store the data, a LinkedList uses nodes to hold the elements. These nodes then point to each other, thus leading to the name "Linked" List. There are three types of Linked Lists: singly-linked lists, doubly-linked lists and circularly-linked lists. Singly-linked lists work by having each node pointing to the next node, with the tail node (or end node) pointing to nothing (or a null reference). Doubly-linked lists expand upon the singly-linked list, with each node pointing to the previous node as well as the next node. In doubly-linked lists, both the head node (first node) and the tail node point to nothing. Circularly-linked lists expand upon the singly-linked list differently than the doubly-linked list; instead of having the tail node pointing to nothing, it "circles" back around, pointing to the head element as the name suggests. more...

Linear Search, Binary Search and other Searching Techniques

Share this post!

 Vote this!

Searching for data is one of the fundamental fields of computing. Often, the difference between a fast program and a slow one is the use of a good algorithm for the data set. This article will focus on searching for data stored in a linear data structure such as an array or linked list. Naturally, the use of a hash table or binary search tree will result in more efficient searching, but more often than not an array or linked list will be used. It is necessary to understand good ways of searching data structures not designed to support efficient search. more...

Space-Time Tradeoffs and Efficiency

Share this post!

 Vote this!

A lot of computer science is about efficiency. For instance, one frequently used mechanism for measuring the theoretical speed of algorithms is Big-O notation. What most people don't realize, however, is that often there is a trade-off between speed and memory: or, as I like to call it, a tradeoff between space and time.
Think of space efficiency and time efficiency as two opposite ends on a band (a continuum). Every point in between the two ends has a certain time and space efficiency. The more time efficiency you have, the less space efficiency you have, and vice versa. The picture below illustrates this in a simple fashion:

Algorithms like Mergesort are exceedingly fast, but require lots of space to do the operations. On the other side of the spectrum, Bubble Sort is exceedingly slow, but takes up the minimum of space. more...

Big-O Notation and Algorithmic Efficiency

Share this post!

 Vote this!

In computer science, often the question is not how to solve a problem, but how to solve a problem well. For instance, take the problem of sorting. Many sorting algorithms are well-known; the problem is not to find a way to sort words, but to find a way to efficiently sort words. This article is about understanding how to compare the relative efficiency of algorithms and why it's important to do so, using a concept called big-O notation to define the efficiency of an algorithm.

Why Brute Force is not Efficient Enough

If it's possible to solve a problem by using a brute force technique, such as trying out all possible combinations of solutions (for instance, sorting a group of words by trying all possible orderings until you find one that is in order), then why is it necessary to find a better approach? The simplest answer is, if you had a fast enough computer, maybe it wouldn't be. But as it stands, we do not have access to computers fast enough. For instance, if you were to try out all possible orderings of 100 words, that would require 100! (100 factorial) orders of words. (Explanation) That's a number with a 158 digits; more...

Graphs and graph theory in computer science

Share this post!

 Vote this!

What is a graph?

A graph is a way of representing connections between places. Mathematically, a graph is a collection of nodes and edges. Nodes are locations that are connected together by the edges of the graph. For instance, if you had two small towns connected by a two-way road, you could represent this as a graph with two nodes, each node representing a town, and one edge, the road, connecting the two towns together. In addition to the undirected graph, in which the edge is a two-way connection, there are directed graphs, in which edges connect only one way. For instance, you could represent the previous example of two cities connected by a road as a directed graph consisting of two nodes and two edges, each edge connecting one of the nodes to the other. more...

What is a heap?

Share this post!

 Vote this!

A heap is a partially sorted binary tree. Although a heap is not completely in order, it conforms to a sorting principle: every node has a value less (for the sake of simplicity, we will assume that all orderings are from least to greatest) than either of its children. Additionally, a heap is a "complete tree" -- a complete tree is one in which there are no gaps between leaves. For instance, a tree with a root node that has only one child must have its child as the left node. More precisely, a complete tree is one that has every level filled in before adding a node to the next level, and one that has the nodes in a given level filled in from left to right, with no breaks. more...

Data Structures Implementation in Java : Ultimate Notes

Share this post!

 Vote this!

These notes provide an introduction to some of the most commonly occurring data structures. The language used is Java. The aim is not the greatest generality. The DataStructures package developed here is not as extensive as the Collections framework, first released with Java 1.2. For portable applications, you should use the Collections framework where possible. The DataStructures package, however, includes graphs which are not currently in the Collections framework; and the greater simplicity of the DataStructures package makes it more suitable as a basis for learning about fundamental principles of data structures and algorithms.

THIS NOTES COVERS THE FOLLOWING

The Queue Data Structure in C++

Share this post!

 Vote this!

Queues are data structures that, like the stack, have restrictions on where you can add and remove elements. To understand a queue, think of a cafeteria line: the person at the front is served first, and people are added to the line at the back. Thus, the first person in line is served first, and the last person is served last. This can be abbreviated to First In, First Out (FIFO).
The cafeteria line is one type of queue. Queues are often used in programming networks, operating systems, and other situations in which many different processes must share resources such as CPU time.
One bit of terminology: the addition of an element to a queue is known as an enqueue, and removing an element from the queue is known as a dequeue. more...

QuickSort Tutorial

Share this post!

 Vote this!

The core concept of quick sorting is very simple. Given a list, a ‘pivot’ is chosen (any arbitrary element from the list). Now all elements of the list, greater than the pivot are moved to the right. And all elements of the list, smaller than the pivot are moved to the left. Thus we form two unsorted lists. One list is on the left of the pivot, consisting of elements smaller than the pivot. Another list is to the right of the pivot, consisting of elements greater than the list. But what is important here, is that the pivot element has found its place. Consider this list...

5 3 7 2 1 6 -The unsorted list

If we take ‘5’ as the pivot, the list is rearranged as follows...

3 2 1 5 7 6 - After arranging the elements around the pivot
1 2 3 5 6 7 -Sorted list (which is our target) more...

Merge Sort using Java with program code

Share this post!

 Vote this!

In computer science, merge sort or mergesort is a sorting algorithm for rearranging lists (or any such linear sequential data storage structure) into a specified order. It is a particularly good example of the divide and conquer algorithmic paradigm. It is a comparison sort. Merging is the process of combining two or more sorted files into a third sorted file.

Conceptually, merge sort works as follows:

1. Divide the unsorted list into two sublists of about half the size
2. Sort each of the two sublists
3. Merge the two sorted sublists back into one sorted list more...