Home / Algorithm

Data Structure and Algorithm - Hanoi College of Industry - 14

QUESTIONS AND EXERCISES AT THE END OF CHAPTER 4

1) Write a program to do the following:

a. Write a function to randomly generate an integer sequence of about 100 numbers (including integers from 1 to 100.

b. Write a function to display a series of numbers on the screen.

c. Write 5 functions to sort the sequence of numbers according to 5 different algorithms in descending order.

d. Write a menu function and a main function that allows you to select and perform tasks until you want to finish.

e. Add a time calculation section for each algorithm to evaluate, compare, and rerun the program with key sequences when n=20; n=200 and n=2000.

2) Write a program to do the following job:

a. Write a function to create an array containing a list of student names in a class, each student has 2 fields: middle name and first name.

b. Write a function to display a list of student names on the screen (each name on a line).

c. Write 5 functions to sort according to 5 different algorithms in the dictionary order of student names.

d. Write a menu function and a main function that allows you to select and perform tasks until you want to finish.

3) Write a program to do the following job:

a. Write a function to randomly generate an array of about 50 integers (including integers from 1 to 100.

b. Write a function to display a series of numbers on the screen.

c. Write a sorting function using the QuickSort algorithm with the pivot key being the first element of the array.

d. Write a sorting function using the QuickSort algorithm with the pivot key being the last element of the array, in ascending order of the array.

e. Write a sorting function using the QuickSort algorithm with the key being the element in the middle of the array, in ascending order of the array.

f. Write a sorting function using QuickSort algorithm with the pivot key being the median element in 3 keys: First, middle and last as pivot key, in ascending order of the sequence.

g. Write a menu function and a main function that allows you to select and perform tasks until you want to finish.

CHAPTER 5 SEARCH

Target:

- Understand algorithms, implement algorithms and evaluate the complexity of linear search and binary search algorithms.

- Use linear search and binary search algorithms to suit the requirements of practical problems.

1. Search problem

The need to search frequently occurs in real life as well as in computer processing. The general search problem is to find a record with a given key field value X in a table of n records.

The search is performed by comparing X (the search key) with the value of the key field. The algorithm will complete when one of the following two situations occurs:

- Found: Found a record with a corresponding key value equal to X.

- Not found: No record with corresponding key value equal to

X.

Unlike sorting, search keys are considered as identifying features of

each record. To simplify, let's assume that the search algorithm is performed on a table of n records with only one key field, which is unique, and the key values ​​are integers.

The search algorithms considered in this chapter are two popular algorithms: Sequential search and binary search and are implemented in internal memory (internal search).

2. Linear Search

2.1. Algorithm idea

It is a very simple and classic search technique. The content can be summarized as

after:

Starting from the first record, compare the search key with the corresponding key in turn.

the records in the table, until the desired record is found or the table is exhausted and not found.

2.2. Algorithm description.

Input:

- K is a key sequence of n records

- The keys are numbered from K 0 , K 1 ,…K i ,…K n-1

- X is the search key

Process:

Step 1 : Initialize

- Add key X to the end of the key sequence (so that the search always finds X)

- Initialize the value 0 for the index variable i

Step 2: Find key X in key sequence K

Repeat the following until X is found Compare key X with each Ki key

Step 3: Consider the case of finding or not finding If i<n then return (i)

Otherwise return(-1)

Output: i is the index of the key whose value matches X, or -1 if X is not found

2.3. Algorithm installation.

int Sequen-Search(int K[], int n, int X)

{ int i=0; K[n]=X;

While (X != K[i]) i++;

if (i<n) return (i);

else return (-1);

}

2.4. Algorithm representation.

Algorithm description with key sequence:

K: 6 4 9 3 8 2 7 5

n = 8; search with x=2 and x =1

Find with x=2  Add K[n]=x;


K key sequence

6

4

9

3

8

2

7

5

2

Index

0

1

2

3

4

5

6

7

8=n


Start i=0

i

I

i

i

i

i

K[i]=x;

K[i] ≠ x; increase I until K[i]=x;

return (i=5): Found

Find with x=1  Add K[n]=x;

K key sequence

6

4

9

3

8

2

7

5

1

Maybe you are interested!

0

1

2

3

4

5

6

7

8=n

Start i=0

i

i

I

i

i

i

i

i

i

K[i] ≠ x; increase i until K[i]=x;

Since i=n  return (-1): Not found

Index


3. Binary search.

3.1. Algorithm idea.

Similar to the way we look up the phone number of an agency, in the telephone directory or when we look up a word in the dictionary. The binary search algorithm always chooses the "middle" key in the list of keys under consideration to perform comparison with the search key. The search will stop if the search key is equal to the key in the middle of the list, the search will repeat similarly with the first half (left) if the search key is smaller than the key in the middle of the list, and repeat similarly with the second half (right) if the search key is larger than the middle key. The search process continues until the desired key is found or the list of keys under consideration becomes empty (not found).

Thus, the condition to be able to perform binary search algorithm is that the key array must be sorted in ascending (or descending) order with numbers and lexicographic order for the character string.

3.2. Algorithm description.

Input:

- K is a key array of n records sorted in ascending order

gradually


- The keys are numbered from K 0 , K 1 ,…K i ,…K n-1.

- X is the search key.

Process:

Step 1 : Initialize.

- Initialize the value 0 for the index variable left.

- Initialize the value n-1 for the index variable right.

Step 2: Find key X in key sequence K.

- Repeat the following until left > right.

• Initialize the integer value of (left +right)/2 to the mid index variable.

• If X = K mid then return (mid).

• If X < K mid then search in the previous row (right = mid-1).

• If X > K mid then search in the next row (left= mid +1).

- If not found (left > right) then return(-1).

Output: mid is the index of the key whose value matches X, or -1 if X is not found.

3.3. Algorithm installation.

int BinarySearch (int K[], int n, int X)

{ int mid; left=0; right=n-1; do{

mid=(left+right)/2;

if (X== K[mid]) return (mid); else. else

if (X< K[mid]) right=mid-1; else left=mid+1;

} while(left<=right); return -1;

}

3.4. Algorithm representation.

Algorithm description with key sequence:

K: 6 4 9 3 8 2 7 5

n = 8; search with x=2 ; x =1 and x=12

Find with x=2


K key sequence


2

3

4

5

6

7

8

9


Index

-1

0

1

2

3

4

5

6

7

8=n


Start Left=0; Right=n-1


left



mid




right



mid=(left+right)/2


x< K[mid]: right=mid-1




right

mid=(left+right)/2



mid

x< K[mid]: right=mid-1


right



mid

mid=(left+right)/2


K[mid]=x return (mid): Found x

Find with x=1

K key sequence


2

3

4

5

6

7

8

9


Index

-1

0

1

2

3

4

5

6

7

n

Start Left=0; Right=n-1


left







right


mid=(left+right)/2

mid

x< K[mid]: right=mid-1




right

mid=(left+right)/2



Mid

x< K[mid]: right=mid-1


right

Mid=(left+right)/2


mid

x< K[mid]: right=mid-1

rigth

right< left return (-1): x not found

Find with x=12

K key sequence


2

3

4

5

6

7

8

9


Index

-1

0

1

2

3

4

5

6

7

n


Start Left=0; Right=n-1


left







right


mid=(left+right)/2

mid






x> K[mid]: left=mid+1


left





mid=(left+right)/2

mid




x> K[mid]: left=mid+1

left



mid=(left+right)/2

mid



x> K[mid]: left=mid+1

left


mid=(left+right)/2

mid


x> K[mid]: left=mid+1

left

left >right return (-1): x not found



Comment:

We can easily see that the computational complexity of the sequential search algorithm is O(n) and it has also been proven that the computational complexity of the binary search algorithm is O(log 2 n). It is clear that binary search is more optimal than sequential search. However, binary search requires the key array to be sorted, so we also need to consider the computational complexity of the sorting algorithm, which is also a disadvantage of binary search.

QUESTIONS AND EXERCISES AT THE END OF CHAPTER 5


1) Write a program to do the following:

a. Write a function to randomly generate an integer sequence of about 100 numbers (including integers from 1 to 100.

b. Write a function to display a series of numbers on the screen.

c. Write a search function using a sequential search algorithm with x (a number) entered from the keyboard. If found, display the position of the element that matches x, otherwise display the message that it is not found.

d. Write a search function using the binary search algorithm with x (a number) entered from the keyboard. If found, display the position of the element that matches x, otherwise display the message that it is not found ( requires sorting the array of numbers in ascending order before performing the search ).

e. Write a menu function and a main function that allows you to select and perform tasks until you want to finish.

2) Write a program to do the following job:

a. Write a function to create an array containing a list of student names in a class, each student has 2 fields: middle name and first name.

b. Write a function to display a list of student names on the screen (each name on a line)

c. Write a search function using a sequential search algorithm with x (a student name) entered from the keyboard. If found, display the position of the element that matches x, otherwise display the message that it is not found.

d. Write a search function using the binary search algorithm with x (a student name) entered from the keyboard. If found, display the position of the element that matches x, otherwise display the message that it is not found (requires sorting in dictionary order of the student name key field before performing the search ).

e. Write a menu function and a main function that allows you to select and perform tasks until you want to finish.

CHAPTER 6 TREES

Target:

- Present the concept of trees and binary trees;

- Install trees on computers using array structures and linked list structures;

- Solve the problem of traversing a binary tree.


1. Concept of tree

1.1. Tree concept

A tree is a nonlinear structure. A tree is a finite set of nodes including a special node called the root. Between nodes there is a hierarchical relationship called “parent-child relationship”.



Figure 6.1: General tree

A tree can be defined recursively as follows:


A node is a tree. That node is also the root of that tree.

If n is a node and T 1 , T 2 ,....., T k are trees. With n 1 , n 2 ,...., n k being the roots, a new tree T will be created by making n the "parent" of nodes n 1 , n 2 ,...., n k . That is, in this new tree, n is the root and T 1 , T 2 ,..., T k are the children of the root, then n 1 , n 2 ,...., n k are children of node n.

For convenience, a tree with no nodes is allowed, which we call a null tree.



Figure 6.2: Definition of binary tree

Comment


Agree Privacy Policy *