PROGRAMMING

Data structures and algorithms



Table of Contents

Data Structure4

Array4

Heap4

Stack5

Queue5

Deque6

Ring Buffer6

Linked List7

Double Linked List7

Graph8

Hash Table9

Binary Tree10

Red-Black Tree10

Priority Queue10

B-Tree11

Directed Graph11

Weighted Graph12

Algorithms:12

Depth-first search,12

Breadth-first ,12

Dijkstra's algorithm,13

Floyd-Warshall algorithm,14

Ford-Fulkerson,14

Heap Sort,14

Basics15

Example:15

Shell Sort,15

Quick Sort,16

Radix Sort,16

Bucket Sort,17

Selection Sort,17

Merge Sort,18

Bubble Sort,18

Binary Search,19

Greedy Algorithm,19

Brute Force Algorithm,19

Divide and Conquer,20

Fibonacci search technique,20

Monte Carlo methods,20

Alpha-beta pruning21

Data structures and algorithms

Data Structure

Array

It is a linear data structure and it's mainly used to store similar data. An array is a particular method of storing elements of indexed data. Elements of data are stored sequentially in blocks within the array. Each element is referenced by an index, or subscript. Arrays can also be multidimensional - instead of accessing an element of a one-dimensional list, elements are accessed by two or more indices, as from a matrix or tensor. The index is usually a number used to address an element in the array (Russell, 2010).

Heap

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) = key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.) There is no restriction as to how many children each node has in a heap, although in practice each node has at most two (Russell, 2010).

Stack

A stack is a data structure that allows data to be inserted (a 'push' operation), and removed (a 'pop' operation). Many stacks also support a read ahead (a 'peek' operation), which reads data without removing it. A stack is a LIFO-queue, meaning that the last data to be inserted will be the first data to be removed (Russell, 2010). When we insert data into a stack, it is placed at the head of a queue. This means that when we remove data, it will be in reverse order. Adding 1,2,3,4 will return 4,3,2,1. Stacks aren't the most frequently used data structure, but they are extremely useful for certain tasks.

3

2

1

4

3

2

1

Figure 1. Stack before push operation, and stack after

 

4

3

2

1

3

2

1

Figure 1. Stack before pop operation, and stack after

Queue

Queues provide services in computer science, transport, and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the queue performs the function of a buffer. Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes (Russell, 2010). Common implementations are circular buffers and linked lists

Deque

Deque is the data structure that supports insertion and deletion of object on front and rear end of the queue. Deque operation is richer than stack or queue, Abstract Data Type of deque are as follows:

insertFirst(e) - Insert a new element at the front end of deque.

insertLast(e) - Insert a new element at the rear end of ...