DEV Community: steve kimoi

WHAT IS THE DIFFERENCE BETWEEN PROOF OF WORK AND PROOF OF STAKE?

steve kimoi — Sat, 07 Jan 2023 13:08:31 +0000

Proof of Work (PoW) and Proof of Stake (PoS) are both consensus mechanisms that help keep the blockchain secure and add new transactions on the blockchain.

A consensus mechanism is a way in which the nodes agree on the authenticity of transactions that have been recorded in the blockchain.

Proof of Work (PoW): this is a consensus mechanism whereby nodes (computers) compete to be the first to solve a complex computational problem (try to guess the “hash” number) for them to come up with new blocks and add them on the blockchain. The miner who comes up with the block is then awarded with new coins. Check out my blog on Mining (PoW) here.

Proof of Stake (PoS): this is a consensus mechanism whereby a node ‘stakes’ a certain amount of the native cryptocurrency for them to validate transactions and create new blocks. This crypto that they’ve staked acts as collateral for them to participate as validators. The chances of a node being selected as a validator depend on the amount they’ve staked. Once the validator is choosen to come up with the new block, they are awarded a portion of the gas fees (transaction fees).

The purpose of introducing proof of stake was to combat environmental challenges that were being caused by Proof of Work.

The differences between proof of work and proof of stake are:

In PoS the block creators are known as validators: they check the transactions, verify the activity, vote on outcomes and maintain records.
In PoW the block creators are known as miners: the miners work to solve for the “hash”, then they are awarded with a coin.
In PoS for you to become a validator, you only need to own enough tokens or coins to stake. The use of stake promotes:

I) Decentralization: this is because validators are chosen according to their stake in the network rather than computational power. It ensures decentralization since you do not need high computational power to participate as a validator.

II) Security: since the validators have a financial stake in the network, they will act in the best interests of the network.
In PoW for you to become a miner, you must invest in equipment and energy to power the computers solving the computations. This makes PoW less accessible to individual users and more dominated by large mining pools with access to economies of scale.
PoS systems are more energy efficient as compared to PoW, this is because you need less computational power as compared to PoW systems.

One of the downsides of PoS is that an entity or a group of people can decide to acquire a significant portion of total stake in the network, thus causing some form of “centralization”. Which can enable them to have a level of influence on the network, as they will have a greater probability of being chosen as validators therefore having more opportunity to earn rewards.

However, there are mechanisms that are in place to prevent validators from acting maliciously against the best interest of the network e.g slashing.

Slashing is a mechanism where validators who might have violated the rules of the network have a portion of their stake confiscated.

Thread version of this article can be found at:

WHAT IS THE DIFFERENCE BETWEEN PROOF OF WORK AND PROOF OF STAKE?

The terms Proof of Work(PoW) and Proof of Stake(PoS) tend to be confusing a times if you are new in the blockchain ecosystem.

What do they mean in simple definitions and what are their differences? Let’s see pic.twitter.com/MC4emtspqC
— steve.eth (@stevekimoi) January 7, 2023

Thank you. Don't forget to check the rest of my blogs if you'd like to learn more about blockchain and web3!

Cover image by bitpay

WHAT IS MINING IN BLOCKCHAIN?

steve kimoi — Fri, 23 Dec 2022 15:45:20 +0000

Have you ever heard the term "mining" in the context of blockchain and thought it had something to do with extracting cryptocurrency from the earth? While that may sound funny, the concept of mining in blockchain is quite important and complex.

Mining in blockchain refers to two main processes:

It is the process by which new transactions are verified and added to the blockchain.
It is the process by which new “digital coins” are created through a process called Proof of Work(PoW).

So how does mining work?
The process of mining usually involves a A decentralized network of specialized computers, known as "miners," compete to verify and record new transactions on the blockchain. The first miner to solve a complex cryptographic puzzle and provide the correct 64-digit hexadecimal number (called a "hash") is rewarded with new coins. The verified transactions are then added to the blockchain as a new block.

