SWDDA 401: DATA STRUCTURE AND ALGORITHM FUNDAMENTALS

Competency: Apply Data Structure and Algorithm Fundamentals Using Java Script

School: GLORY ACADEMY

Class: level 4 SWD

Module name: SWDDA 401 DATA STRUCTURE AND ALGORITHM FUNDAMENTALS

Competency: Apply Data Structure and Algorithm Fundamentals Using Java Script

Learning Hours: 150

TRAINER: YANKURIJE Gad

Elements of Competence and Performance Criteria

Elements of Performance criteria

competence

1. Apply 1.1 Number systems are correctly converted according to the base conversion
Algorithm methods
Fundamental
s 1.2 Logic gates and expressions are well described based on boolean algebra

1.3 Data types are effectively used according to their intended use

1.4 Operators are appropriately used based on datatype

1.5 Algorithm is properly written based on problem to be solved

2.1 Data structure concepts are clearly identified based on intended use.

2.2 Linear Data Structures are properly applied based on their operational
2. Apply Data
complexity
Structure

2.3 NonLinear Data Structures are properly applied based on their operational
complexity
 3.1 JavaScript Source code is properly developed based on Algorithm

3. Implement 3.2 JavaScript source code is successfully run in accordance with expected
Algorithm using result
JavaScript
3.3 Time and space complexity are successfully tested based on data structure
standards

Learning outcome 1: Apply Algorithm Fundamentals

Learning outcomes: At the end of the module the learner will be able to:

1. Apply Algorithm Fundamentals

2. Apply Data Structure
3. Implement Algorithm using JavaScript
Data structures: a way of storing and organizing data in the computer memory so that it can be processed
efficiently.
An algorithm is a sequence of steps executed by a computer that takes an input and transforms it into a
target output. Together, data structures and algorithms combine and allow programmers to build whatever
computer programs would like.
[Link] systems are correctly converted according to the base conversion methods

Conversion of base numbers

 Description of key concepts
Decimal base: A Decimal number system is the number system that we use on a daily basis
based on the 10 digits. Decimal number system is the number system we use every day and uses
digits from 0 - 9 i.e. 0, 1, 2, 3, 4, 5, 6, 7, 8, & 9. The base number of the decimal number system
is 10 as the total number available in this number system is 10.
Binary base: It describes numeric values by two separate symbols; 1 (one) and 0 (zero).
Hexadecimal base: Hexadecimal is a numbering system with base 16. It can be used to represent
large numbers with fewer digits.
In this system there are 16 symbols or possible digit values from 0 to 9, followed by six
alphabetic characters -- A, B, C, D, E and F. These characters are used to
represent decimal values from 10 to 15 in single bits.

Here's what the decimal and hexadecimal systems look like for digits 0 to 15.
 Decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Hexadecimal 0 1 2 3 4 5 6 7 8 9 A B C D E F

Octal base has a base of eight and uses the numbers from 0 to 7. The octal numbers, in
the number system, are usually represented by binary numbers when they are grouped in pairs of
three. For example, an octal number 128 is expressed as 0010102 in the binary system, where 1 is
equivalent to 001 and 2 is equivalent to 010.

Octal Number System

Base – 8

Octal Symbol – 0, 1, 2, 3, 4, 5, 6 and 7

 Number system from decimal base to:

Binary base and vice versa

To convert numbers from decimal to binary, the given decimal number is divided repeatedly by 2 and the
remainders are noted down till we get 0 as the final quotient. The following steps is considered as the
decimal to binary formula that shows the procedure of conversion.
 Step 1: Divide the given decimal number by 2 and note down the remainder.
 Step 2: Now, divide the obtained quotient by 2, and note the remainder again.
 Step 3: Repeat the above steps until you get 0 as the quotient.
 Step 4: Now, write the remainders in such a way that the last remainder is written first, followed
by the rest in the reverse order.
 Step 5: This can also be understood in another way which states that the Least Significant Bit
(LSB) of the binary number is at the top and the Most Significant Bit (MSB) is at the bottom.
This number is the binary value of the given decimal number.

Let us understand this with an example.

Example: Convert the decimal number 1310 to binary.

Solution: We will start dividing the given number (13) repeatedly by 2 until we get the quotient as 0. We
will note the remainders in order.

Division by 2 Quotient Remainder

13 ÷ 2 6 1 (LSB)

6÷2 3 0

3÷2 1 1

1÷2 0 1 (MSB)

After noting the remainders, we will write them in such a way that the Most Significant Bit (MSB) of the
binary number is written first, followed by the rest. Therefore, the binary equivalent for the given decimal
number 1310 is 11012. This means that 1310 = 11012.
Decimal to Binary Table

There are different methods of converting numbers from decimal to binary. When we convert numbers from
decimal to binary, the base of the number changes from 10 to 2. It should be noted that all decimal numbers
have their equivalent binary numbers. The following table shows the decimal to binary chart of the first
20 whole numbers.

Decimal Numbers Binary Numbers

0 0

1 1

2 10

3 11

4 100

5 101

6 110

7 111

8 1000

9 1001

10 1010

11 1011

12 1100

13 1101

14 1110

15 1111

16 10000
 Decimal Numbers Binary Numbers

17 10001

18 10010

19 10011

20 10100

Examples
1: Convert 17410 to binary.
2: Convert the following decimal number into binary number: 156
3: State true or false with reference to decimal to binary conversion.

a.) The binary number system has a base of 2 since it uses only two digits to represent a number.

b.) When the decimal number 10 is converted to binary, it gives the value as 1010.

c.) When the decimal number 4 is converted to binary, it gives the value as 100.

Solution:

a.) True, the binary number system has a base of 2 since it uses only two digits to represent a number.

b.) True, when the decimal number 10 is converted to binary, it gives the value as 1010.

c.) True, when the decimal number 4 is converted to binary, it gives the value as 100.

Binary to Decimal Conversion Methods

There are two main methods for converting binary number systems into decimal number systems. These
methods are:

1. Positional Notation
2. Doubling
Conversion Using Positional Notation

 Write the binary number and count the power of 2 from right to left, starting from 0 onwards.
 Now each binary number has the corresponding power of 2 starting from right to left. So the
most significant bit will have the highest power of 2.
 Add the product of the second step
 The final answer will be converted into a decimal number that is base 10.
Example of Positional Notation

Binary Number: (101)2

1 0 1

1 x 22 + 0 x 21 + 1 x 20

4+0+1

(5)10

So, the decimal number of (101)2 is (5)10

Similar we can represent fractional binary number into decimals

Binary Number: (0.101)2

1 0 1.1 0 1

1 x 22 + 0 x 21 + 1 x 20 . 1 x 2-1 + 0 x 2-2 + 1 x 2-3

(4 + 0 + 1) . (0.5 + 0 + 0.125)

(5.625)10

So, the decimal number of (0.101)2 is (5.625)10

Conversion Using Doubling

Conversion using doubling is one of the simplest ways for converting binary numbers into decimal numbers.
We need to take the most signification bit or leftmost digit of the number. Then multiply the digit by 2 and
add the second leftmost bit and store the result. Similarly, we need to take the result and multiply it by 2 and
take the third leftmost bit and update the result. This process will continue till we reach the least significant
bit which is the rightmost bit. Since we are multiplying by 2 so this process is known as Doubling.

Example of Doubling

Binary Number: (101)2

=1

=1x2+0=2

=2x2+1=5

So, the decimal number of (101)2 is (5)10

Binary to Decimal Formula

The formula to convert binary number system into decimal can be represented by,

A = xn * bn + xn-1 * bn-1 + ….. + x1 * b1 + x0 * b0

Where,

A represents the integer

x represents the digit value

b represents the base value

For Example :

(1000)2 = 1 x 23 + 0 x 22 + 0 x 21 + 0 x 20

Tabular Representation of Binary to Decimal Number

Binary1 Decimal1 Binary2 Decimal2

0000 0 1000 8

0001 1 1001 9

0010 2 1010 10
 Binary1 Decimal1 Binary2 Decimal2

0011 3 1011 11

0100 4 1100 12

0101 5 1101 13

0110 6 1110 14

0111 7 1111 15

