Hashing Algorithms for Memory Addressing

Posted on October 17, 2018 by Administrator Posted in A Level Concepts, Algorithms, Computer Science, Computing Concepts

In this blog post, we will investigate the use of hashing algorithms to quickly locate a record in a large database.

Let’s consider the database of members of a social network such as Instagram, Twitter or Facebook.

Every time the user uses the website or their smartphone app to access the social network, the server retrieves the user’s login name and password. It then has to find the record matching the given username to access their data and verify their password.

Large social networks have millions of members. Locating a single record in a table that contains millions of records can be time consuming especially if you perform a linear search to locate the record. (Linear Big O Notation). Alternative algorithms such as a binary search can speed up the process (Logarithmic Big O Notation), however a binary search only works when the data is sorted in alphabetical order. This is unlikely to be the case for a social network members table as members will have joined the network at different dates, hence the data will not be sorted in alphabetical order of their usernames. The assumption is that the records are stored in chronological order (based on the date they first signed in).

Using a Hashing Algorithm

To solve this problem, social networks use hashing algorithms when storing and accessing data in a large database.

A hashing algorithm is a complex mathematical calculation that takes an input (a.k.a. the key) (in this case the username of the member) and returns a value called a hash value or hash. When used for memory addressing the hash value generated is the memory location of where the record is stored.

Let’s consider a very basic hashing algorithm used to identify the memory location of a new member who has just signed up.

Our hashing algorithm will add up all the ASCII values of each character of their username. We will assume our database will contain around 50 memory locations. So our hashing algorithm will use the remainder of dividing the total ASCII value by 50 to get a unique number between 0 and 50.

For instance, for a user called James Bond whose username is “Bond”, the resulting hash value would be:

hashKey("Bond") =  (ASCII("B") + ASCII("o") + ASCII ("n") + ASCII("d")) MOD 50
                =  (  66       +     111    +     110     +     100   ) MOD 50
                =  387 MOD 50
                =  37

The details can be stored on location 37 of the members table (hash table) provided below.

Every time the user James Bond accesses the social network, he will provide his username. As part of the login process, the server will use the hashing algorithm on this username to quickly calculate the memory location of where James Bond’s record is stored. This is a very efficient approach to access the data. (Constant Big O notation).

Collisions

The hash values generated by a hashing algorithm should be fairly unique. However there will be occasions where two input values return the same hash value. For instance, let’s consider what would happen if a new user, Austin Powers signs in and their username is aPowers:

hashkey("aPowers") =  (ASCII("a") + ASCII("P") + ASCII ("o") + ASCII("w") + ASCII("e") + ASCII("r") + ASCII("s")) MOD 50
                   =  (  97       +     80     +     111     +     119    +    101     +     114    +   115     ) MOD 50
                   =  737 MOD 50
                   =  37

This hash is the same as the hash generated for James Bond’s username. This create a collision. In this case, instead of overwritting the content of memory location 37 (already used by James Bond) the algorithm will jump to location 37 and carry on a linear search from there to find the next empty memory location. This could be memory location 38 if it’s empty, 39 if not, and so on till an empty location is found.

This will slightly slow down the process when trying to locate Austin Powers’ record but would still be far more efficient than without using a hashing algorithm.

Complex hashing algorithms are designed the minimize the risk of collisions: The effectiveness of a hashing algorithm is based on the total number of unique values the algorithm will generate to minimize the risks of collisions.

Hashing Algorithm in Action!

We have implemented our basic hashing algorithm as described above.

Your task is to use it to generate the hash values for these new members of our social network.
Using these hash values, you will then be able to add their information on the members hash table (see “Members Table” tab below). You will notice that a few members have already been stored in this table.

Warning: On occasion the generated hash may generate a collision with an existing member. In this case you you will have to use the next available location to store the members detail in the members table.

The new members to add are:

Jason Bourne, username: jBourne
Johny English, username: English
Lara Croft, username: lCroft

Also, a few users are logging in. Can you use the hashing algorithm to quickly locate their records in the members hash table and access their details.

The users are:

jBauer
eHunt
Holmes

Hashing AlgorithmMembers Table / Hash Table

Memory Location	Username	Firstname	Lastname
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

Recursive vs. Iterative Palindrome Check