The process of mining can be resource-intensive, as it requires a lot of computational power to solve cryptographic puzzles. Miners often use specialized hardware, such as application-specific integrated circuits (ASICs) or graphics processing units (GPUs), to increase their chances of solving the puzzles and earning rewards.

The rewards for mining are not just limited to new coins. Miners also receive transaction fees (gas fees) from users who want their transactions to be included in the next block. These fees incentivize miners to prioritize and include the transactions in their blocks. The higher the gas fee the higher the probability of your transaction being added to the block.

The process of mining is designed to be difficult, as it helps to ensure the security of the blockchain. As more miners join the network and the competition for rewards increases, the puzzles become harder to solve, requiring even more computational power. This ensures that it is not easy for attackers to manipulate the blockchain by adding fraudulent transactions.

The concept of Proof of Work (PoW) is not used by all blockchain networks. Some alternative consensus algorithms, such as Proof of Stake (PoS), do not rely on mining to verify transactions and create new blocks. Instead, they use a different process, such as selecting the next block creator through a randomized "lottery" based on their stake (i.e. the amount of coins they hold) in the network. An example of a blockchain network that uses PoS is Ethereum.

Why is mining important?

Mining helps to decentralize the network: By allowing anyone with the necessary hardware and resources to participate in the process of mining, the blockchain becomes decentralized and not controlled by a single entity. This ensures that the network is resistant to censorship and manipulation.
Mining ensures the integrity of the blockchain: By verifying transactions and adding them to the blockchain, miners help to ensure the integrity and accuracy of the data on the blockchain. This is especially important for financial transactions, as it helps to build trust and confidence in the network.
For cryptocurrencies like bitcoin, mining is the only way to release new coins into circulation. It also gives miners voting power in the network and verifies and secures the blockchain, allowing it to function as a decentralized network without the need for third parties.
Additionally, mining helps to prevent the "double spend" problem, where a single digital coin is spent twice.

In conclusion, mining plays a crucial role in the functioning and security of blockchain networks and is essential for the creation and circulation of new digital coins.

ACCESSING NFT SMART CONTRACT CODE

steve kimoi — Sat, 03 Dec 2022 08:22:27 +0000

Web3 is fascinating! Did you know that you are able to access the source code of any NFT smart contract deployed in the Ethereum network?

Let's see how:

The best way to view the smart contracts is through Etherscan, an Ethereum block explorer. Etherscan allows users to easily search and browse transactions and blocks. It’s like the Google of Ethereum.

Go to Etherscan through https://etherscan.io: This is the landing page that you’ll see:

Now, we are going to search the smart contract of a popular NFT marketplace,Bored Ape Yatch Club. We will type in the symbol which is BAYC inside the search bar.

Scroll down through the filter search bar under Tokens (ERC 721).

Click on the “BoredApeYachtClub(BAYC)” and you'll be automatically redirected to the site containing the contract details.

You will immediately see this page:

On your far right you will see “Profile summary” containing the contract address, the official site link and the social profles.

Click on the contract address. This is the site that you’ll see:

Scroll downwards and you’ll immediately see this:

Click on the contract tab that has a green tick on the right. You will be immediately redirected to this page:

Scroll downwards and you’ll see the smart contract code. Fascinating!

A practical example of decentralization in web3.

WHAT IS GAS IN THE ETHEREUM BLOCKCHAIN NETWORK?

steve kimoi — Thu, 20 Oct 2022 12:27:49 +0000

GAS:
Gas in the blockchain ecosystem is normally compared to the gasoline that is required by a car to move.

Why do we give such a comparison, and what is gas anyway? Let's have a look:

Gas: this is the fee that is required to successfully run a transaction or execute a smart contract in the Ethereum blockchain network.

The main reason for introducing the concept of gas was:

To pay the Ethereum miners for the energy they’ve used to conduct transactions. This is why it is described as the fuel that is needed to run the Ethereum network.
To provide a layer of security by making it expensive for users to spam the network.