How to Convert Decimal to Octal Number?

To convert a decimal number to an octal number, there are several direct and indirect methods. They are as
given below:

o Decimal to Octal Conversion Using by Direct Method: As the name suggests decimal numbers are
directly converted to octal numbers.
o Decimal to Octal Conversion Using by Indirect Method: This method converts the decimal number
into a binary number or hexadecimal first and then converts that to an octal number.

Decimal to Octal Conversion Using Direct Method

To convert a Decimal number to an Octal number directly, you must start dividing the number by 8 until you
get 0 as the quotient. This is a straightforward method that involves dividing the number to be converted.

Step 1: If the decimal number is N, divide it by 8 because the octal number system’s base is 8.

Step 2: Note the value of the residual, which will be one of the following: 0, 1, 2, 3, 4, 5, 6, or 7. Divide the
remaining decimal number until it equals 0 and record the remainder of each step.

Step 3: Then, from bottom to top (or in reverse order), write the remainders, which will be the equivalent
octal number of the provided decimal number.

Let’s see this with the help of an example:

Note: The dividend (here given decimal number) is the number to be divided, the divisor (here base of octal,
i.e., 8) is the number to be divided by, and the quotient (remaining divided decimal number) is the outcome
of the division.

Decimal to Octal Conversion Using Indirect Method

As mentioned above this method converts the decimal number into a binary number or hexadecimal first and
then converts that binary or hexadecimal number to an octal number.

Convert Decimal to Binary to Octal

Let’s see how to convert decimal numbers to binary to octal conversion. By repeatedly dividing a number by
two and recording the result, decimal values can be transformed into binary.

Conversion of Integral Decimal Numbers

Step 1: Divide the number by 2.

Step 2: Get the integer quotient for the next iteration.

Step 3: Get the remainder for the binary digit.

Step 4: Repeat the above steps until the quotient is equal to 0.

Take a look at an example to see how this works.

The remainders are to be read from bottom to top to obtain the binary equivalent.

4310=1010112

A binary number can be converted to an octal number in a variety of ways. Direct and indirect approaches
can both be used to convert. To begin, you must convert a binary into a different base system (e.g., into
decimal, or into hexadecimal). After that, you must convert it to an octal number.

Because the octal number system has only eight digits (from 0 to 7), we may express each octal digit using
only three bits, as seen below.

Octal Digit Value Binary Equivalent

0 000

1 001

2 010

3 011

4 100

5 101

6 110

7 111

The process to convert a binary number to an octal number is as follows:

Step 1: Consider the binary number. For the integer component, divide the binary digits into three groups
(beginning from the right), and for the fraction part, start from the left.

Step 2: Each set of three binary digits should be converted to one octal digit.

Let’s see with the help of an example.

Convert binary number 1010111100 into an octal number.

Therefore, Binary to octal is

= (1010111100)

= (001 010 111 100)

= (1 2 7 4)

= (1274)

Convert Decimal to Hexadecimal to Octal

Let’s see how to convert decimal numbers to hexadecimal to octal.

Converting with Remainders (for the integer part)

This is a simple procedure that involves dividing the number to be transformed by two.

Step 1: If the decimal number is N, divide it by 16 because the hexadecimal number system’s base is 16.
Make a note of the value of the remainder, which will range from 0 to 15 (replace 10, 11, 12, 13, 14, 15 with
A, B, C, D, E, and F respectively). Divide the remaining decimal number until it equals 0 and record the
remainder of each step. Then, from bottom to top (or in reverse order), write the remainders, which will be
the equivalent hexadecimal number of the supplied decimal number.

Example:
Converting with Division

This approach works by estimating a decimal number’s hexadecimal equivalent. Any decimal number can
be used as a starting point. Make a list of 16’s abilities. Multiply the decimal number by the 16th power.
Find the rest of the items. Multiply the residual by the 16th power. Repeat until you’ve figured out the whole
solution.

Example:

Now we will convert hexadecimal number to octal number. Here are the steps:

Step 1: To begin, count the digits in the number.

Step 2: If n is the digit’s position from the right end, multiply each digit by 16n−116�−1.

Step 3: After you’ve multiplied the terms, add them together. The comparable decimal form is the resultant.

Step 4: Write down the rest of the information.

Step 5: With the quotient, repeat the previous two steps until the quotient is zero. Reverse the order of the
remainder. The obtained number corresponds to the desired outcome.

Example:
Convert Decimal to Octal including Decimal Point

To convert Decimal to Octal including decimal points, we first convert it to hexadecimal and then convert it
to octal.

Here’s how we convert to hexadecimal.

Converting with Remainders (for fractional part)

If the decimal fractional portion is M, multiply it by 16 because the hexadecimal number system’s base is
16. Take note of the integer part’s value, which will range from 0 to 15. (replace 10, 11, 12, 13, 14, and 15
by A, B, C, D, E, and F respectively). Multiply the remaining decimal fractional number until it equals 0 and
record each integer part of the result. Then write the integer part’s results, which will be a fraction
hexadecimal number comparable to the specified decimal value.

Once we get the hexadecimal number we convert it to octal using the steps we discussed above.

Solved Examples of Decimal to Octal Conversion

Let’s see some more solved examples from decimal to Octal.

Example 1: Convert 4401044010 in octal.

Solution: We divide the number 440 by 8 till we get the quotient 0.

Division Quotient Reminder

4330/8 541 2

541/8 67 5

67/8 8 3

8/8 1 0

1/8 0 1

We read the reminder in reverse order. So 44010=10352844010=10352 8

Example 2: What is the number 4321.356104321.35610 in the octal number system? (till 6 significant
digits)

Solution: In order to convert 4321.356104321.35610 into octal, we divide it into two parts of whole number
and fraction. First, let’s convert the whole number part. We divide the number 4321 by 8 till we get the
quotient 0.

Division Quotient Reminder

4321/8 540 1

540/8 67 4

67/8 8 3

8/8 1 0

1/8 0 1

We read the reminder in reverse order. So 44010=14352844010=143528. Next is the conversion of the
fraction part. If the decimal fractional component is M, multiply it by 8 because the octal number system’s
base is 8; till the significant digits are required.
— Octal

0.356 x 8 = 12.848 2

0.848 x 8 = 6.784 6

0.784 x 8 = 6.272 6

0.272 x 8 = 2.176 2

0.176 x 8 = 1.408 1

0.408 x 8 = 3.264 3

We have reached 6 significant digits. So we stop here. So 440.35610=14352.2662138

Decimal to Hexadecimal Conversion With Steps

Go through the steps given below to learn how to convert the numbers from decimal to hex.

Step 1: First, divide the decimal number by 16, considering the number as an integer.

Step 2: Keep aside the remainder.

Step 3: Again divide the quotient by 16 and repeat till you get the quotient value equal to zero.

Step 4: Now take the values of the remainder’s left in the reverse order to get the hexadecimal numbers.

Note: Remember, from 0 to 9, the numbers will be counted as the same in the decimal system. But from 10 to
15, they are expressed in alphabetical order such as A, B, C, D, E, F and so on.

Let us take an example to understand the steps given above for decimal to hex conversion.

Example: Convert (960)10 into hexadecimal.

Solution:

To convert decimal to hex, i.e. 960 base 10 to a hexadecimal number, follow the steps given below:

Step 1: First, divide 960 by 16.

960 ÷ 16 = 60 and remainder = 0

Step 2: Again, divide quotient 60 by 16.

60 ÷ 16 = 3 and remainder 12.
Step 3: Again dividing 3 by 16, will leave quotient=0 and remainder = 3.

Step 4: Now taking the remainder in reverse order and substituting the equivalent hexadecimal value for
them, we get,
3→3, 12→C and 0→0

Therefore, (960)10 = (3C0)16

Number system from hexadecimal base to:

How to Convert Octal to Binary

We can convert a number from octal to binary using two ways:

 Indirect Method: Octal to decimal followed by decimal to binary

 Direct Method: Converting an octal number directly into the binary number system
Indirect Method: Octal to Decimal to Binary

Let’s discuss the octal to binary conversion steps for the indirect method.

Step 1: Convert octal to decimal.

