DEV Community: Amira Abdelhalim

Breadth-First Search

Amira Abdelhalim — Fri, 18 Feb 2022 13:25:54 +0000

Breadth-First Search is an algorithm to search graph to find the shortest distance between two things.
In order to talk about breadth-first search we need to know what is a graph? and what do we mean by shortest path? So first, let's figure out what is a graph.

Graph

It is a model for a set of connections.
For Example, you are heading to many places today and you want to draw a graph to the places you would pass by, you will go from home to work, then to a restaurant, then you go back home, after that you would go to the supermarket.

Graphs are made of nodes and edges. A node can be directly connected to other nodes through edges. The directly connected nodes are called neighbors. In the above graph home is directly connected to work, so they are neighbors but work isn't directly connected to supermarket.
graphs are a way to model how different things are connected to one another.

Now let's talk about what is meant by shortest-path.

Shortest-Path

It is an algorithm to find the path with the fewest steps. consider the path from your house to your friends house, ask yourself can you do it in one step? if no can you do it in two steps? keep asking until you find the shortest path.
So in shortest path algorithms we follow two steps:

Model the problem as a graph.

Solve the problem using breadth-first search.😉

It is time to talk about breadth-first search.

Breadth-First Search

It is an algorithm that runs on a graph. It helps in answering two questions:

Is there a path from node A to node B?

What is the shortest path from node A to node B?

let's have an example to understand breadth-first more.
Suppose you are a new cat parent and you want to take your cat to a vet to make a checkup but you don't know any vet yet. Yo decided to have a look in your Facebook friends list to know if you are having a vet in your list.

First, you will make a list of your friends to search.

second, go to each person on the list and check whether that person is vet. If the person is a vet CONGRATULATIONS you are done. If not go to the next person in the list.

Suppose none of your friends are vet. Now you have to search through your friends' friends. so you need to connect every friend of your friends with a list of their friends and start searching the new list. while doing this process you have created a graph of connected people and preformed a search algorithm to find a vet.
In the previous process we saw how breadth-first search answers the first question. Is there a vet in my network?
Now let's try to answer the second question who is the closest vet? Your friends are 1st degree connections and their friends are 2nd degree, so it is preferred to find vet in your 1st degree connections. While forming a list of connections it is preferred to use a QUEUE to make sure that people are searched in the order you added them.

Breadth-First Search Usage

Here are some examples where breadth-first search is used:

AI checkers that calculates the fewest moves to victory.

Spell checker (fewest edits for the misspelled words).

Implementing a Graph

Implementing Breadth-First

Hash Tables

Amira Abdelhalim — Sun, 17 Oct 2021 10:41:18 +0000

In this article we are starting by example before digging deeper into hash tables.
suppose a cashier working in a grocery store and need to know the price of an apple, he/she would find the price in a book. If the book is alphabetized he/she would use a simple search which would take O(n) time. And if the book is alphabetized he/she would use binary search to find price of apples which would take O(log n) time.
But what if the cashier is having an assistant, who memorize every item and its price, so it would take O(1) time.

Hash Function

hash function maps a string to a number. So a hash function can play the cashier assistant role, where he/she maps string item to number price.
suppose we are having an array where we store the prices, we would give the hash function the apple price to be stored and the hash function would output number 0 which is the index where the apple price is stored in the array.

Hash Table

It is a complex data structure as it is a combination of a hash function and an array. hash tables consist of key and value.
{"apple": 5, "banana": 3}
you don't have to implement a hash table yourself it is already implemented in most programming languages.

Hash Table Use Cases

Using hash tables for lookup

the phone contact every name has a number associated to it.

lookup for IP address that is associated with a web address.

Preventing duplicate entries

like voting system the same person cannot vote twice.

Using hash table as a cache

memorizing data instead of requesting it over and over.

Collisions

It is when two keys are assigned to the same slot in memory.
One way to deal with a collision, if multiple keys are assigned to the same slot, start a linked list at this slot.

Performance

In the average case, hash tables have O(1) time complexity of everything!

Divide and Conquer

Amira Abdelhalim — Wed, 13 Oct 2021 12:23:58 +0000

Divide and Conquer

it is a well-known recursive technique for solving problems. D&C gives a new way to think about solving problem.
To solve a problem using D&C technique, there are two steps:

figure out the base case(the simplest possible case).

divide the problem until it becomes the base case.

D&C isn't a simple algorithm that is applied to a problem. it is a way of thinking about the problem.

Example

If we want to know the sum of numbers in an array... let's think of the simplest base case we can have.
The simplest case is to have an array of 0 or 1 item. so in each step we need to take our array closer to an empty array.

Quicksort

Quicksort is one of the algorithms that is built on divide and conquer technique. It is a sorting algorithm faster than selection sort and it is frequently used in real life.
let's say we want to sort an array using quicksort what are the steps we shall do to have a sorted array.

pick an element from the array, this element is called the pivot.

find the elements smaller than the pivot then the elements greater than the pivot. this process is called partitioning

[33, 10] (33) [50, 34]

if sub-arrays are sorted we just need to combine them together.

if sub-arrays are not sorted then repeat the first 2 steps until having a sorted array.

Recursion and Stacks

Amira Abdelhalim — Fri, 01 Oct 2021 16:41:11 +0000

What is Recursion?

Recursion is where a function calls itself.

lets have an example

we are having a box that contains other boxes, and you know there is a key inside one of these boxes. You want to find that key, what would you do?

Here is an approach:

Make a pile of boxes to look through.
Grab a box, and look through it.
If you find a box, add it to the pile to look through later.
If you find a key, you are DONE!🎉

This approach uses a while loop, while pile is not empty grab a box, and look through it.

An alternate approach:

Look through the box.
If you find a box, go to step 1.
If you find a key, you are DONE!🎉

This second approach uses recursion.

be careful using recursion as it may end up with infinite loop. 
That's why recursive functions has two parts
1. The base case -> function doesn't call itself again.
2. The recursive case -> function calls itself.

Stacks

Stack is an important concept in general programming, and also important to understand when using recursion.
let's have an example
we are having a stack of sticky notes. when we insert an item we add it to the top of the stack. when we read an item we only read the topmost item, and it is taken of the stack.
so our todo has two actions push(insert) and pop(remove)
stack is last in first out data structures

The Call Stack

The computer uses a stack internally called the call stack let's see how it works:
example

This greet() function calls two functions greet2() and bye().

suppose you call greet('maggie') your computer allocates a box in memory for that function call.

variable name is set to maggie inside that memory box.

every time you make a function call, your computer saves variables for that call in memory like the previous steps. Computer uses a stack of these boxes on top of each other every time you call a new function it is added to the top until it is finished then removed, that means the first function called the last to be finished.

Linked lists, Arrays and Selection sort...

Amira Abdelhalim — Thu, 09 Sep 2021 22:56:26 +0000

Here is with chapter 2 of Grokking Algorithms.
• Computer memory is like a giant set of drawers, each drawer has an address. Each time we want to store an item we ask computer for some space and it gives us an address where we can store the item.
• Storing multiple items requires an array or a list

“Array Vs Linked List”

Arrays
• using array means our items will be stored contiguously in memory.
• Every time we add an item to the array we need to check if there is an empty place in the array it is added successfully else we need to ask if there is an empty place in memory that fits all our items right next to each other.
• The place of an item in array is known because items are stored contiguously so to read an item from array it takes O(1).
• To insert in an array it takes O(n) as if we want to insert item at the beginning of an array we will need to shift all other items in the array.
• To delete from an array it also takes O(n) as every thing needs to be moved up when we delete an item.

• Elements in array should be of the same type (int, string...etc,)

“Let’s say we created an array with 10 slots but used only 5 slots in this case we won’t need to move to a new place in memory but here we wasted 5 places in memory.”

Linked Lists
• using linked lists allow items to be stored anywhere in memory.
• Each item in the list stores the address of the next item.
• insertion takes O(1) in linked list as we only need to change what a previous element points to.
• deletion takes O(1) as well .
• Reading from a linked list takes O(n) as reading needs to go one by one to read the required element.

“Selection Sort”
• sorting items according to certain criteria like:
1. sorting list of songs from most liked to least.
2. travel dates
3. emails ( newest to oldest)
4. names in a phone book
• time complexity of selection sort is O(n2) as we loop through list items 2 times (n x n).

# Here is an example of selection sort to find the smallest number in an array.

Binary Search vs Simple Search

Amira Abdelhalim — Mon, 06 Sep 2021 10:00:51 +0000

I have been reading Gorkking Algorithms by Aditya Y.Bhargava. The book is one of the most interesting and enjoyable books about algorithms, so I thought I would share insights from each chapter.

Chapter one is mainly about the differences between simple search and binary search, the differences are as follow:

  “study case searching for number 10 in a list of 10 elements”

• simple search would loop on each element check if it is number 10 in case number 10 is the last element we would loop 10 times to reach our element …. what is the list is 1000,000 elements?

• Binary search is one of the searching algorithms that requires a sorted list as an input and outputs the location of the required element or null if doesn’t exist.

• Binary search works as follow => “we are still working on our 10 elements list”
1. Low => 0   first element of the list
2. high => length(list) – 1  the last element of the list
3. mid => (low + high) / 2
• check if number 10 is equal to mid if yes … Congratulations number 10 is found
• if number 10 is greater than mid … update low value to mid and recalculate mid value
• if number 10 is less than mid update high value to mid and recalculate mid value 
  “IN THIS STEP WE ELIMINATED THE LIST BY HALF”
• Repeat the past two steps until 10 is found.

• binary search would find an element in a list of 10 elements in only 3 steps if the element is the last element… if it is a list of 1000,000 elements it would take 20 steps only.

• simple search complexity according to big O notation is O(n).

• binary search complexity is O(log n).