Posted on October 16, 2018 by Administrator Posted in Algorithms, Computer Science, Python - Advanced, Python Challenges, Solved Challenges

A word, phrase, or sequence that reads the same backwards as forwards, e.g. madam.

For this challenge we will investigate two algorithms used to find out if a word is a palindrome or not. The first algorithm will use an iterative approach, the second algorithm will use a recursive approach.

Iterative Approach

An iterative approach is based around the use of a loop which can be:

A count-controlled loop (e.g. FOR loop)
A condition-controlled loop (e.g. WHILE loop or REPEAT UNTIL loop)

For our iterative palindrome check algorithm, we will use a loop to check all the letters in the first half of the word and compare them with the letters in the second half of the word (in reverse order). If they all match then the word is a palindrome.

Recursive Apporach

A recursive function is a function that:

Includes a call to itself,
Has a stopping condition to stop the recursion.

For our recursive palindrome check algorithm, we will use a function that:

Checks that the word is at least two characters long:

If the word is less than two characters then the function will stop the recursion (stopping condition) and Return True as the word is a palindrome.
If the word is two or more characters long, the function will check that the first and last letter of the word are the same:

If they are the same, the function will extract the word in the middle (remove the first and the last letter) and call itself with this new shortest word.
If they are different, then the word is not a palindrome. The function will stop the recursion here (stopping condition) and return False.

You can visualise/trace this recursive function on recursionvisualizer.com

Your Task

Complete the following factorial challenge using both an iterative approach and a recursive approach.

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Tagged with: iteration, recursion

Blackbeard’s Hidden Treasures

Posted on October 14, 2018 by Administrator Posted in A Level Quiz, Coding Quiz, Computer Science, Computing Concepts, GCSE Concepts, GCSE Quiz, Quizzes, Solved Challenges

The period of the late 17th and early 18th centuries is known as the Golden Age of Piracy. During this period the most notorious and the most feared of all pirates was Blackbeard. There are many legends based around Blackbeard’s piracy acts in the Caribbean sea and in the Pacific Ocean but the most captivating legend is based around Blackbeard’s great buried treasure, which has yet to be found.

A small treasure chest, full of parchments has recently been found by a team of historians who were researching the Golden Age of piracy at The Codrington Library, Oxford UK. The parchments were hidden within the inside cover of an ancient book about Myths and Legends of the Golden Age of Piracy.

It would seem that Blackbeard may not have buried his treasure in one single location but may instead have split his treasure and buried it using twelve different locations.

Your task is to use the 12 parchments, as well as the treasure map provided below to locate all the content of Blackbeard’s treasure.

Blackbeard’s TreasuresOpen in New Window

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Blackbeard’s Treasure Map

Posted on October 10, 2018 by Administrator Posted in A Level Concepts, A Level Quiz, Coding Quiz, Computer Science, GCSE Concepts, GCSE Quiz, Python - Intermediate, Python Challenges, Solved Challenges

We have all heard of the famous English pirate called Blackbeard who sailed the seven seas during the XVIII century. Through his numerous acts of piracy, Blackbeard accumulated a huge collection of riches including golden coins, jewels, golden plates and precious stones. Blackbeard was wise enough not to carry his treasure on his vessel. Instead he buried his treasure in a secret location, somewhere in the middle of the Pacific Ocean.

Recently, a team of SCUBA divers found a message in a bottle while SCUBA diving near Coral Bay, Western Australia. Inside this old bottle of rhum, they found two pieces of parchment believed to have belonged to Blackbeard.

The first piece of parchment is a map. Looking at the shapes of the three islands on the map, the SCUBA divers have been able to locate the location of these islands somewhere a few miles off the coast of Australia. They strongly believe that this map will help them find the exact location of Blackbeard’s treasure.

The second parchment is believed to be the key to help locate the position of the treasure on the map.

Treasure Hunt

Your task is to write a computer program, using the programming language of your choice, in order to find the row number and the column number to solve the following equation:

Row x Column = 1889121
Looking at the map, we can deduce that the row number could be any number between 2440 and 2470 and that the column number could be any number between 750 and 770.

Your computer program will enable you to pinpoint the exact location of Blackbeard’s treasure on this map!

Once you have found your row and column numbers type them below to check if you have located the treasure!

Row:
Column:

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

The Pigpen Cipher

Posted on October 10, 2018 by Administrator Posted in Computer Science, Cryptography, HTML, CSS & JavaScript, JavaScript

The Pigpen cipher (a.k.a. tic-tac-toe cipher) is a geometric substitution cipher, which exchanges letters for symbols which are fragments of a grid.

Secret Message

Using the key provided on the right, can you decode the following secret message?

Pigpen Cipher Encoder

You can use our online Pigpen Cipher Encoder to encode your own secret messages.

See the Pen pigpen cipher – encoder by 101 Computing (@101Computing) on CodePen.

Press the “Edit on CodePen” button at the top of this codepen to open in full screen mode

Tagged with: cryptography, encryption

The Rail Fence Cipher

Posted on October 8, 2018 by Administrator Posted in Computer Science, Cryptography, Python - Intermediate, Python Challenges, Solved Challenges

The rail fence cipher (sometimes called zigzag cipher) is a transposition cipher that jumbles up the order of the letters of a message using a basic algorithm.

The rail fence cipher works by writing your message on alternate lines across the page, and then reading off each line in turn.

For example, let’s consider the plaintext “This is a secret message”.

To encode this message we will first write over two lines (the “rails of the fence”) as follows:

Note that all white spaces have been removed from the plain text.

The ciphertext is then read off by writing the top row first, followed by the bottom row:

Your Challenge

For this challenge, you will have to write two python programs, one to encrypt a message (plaintext to ciphertext), one to decrypt an encoded message (ciphertext to plaintext). To help you with this challenge we have created the flowcharts of both the encoder and the decoder algorithms.

Encoder AlgorithmDecoder Algorithm

Rail Fence Cipher – Encoder

Rail Fence Cipher – Encoder Algorithm

Python Code

Rail Fence Cipher – Decoder

The Rail Fence Cipher – Decoder Algorithm

Python Code

Break the code!

Use your python script to decipher the following encoded message:

CYTGAHITEROWIIGROVNCDSRPORPYSHATFRTNOSLIGOE

Extension Task

More complex Rail Fence Ciphers have more “rails”. For instance instead of writing the code over two lines (“rails”) you can write over three or four or more lines. The number of lines used in a Rail Fence Cipher is called the key.

Key = 3

A Rail Fence Cipher with 3 “rails” (Key = 3)

Key = 4

A Rail Fence Cipher with 4 “rails” (Key = 4)

Investigate how you could adapt both your encoding and decoding python programmes to enable to encrypt and decrypt messages with different keys.

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Tagged with: cryptography, encryption

Semaphore Code Using Python Turtle

Posted on October 7, 2018 by Administrator Posted in Computer Science, Python - Intermediate, Python Challenges

Flag semaphore is a telegraphy system conveying information at a distance by means of visual signals with hand-held flags. Information is encoded by the position of the flags. The current flag semaphore system uses two short poles with square flags, which a signalman holds in different positions to signal letters of the alphabet and numbers. The signalman holds one pole in each hand, and extends each arm in one of eight possible directions. At sea, the flags are coloured red and yellow, while on land, they are white and blue.

The following table shows all the different flag positions to represent the 26 letters of the alphabet and the number digits 0 to 9:

Click on the picture to zoom in

Python Turtle Code

We have created an animation that will scan all the characters of a message and animate the signalman to display the right semaphore flags for each character in the message.

For this demo, the message variable is set on line 45 to “ABCDEFGHIJKLMNOPQRSTUVWXYZ” but you can change this message to any text.

message = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

Our code also uses a dictionary called semaphore to store the 26 characters of the alphabet (and the space character). For each key of this dictionary, we store the two angles used to define the position of both arms using the following angles:
semaphore-angles

A dictionary is used to store the angles of both flags, for each character of the alphabet.

Tagged with: cryptography, Python Turtle

Is my credit card valid?

Posted on October 7, 2018 by Administrator Posted in Algorithms, Computer Science, Python - Intermediate, Python Challenges, Solved Challenges

In this challenge we will use the Luhn Algorithm to check if a debit card or credit card number is a valid card number.