To convert octal to decimal, we multiply each digit by the power of 8 based on the position starting from the
right. We will multiply the first digit from the right by 80. Next, we will multiply the second digit by 81 and
so on.

Step 2: Convert decimal to binary.

For converting decimal to binary, we will divide the given number by 2 and record
the quotient and reminder. We will repeat the process until we obtain 0 as the quotient.

Example: Convert from octal to binary: 548.

Step 1: Octal to decimal

548=4×80+5×81

548=4×1+5×8

548=4+40
548=4410

Step 2: Decimal to binary

Division Quotient Remainder

44÷2 22 0

22÷2 11 0

11÷2 5 1

5÷2 2 1

2÷2 1 0

1÷2 0 1

On arranging all the remainders in the reverse order, we will obtain the following binary number:

Thus, 4410=1011002

Direct Method: Octal to Binary Conversion Using the Chart

There is no specific octal to binary formula for conversion. However, if you are looking for an easier and
less complicated octal to binary conversion method, the direct method involves the following steps:

In octal to binary conversion, each digit in the octal number has a three-digit binary representation. Using it,
we can easily convert a number from octal to binary. We can convert octal to binary by choosing the binary
equivalent of every digit of the octal number from the below-mentioned chart.

Octal to Binary Conversion Table

The following table includes the octal numbers 0 to 7 and their equivalent three-digit binary representation
to aid octal to binary conversion.
 Octal Number Equivalent Three-digit Binary Representation

0 000

1 001

2 010

3 011

4 100

5 101

6 110

7 111

Let’s convert 548 to binary.

The number 54 has two digits: 5 and 4.

From the above chart, we will note down their binary equivalents.

5→101

4→100

Now, combining the two, we get the following binary number: 1011002.

Octal to Binary Conversion without Using the Conversion Table

Let’s understand the steps with the help of an example. We will also understand how the three-digit binary
representation is obtained for each octal digit.
Example: Convert 7658 to binary.

Step 1: Write the octal number by separating the digits.

7 6 5

Step 2: Each octal digit represents 3 binary bits. Starting from right to left, the value of these three digits
is 20=1,21=2, and 22=4 respectively. Thus, write (4, 2, 1) below each octal digit.

7 6 5

4 2 1 4 2 1 4 2 1

Step 3: Identify the numbers among 4, 2, and 1 (powers of 2), which add up to the octal number written on
the top. Write 1 below if the number is used. Write 0 below the number that is not used in the sum. For
example, 7=4+2+1, so we write 1 under all the three numbers.

7 6 5

4 2 1 4 2 1 4 2 1

1 1 1 1 1 0 1 0 1

Step 4: Write the 1s and 0s from left to write to find the binary equivalent of the given octal number.

Thus, 7658=1111101012

Octal to Binary Conversion: Examples

Let’s look at some examples based on all the methods we learned.

Example 1: Find the binary equivalent of the octal number 348.

Octal to decimal:
348=(3×81)+(4×80)

348=24+4

348=2810

Octal to Hexadecimal Conversion Table

Octal numbers converted to their corresponding hexadecimal values

Octal number Hexadecimal number

0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
10 8
11 9
12 A
13 B
14 C
15 D
16 E
17 F
20 10

Solved Examples of Octal to Hexadecimal

Problem : 1

What is the hexadecimal equivalent of (50)8

Solution:
Octal is first converted to binary before being converted to hexadecimal. Looking at the table of the octal to
binary conversion,

5 = 101

1 =000

(50)8=(101000)2

As we can see from the binary to hexadecimal conversion table,

0010 = 2

1000 = 8

As the result the hexadecimal equivalent of (50)8=(28)16

Problem : 2

Covert the octal number (56)8 to a hexadecimal number.

Solution:

Fist convert (56)8 into binary number

(56)8

= (101)(110)

=(101110)2

Now convert (101110)2(101110)2 in hexadecimal

(101110)2(101110)2

= (10)(1110)

= (2)(14)

= (2e)16

Problem: 3

Covert the octal (36.125)8(36.125)8 to Decimal Conversion

Solution:

= 3×81+6×80+1×8−1+2×8−2+5×8−3

= 24 + 6 + 0.125 + 0.03125 + 0.009765625

= (30.16601563)10(30.16601563)10

Decimal number =(30.16601563)10

Application of number base arithmetic operation

It is safe and wise to agree that number system holds its importance for everything which includes
proportion and percentage. Number system plays a crucial role, both in our everyday lives and the
technological world. With its myriad qualities, it simplifies our lives a lot, which has been discussed as
follows:

 It enables to keep count of all the things around people. Like how many apples are in the
basket, or the number of milk cartons to be purchased, etc.
 It enables the unique and accurate representation of different types of numbers.
 Making a phone call is possible only because we have a proper and efficient number system.
 Elevators used in public places also depend upon number systems for their functioning.
 Computation of any kind of interest on amounts deposited in banks.
 Creation of passwords on computers, security purposes.
 Encrypting important data, by converting figures into another number system to avoid hacking
and misuse of data.
 It enables easy conversion of numbers for technical purposes.
 The entirety of computer architecture depends upon number systems (octal, hexadecimal).
Every fiber of data gets stored in the computer as a number.
Description of logic gates

 Representation of Boolean logic gates

Logic gates are an important concept if you are studying electronics. These are important digital devices
that are mainly based on the Boolean function. Logic gates are used to carry out logical operations on single
or multiple binary inputs and give one binary output. In simple terms, logic gates are the electronic circuits
in a digital system.
AND gate

In the AND gate, the output of an AND gate attains state 1 if and only if all the inputs are in state 1.
The Boolean expression of AND gate is Y = A.B

The truth table of a two-input AND basic gate is given as

A B Y

0 0 0

0 1 0

1 0 0

1 1 1

NAND gate

This basic logic gate is the combination of AND and NOT gates.

The Boolean expression of the NAND gate is

The truth table of NOT gate is as follows

A Y

0 1

1 0
OR gate

In an OR gate, the output of an OR gate attains state 1 if one or more inputs attain state 1.
The Boolean expression of the OR gate is Y = A + B, read as Y equals A ‘OR’ B.

The truth table of a two-input OR basic gate is given as

A B Y

0 0 0

0 1 1

1 0 1

1 1 1

NOR gate
The NOR gate is a combination OR gate followed by an inverter. Its output is "true" if both inputs are
"false." Otherwise, the output is "false."

The truth table of a two-input OR basic gate is given as

A B Y

0 0 0

0 1 1

1 0 1

1 1 1
XOR gate

In an XOR gate, the output of a two-input XOR gate attains state 1 if one adds only input and attains state 1.

The Boolean expression of the XOR gate is

The truth table of an XOR gate is

A B Y

0 0 0

0 1 1

1 0 1

1 1 0

Exclusive-NOR Gate (XNOR Gate)

In the XNOR gate, the output is in state 1 when both inputs are the same, that is, both 0 or both 1.

The Boolean expression of the XNOR gate

The truth table of an XNOR gate is given below

A B Y

0 0 1

0 1 0

1 0 0

1 1 1

What is the Easiest Way to Learn Logic Gates?

The easiest way to learn the function of basic logic gates is explained below.

 For AND Gate – If both the inputs are high then the output is also high
 For OR Gate – If a minimum of one input is high then the output is High
 For XOR Gate – If the minimum one input is high then only the output is high
 NAND Gate – If the minimum one input is low then the output is high
 NOR Gate – If both the inputs are low then the output is high.

Applications of Logic Gates

 Circuits

De-Morgan's First Theorem

According to the first theorem, the complement result of the AND operation is equal to the OR operation of
the complement of that variable. Thus, it is equivalent to the NAND function and is a negative-OR function
proving that (A.B)' = A'+B' and we can show this using the following table.

Inputs Output For Each Term

A B A.B (A.B)' A' B' A'+B'

0 0 0 1 1 1 1

0 1 0 1 1 0 1

1 0 0 1 0 1 1

1 1 1 0 0 0 0

De-Morgan's Second Theorem

According to the second theorem, the complement result of the OR operation is equal to the AND operation
of the complement of that variable. Thus, it is the equivalent of the NOR function and is a negative-AND
function proving that (A+B)' = A'.B' and we can show this using the following truth table.