A lot of people hate gas fees because they can be very expensive. Why is this so?

When there is a surge in activity of the network; a lot of people trying to conduct transactions at once, the gas fees usually skyrocket. This is because as more transactions occur, the blockchain needs more computational power, thus leading to the surge in gas prices.
When you’re executing a transaction that requires more computational power. Simple transactions such as a peer-to-peer transaction of sending ether, doesn’t require a lot of computational power thus it will use little gas. But complex transactions such as interacting with smart contracts will require higher gas fees.

Now that we have an idea of what is gas, let's see at how gas fees are calculated:

How are gas fees calculated:
Gas fees are paid in Ethereum’s native currency, ether (ETH). The gas prices are usually denoted in gwei (a denomination of ETH i.e 1 gwei = 0.000000001 ETH (10^-9 ETH).

Gas fees are usually calculated using the formular:

Gas limit * Gas price per unit = Gas fees

Gas limit is the maximum amount of gas a user can use to in a transaction.

Gas price is the the amount of ETH paid to the miners for processing the transactions.

So, if the gas limit was 30,000 and price unit was 300 gwei, the result would be:

30,000 * 300 = 9,000,000 gwei or 0.004ETH

That sums it all. I hope you now have a good understanding of what gas is in the blockchain ecosystem and how it works.

Thank you for reading this far!

103: DATA STRUCTURES IMPLEMENTATION

steve kimoi — Thu, 18 Aug 2022 11:22:00 +0000

In my previous article, 102(a):Deep dive into data structures, I expounded more on the various types of data structures that are commonly used and theoretically explained how they are implemented.
In this article, we will get our hands a little bit dirty by practically implementing them.

Note:
I’ve used python for implementation since it is human friendly thus can be understood by a vast number of people.
Link to the GitHub repository that contains the sample codes can be found in their respective sections

1.Stack data structure:
As we stated earlier, stack is a data structure that follows the LIFO principle, that is, elements that get in last come out first. Any time an element is added it goes onto the top of the stack and the only element that can be removed is the element on top of the stack. It is an example of a linear data structure

Types of stacks:
There are two types of stacks:

Register stack: It is a memory element present in the memory unit and can handle a small amount of data only. It is small compared to memory stack.
Memory stack: It handles a large amount of memory data. It’s height is quite flexible as compared to register stack.

Applications of stack:

Reverse a word: you can push a given word to stack letter by letter then pop letters from the stack.
Redo and undo features in places such as editors
Backtracking algorithms, as it helps you come back from the previous state. This can be seen in games such as chess, finding your way through a maze e.t.c
Forward and backward features in browsers

Implementation of stack:
Stacks can be implemented in two ways:

Arrays
Linked lists

a)Implementing stacks using arrays:

output

Github link

b)Implementing stacks using linked lists:

Output:

Github link

2.Queue data structure:
This is also a type of linear data structure in which addition of an element takes place from one end called the rear(tail) and removal of an element takes place from the other end also called front(head).

It follows the FIFO (first in first out) principle, meaning the first element to be inserted will be the first element to be removed.

Applications of queue:

Serving requests on a single shared resource e.g printer
In call center stations, queues are used to put callers on hold until a service representative is free Implementation of queue: Queue can be implemented using:
- Arrays
- Linked lists

a)Implementing using arrays:

Output:

Github link

b)Implementing using Queue from queue library:

Output:

Github link

3.HashMap data structure:
As I stated in the previous article, a HashMap is a type of data structure that maps certain keys to certain values.

Implementation of HashMap:
HashMaps are implemented in python using dictionaries

Example 1:

Output:

Github link

Example 2:

Output:

GitHub link

4.Graph data structure:
Graphs are a type of non-linear data structure that arranges data as multiple nodes. They are connected together using edges. Nodes represent entities where data is stored and the relationship between nodes are expressed by edges.

Types of graphs:

Undirected: a type of graph where all the edges are bi-directional, the edges do not point at a specific direction.
Directed graph: a type of graph where all edges are uni-directional, the edges point at a specific direction.
Weighted graph: a graph that has a value associated with every edge.
Unweighted graph: a type of graph that has no value or weight associated with the edge. Applications of graph:
Used in social networks such as Facebook and LinkedIn
Used in blockchain technology, where the nodes are blocks that store many transactions while edges connect many subsequent blocks
Google maps also uses graphs
It also helps define the flow of computational software programs. Implementation of graphs:

Output:

GitHub link

5.Set data structure:
This is a type of data structure that can store any unique values. It does not allow repeating of values
Applications of set data structures:

It is used in eliminating duplicates
It is used to sort, because it is ordered
It is also used for searching, checking whether a given element is present in the in the set.

Implementations of set data structures:
They can be implemented using the set() function in python

Output:

GitHub link

Thank you for reading this far!

102(b):DEEP DIVE INTO DATA STRUCUTURES AND ALGORITHMS:

steve kimoi — Tue, 19 Jul 2022 06:35:00 +0000

Deep dive into Algorithms:
In my first article, I gave a very brief introduction to algorithms, its definition, characteristics, types and their importance. In this article, I’ll give an in-depth explanation.

We will cover:

Time complexity
Space complexity
Asymptotic notations

An algorithm is said to be efficient if it takes less time and consumes less memory. The performance of an algorithm is based on the time complexity and space complexity. Thus, knowing time and space complexity enables us to make the program behave in required optimal conditions. This makes us efficient programmers.

Time complexity:
Time complexity of a program is the total time required by a program to run till its completion. It does not examine the total execution time but rather it gives information about the variation (increase or decrease) in execution time when the number of operations (increase or decrease) in an algorithm.

Time complexity of an algorithm is usually expressed using the big-0 notation. This is an asymptotic notation to represent the time complexity.

Time complexity is estimated by counting the number of steps performed by and algorithm to finish its execution.

A basic example could be:

We are told to find the square of any number, n. One solution can be running a loop for n times, and adding the number n to itself n times:

         ``` 
          for i = 1 to n:  
             n = n + n  
             return n
         ```

Or we can simply use the mathematical operator * to find the square:

          ```
          return n * n
          ```

For the first solution, the loop will run n number of times, thus, the time complexity will be n at least, and as the value of n increases the time taken also increases.

For the second solution, the time taken will be independent of the value of n. Thus, the time complexity will be constant.

Calculating time complexity:
Disclaimer: I have used the same example as study tonight site.

The most common way of calculating time complexity is by using the big-0 notation. This method removes all the constants, so that the running time can be estimated using n as n approaches infinity.

For example:

             ```
             statement
             ```

For the above statement, the running time will not change in relation to n. This will make the time complexity constant.

               ```
               for x in range(n):  
                   statement
               ```

The time complexity for the above algorithm will be linear. The running time of the loop will be directly proportional to n. When n increases, so does the running time.

               ```
               for x in range(n):  
                   for j in range(n):  
                       statement
               ```

The time complexity for the above code will be quadratic. This is because the running time of the above loops is proportional to the square of n.

Types of notation for time complexity:

The various notations used for time complexity are:

1. Big 0 notation (oh)
2. Big Ω notation (omega)
3. Big theta notation (theta)

1. Big Oh:represents worst case of an algorithm’s time
complexity. A set of functions that grow slower than,
or at the same rate as the expression. It indicates
maximum time required by an algorithm for all input
values.
2. Big Omega: represents best case of an algorithms
time complexity. It is a set of functions that grow
faster than or at the same rate as the expression. It
indicates minimum time required by an algorithm for
all input values.
3. Big theta: represents average case of an
algorithm’s time and space complexity. Consists of
all functions that lie in both O and Omega.

Now let’s understand what space complexity is:

Space complexity:
Space complexity is the amount of memory required by the algorithm during the time of its execution. It includes both auxiliary space and space used by the input. Auxiliary space is the extra/temporary space used by an algorithm.

Space complexity = auxiliary space + input space

The following components in an algorithm generally require space:
1. Data space: this is the space required to store all
the constants and variables (including temporary
variables).
2. Instruction space: this is the space required to
store the executable version of the program.
3. Environmental space: this is the space used to store
the environment information used to restore the
suspended function. E.g when a function (x) calls a
function (y), the variables of the function (x) are
stored in the system stack temporarily while
function (y) is being executed inside function (x).

When we are calculating the space complexity, we usually consider data space only and neglect instruction space and environment space.

Calculating the space complexity:
In order to calculate the space complexity, we need to know the amount of memory used by different data variables, although it may be different for different operating systems, the method of calculation is the same.

Let's compute the space complexity using a few examples:

Disclaimer: the examples below are copied from study tonight.

Example 1:

            ```
            def myFunction():  
                 Int(a) = x + y + z  
                 return a 
            ```

In the example above, the total amount of memory used is ( 4 + 4 + 4 + 4 ) = 20 bytes since the variable types are all integers . The additional 4 bytes is for the return value.

This is a Constant Space Complexity, since the memory required is fixed.

Example 2:

              ```
              def myFunction():  
                 int( sum( int(arr[]), int(n) )) 
                 int(x) = 0   
                 for i in range(n):  
                     x = x + arr[i]  
                     return x 
              ```

In the above example, 4*n bytes is required for the arr[].
4 bytes each is required for x, n and i

Thus, the total memory required will be (4n + 12), thus the space complexity will be called Linear Space Complexity.

Now that we have a good understanding of time and space complexity, we’re going to look at the standard ways of expressing them.

Asymptotic notations:
These are standard notations that are used to express the time and space required by an algorithm. This is because it's impossible to provide an exact number of time and space required by the algorithm.
There are three main types of Asymptotic notations:

1. Big O notation

2. Theta notation
3. Omega notation

Big O notation:
This usually represents the worst-case scenario of an algorithm. It is also known as the upper bound of the running time of an algorithm. It represents the complexity of your code using algebraic terms.

It tells us that a function will never exceed a specified time for any value of input n.

Example: let us consider a linear search algorithm where we pass through elements inside an array, one after the other, to search for a particular number. Our worst-case scenario will be if the element is located at the end of an array. This leads to a time complexity of n, where n is the total number of the elements. When we use Big O notation, we say that the time complexity will be O(n). This means that the time complexity will never exceed n. This defines the upper bound, which means that it can be less than or equal to n.

Omega notation:
This is used to define the best-case scenario. It defines the lower bound. It indicates the minimum time required for an algorithm.

Theta notation:
Time complexity represented by this notation is the average value or range within which the actual time of execution will be.

102(a) : DEEP DIVE INTO DATA STRUCTURES AND ALGORITHMS:

steve kimoi — Mon, 04 Jul 2022 12:53:53 +0000

We started off by having a brief introduction to data structures and algorithms in our first article, lets now have a more in depth look into each of these:

Note: I’ll be using python through these series of articles.

Deep dive into data structures:
In our first article, Introduction to data structures and algorithims, we began by defining what data structures are, now let's have a more detailed understanding of them.

The term data structure is made up of two words, “Data” and “Structures”. Data itself means collection of some information e.g some users information. Structure in simple words can be described as organizing. Combining the two, data structures can be described as organizing a bunch of data in such a way that it can be used efficiently with respect to time and memory.

Before having a deeper look into the classic and fundamental data structures, let’s first distinguish the difference between data structures and data types:

Data type: this is a classification that defines which type of value a variable has and which type of mathematical, relational or logical operations can be applied to it without an error. Examples: float, strings, integers e.t.c

Data structures: as we have said, data structures are collection of different forms and types of data that has a set of specific operations that can be performed. It can be described as a collection of data types. Examples: stacks, queues, linked lists, binary tree e.t.c