This method is used every time you scan or enter your credit card number (e.g. when paying online) to check if your card number is a valid credit card number. This method can be used to quickly detect credit card numbers that have been mistyped or to detect when someone is trying to enter a fake/made up credit card number. Note that it’s not 100% efficient, so is only used as a pre-check to deter some invalid card numbers. If this first test passes, other more robust checks will be performed for the online transaction to be approved.

The Luhn Algorithm

The Luhn Algorithm consists of 4 key steps:

Python Challenge

Write program that will ask the end-user to enter a 16-digit card number.
Your program will then apply the Luhn algorithm to decide and output whether or not this card number is valid.

Valid or Invalid Card Numbers?

Test your program with the following card numbers to find the 2 invalid card numbers:

#	Card	Card Number	Valid or Invalid?
#1		4137 8947 1175 5904
#2		6499 8024 5027 3568
#3		8504 1721 9127 3888
#4		0043 6687 8348 5480

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Cryptographic Challenge: Base64 to Hex

Posted on October 7, 2018 by Administrator Posted in Computer Science, Computing Concepts, Cryptography

ChallengeBase64Hexadecimal

Your challenge is to write a piece of code, using the programming language of your choice, to code and to decode messages encrypted using Base 64 encoding and Hexadecimal (Base 16) encoding.

Your progamme will first ask the user if they want to encode or decode a message. It will then ask the user to enter either the plain text (using the base64 character set) or the ciphertext (hexadecimal).

Your program will then output the decoded (plaintext) or the encoded message (ciphertext).

For instance:
Plain: Code/Breaker Cipher: 0A875EFC1ADE6A47AB

The following diagram will help you understand how the conversion from Base 64 to Hexadecimal works:
cryptography-base64-hexadecimal

Code Breaking Challenge:
You will then be able to decrypt the following encoded message:

Cipher: Plain Text:

Base64

Base64 is a binary-to-text encoding scheme where each character (plaintext) is coded using 6 bits of data. Hence a base64 character set contains exactly 64 characters:

Index	Char	Index	Char	Index	Char	Index	Char
0	`A`	16	`Q`	32	`g`	48	`w`
1	`B`	17	`R`	33	`h`	49	`x`
2	`C`	18	`S`	34	`i`	50	`y`
3	`D`	19	`T`	35	`j`	51	`z`
4	`E`	20	`U`	36	`k`	52	`0`
5	`F`	21	`V`	37	`l`	53	`1`
6	`G`	22	`W`	38	`m`	54	`2`
7	`H`	23	`X`	39	`n`	55	`3`
8	`I`	24	`Y`	40	`o`	56	`4`
9	`J`	25	`Z`	41	`p`	57	`5`
10	`K`	26	`a`	42	`q`	58	`6`
11	`L`	27	`b`	43	`r`	59	`7`
12	`M`	28	`c`	44	`s`	60	`8`
13	`N`	29	`d`	45	`t`	61	`9`
14	`O`	30	`e`	46	`u`	62	`+`
15	`P`	31	`f`	47	`v`	63	`/`

Hexadecimal

Hexadecimal is a base-16 number system. The hexadecimal numbers are 0-9 and then use the letters A-F to represent the decimal values 10 to 15.

Each digit in hexadecimal can be coded in binary using 4 bits as follows:

Binary	Decimal	Hexadecimal
0000	0	0
0001	1	1
0010	2	2
0011	3	3
0100	4	4
0101	5	5
0110	6	6
0111	7	7
1000	8	8
1001	9	9
1010	10	A
1011	11	B
1100	12	C
1101	13	D
1110	14	E
1111	15	F

Extension Task

Using the same approach, we can encode message in a range of encoding schemes such as Hexadeximal (4-bits per character), Base32 (5 bits per character), Base64 (6 bits per character), Extended ASCII (8 bits per character).

You can now update your code to cater for a range of encoding/decoding techniques between all these encoding schemes.

Tagged with: cryptography, encryption

Name the Logic Gate

Posted on October 2, 2018 by Administrator Posted in A Level Concepts, A Level Quiz, Computer Hardware, Computer Science, Computing Concepts, Physical Computing

Look at the logic gates diagrams below. For each of these diagrams, complete the Truth Table corresponding to the diagram. Can you name the logic gate that each diagram is equivalent to?

Diagram #1Diagram #2Diagram #3Diagram #4Diagram #5Diagram #6Diagram #7