Inputs Output For Each Term

A B A+B (A+B)' A' B' A'.B'

0 0 0 1 1 1 1

0 1 1 0 1 0 0

1 0 1 0 0 1 0

1 1 1 0 0 0 0

Let's take some examples in which we take some expressions and apply DeMorgan's theorems.

Example 1: (A.B.C)'

(A.B.C)'=A'+B'+C'

Example 2: (A+B+C)'

(A+B+C)'=A'.B'.C

Example 3: ((A+BC')'+D(E+F')')'

For applying the DeMorgan's theorem on this expression, we have to follow the following expressions:

1) In complete expression, first, we find those terms on which we can apply the DeMorgan's theorem and
treat each term as a single variable.

So,
2) Next, we apply DeMorgan's first theorem. So,

3) Next, we use rule number 9, i.e., (A=(A')') for canceling the double bars.

4) Next, we apply DeMorgan's second theorem. So,

5) Again apply rule number 9 to cancel the double bar

Now, this expression has no term in which we can apply any rule or theorem. So, this is the final expression.

Example 3: (AB'.(A + C))'+ A'B.(A + B + C')'

  Use of data types on variables
Definition of datatype: is a type of data. a better definition of a data type is a data storage format
that can contain a specific type or range of values. It specifies the type of data that the variable can
store like integer, character, floating, double, etc.

Every Variable has a data type that tells what kind of data is being stored in a variable. There are two types
of data types in JavaScript.

 Primitive data types

 Non-primitive data types

Primitive data types: The predefined data types provided by JavaScript language are known as primitive
data types. Primitive data types are also known as in-built data types.

Below is a list of Primitive Data Types with proper descriptions and examples:

1. Number: Number data type in javascript can be used to hold decimal values as well as values without
decimals.

2. String: The string data type in javascript represents a sequence of characters that are surrounded by single
or double quotes.
3. Undefined: The meaning of undefined is ‘value is not assigned’.

4. Boolean: The boolean data type can accept only two values i.e. true and false.

5. Null: This data type can hold only one possible value that is null.

6. BigInt: This data type can represent numbers greater than 253-1 which helps to perform operations on
large numbers. The number is specified by writing ‘n’ at the end of the value

7. Symbol: This data type is used to create objects which will always be unique. these objects can be created
using Symbol constructor.

Non-primitive data types: The data types that are derived from primitive data types of the JavaScript
language are known as non-primitive data types. It is also known as derived data types or reference data
types.

Below is a list of Non-primitive data types.

Below is a list of Non-primitive Data Types with proper descriptions and examples:

1. Object: An object in Javascript is an entity having properties and methods. Everything is an object in
javascript.

2. Array: With the help of an array, we can store more than one element under a single name.

Difference between Primitive vs Non-Primitive:

Primitive Non-Primitive

Primitive Data types are predefined. Non-Primitive data types are created by the programmer

Primitive Data types will have certain values. Non-Primitive data types can be NULL.

Size depends on the type of data structure. Size is not fixed

Examples are numbers and strings. Examples are Array and Linked List.

It can start with a lowercase. It can start with uppercase.

 Application of datatypes

JavaScript is a dynamically typed language. It means that a variable doesn’t associate with a type. In other
words, a variable can hold a value of different types. For example:

let counter = 120; // counter is a number

counter = false; // counter is now a boolean
counter = "foo"; // counter is now a stringCode language: JavaScript (javascript)

To get the current type of the value that the variable stores, you use the typeof operator:

let counter = 120;

[Link](typeof(counter)); // "number"
counter = false;
[Link](typeof(counter)); // "boolean"
counter = "Hi";
[Link](typeof(counter)); // "string"Code language: JavaScript (javascript)

Output:

"number"
"boolean"
"string"

The undefined type

The undefined type is a primitive type that has only one value undefined. By default, when a variable is
declared but not initialized, it is assigned the value of undefined.

Consider the following example:

let counter;
[Link](counter); // undefined
[Link](typeof counter); // undefinedCode language: JavaScript (javascript)

In this example, the counter is a variable. Since counter hasn’t been initialized, it is assigned the value
undefined. The type of counter is also undefined.

It’s important to note that the typeof operator also returns undefined when you call it on a variable that
hasn’t been declared:

[Link](typeof undeclaredVar); // undefinedCode language: JavaScript (javascript)

The null type

The null type is the second primitive data type that also has only one value null. For example:

let obj = null;

[Link](typeof obj); // objectCode language: JavaScript (javascript)
The typeof null returns object is a known bug in JavaScript. A proposal to fix this was proposed but rejected.
The reason was the that fix would break a lot of existing sites.

JavaScript defines that null is equal to undefined as follows:

[Link](null == undefined); // trueCode language: JavaScript (javascript)

The number type

JavaScript uses the number type to represent both integer and floating-point numbers.

The following statement declares a variable and initializes its value with an integer:

let num = 100;Code language: JavaScript (javascript)

To represent a floating-point number, you include a decimal point followed by at least one number. For
example:

let price= 12.5;

let discount = 0.05;Code language: JavaScript (javascript)

Note that JavaScript automatically converts a floating-point number into an integer number if the number
appears to be a whole number.

The reason is that Javascript always wants to use less memory since a floating-point value uses twice as
much memory as an integer value. For example:

let price = 200.00; // interpreted as an integer 200Code language: JavaScript (javascript)

To get the range of the number type, you use Number.MIN_VALUE and Number.MAX_VALUE. For
example:

[Link](Number.MAX_VALUE); // 1.7976931348623157e+308
[Link](Number.MIN_VALUE); // 5e-324Code language: JavaScript (javascript)

Also, you can use Infinity and -Infinity to represent the infinite number. For example:

[Link](Number.MAX_VALUE + Number.MAX_VALUE); // Infinity

[Link](-Number.MAX_VALUE - Number.MAX_VALUE); // -InfinityCode language: JavaScript
(javascript)
NaN

NaN stands for Not a Number. It is a special numeric value that indicates an invalid number. For example,
the division of a string by a number returns NaN:.

[Link]('a'/2); // NaN;Code language: JavaScript (javascript)

The NaN has two special characteristics:

 Any operation with NaN returns NaN.

 The NaN does not equal any value, including itself.

Here are some examples:

[Link](NaN/2); // NaN
[Link](NaN == NaN); // falseCode language: JavaScript (javascript)

The string type