Now let’s have a deeper look into the classic and fundamental data structures:

A. Array:
A data structure that stores data types by allocating memory slots. It is the simplest way to store information in a computer.

All elements stored in an array have to be of the same data type.

Arrays are usually used in numerical computation tasks or as a supporting data structure to implement other data structures e.g stacks, lists, queues.

Implementing array data structure in python:
In order to use arrays in python you’ll have to import a library like NumPy library.

Python has a numeric implementation of arrays with the array module

It helps users specify the python data type that the array holds at initiation.

Python array comes in with built in functions like:

append(item): for adding items to the end of the array.

count(item): for counting the number of occurrences of an item within an array.

insert(item, index): to insert item at position index.

remove(item): for deleting the item.

You can check out more methods over here.

There are more specialized implementations of arrays in python:

bytes objects: this is an immutable sequence of single bytes.

bytearray(): this is a mutable arrays of single bytes.

str objects: immutable arrays of unicode characters declared as single quotes, double quotes or tripple quotes.

tuple objects: an immutable sequence for storing multilpe items in a single variable.

B. Stack(LIFO):

This is a container of objects where item insertion and deletion are carried out according to last in first out (LIFO) principle.

The insert and deletion operations are normally called push() and pop() respectively.

A practical example of where stack is used in an application is: the “undo” button in a text editor checks the last inserted command, and removes it from the stack.

Some other functions associated with stack are:

empty(): returns whether a stack is empty

size(): returns the size of the stack

top() / peek(): returns a reference to the topmost element of the stack.

Implementing stack data structure in python:
Stacks in python can be implemented using the following ways:

Lists
Collections.deque
Queue.LifoQueue

1. Lists:
Pythons built in lists can be used as a stack.

append() is used to put elements on top of the stack while pop() is used to remove the elements in the LIFO order.

One of the shortcomings of using list as stack is speed issues as the list grows. If the stack grows bigger than the block of memory that currently holds it, then python needs to do some memory allocations. This can cause some append() calls taking more time than others.

2. collections.deque:
Python stack can also be implemented using the deques class from the collections module.

This is preferred from the list in the cases where we need quicker append and pop operations from both ends of the container.

The same methods, append() and pop(), used in lists are also used in deque.

3. Queue.LifoQueue:
Queue module in python has a LIFO queue which works as a stack.

Data is inserted using the put() function and removed using the get() function.

There are a number of functions available in this module, they can be found here.

C. Queue (FIFO):

They are collection of items that hold elements. They collect elements according to the “First in First out” concept. The first element to be added is the first to be deleted.

The two main operations are; enqueue(): adding item to the back of the queue and dequeue(): remove item at the front of the queue.

Implementing Queue data structure in python:
Queues in python can be implemented using the following methods:

Lists
collections.deque
queue.Queue

1. Lists:
You can implement the FIFO principle using slicing. This is well explained in the python documentation.

Instead of using enqueue() and dequeue(), the append() and pop() functions are used. Lists are slow in this since in order to add or delete the item it will require you to shift all the other elements by one.

2. collections.deque:
Queue in python can also be implemented using the deque class from the collections module.

Instead of enqueue() and dequeue(), append() and popleft() functions are used.

Deques are preferred over lists when we need a quicker add and remove operations from both ends of the container.

3. queue.Queue:
Queue is a built-in module of python used to implement the queue.

queue.maxsize(maxsize) initializes a variable to a maximum size of maxsize.

To add items you use the put() function and to remove or get an item you use the get() function.

D. Map:
This is a data structure, (also referred to as hash tables, lookup tables, hashmaps or associative arrays), which is a collection of named items.

It is efficient in item insertion, lookup and deletion. But it requires more space than other data structures, since it is implemented as a key-value table.

Maps have the following operations:

set(key, value) - adds a key-value mapping to the map.
delete(key) - removes a key and its associated value.
get(key) - retrieves the value associated with the given key.

Implementing map data structure in python:
Maps in python can be implemented by using dictionaries.

Dictionaries are used to store values in key value pairs. Python has a built in function dict() that can be used to create dictionaries.

Values in the dictionary can be accessed using the key values, built in functions and loops.

For the built in functions we have:

get() - enables you to access the items
keys() - this returns a list of all the keys in the dictionary
values() - this will return a list of all values in the dictionary

You can check more on the access methods over here.

Values in the dictionary can be changed using the following method:

Update() - updates the dictionary with items of the given argument.

More on how to change the values an implement the update() function can be found here.

The update() method can also be used to add an item to the dictionary. More on how to add an item can be found here.

Items can be removed using the pop() function. There are other methods on how to remove an item that can be checked here.

E. Graph:
Graph is a type of data structure that arranges data as multiple nodes. The nodes are connected together using edges. They are used to model pairwise relations between objects.

They are used to model networks that naturally occur in real life. They are used in social networks such as Facebook and LinkedIn.

Implementing graph data structures in python:
The first way is by use of a dictionary. The keys in the dictionary used are the nodes of our graph and the corresponding values are the lists with each node.

For more on how to implement a graph using dictionaries in python, you can check out here.

We can also use the NetworkX Library. This library allows you to easily add or remove nodes and edges. It also comes with a lot of out-of-the-box methods such as: finding the shortest path between the nodes, measures of associativity and centrality within the graph.

You can check out more on NetworkX library here.

D. Set:
This is a data structure in python with an unordered and unindexed collection of elements. Each element in a set is unique and the set does not allow any duplication of elements.

Sets can be used to perform mathematical set operations like union, intersection, symmetric difference e.t.c

Sets are usually used for validating data, finding the difference between the two data sets, joining unique data sets together and more.

Implementing set data structure in python:
There are two main methods for implementing sets in python:

Using the set function available in python.
Typing the list of various elements using the curly “{}” braces.

Sets have the following operations:

add() function: this function adds an element to the set.
update() function: this function is used to add multiple elements to the set. Items from another set can also be added using this function.
remove() and discard() functions: they are used to remove an item from a set.

Wrapping up:
As we finalize ,let's have some recap, in this article we’ve learned about:
1. The 6 fundamental data structures
2. How to implement the various data structures in python

I'll be giving a thorough explanation on algorithms in the next article. Stay tuned!

101: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

steve kimoi — Tue, 21 Jun 2022 07:47:31 +0000

We have all heard about data structures and algorithms, and how essential they are to any programmer or software engineer/developer. But do we really have a good understanding of what data structures and algorithms are?

Let’s dive deep into it:

DEFINITIONS:
What is a data structure: it is a named location that can be used to store and organize data.

What is an algorithm: they are steps that can be used to solve a particular problem.

Having a good understanding of the above allows you (a programmer) to write efficient and optimized computer programs. This leads us to our next question, what is a computer program?

A computer program is a sequence of instructions in a programming language that a computer can execute or interpret. A computer program may need to store data, retrieve data and perform computations on the data.

Now that we have a basic understanding of data structures and algorithms and how they’re related to a computer program, let’s see the various types of data structures:

TYPES OF DATA STRUCTURES:
There are several basic and advanced types of data structures, all designed to arrange data to suit a specific purpose. There are 8 commonly used data structures every programmer must know:

1. Arrays:

An array is a structure of fixed size that can hold items of the same data type e.g integers, strings, floating point numbers e.t.c. The type of elements that can be stored in the form of array is determined by the programming language. Random access of the data is possible since they are indexed.

2. Linked lists:

A sequential structure that consists of a sequence of items in linear order that are linked to each other. Random access is not possible since you have to access the data sequentially. Elements in a linked lists are known as nodes. Each node contains a key and a pointer to its successor node.

3. Stacks:
A stack is a LIFO (Last in first out) structure which can be found in many programming languages. This structure is named as “stack” since it resembles a real-world stack – e.g a stack of plates. It is named this way since the last element to go in comes out first.

4. Queues:

This behaves in the opposite manner as compared to stack. It uses the FIFO (First in first out) principle, where the element to go in first comes out first. It is named “queue” since it represents a real world queue.

5. Hash tables:

A data structure that stores values which have keys associated with each one of them. It supports lookup efficiently if we know a key associated with the value.

6. Trees:
This is a hierarchical structure where the data is organized hierarchically and are linked together. It is a bit different from a linked list since a linked list has items linked together.

7. Heaps:

A special case of a binary tree where the parent nodes are compared to their children with their values and are arranged accordingly.

8. Graphs:
This is a fine set of vertices or nodes and a set of edges connecting these vertices. Order of the graph is the number of vertices in the graph and the size of the graph is the number of edges in the graph.

Let us now look on the importance of data structures.

WHY ARE DATA STRUCTURES IMPORTANT:
Data types such as integers and floating-point values that are available in most programming languages are not sufficient to capture the logical intent for data processing and use. Data structures bring together the data elements in a logical way and facilitate their effective use, persistent and sharing of data. They provide a formal model that describes the way the data elements are organized.

Basically, data structures are the building blocks for more sophisticated applications.

We now understand what are data structures and the various types, we can now have a look into algorithms.

ALGORITHIMS:
We started off by defining what algorithms are at the start of this article, now let’s have a look into how algorithms work, their characteristics, the various types and their importance in computer programming.

How do algorithms work:
As I had mentioned earlier, algorithms are basically steps that are used to solve a particular problem. They can be expressed as natural languages(e.g English), pseudocodes, programming languages, flowcharts and control tables. Programming languages are the ones commonly used for expressing algorithms used by a computer.

It usually takes an input, and passes it through a set of instructions. The input acts as the initial data. It then gives out an output, which is usually the last step.

What are the characteristics of algorithms:
In order for a program to become an algorithm, it usually has some type of characteristics:

Finiteness: it should have a finite number of steps, and should end after a finite time.
Well defined inputs: the inputs of an algorithm must be well defined.
Well defined outputs: the algorithm must clearly define what output will be yielded and it should be well defined as well.
Clear and unambiguous: each of the steps should be clear in all aspects and must lead to one meaning.
Language independent: it must be plain instructions that can be implemented in any language, and the output will be the same as expected.

Types of algorithms:
There are several types of algorithms available, some important ones are:

Brute force algorithm: straightforward methods of solving a problem that rely on sheer computer power.
Recursive algorithm: Based on recursion. A problem is broken into smaller sub-parts and called the same function over and over.
Backtracking algorithms: It builds the solution by searching among all possible solutions. In short it builds a solution incrementally, one piece at a time.
Searching algorithm: they are algorithms that are used to search for elements or groups of elements from a particular data structure.
Sorting algorithms: sorting is arranging a group of data in a particular manner according to the requirement. Algorithms that help performing this kind of task are called sorting algorithms.
Hashing algorithms: they work similarly to searching algorithms but the difference is, they contain index with a key ID. A key is assigned to a specific data.
Divide and conquer algorithm: involves breaking a problem into sub-problems, and merges the solutions together to get the final solution.
Greedy algorithm: the solution is built part by part. The solution of the next part is built based on the immediate benefit of the next part.
Dynamic programming algorithm: Uses the concept of using the already found solution to avoid repetitive calculation of the same part of the problem.
Randomized algorithms: we use a random number so it gives immediate benefit. The random number helps in deciding the expected outcome.

Importance of algorithms:
Algorithms are very key and important to computer programming. The best-chosen algorithm makes sure the computer will do the given task in the best possible manner.

Some of the importance of algorithms are:

To improve the efficiency of a computer program: the best algorithm enables the computer produce the very accurate results.
Proper utilization of resources: an algorithm determines the amount of memory used by the program and also amount of processing power determined by the program. A good algorithm will use less recourses.

References: