Site icon Flutter Packages | Pub dev Packages – Flutter Mobile App World

Implementation of Data Structures and Algorithms in Dart

Flutterappworld

A repository that contains the Implementation of Data structures and Algorithms in Dart.

What is an Algorithm?

f: I => O

An algorithm is defined as a function that maps arbitrary-sized input to fixed-sized output. The function could be a single step or a series of steps. It can be applied just once, in an iteration or under recursion.

An algorithm has to be –

  1. Correct
  2. Efficient

Correctness –

The correctness of an algorithm is defined through Induction. It follows the following steps –

  1. Base Case – We check the algorithm for the smallest number of inputs possible ie. 1
  2. Hypothesis – We assume that the algorithm is going to work for a random number of input n.
  3. Inductive Step – We check the correctness of the algorithm for input n+1.

Now that we have proved the correctness of the algorithm, let’s argue for efficiency.

Efficiency –

Efficiency defines how fast an algorithm runs and how fast it runs relative to all other possible approaches. Mathematically, we assume all processors have the same processing power and expect efficiency to depend upon the size of the input. If we were to plot it on the graph, it would be a value on y-axis(as a dependent variable), dependent on the size of the input(on x-axis).

We have a few functions that relate the algorithm’s input size to its performance.

  1. Constant Time – O(c)
  2. Linear Time – O(n)
  3. Logarithmic Time – O(log(n))
  4. Logarithmic Linear Time – O(n * log(n))
  5. Quadratic Time – O(n^2)
  6. Polynomial Time – O(n^c)
  7. Exponential Time – 2^(O(n))

Data Strcutures –

To understand Data Structures, we first need to understand our current model of computation –

We used to have 32-bit CPUs(processors), which allowed only 2^32 ie. 4 gigs of RAM(memory). Technology evolved and now we have 64-bits system which allows 2^64 ie. 20 exabytes of memory. But the CPU’s word size is still pretty small ie. 64 bits. They can perform –

  1. binary ops
  2. arithmetic ops
  3. bitwise ops
  4. read and write in memory

But what if we need to perform any operation on a data larger than 64 bits?

Thats what we need to Data Structures for.

Data Structures are used to operate on large amount of data. There are two ways to store data of a non-constant amount to perform operations on that information faster –

  1. Reduce the problems to Structurs you already know.
  2. Design your own Recursive Algorithms.

Following are the topics that comes under each of those ways –

1. Reeduce the problem to what you already know –

Search Problems –

  1. Static Array
  2. Linked List
  3. Dynamic Array
  4. Sorted Array
  5. Direct Access Array
  6. Hash Tables
  7. Balanced Binary Tree
  8. Binary Heap

Sort Algorithm –

  1. Insertion Sort
  2. Selection Sort
  3. Merge Sort
  4. Counting Sort
  5. Radix Sort
  6. AVL Sort
  7. Heap Sort

Shortest Path Algorithm –

  1. Breadth First Search
  2. DAG Relaxation
  3. Depth First Search
  4. Topological Sort
  5. Bellman Ford
  6. Dijkstra
  7. Johnson
  8. Floyd-Warshall

2. Design your own Recursive Algorithm

  1. Brute Force
  2. Decrease and Conquer
  3. Divide and Conquer
  4. Dynamic Programming
  5. Greedy/ Incremental

Download and/or contribute this code on GitHub

Implementation of Data Strcutures and Algorithms in Dart
https://github.com/kaljitism/Data-Structures-and-Algorithms-Dart
0 forks.
5 stars.
0 open issues.

Recent commits:

Exit mobile version