In JavaScript, a string is a sequence of zero or more characters. A string literal begins and ends with either a
single quote(') or a double quote (").

A string that begins with a double quote must end with a double quote. Likewise, a string that begins with a
single quote must also end with a single quote:

let greeting = 'Hi';

let message = "Bye";Code language: JavaScript (javascript)

If you want to single quote or double quotes in a literal string, you need to use the backslash to escape it. For
example:

let message = 'I\'m also a valid string'; // use \ to escape the single quote (')Code language: JavaScript
(javascript)

JavaScript strings are immutable. This means that it cannot be modified once created. However, you can
create a new string from an existing string. For example:

let str = 'JavaScript';

str = str + ' String';Code language: JavaScript (javascript)

In this example:
  First, declare the str variable and initialize it to a string of 'JavaScript'.
 Second, use the + operator to combine 'JavaScript' with ' String' to make its value as 'Javascript
String'.

Behind the scene, the JavaScript engine creates a new string that holds the new string 'JavaScript String' and
destroys the original strings 'JavaScript' and ' String'.

The following example attempts to change the first character of the string JavaScript:

let s = 'JavaScript';
s[0] = 'j';
[Link](s)Code language: JavaScript (javascript)

The output is:

'JavaScript'Code language: JavaScript (javascript)

But not:

'javaScript'Code language: JavaScript (javascript)

The boolean type

The boolean type has two literal values: true and false in lowercase. The following example declares two
variables that hold the boolean values.

let inProgress = true;

let completed = false;

[Link](typeof completed); // booleanCode language: JavaScript (javascript)

JavaScript allows values of other types to be converted into boolean values of true or false.

 Application of JavaScript operators

What is an Operator?

In JavaScript, an operator is a special symbol used to perform operations on operands (values and
variables). For example, 2 + 3; // 5. Here + is an operator that performs addition, and 2 and 3 are
operands.
Let us take a simple expression 4 + 5 is equal to 9. Here 4 and 5 are called operands and ‘+’ is called
the operator. JavaScript supports the following types of operators.

 Arithmetic Operators
 Comparison Operators
 Logical (or Relational) Operators
 Assignment Operators
 Conditional (or ternary) Operators

Lets have a look on all operators one by one.

Arithmetic Operators

JavaScript supports the following arithmetic operators −

Assume variable A holds 10 and variable B holds 20, then −

[Link]. Operator & Description

1
+ (Addition)

Adds two operands

Ex: A + B will give 30

2
- (Subtraction)

Subtracts the second operand from the first

Ex: A - B will give -10

3
* (Multiplication)

Multiply both operands

Ex: A * B will give 200

4
/ (Division)

Divide the numerator by the denominator

Ex: B / A will give 2

 5
% (Modulus)

Outputs the remainder of an integer division

Ex: B % A will give 0

6
++ (Increment)

Increases an integer value by one

Ex: A++ will give 11

7
-- (Decrement)

Decreases an integer value by one

Ex: A-- will give 9

Note − Addition operator (+) works for Numeric as well as Strings. e.g. "a" + 10 will give "a10".

Example

The following code shows how to use arithmetic operators in JavaScript.

<html>
<body>

<script type = "text/javascript">

<!--
var a = 33;
var b = 10;
var c = "Test";
var linebreak = "<br />";

[Link]("a + b = ");
result = a + b;
[Link](result);
[Link](linebreak);

[Link]("a - b = ");
result = a - b;
[Link](result);
 [Link](linebreak);

[Link]("a / b = ");
result = a / b;
[Link](result);
[Link](linebreak);

[Link]("a % b = ");
result = a % b;
[Link](result);
[Link](linebreak);

[Link]("a + b + c = ");
result = a + b + c;
[Link](result);
[Link](linebreak);

a = ++a;
[Link]("++a = ");
result = ++a;
[Link](result);
[Link](linebreak);

b = --b;
[Link]("--b = ");
result = --b;
[Link](result);
[Link](linebreak);
//-->
</script>

Set the variables to different values and then try...

</body>
</html>
Output
a + b = 43
a - b = 23
a / b = 3.3
a%b=3
a + b + c = 43Test
++a = 35
--b = 8
Set the variables to different values and then try...

Comparison Operators

JavaScript supports the following comparison operators −

Assume variable A holds 10 and variable B holds 20, then –

[Link]. Operator & Description

1
= = (Equal)

Checks if the value of two operands are equal or not, if yes, then the condition
becomes true.

Ex: (A == B) is not true.

2
!= (Not Equal)

Checks if the value of two operands are equal or not, if the values are not equal,
then the condition becomes true.

Ex: (A != B) is true.

3
> (Greater than)

Checks if the value of the left operand is greater than the value of the right operand,
if yes, then the condition becomes true.

Ex: (A > B) is not true.

4
< (Less than)

Checks if the value of the left operand is less than the value of the right operand,
if yes, then the condition becomes true.

Ex: (A < B) is true.

 5
>= (Greater than or Equal to)

Checks if the value of the left operand is greater than or equal to the value of the
right operand, if yes, then the condition becomes true.

Ex: (A >= B) is not true.

6
<= (Less than or Equal to)

Checks if the value of the left operand is less than or equal to the value of the right
operand, if yes, then the condition becomes true.

Ex: (A <= B) is true.

Example

The following code shows how to use comparison operators in JavaScript.

<html>
<body>
<script type = "text/javascript">
<!--
var a = 10;
var b = 20;
var linebreak = "<br />";
[Link]("(a == b) => ");
result = (a == b);
[Link](result);
[Link](linebreak);

[Link]("(a < b) => ");

result = (a < b);
[Link](result);
[Link](linebreak);

[Link]("(a > b) => ");

result = (a > b);
[Link](result);
[Link](linebreak);
 [Link]("(a != b) => ");
result = (a != b);
[Link](result);
[Link](linebreak);

[Link]("(a >= b) => ");

result = (a >= b);
[Link](result);
[Link](linebreak);

[Link]("(a <= b) => ");

result = (a <= b);
[Link](result);
[Link](linebreak);
//-->
</script>
Set the variables to different values and different operators and then try...
</body>
</html>
Output
(a == b) => false
(a < b) => true
(a > b) => false
(a != b) => true
(a >= b) => false
a <= b) => true
Set the variables to different values and different operators and then try...

Logical Operators

JavaScript supports the following logical operators −

Assume variable A holds 10 and variable B holds 20, then −

[Link]. Operator & Description

1
&& (Logical AND)
 If both the operands are non-zero, then the condition becomes true.

Ex: (A && B) is true.

2
|| (Logical OR)

If any of the two operands are non-zero, then the condition becomes true.

Ex: (A || B) is true.

3
! (Logical NOT)

Reverses the logical state of its operand. If a condition is true, then the Logical
NOT operator will make it false.

Ex: ! (A && B) is false.

Example

Try the following code to learn how to implement Logical Operators in JavaScript.

<html>
<body>
<script type = "text/javascript">
<!--
var a = true;
var b = false;
var linebreak = "<br />";

[Link]("(a && b) => ");

result = (a && b);
[Link](result);
[Link](linebreak);

[Link]("(a || b) => ");

result = (a || b);
[Link](result);
[Link](linebreak);

[Link]("!(a && b) => ");

result = (!(a && b));
 [Link](result);
[Link](linebreak);
//-->
</script>
<p>Set the variables to different values and different operators and then try...</p>
</body>
</html>
Output
(a && b) => false
(a || b) => true
!(a && b) => true
Set the variables to different values and different operators and then try...

Bitwise Operators

JavaScript supports the following bitwise operators −

Assume variable A holds 2 and variable B holds 3, then −

[Link]. Operator & Description

1
& (Bitwise AND)

It performs a Boolean AND operation on each bit of its integer arguments.

Ex: (A & B) is 2.

2
| (BitWise OR)

It performs a Boolean OR operation on each bit of its integer arguments.

Ex: (A | B) is 3.

3
^ (Bitwise XOR)

It performs a Boolean exclusive OR operation on each bit of its integer arguments.

Exclusive OR means that either operand one is true or operand two is true, but not
both.

Ex: (A ^ B) is 1.
 4
~ (Bitwise Not)

It is a unary operator and operates by reversing all the bits in the operand.

Ex: (~B) is -4.

5
<< (Left Shift)

It moves all the bits in its first operand to the left by the number of places specified
in the second operand. New bits are filled with zeros. Shifting a value left by one
position is equivalent to multiplying it by 2, shifting two positions is equivalent to
multiplying by 4, and so on.

Ex: (A << 1) is 4.

6
>> (Right Shift)

Binary Right Shift Operator. The left operand’s value is moved right by the
number of bits specified by the right operand.

Ex: (A >> 1) is 1.

7
>>> (Right shift with Zero)

This operator is just like the >> operator, except that the bits shifted in on the left
are always zero.

Ex: (A >>> 1) is 1.

Example

Try the following code to implement Bitwise operator in JavaScript.

<html>
<body>
<script type = "text/javascript">
<!--
var a = 2; // Bit presentation 10
var b = 3; // Bit presentation 11
var linebreak = "<br />";

[Link]("(a & b) => ");

 result = (a & b);
[Link](result);
[Link](linebreak);

[Link]("(a | b) => ");

result = (a | b);
[Link](result);
[Link](linebreak);

[Link]("(a ^ b) => ");

result = (a ^ b);
[Link](result);
[Link](linebreak);

[Link]("(~b) => ");

result = (~b);
[Link](result);
[Link](linebreak);

[Link]("(a << b) => ");

result = (a << b);
[Link](result);
[Link](linebreak);

[Link]("(a >> b) => ");

result = (a >> b);
[Link](result);
[Link](linebreak);
//-->
</script>
<p>Set the variables to different values and different operators and then try...</p>
</body>
</html>
(a & b) => 2
(a | b) => 3
(a ^ b) => 1
(~b) => -4
(a << b) => 16
(a >> b) => 0
Set the variables to different values and different operators and then try...

Assignment Operators

JavaScript supports the following assignment operators −

[Link]. Operator & Description

1
= (Simple Assignment )

Assigns values from the right side operand to the left side operand

Ex: C = A + B will assign the value of A + B into C

2
+= (Add and Assignment)

It adds the right operand to the left operand and assigns the result to the left
operand.

Ex: C += A is equivalent to C = C + A

3
−= (Subtract and Assignment)

It subtracts the right operand from the left operand and assigns the result to the left
operand.

Ex: C -= A is equivalent to C = C - A

4
*= (Multiply and Assignment)

It multiplies the right operand with the left operand and assigns the result to the
left operand.

Ex: C *= A is equivalent to C = C * A

5
/= (Divide and Assignment)

It divides the left operand with the right operand and assigns the result to the left
operand.
 Ex: C /= A is equivalent to C = C / A

6
%= (Modules and Assignment)

It takes modulus using two operands and assigns the result to the left operand.

Ex: C %= A is equivalent to C = C % A

Note − Same logic applies to Bitwise operators so they will become like <<=, >>=, >>=, &=, |= and ^=.

Example

Try the following code to implement assignment operator in JavaScript.

<html>
<body>
<script type = "text/javascript">
<!--
var a = 33;
var b = 10;
var linebreak = "<br />";

[Link]("Value of a => (a = b) => ");

result = (a = b);
[Link](result);
[Link](linebreak);

[Link]("Value of a => (a += b) => ");

result = (a += b);
[Link](result);
[Link](linebreak);

[Link]("Value of a => (a -= b) => ");

result = (a -= b);
[Link](result);
[Link](linebreak);

[Link]("Value of a => (a *= b) => ");

result = (a *= b);
[Link](result);
 [Link](linebreak);

[Link]("Value of a => (a /= b) => ");

result = (a /= b);
[Link](result);
[Link](linebreak);

[Link]("Value of a => (a %= b) => ");

result = (a %= b);
[Link](result);
[Link](linebreak);
//-->
</script>
<p>Set the variables to different values and different operators and then try...</p>
</body>
</html>
Output
Value of a => (a = b) => 10
Value of a => (a += b) => 20
Value of a => (a -= b) => 10
Value of a => (a *= b) => 100
Value of a => (a /= b) => 10
Value of a => (a %= b) => 0
Set the variables to different values and different operators and then try...

Miscellaneous Operator

We will discuss two operators here that are quite useful in JavaScript: the conditional operator (? :) and
the typeof operator.

Conditional Operator (? :)

The conditional operator first evaluates an expression for a true or false value and then executes one of the
two given statements depending upon the result of the evaluation.

[Link]. Operator and Description

1
? : (Conditional )
 If Condition is true? Then value X : Otherwise value Y

Example

Try the following code to understand how the Conditional Operator works in JavaScript.

<html>
<body>
<script type = "text/javascript">
<!--
var a = 10;
var b = 20;
var linebreak = "<br />";

[Link] ("((a > b) ? 100 : 200) => ");

result = (a > b) ? 100 : 200;
[Link](result);
[Link](linebreak);

[Link] ("((a < b) ? 100 : 200) => ");

result = (a < b) ? 100 : 200;
[Link](result);
[Link](linebreak);
//-->
</script>
<p>Set the variables to different values and different operators and then try...</p>
</body>
</html>
Output
((a > b) ? 100 : 200) => 200
((a < b) ? 100 : 200) => 100
Set the variables to different values and different operators and then try...

typeof Operator

The typeof operator is a unary operator that is placed before its single operand, which can be of any type. Its
value is a string indicating the data type of the operand.
The typeof operator evaluates to "number", "string", or "boolean" if its operand is a number, string, or boolean
value and returns true or false based on the evaluation.

Here is a list of the return values for the typeof Operator.

Type String Returned by typeof

Number "number"

String "string"

Boolean "boolean"

Object "object"

Function "function"

Undefined "undefined"

Null "object"

Example

The following code shows how to implement typeof operator.

<html>
<body>
<script type = "text/javascript">
<!--
var a = 10;
var b = "String";
var linebreak = "<br />";

result = (typeof b == "string" ? "B is String" : "B is Numeric");

[Link]("Result => ");
[Link](result);
[Link](linebreak);
 result = (typeof a == "string" ? "A is String" : "A is Numeric");
[Link]("Result => ");
[Link](result);
[Link](linebreak);
//-->
</script>
<p>Set the variables to different values and different operators and then try...</p>
</body>
</html>
Output
Result => B is String
Result => A is Numeric
 Write an algorithm
An algorithm is a procedure or step-by-step instruction for solving a problem. They form the foundation of
writing a program.

For writing any programs, the following has to be known:

 Input
 Tasks to be preformed
 Output expected

Type of algorithms used in javascript.

1. Sorting algorithms

Javascript provides a rich set of data types and operators that can be used to implement various sorting
algorithms such as bubble sort, insertion sort and quick sort.

These algorithms are useful in many applications because they can be used to sort data of different sizes and
types.

There are different sorting algorithms.

they are:-

(i) Bubble sort: An uncomplicated sorting algorithm that compares nearby components repeatedly and
switches them out if they are out of order.

The Algorithm for Bubble sort is:-

 1. Start with an unsorted list of elements.
2. Compare the first two elements in the list. If the first element is larger than the second element, swap
them.
3. Move on to the next pair of elements and repeat step 2 until the end of the list is reached.
4. For each item on the list, repeat steps 2 and 3 once more. that is referred to as passes.
5. Repeat steps 2-4 for the entire list. As you repeat the passes, elements will "bubble up" to their correct
position in the sorted list.
6. Once a pass is completed and no swaps are made, the list is sorted, and the algorithm can stop.
7. The final sorted list is returned.

(ii) Insertion sort: a method of sorting that creates a sorted list one individual element at a time by placing
each one in the appropriate spot.

The Algorithm for Insertion sort is:-

1. Initialize an empty sorted list and an unsorted list of the elements to be sorted.
2. The first member from the unsorted list should be taken and placed in the appropriate position in the
sorted list.
3. Repeat step 2 for each subsequent element in the unsorted list.
4. Compare the current element with the elements in the sorted list, starting with the element immediately
to the left.
5. Swap the two elements if the current element is smaller than the element to its left.
6. If the current element is larger than the element to its left, insert it at its correct position in the sorted
list.
7. Repeat steps 4-6 for each subsequent element in the unsorted list.
8. Once all elements have been processed, the sorted list will contain all elements in the correct order.
9. The sorting process is complete.

(iii) Selection sort: a method of sorting that consistently starts the sorted listing with the smallest detail from
the unordered listing.

The Algorithm for Selection sort is:-

1. Begin by setting the primary element of list as the min element.

2. Repeat through the remaining items in the list, comparing each one to the current minimum.
3. Set a new minimum if an element is found to be smaller than the existing one.
4. Change the current minimum to the first element of the list whenever it reaches its conclusion.
 5. For the remaining unsorted portion of the listing, repeat steps 2-4, but begin with the second item on
the list (as the first element is already sorted).
6. Continue sorting the list in this manner until it is all sorted.

(iv) Quick sort: A divide-and-conquer sorting algorithm that chooses a pivot element and splits the list into
sublists depending on whether the elements are fewer than or more than the pivot. After that, the sublists are
sorted repeatedly until the full list is sorted.

The Algorithm for Quick sort is:-

1. Choose a pivot element from the list. This is typically the first element, but it can also be a random
element or the median of the list.
2. Divide the list into two sublists: one containing elements less than the pivot and one containing
elements greater than the pivot.
3. Recursively sort the sublist containing elements less than the pivot using the same process.
4. Use the same procedure to recursively sort the sublist of entries larger than the pivot.
5. Concatenate the sorted sublists with the pivot element in between to form a fully sorted list.
6. Return the fully sorted list.

(v) Merge sort: The divide-and-conquer sort algorithm divides the list into two halves, sorts each half, and
then merges the two halves in sorted order.

Merge-sort Algorithm:

1. Make two sublists out of the list: one with elements below the pivot and one with elements above the
pivot.
2. Produces a new sorted sublist by iteratively merging sublists until only one sublist exists. This will be
your sorted list.
3. Steps to merge two sub-directories:-
4. Create an empty list to hold the sorted elements.
5. Compares the first element of each sublist.
6. Adds the smaller element to the new list and removes it from the parent sublist.
7. Repeat the steps 2 and 3 until a list is completly empty.
8. Adds the remaining elements from other sublists to a new list.
9. Replaces the merged sublist with the new sorted list.
10. Repeat this process until all sublists are merged into one sorted list.
(vi) Heapsort: A sorting algorithm that sorts elements using a data structure called heap.

This is the classification algorithm:

1. Build max heap: Starting with the first non-leaf node, compare each node with its child nodes and
replace the nodes with the largest of its children to satisfy the max heap property.
2. Swap root with last element: Swap the root (largest element) with the last element in the stack.
3. Stack the rest of the elements. Starting from the root, each node is compared with its children, swapping
nodes with their older children until the max heap property is satisfied.
4. Repeat steps 2 and 3 with the newly stacked elements, except for the last element in the correct
position.
5. Repeat this process until only one element remains in the stack. This is now sorted.
6. Heapify Down: Starting from the root node, it compares elements with its children and swaps with
the larger of the two until the max heap property is satisfied.
7. Heapify Up: Start with the last element in the heap, compare it to its parent, and swap it with the parent
to satisfy the max heap property.

(vii) Radix sort: A sorting algorithm that sorts elements based on the digits or digits of their binary
representation.

The Algorithm for Radix sort is:-

1. determine how many digits are contained in the input listing's largest element.
2. Initialize a variable, say digit place, to 1, which represents the current digit place.
3. Create an empty list for each possible digit value from 0 to 9.
4. Iterate through the input list and add each element to the appropriate list based on the value of the
current digit place.
5. Concatenate all the lists together to form the new list in the order of the digit lists.
6. Multiply digitPlace by 10 to move to the next digit place.
7. Repeat steps 4-6 for each digit place until all digits in the largest element have been considered.
8. The final list will be sorted in ascending order by the digits of the elements.
9. Return the final sorted list.

2. Searching algorithms
C also provides the tools necessary to implement a variety of searching algorithms, such as linear search and
binary search. These algorithms can quickly find specific items in a data set, making them useful for a wide
range of applications.

There are many types of search algorithms.

They are:-

(i) Linear search: A basic search algorithm that examines each item in the listing one by one until it finds the
desired item.

Algorithm for Linear search:-

1. Define the input for the algorithm: The input for a linear search algorithm is a list of elements (or an
array) and a target element we are searching for.
2. Initialize a variable called "index" to -1: This variable will be used to store the index of the target
element if it is found.
3. Loop through the list of elements: Starting from the first element, check each element in the list one
by one.
4. Compare the present element to the desired element for evaluation: Keep the index of the current
element in the index variable and exit the loop if the modern element and the goal element are identical.
5. Return the index of the target element: After the loop completes, return the value stored in the index
variable. If the target element is not found, the value of the index will be -1

(ii) Binary search: A search algorithm that operates by splitting the listing into halves and searches within of
those halves is more likely to include the element.

Algorithm for Binary search:-

1. Input: A sorted list of n elements and a target element x.

2. Initialize variables: Set the low index to 0, the high index to n-1, and mid to (low+high)/2.
3. Start a loop: While the low index is less than or equal to the high index, repeat the following steps.
4. Compare the mid element with x: If the mid element is equal to x, return the mid index.
5. Update the low or high index: If x is greater than the mid element, set the low index to mid + 1. Else,
set the high index to mid - 1.
6. Update the mid index: Mid = (low+high)/2.
7. End of the loop: If the low index is greater than the high index, then x is not in the list, and the algorithm
returns a failure.
 8. Output: The index of x in the list or failure message.

(iii) Depth-first search: A search algorithm that examines each branch as far as is feasible before turning
around.

The following guidelines apply to depth-first search:

1. select the graph's starting vertex or node to start with.

2. Add a visiting mark to the first vertex.
3. Directly place the beginning vertex into a stack.
4. Until the stack is empty, repeat the following actions: -
o Remove the stack's top vertex.
o Mark as visited and insert into the stack each unvisited neighbour of the popped vertex.
5. Continue this process until all vertices in the graph have been visited.
6. Once all vertices have been visited, the algorithm is complete, and a depth-first search is performed on
the graph.

(iv) Breadth-first search: A search algorithm that explores all the neighbors of a node before moving to the
next level.

The algorithm for the breadth-first search is:-

1. Start with the root node or the initial state.

2. Add the root node to a queue.
3. Check if the queue is empty; if yes, then terminate the algorithm.
4. Take the first element from the queue and mark it as visited.
5. Amplify the contemporary node by adding all its unvisited neighbors to the queue.
6. Until the desired node is located or the queue is empty, repeat steps 3 to 5.
7. Return the path from the preliminary state to the target state if the goal node is found.
8. Terminate the set of rules and report that the goal state was not identified if the queue is empty.

(v) Interpolation Search: A search algorithm that uses the values of the searched elements to estimate the
position in the index.

It is important that the array is evenly distributed. Otherwise, it is an algorithm.

It works as expected.
The algorithm can be summarized as follows.

1. Get the input list and key value to search.

2. Initialize the lower and upper variables at the first and last indices of the list.
3. If the Lower value is less than or equal to higher value, then :-
1. Calculate the estimated location using the following formula:
pos = low + ((high - low) / (arr[high] - arr[low])) * (x - arr[low]).
2. Return the position if the estimated position value is a key value.
3. c) If the estimated position value is less than the key value, set it lower.
Position + 1.
4. d) If the value of the estimated position is greater than the key Set value, position - 1 up.
4. If the key value is not found, return -1 to indicate that the value is not in the list.

(vi) Jump search: A search method that iterates over the list in constant-length steps until it finds the relevant
element or determines that it is no longer present.

The jump search algorithm is as follows:

1. First, set the jump size to the square root of the number of array elements.
2. Sets a variable named "current" to the first element of the array.
3. Iterates over the array by jumping by jump size while incrementing a variable called "jump".
4. Move on to the following leap if the existing element is smaller than the desired element.
5. If the current element is larger than the target element, perform a linear search between the current
element and the previous jump element to find the target element.
6. If the target element is not found in the array, it returns -1 to indicate that it is not in the array.
7. If the element is found, it returns the element's index in the array.

3. Graph algorithms

C's support for pointers and data structures such as arrays and linked lists makes it suitable for implementing
algorithms that manipulate graphs, such as finding the shortest path between two nodes in a graph.

There are different types of graph algorithms.

they are:-

1. Dijkstra's Algorithm: An algorithm that finds the shortest path between two nodes in a graph by
continuously updating the shortest distance from each node.
 2. Algorithm A*: A method that continually updates the shortest course to each node in a graph to
determine the shortest route between them.
3. Prim's Algorithm: An approach for figuring out the weighted connected graph's smallest spanning
tree.
4. Kruskal's algorithm: An approach to identify the linked weighted graph's lowest spanning tree.
5. Bellman-Ford Algorithm: An algorithm that, even when the graph has negative edge weights,
displays the shortest path between a particular supply node and every other node in the network.

4. Cryptographic Algorithms

C supports low-level operations and efficient data manipulation, making it ideal for implementing algorithms
used in cryptography, such as data encryption and decryption algorithms.

There are different types of encryption algorithms.

They are:-

1. Hash Algorithms: These algorithms produce fixed-size outputs (hash) from arbitrary-sized inputs.
Examples include MD5, SHA-1 and SHA-2.
2. Symmetric key algorithms: The encryption and decryption steps in such algorithms employ the same
private key. AES, DES, and Blowfish are a few examples.
3. Asymmetric key algorithms: A public key and a non-public key are used by those methods as separate
keys for encryption and decryption. Some examples include RSA, ECC, and DSA.
4. Key exchange algorithms: These algorithms allow two parties to exchange keys over an insecure
channel securely. For example, we can mention Diffie-Hellman and Elliptic Curve Diffie-Hellman.

Characteristics/qualities of a good algorithm

 Efficiency: A good algorithm should perform its task quickly and use minimal resources.
 Correctness: It must produce the correct and accurate output for all valid inputs.
 Clarity: The algorithm should be easy to understand and comprehend, making it maintainable and
modifiable.
 Scalability: It should handle larger data sets and problem sizes without a significant decrease in
performance.
 Reliability: The algorithm should consistently deliver correct results under different conditions and
environments.
 Optimality: Striving for the most efficient solution within the given problem constraints.
 Robustness: Capable of handling unexpected inputs or errors gracefully without crashing.
  Adaptability: Ideally, it can be applied to a range of related problems with minimal adjustments.
 Simplicity: Keeping the algorithm as simple as possible while meeting its requirements, avoiding
unnecessary complexity.

Develop an algorithm using structured English

Structured English is the use of the English language with the syntax of structured programming to
communicate the design of a computer program to non-technical users by breaking it down into logical steps
using straightforward English words. Structured English gives aims to get the benefits of both the
programming logic and natural language: program logic helps to attain precision, whilst natural language
helps with the familiarity of the spoken word.

Structured English

Structure English is derived from structured programming language which gives more understandable and
precise description of process. It is based on procedural logic that uses construction and imperative
sentences designed to perform operation for action.

 It is best used when sequences and loops in a program must be considered and the problem needs
sequences of actions with decisions.
 It does not have strict syntax rule. It expresses all logic in terms of sequential decision structures and
iterations.

For example, see the following sequence of actions −

if customer pays advance

then
Give 5% Discount
else
if purchase amount >=10,000
then
if the customer is a regular customer
then Give 5% Discount
else No Discount
end if
else No Discount
end if
end if

Following are the algorithm of the sum and the average of three numbers is given below.
Explanation:

Step 1: Start

Step 2: Read the three number suppose "a","b","c" form the user.

Step 3: Declared a variable "sum" and "Avg".

Step 4 : sum=a+b+c;

Step 5: Avg=sum/3

Step 6: Display "sum " and "Avg".

Step 7: End.

Find the Largest Number Using if-else Statements

The idea is to use the compound expression where each number is compared with the other two to find out
which one is the maximum of them.

Algorithm

 Check if A is greater than or equal to both B and C, A is the largest number.

 Check if B is greater than or equal to both A and C, B is the largest number.
 Check if C is greater than or equal to both A and B, C is the largest number.

Develop an algorithm using pseudocode

1. Definition:
Sequence, the order that commands are executed by a computer, allows us to carry out tasks that have
multiple steps.
In programming, sequence is a basic algorithm: A set of logical steps carried out in order. Computers need
instructions in the form of an algorithm in order to complete a desired task, and this algorithm must have the
correct order of steps, or sequence.
2. Selection/conditional structures
A CONDITIONAL is a type of step in an algorithm where a decision must be made.
Computers follow logical instructions and they need to know how to handle different
decisions so that programs can proceed no matter what the outcome of those selections may
be.

a. IF-THEN-ELSE CONDITIONALS
 One of the first things that programmers learn is how to use IF-THEN-ELSE statements. Every
programming language has some version of these. The syntax and exact usage may be different but
they all accomplish the same thing, which is to allow for program execution based on conditionals.
The basic flow is: If some condition is true then do this, otherwise do that.
Complex conditional statements can have more than just two choices. As humans, the way we make
decisions when we have several options to choose from is very different than computers. We are able
to select one item out of a group of choices, however a computer program must proceed by making
binary decisions, meaning that it can only select between two things at a time. Even the most complex
conditional statements boil down to a series of binary choices.

b. SWITCH AND CASE CONDITIONALS

The switch statement is used to allow you to perform different actions based
on different conditions. In some languages this was a common structure for
conditional execution that makes it easier for a program to execute one of
several cases depending on the value of the expression at the switch.
Pseudocode is an informal way of programming description that does not require any strict programming
language syntax or underlying technology considerations. It is used for creating an outline or a rough draft
of a program. Pseudocode summarizes a program’s flow, but excludes underlying details.

Pseudo code can be broken down into five components.

• Variables:

• Assignment:

• Input/output:

• Selection:

• Repetition:

Advantages of pseudocode –

 Pseudocode is understood by the programmers of all types.

 It enables the programmer to concentrate only on the algorithm part of the code development.
 It cannot be compiled into an executable program.
 The main goal of a pseudo code is to explain what exactly each line of a program should do, hence
making the code construction phase easier for the programmer.

Best practices for writing pseudocode

Some pseudocode rules include:

 Capitalize the construct keyword.

  Apply one construct per line unless pairing it with a construct like IF-THEN.
 Indent the code when using multiple constructs.
 Use plain language that describes the problem.
 Use the phrase END plus the construct keyword to show that an element of pseudocode is complete,
such as ENDFOR and ENDWHILE.

Examples

1: Write pseudo code that reads two numbers and multiplies them together and print out their product.

2: Write pseudo code that tells a user that the number they entered is not a 5 or a 6.

3: Write pseudo code that performs the following: Ask a user to enter a number. If the number is between 0
and 10, write the word blue. If the number is between 10 and 20, write the word red. if the number is
between 20 and 30, write the word green. If it is any other number, write that it is not a correct color option.

4: Write pseudo code to print all multiples of 5 between 1 and 100 (including both 1 and 100).

5: Write pseudo code that will count all the even numbers up to a user defined stopping point.

6: Write pseudo code that will perform the following.

a) Read in 5 separate numbers.

b) Calculate the average of the five numbers.

c) Find the smallest (minimum) and largest (maximum) of the five entered numbers.

d) Write out the results found from steps b and c with a message describing what they are.

Homework

1: Write pseudo code that reads in three numbers and writes them all in sorted order.

2: Write pseudo code that will calculate a running sum. A user will enter numbers that will be added to the
sum and when a negative number is encountered, stop adding numbers and write out the final result.

 Design of Flowchart

Flowchart: It is a diagram of the sequence of movements or actions of people or things involved in a

complex system or activity.

It is a graphical representation of a computer program in relation to its sequence of functions (as distinct
from the data it processes).
When to Use a Flowchart

 To develop understanding of how a process is done

 To study a process for improvement
 To communicate to others how a process is done
 When better communication is needed between people involved with the same process
 To document a process
 When planning a project

Flowchart Basic Procedure

Materials needed: Sticky notes or cards, a large piece of flipchart paper or newsprint, and marking pens.

1. Define the process to be diagrammed. Write its title at the top of the work surface.
2. Discuss and decide on the boundaries of your process: Where or when does the process start? Where
or when does it end? Discuss and decide on the level of detail to be included in the diagram.
3. Brainstorm the activities that take place. Write each on a card or sticky note.
4. Arrange the activities in proper sequence.
5. When all activities are included and everyone agrees that the sequence is correct, draw arrows to
show the flow of the process.
6. Review the flowchart with others involved in the process (workers, supervisors, suppliers,
customers) to see if they agree that the process is drawn accurately.

Description of Elements of Flowchart

Flowchart Symbols

Here is a chart for some of the common symbols used in drawing flowcharts.

Symbol Symbol Name Purpose

Used at the beginning and end of the algorithm to show

Start/Stop
start and end of the program.

Process Indicates processes like mathematical operations.

Input/ Output Used for denoting program inputs and outputs.

 Stands for decision statements in a program, where answer
Decision
is usually Yes or No.

Arrow Shows relationships between different shapes.

Connects two or more parts of a flowchart, which are on

On-page Connector
the same page.

Connects two parts of a flowchart which are spread over

Off-page Connector
different pages.

Guidelines for Developing Flowcharts

These are some points to keep in mind while developing a flowchart −

 Flowchart can have only one start and one stop symbol
 On-page connectors are referenced using numbers
 Off-page connectors are referenced using alphabets
 General flow of processes is top to bottom or left to right
 Arrows should not cross each other

Example Flowcharts

Here is the flowchart for going to the market to purchase a pen.

Here is a flowchart to calculate the average of two numbers.

[Link]
[Link]
Learning outcome 2: Apply Data Structure
 Identification of data structure concepts

Definition of Data structures: