Data Structures &

Algorithms

Week1

Contents
Textbook
Grade
Software

Textbook
C

& Data Structures

P. S. Deshpande, O. G. Kakde
CHARLES RIVER MEDIA, INC.
Hingham, Massachusetts

Grade
Midterm

test (Lab)
Final test (Lab)
Project (working on group)
Multiple choice test
How to Grade

Grade

Software: C/C++ edittor

BC++, TC++
C-Free is a professional C/C++ integrated
development environment (IDE) that support multicompilers. Use of this software, user can edit, build,
run and debug programs freely.
With C/C++ source parser included
Lightweight C/C++ development tool.
http://www.programarts.com/cfree_en/

C/C++ edittor: demo

Find

max of 3 numbers: a,b,c

Using scanf, printf (C standard)

Using cin, cout (Cpp)

CHAPTER 0: INTRODUTION
What

is Data Structures?

A data structure is defined by

(1)

the logical arrangement of data elements,

combined with
(2) the set of operations we need to access the
elements.

Atomic Variables
Atomic

variables can only store one value at

a time.
int num;
float s;
A value

stored in an atomic variable cannot

be subdivided.

What is Data Structures?

Example:library

is composed of elements
(books)
Accessing a particular
book requires knowledge
of the arrangement of the
books
Users access books only
through the
librarian
the logical arrangement of data elements,
combined with
the set of operations we need to access the
elements.

Basic Data Structures

Structures

include

linked lists
Stack, Queue
binary trees
and others

What is Algorithm?
Algorithm:

A computable set of steps to achieve a desired

result
Ralationship to Data Structure
Example:

Find an element
2
1
1

4
3

6
5

7
6

Sumary

Chapter 0: C LANGUAGE
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

ADDRESS
POINTERS
ARRAYS
ADDRESS OF EACH ELEMENT IN AN ARRAY
ACCESSING & MANIPULATING AN ARRAY USING
POINTERS
ANOTHER CASE OF MANIPULATING AN ARRAY USING
POINTERS
TWO-DIMENSIONAL ARRAY
POINTER ARRAYS
STRUCTURES
STRUCTURE POINTERS

Chapter 0: C LANGUAGE
1.

ADDRESS
For every variable there are two attributes:
address and value
In memory with address 3: value: 45.
In memory with address 2: value "Dave"

cout << "Value of 'y' is: " << y << "\n";

cout << "Address of 'y' is: " << &y << "\n\n";

Chapter 0: C LANGUAGE
2. POINTERS
1.
2.

is a variable whose value is also an address.

A pointer to an integer is a variable that can
store the address of that integer

ia: value of variable

&ia: address of ia
*ia means you are printing the value at the
location specified by ia

Chapter 0: C LANGUAGE
int i;
//A
int * ia;
//B
cout<<"The address of i "<< &i << " value="<<i <<endl;
cout<<"The address of ia " << &ia << " value = " << ia<< endl;
i = 10;
//C
ia = &i; //D
cout<<"after assigning value:"<<endl;
cout<<"The address of i "<< &i << " value="<<i <<endl;
cout<<"The address of ia " << &ia << " value = " << ia<< " point to: "<< *ia;

Chapter 0: C LANGUAGE
Points to Remember
Pointers give a facility to access the value of
a variable indirectly.
You can define a pointer by including a *
before the name of the variable.
You can get the address where a variable is
stored by using &.

Chapter 0: C LANGUAGE
3. ARRAYS
1.
2.
3.

An array is a data structure

used to process multiple elements with the same data
type when a number of such elements are known.
An array is a composite data structure; that means it
had to be constructed from basic data types such as
array integers.
1.
2.

int a[5];
for(int i = 0;i<5;i++)
1.

{a[i]=i; }

Chapter 0: C LANGUAGE
4. ADDRESS OF EACH ELEMENT IN AN
ARRAY
Each element of the array has a memory
address.
void printdetail(int a[])
{
for(int i = 0;i<5;i++)
{
cout<< "value in array << a[i] << at address: << &a[i]);
}

Chapter 0: C LANGUAGE
5. ACCESSING & MANIPULATING AN
ARRAY USING POINTERS

You can access an array element by using a pointer.

If an array stores integers->use a pointer to integer to
access array elements.

Chapter 0: C LANGUAGE
6. ANOTHER CASE OF MANIPULATING AN
ARRAY USING POINTERS
The array limit is a pointer constant : cannot
change its value in the program.

int a[5];

int *b;

a=b; //error
b=a; //OK

It works correctly even using

a++ ???

Chapter 0: C LANGUAGE
7. TWO-DIMENSIONAL ARRAY
int a[3][2];

Chapter 0: C LANGUAGE
8. POINTER ARRAYS

You can define a pointer array (similarly to an array of

integers).
In the pointer array, the array elements store the
pointer that points to integer values.

Chapter 0: C LANGUAGE
9. STRUCTURES

Structures are used when

you want to process data of
multiple data types
But you still want to refer to
the data as a single entity
Access data:
structurename.membernam
e

Chapter 1: C LANGUAGE
10. STRUCTURE POINTERS
Process the structure using a structure pointer

CHAPTER 2: FUNCTION & RECURSION

1. FUNCTION
2. THE CONCEPT OF STACK
3. THE SEQUENCE OF EXECUTION DURING A
FUNCTION CALL
4. PARAMETER PASSING
5. CALL BY REFERENCE
6. RESOLVING VARIABLE REFERENCES
7. RECURSION
8. STACK OVERHEADS IN RECURSION
9. WRITING A RECURSIVE FUNCTION
10. TYPES OF RECURSION

CHAPTER 2: FUNCTION & RECURSION

1.

FUNCTION
provide modularity to the software
divide complex tasks into small manageable tasks
avoid duplication of work

CHAPTER 2: FUNCTION & RECURSION

2.

THE CONCEPT OF STACK

A stack is memory in which values are stored and
retrieved in "last in first out" manner by using
operations called push and pop.

CHAPTER 2: FUNCTION & RECURSION

3. THE SEQUENCE OF EXECUTION DURING A

FUNCTION CALL

When the function is called, the current execution is

temporarily stopped and the control goes to the called
function. After the call, the execution resumes from the point
at which the execution is stopped.
To get the exact point at which execution is resumed, the
address of the next instruction is stored in the stack. When
the function call completes, the address at the top of the
stack is taken.

CHAPTER 2: FUNCTION & RECURSION

3. THE SEQUENCE OF EXECUTION

DURING A FUNCTION CALL

Functions or sub-programs are implemented

using a stack.
When a function is called, the address of the next
instruction is pushed into the stack.
When the function is finished, the address for
execution is taken by using the pop operation.

CHAPTER 2: FUNCTION & RECURSION

3.

THE SEQUENCE OF
EXECUTION DURING A
FUNCTION CALL
Result:?

CHAPTER 2: FUNCTION & RECURSION

4.

PARAMETER * REFERENCE PASSING

passing by value
the

value before and after the call remains the same

passing by reference
changed

value after the function completes

CHAPTER 2: FUNCTION & RECURSION

6.

RESOLVING VARIABLE REFERENCES

When a variable can

be resolved by using
multiple references,
the local definition is
given more preference

CHAPTER 2: FUNCTION & RECURSION

7.

RECURSION
A method of
programming
whereby a function
directly or indirectly
calls itself
Problems: stop
recursion?

CHAPTER 2: FUNCTION & RECURSION

7.

RECURSION

CHAPTER 2: FUNCTION & RECURSION

7.

RECURSION:
Hanoi tower

CHAPTER 2: FUNCTION & RECURSION

7.

RECURSION

CHAPTER 2: FUNCTION & RECURSION

8.

STACK OVERHEADS IN RECURSION

two important results: the depth of recursion and
the stack overheads in recursion

CHAPTER 2: FUNCTION & RECURSION

9. WRITING A RECURSIVE FUNCTION

Recursion enables us to write a program in a

natural way. The speed of a recursive program is
slower because of stack overheads.
In a recursive program you have to specify
recursive conditions, terminating conditions, and
recursive expressions.

CHAPTER 2: FUNCTION & RECURSION

10. TYPES

OF RECURSION

LINEAR RECURSION
TAIL RECURSION
BINARY RECURSION
EXPONENTIAL RECURSION
NESTED RECURSION
MUTUAL RECURSION

CHAPTER 2: FUNCTION & RECURSION

10. TYPES

OF RECURSION

LINEAR RECURSION
only

makes a single call to itself each time the

function runs

CHAPTER 2: FUNCTION & RECURSION

10. TYPES

OF RECURSION

TAIL RECURSION
Tail

recursion is a form of linear recursion.

In tail recursion, the recursive call is the last thing
the function does. Often, the value of the recursive
call is returned.

CHAPTER 2: FUNCTION & RECURSION

10. TYPES

OF RECURSION

BINARY RECURSION
Some

recursive functions don't just have one call to

themself, they have two (or more).

CHAPTER 2: FUNCTION & RECURSION

10. TYPES

OF RECURSION

EXPONENTIAL RECURSION
An

exponential recursive function is one that, if you

were to draw out a representation of all the function
calls, would have an exponential number of calls in
relation to the size of the data set
(exponential meaning if there were n elements, there
would be O(an) function calls where a is a positive
number)

CHAPTER 2: FUNCTION & RECURSION

10. TYPES

OF RECURSION

EXPONENTIAL RECURSION

CHAPTER 2: FUNCTION & RECURSION

10. TYPES

OF RECURSION

NESTED RECURSION
In

nested recursion, one of the arguments to the

recursive function is the recursive function itself
These functions tend to grow extremely fast.

CHAPTER 2: FUNCTION & RECURSION

10. TYPES

OF RECURSION

MUTUAL RECURSION
A recursive

function doesn't necessarily need to call

itself.
Some recursive functions work in pairs or even larger
groups. For example, function A calls function B which
calls function C which in turn calls function A.

CHAPTER 2: FUNCTION & RECURSION

10. TYPES

OF RECURSION

MUTUAL RECURSION

Exercises 1: Recursion

Exercises 2: Recursion
Convert

number from H10->H2

7
1

2
3
1

2
1

Week3: Recursion Excercises (1)

E1.

(44/174) Write a program to compute: S

= 1 + 2 + 3 + n using recursion.

Week3: Recursion Excercises (2-3)

E3(a).

Write a program to print a revert

number Example: input n=12345. Print out:
54321.

E3(b).

Write a program to print this number

Example: input n=12345. Print out:
12345.

Week3: Recursion Excercises (4)

E4.

Write a recursion function to find the sum

of every number in a int number. Example:
n=1980 => Sum=1+9+8+0=18.

Week3: Recursion Excercises (5)

E4.

Write a recursion function to calculate:

S=a[0]+a[1]+a[n-1]
A:

array of integer numbers

Week3: Recursion Excercises (6)

E4.

Write a recursion function to find an

element in an array (using linear algorithm)

Week3: Recursion Excercises (7)

Print

triangle
c

Week3: Recursion Excercises (8)

Convert

number from H10->H2

7
1

2
3
1

2
1

Week3: Recursion Excercises (9)

Minesweeper

Week 3
CHAPTER 3: SEARCHING TECHNIQUES
1. LINEAR (SEQUENTIAL) SEARCH
2. BINARY SEARCH
3. COMPLEXITY OF ALGORITHMS

SEARCHING TECHNIQUES
To finding

out whether a particular element is

present in the list.
2 methods: linear search, binary search
The method we use depends on how the
elements of the list are organized

unordered list:
linear

search: simple, slow

an ordered list
binary

search or linear search: complex, faster

1. LINEAR (SEQUENTIAL) SEARCH

How?

Proceeds by sequentially comparing the key with

elements in the list
Continues until either we find a match or the end
of the list is encountered.
If we find a match, the search terminates
successfully by returning the index of the element
If the end of the list is encountered without a
match, the search terminates unsuccessfully.

1. LINEAR (SEQUENTIAL) SEARCH

void lsearch(int list[],int n,int element)
{ int i, flag = 0;
for(i=0;i<n;i++)
if( list[i] == element)
{ cout<<found at position<<i);
flag =1;
break; }
if( flag == 0)
cout<< not found;
}

flag: what for???

1. LINEAR (SEQUENTIAL) SEARCH

int lsearch(int list[],int n,int element)
{ int i, find= -1;
for(i=0;i<n;i++)
Another way using flag
if( list[i] == element)
{find =i;
break;}
return find;
}
average time: O(n)

2.
List

BINARY SEARCH

must be a sorted one

We compare the element with the element
placed approximately in the middle of the list
If a match is found, the search terminates
successfully.
Otherwise, we continue the search for the
key in a similar manner either in the upper
half or the lower half.

Baba?

Eat?

void bsearch(int list[],int n,int element)

{
int l,u,m, flag = 0;
l = 0; u = n-1;
while(l <= u)
{ m = (l+u)/2;
if( list[m] == element)
{cout<<"found:"<<m;
flag =1;
break;}
else
if(list[m] < element)
l = m+1;
else
u = m-1;
}
if( flag == 0)
cout<<"not found";
}

average time: O(log2n)

BINARY SEARCH: Recursion

int Search (int list[], int key, int left, int right)
{
if (left <= right) {
int middle = (left + right)/2;
if (key == list[middle])
return middle;
else if (key < list[middle])
return Search(list,key,left,middle-1);
else return Search(list,key,middle+1,right);
}
return -1;
}

3. COMPLEXITY OF ALGORITHMS

In Computer Science, it is important to measure the

quality of algorithms, especially the specific amount
of a certain resource an algorithm needs
Resources: time or memory storage (PDA?)
Different algorithms do same task with a different set
of instructions in less or more time, space or effort
than other.
The analysis has a strong mathematical background.
The most common way of qualifying an algorithm is
the Asymptotic Notation, also called Big O.

3. COMPLEXITY OF ALGORITHMS

It is generally written as

Polynomial time algorithms,

Sub-linear time algorithms

O(1) --- Constant time --- the time does not change in response to
the size of the problem.
O(n) --- Linear time --- the time grows linearly with the size (n) of
the problem.
O(n2) --- Quadratic time --- the time grows quadratically with the
size (n) of the problem. In big O notation, all polynomials with the
same degree are equivalent, so O(3n2 + 3n + 7) = O(n2)
O(logn) -- Logarithmic time

Super-polynomial time algorithms

O(n!)
O(2n)

3. COMPLEXITY OF ALGORITHMS
Example1:

complexity of an algorithm

void f ( int a[], int n )

{
int i;
cout<< "N = << n;
for ( i = 0; i < n; i++ )
cout<<a[i];
printf ( "n" );
}

2 * O(1)? + O(N)

O(N)
?

3. COMPLEXITY OF ALGORITHMS
Example2:

complexity of an algorithm

void f ( int a[], int n )

{ int i;
cout<< "N = << n;
for ( i = 0; i < n; i++ )
for (int j=0;j<n;j++)
cout<<a[i]<<a[j];
for ( i = 0; i < n; i++ )
cout<<a[i];
printf ( "n" );
}

2
2 * O(1) + O(N)+O(N
?
)

O(N2)
?

3. COMPLEXITY OF ALGORITHMS
Linear

Search

O(n).

Binary

Search

O(log2 N)

Week4: (Chapter 4)
20

test

Write a small program

Input

the number of array

Input array of integer
Display array
Input a value. Using linear search to find position of first
match item in array
Using 3 function: enterarray, displayarray,linearfind

Week4: (Chapter 4)
SORTING TECHNIQUES
Why?

Do binary search
Doing certain operations faster

SORTING

Week4: (Chapter 4)
SORTING TECHNIQUES

Given a set (container) of n elements

E.g. array, set of words, etc.

Suppose there is an order relation that can be set

across the elements
Goal Arrange the elements in ascending order

Start 1 23 2 56 9 8 10 100
End 1 2 8 9 10 23 56 100

Week4: (Chapter 4)
SORTING TECHNIQUES
Bubble

sort, Insertion sort, Selection sort,

Quick sort, Heap sort, Merge sort, Exchange
sort
Focus on

Bubble sort
Insertion sort
Selection sort
Exchange sort
Quick sort

Week4: (Chapter 4)
SORTING TECHNIQUES

Average

Worst

Bubblesort
O(n2)
Exchangesort

O(n2)

Insertionsort

O(n2)

O(n2)

Selectionsort O(n2)

O(n2)

Quicksort

O(n2)

O(nlogn)

1.Bubble sort: idea

arrange

the elements of the list by forming

pairs of adjacent elements.
The pair of the ith and (i+1)th element.
If the order is ascending, we interchange the
elements of the pair
This will bring the highest value from among
the remaining (n1) values to the (n1)th
position.

1.Bubble sort: idea

1.Bubble sort: idea

Why it is called Bubble?
3

compare3and7;7is>3soadvance

compare7and5,7>5soswapthem

compare7and2,7>4soswapthem

compare7and4,7>4soswapthem

Endofpass1;noticethat7isintherightplace

2.Bubble sort: idea

Simplest

sorting algorithm

Idea:

1. Set flag = false

2. Traverse the array and compare pairs of two
elements
If E1 E2 - OK
1.2 If E1 > E2 then Switch(E1, E2) and set flag = true
1.1

3. If flag = true goto 1.

What

happens?

1.Bubble sort:algorithm idea

void bubbleSort (Array S, length n) {
boolean isSorted = false;
while(!isSorted)
{
isSorted = true;
for(i = 0; i<n; i++)
if(S[i] > S[i+1])
{
swap(S[i],S[i+1];)
isSorted = false;
}
}

1.Bubble sort: implement

void bsort(int list[], int n)
{
int count,j;
for(count=0;count<n-1;count++)
for(j=0;j<n-1-count;j++)
if(list[j] > list[j+1])
swap(list[j],list[j+1]);
}

DEMO

2. Exchange Sorting
Method

: make n-1 passes across the data,

on each pass compare adjacent items,
swapping as necessary (n-1 compares)
O(n2)

2. Exchange Sorting
void Exchange_sort(int arr[], int n)
{
int i,j;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(arr[i] > arr[j])
swap(arr[i],arr[j]);
}

DEMO

2. Exchange Sorting
Notes:

on each successive pass, do one less compare,

because the last item from that pass is in place
if you ever make a pass in which no swap occurs,
the sort is complete
There are some algorithms to improve
performance but Big O will remain O(n2)

3. Insertion Sort
Strategy:

divide the collection into two lists,

one listed with one element (sorted) and the
other with the remaining elements.
On successive passes take an item from the
unsorted list and insert it into the sorted list
so the the sorted list is always sorted
Do this until the unsorted list is empty

3. Insertion Sort
sorted

unsorted

sorted
3

unsorted
7

unsorted
5

unsorted
5

takenextitemfromtheunsortedlist(2)
andinsertintothesortedlist

sorted
2

takenextitemfromtheunsortedlist(5)and
insertintothesortedlist

sorted
2

takeanitemfromtheunsortedlist(7)and
insertintothesortedlist

unsorted

sorted
3

takenextitemfromtheunsortedlist(4)
andinsertintothesortedlist

3. Insertion Sort
void insertionSort(int arr[], int n){
int j, key;
for(int i = 1; i < n; i++){
key = arr[i];
j = i - 1;
while(j >= 0 && arr[j] > key)
{ arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

3. Insertion Sort
Note

that each insertion could be O(n-1) and

there are n-1 insertions being done therefore
Big O is O(n2)
This is very much like building an ordered
linked list except there is more data
movement

4. Selection Sort
Strategy:

make a pass across the data

looking for the largest item, swap the largest
with the last item in the array.
On successive passes (n-1) assume the
array is one smaller (the last item is in the
correct place) and repeat previous step

biggest

4. Selection Sort

last

biggest last

biggest last

4. Selection Sort
void selection_sort(int arr[], int n)
{int i, j, min;
for (i = 0; i < n - 1; i++)
{
min = i;
for (j = i+1; j < n; j++)
{ if (list[j] < list[min]) min = j; }
swap(arr[i],arr[min]);
}
}

4. Selection Sort
Notice

that in selection sort, there is the least

possible data movement
There are still n-1 compares on sublists that
become one item smaller on each pass so,
Big O is still O(n2)
This method has the best overall
performance of the O(n2) algorithms because
of the limited amount of data movement

5. Quick Sort

This sorting method by far outshines all of the others

for flat out speed
Big O is log2n
there are problems, worst case performance is when
data is already in sorted order or is almost in sorted
order (well analyze this separately)
and there are solutions to the problems
and there is an improvement to make it faster still

5. Quick Sort
Sorting

algorithms that rely on the DIVIDE

AND CONQUER paradigm

One of the most widely used paradigms

Divide a problem into smaller sub problems, solve
the sub problems, and combine the solutions
Learned from real life ways of solving problems

5. Quick Sort
Another divide-and-conquer sorting algorihm
To understand quick-sort, lets look at a high-level description of
the algorithm
1) Divide : If the sequence S has 2 or more elements, select an
element x from S to be your pivot. Any arbitrary element, like
the last, will do. Remove all the elements of S and divide them
into 3 sequences:

L, holds Ss elements less than x

E, holds Ss elements equal to x
G, holds Ss elements greater than x

2) Recurse: Recursively sort L and G

3) Conquer: Finally, to put elements back into S in order, first
inserts the elements of L, then those of E, and those of G.

5. Quick Sort: idea

1) Select: pick an element

2) Divide: rearrange elements so

that x goes to its final position E

3) Recurse and Conquer:

recursively sort

5. Quick Sort: idea

Quick Sort
Picktheleftmostelementasthepivot(23).Now,starttwocursors(oneateitherend)goingtowardsthe
middleandswapvaluesthatare>pivot(foundwithleftcursor)withvalues<pivot(foundwithrightcursor)

23

17

12

19

24

43

34

11

33

14

26

27

swap
23

17

12

19

43

34

11

33

14

26

24

27

33

43

26

24

27

34

33

43

26

24

27

swap
23

17

12

19

14

34

11
swap

23

17

12

19

14

11

swap
Finally,swapthepivotandthevaluewherethecursorspassedeachother
11

17

12

19

14

23

34

33

43

Note:23isnowintherightplaceandeverythingtoitsleftis<23
andeverythingtoitsrightis>23

26

24

27

Quick Sort
Now,repeattheprocessfortherightpartition

11

17

12

19

14

14

12

14

17

14

17

23

34

33

43

26

24

27

swap
11

17

12

19
swap

11

19

swap
11

19

12

swap
8

11

19

12

14

17

Note:the11isnowintherightplace,andtheleftpartitionisall<pivotandtherightpartitionisall>pivot

Quick Sort (worst case)

If the data is already sorted watch what happens to the partitions

11

12

14

17

19

23

24

26

27

33

34

43

19

23

24

26

27

33

34

43

Thereisnothingtoswap
4

11

12

14

17

Again,nothingtoswap..
Thepartitionsarealwaysthemaximumsizeandtheperformance
degradestoO(n2)

Quick
Sort
void quickSort(int Arr[], int lower, int upper)
{
int x = Arr[(lower + upper) / 2];
int i = lower; int j = upper;
do{
while(Arr[i] < x) i ++;
while (Arr[j] > x) j --;
if (i <= j)
{
swap(Arr[i], Arr[j]);
i ++; j --; }
}while(i <= j);
if (j > lower)
quickSort(Arr, lower, j);
if (i < upper)
quickSort(Arr, i, upper);
}

Kim tra 15

Vit chng trnh han chnh

Menu cha 4 chn la

1. Nhp v kim tra 1 s X c phi l s nguyn t (s X :

nhp vo)
2. Xut ra cc s nguyn t < n (n nhp vo)
3. Xut ra n s nguyn t u tin (n nhp vo)
4. That chng trnh

S dng hm hp l.
Ch : li syntax

Common logic error

Ending

loop with ;

int sum = 0;
for (i=1;i<=n;i++)
sum+=i;
cout <<"Sum="<<sum;
int sum = 0;

for (i=1;i<=n;i++)
sum+=i;
cout <<"Sum="<<sum;

Common logic error

int i, flag = 0;
for(i=0;i<n;i++)
if( arr[i] == element)
{ flag =1;
cout<<"tim thay o vi tri: "<<i;
break;
}
if (flag==0)
cout<<"khong tim thay";

int i, flag = 0;
for(i=0;i<n;i++)
if( arr[i] == element)
{ flag =1;
cout<<"tim thay o vi tri: "<<i;
break;
}
else
cout<<"khong tim thay";

Week 5: STACKS AND QUEUES

STACKS:

concept
QUEUES : concept
STACKS,QUEUES : implement

Using array
Using Linked List (next chapter)

1.Stack
LIFO

(last in first out)

1.Stack
Managing

Top element

1.Stack: implement using array

#define MAX 10
void main()
{
int stack[MAX];
int top = -1;
push(stack,top, 10 );
pop(stack,top,value);
int value;
cout<<value;
}

1.Stack: implement using array

void push(int stack[], int &top, int value)
{
if(top < MAX )
{
top = top + 1;
stack[top] = value;
}
else
cout<<"The stack is full";
}

1.Stack: implement using array

void pop(int stack[], int &top, int &value)
{
if(top >= 0 )
{
value = stack[top];
top = top - 1;
}
else
cout<<"The stack is empty ";
}

2.QUEUE
FIFO

(first in first out)

2.QUEUE: implement using array

A circular queue

2.QUEUE: implement using array

#define MAX 10
void main()
{
int queue[MAX];
int bottom,top,count=0;
bottom=top=-1;
enqueue(queue,count,top, 100
);
int value;
dequeue(queue,count,bottom,top,value);
}

2.QUEUE: implement using array

void enqueue(int queue[],int &count, int &top, int value)
{
if(count< MAX)
{
count++;
top= (top +1)%MAX;
queue[top] = value;
}
else
cout<<"The queue is full";
}

2.QUEUE: implement using array

void dequeue(int queue[], int &count,int &bottom,int top, int
&value)
{
if(count==0)
{
cout<<"The queue is empty";
exit(0);
}
bottom = (bottom + 1)%MAX;
value = queue[bottom];
count--;
}

3. Application of stack, queue

Stack:

Expression evaluation

a*(bc)/d => abc*d/

Queue:

priority queues

Exercise:
Implement:

5 sort algorithms
Implement stack, queue using array

Menu with 4 choices

Add,

remove, display, exit

Week 6: V vic kim tra gia k

Phn

nhm thc hnh lm 2 ca

im di 5 th
Ni dung

Week 6: n tp function
On

return value

Void Functions
Return Function
Example:

On

void display(); int max(int a,int b);

Parameters

value parameters
reference parameters
Exmple:

void swap(int &a, int &b); int BinhPhuong(int n);

Week 6: n tp function
Nothing

return

void

Week 6: n tp function
Return

1 value

int

return

Week 6: n tp function
Return

many value

void

int

reference

parameters

On natural way
return

Week 6: n tp function
Example

??? FindMax(3 numbers ???)

??? FindMin(3 numbers ???)
??? TinhChuVi_ChuNhat (????)
??? TinhChuVi__DienTich_ChuNhat (????)
??? GiaiPT_bac_1 (???)
??? GiaiPT_bac_2 (???)
??? Sum_of_array(???)
??? FindElement_in_array(???)

Week 6: Linked List

THE

CONCEPT OF THE LINKED LIST

SINGLE LINKED LIST
DOUBLE LINKED LIST
CIRCULAR LINKED LIST

THE CONCEPT OF THE LINKED LIST

the

size requirement need not be known at

compile time
A linked list is a data structure that is used to
model such a dynamic list of data items, so
the study of the linked lists as one of the data
structures is important.

Array and LINKED LIST

ARRAY

sequential mapping, elements are fixed distance apart

makes insertion or deletion at any arbitrary position in an
array a costly operation

Linked List

not necessary that the elements be at a fixed distance apart

an element is required to be linked with a previous element
of the list
done by storing the address of the next element

Array and LINKED LIST

Array: max length=7
0

Get element by order number

Linked List: max length=18

X 10 11 X 12 13 14 X 15 16 17 18

Type of Linked List

1

data

data

Link

Link

data

data

Link

Link

NULL

Link

Link

data

data

Link

Link

data
LinkLink
data

data

LinkLink

LinkLink

4 things when building Linked List

1. Structure

2. The way to make link between elements

Data element
Link field element
First, last, middle element

3. How many node to take all list elements, how to take all
list
4. Basic operations:

Insert new element (every position)

Delete (every position)
Find
Notes: Check value change in step 3

2.Singly Linked List

data

Link

Data element
Link field element

2. The way to make link between elements

data

1. Structure

Link

First, last, middle element

3. How many node to take all list elements , how

to take all list
4. Basic operations:

Insert new element (every location)

Delete (every position)
Find

NULL

2.Singly Linked List

1.

Structure
struct Node
{
int data;
Node *link;

2.Singly Linked List

1.

Structure: how to use one node

Node *b;
Node a;
b=new Node;

a.data=10;
a.link=NULL;
cout<<a.data;

b->data=20;
b->link=NULL;
cout<<b->data;
delete b;

Compare??? What is the different? Delele and change address

2.Singly Linked List

2.

The way to make link between elements

First, last, middle element

data Link

Head

data Link

Middle

data Link

data Link

Last

NULL

2.Singly Linked List

3.

How many node to take all list

elements, how to take all list

data Link

data Link

data Link

data Link

pTail

NULL

Why
+from pHead, can we list all items?

pHead

+from pHead, can we do everything with list:

insert new, delete?
+Do we need pTail?

2.Singly Linked List

3.

How many node to take all list

elements, how to take all list

data Link

data Link

data Link

pTail

data Link

How to store pHead, pTail

pHead

Type 1: Node *pHead=NULL, *pTail=NULL;

Type 2: typedef struct Node *List;
List pHead, pTail;

NULL

2.Singly Linked List

4.

Basic operations:
data Link

data Link

data Link

NULL

Remove node
Insert node
creating new node

2.Singly Linked List

4.

Basic operations: creating new node

Node * createNewNode(int X)
{
Node *p=new Node;
If (p!=NULL)
{
p->data=X;
p->link=NULL;
}
return p;

p
data Link

NULL

2.Singly Linked List: using Phead only

void addnodeatFirst(node *newnode)
{
Insert
if (pHead==NULL)
{
pHead =newnode;
}
else
{
newnode->next=pHead;
pHead =newnode;
}
}

Node at First

2.Singly Linked List: using Phead only

void displaylist()
{
node *temp=h;
while (temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
}

Seek Nodes

2.Singly Linked List: using Phead only

void RemoveNodeatFirst()
{
if (pHead!=NULL)
{
node *t= pHead;
pHead = pHead ->next;
delete t;
}
}

Remove Node at
First

2.Singly Linked List: using Phead only

node *find(int key)
{
node *temp=h;
while (temp!=NULL && temp->data!=key)
temp=temp->next;
return temp;
}

Find Node

2.Singly Linked List: using Phead only

void removeatlast()
{
node *t=h;
node *truoc=t;
while (t->next!=NULL)
{
truoc=t;
t=t->next;
}
truoc->next=NULL;
delete t;
}

Remove Node at
Last

2.Singly Linked List: using Phead only

void insertatlast(node *newnode)
{
node *t=h;
while (t->next!=NULL)
t=t->next;
t->next=newnode;
}

Insert Node at
Last

2.Singly Linked List:using pHead &

pTail
4.

Basic operations: Insert new node

pHead
data Link

pTail
data Link

data Link

data Link

NULL

2.Singly Linked List

4.

Basic operations: Insert new node at First

void Insert_First (node *newnode)

{ if ( pTail == NULL )
{
pHead=pTail =newnode ;
}
else
{
newnode->next=pHead ;
pHead=newnode;
}
}

2.Singly Linked List

4.

Basic operations: Insert new node at Last

void Insert_Last (node *newnode)

{ if ( pTail == NULL )
{
pHead=pTail =newnode ;
}
else
{
pTail>next=newnode ;
pTail=newnode;
}
}

2.Singly Linked List

4.

Basic operations: Insert new node after

void Insert_after (node *newnode,node *p)
node
{
If (p!=pTail)
{
newnode->next=p>next;
p->next=newnode;
}
else
insert_Last (newnode);
}

2.Singly Linked List

4.

Basic operations: remove node at First

void removeNodeAtFirst ()
{
If (pHead!=NULL)
{
Node *temp=pHead;
pHead = pHead >next;
delete temp;
}
}

2.Singly Linked List

4.

Basic operations: remove node after

void removeNodeAfter (node *p)

{
Node *temp=p>next;
p->next=p->next->next;
delete temp;
}

2.Singly Linked List

4.

Basic operations: remove node at Last

void removeNodeatLast ()
{
???
}

2.Singly Linked List

4.

Basic operations: Seek all nodes

Void Display()
{
node *p=pHead;
while (p!=NULL)
{
cout<<p->data<< ;
p=p->next;
}
}

2.Singly Linked List

4.

Basic operations: count number of nodes

int Count ()
{
int count=0;
node *p=pHead;
while (p!=NULL)
{
count+=1;
p=p->next;
}
return count;
}

2.Singly Linked List

4.

Basic operations: Remove List

Remove pHead node

Do until pHead is NULL

2.Singly Linked List: Demo

Write a program for buiding single linked list: using pHead only

Display menu

Add one node at first

Add one node at last
Add many node at first
Add many node at last
Select and display n(th) node
Find one node
Add one node after select node
Display node count
Display List
Remove one node
Remove List
Get sum of all nodes

Week 7
Find

node
Single linked list: pHead and pTail
Circular single linked list
Double Linked List

Find Node
Using

While
Using Loop

Find Node: using while loop

Node* temp; //Node *temp=new Node();???
temp=pHead;
while (temp->data!=Xvalue)
Exactly
temp=temp->next;
=========================================
Node* temp; //Node *temp=new Node();???
temp=pHead;
while (temp!=NULL && temp->data!=Xvalue)
temp=temp->next;
May be not found

Find Node: using for loop

for (Node* temp=pHead;temp->data!=Xvalue; temp=temp->next)

3.Singly Linked List: pHead and pTail

Same

to manage list with pHead

Take care: cases change pTail

Add node
Remove Node

3.Singly Linked List: pHead and pTail

When

pTail is changed?

Insert new node at first

pHead =

pTail=NULL
How to check ?

pHead= pTail
data Link

pHead
data Link

pTail
data Link

3.Singly Linked List: pHead and pTail

When

pTail is changed?

Insert new node at Last

pHead =

pTail=NULL
How to check ?

pHead= pTail
data Link

pHead
data Link

pTail
data Link

3.Singly Linked List: pHead and pTail

When

pTail is changed?

Insert new node after one node

pHead =

pTail=NULL
How to check ?

pHead= pTail
data Link

pHead
data Link

pTail
data Link

data Link

3.Singly Linked List: pHead and pTail

When

pTail is changed?

Remove node
pHead =

pTail=NULL

pHead= pTail

How to check ?

data Link

pHead
data Link

pTail
data Link

data Link

3.Singly Linked List: pHead and pTail

Example:

Write function to insert at last

Single linked list with pHead and pTail

4. Circular single linked list

Circular

Last node point to first node

Draw like Circle

When

using Circular single linked list

Every node in list had the same position

Neednt Head, Tail

4. Circular single linked list

Control

Circular single linked list: Insert node

pHead =NULL
pHead

How to check ?

data Link

pHead
data Link

data Link

data Link

4. Circular single linked list

Control

steps

Circular single linked list: Insert node

pHead
data Link

data Link

data Link

data Link

data Link

data Link

data Link

data Link

data Link
data Link

data Link

data Link

4. Circular single linked list

Control

Circular single linked list: Remove

nodepHead =NULL
pHead

How to check ?

data Link

pHead
data Link

data Link

data Link

4. Circular single linked list

Example:

Write function to remove a node

Circular single linked list with pHead and pTail

4. Double Linked List

Struct Node
{
Int data;
Node *next;
Node * pre;

};

4. Double Linked List

Insert

new node

First, Last, after node

Remove

node

First,Last, at one middle node

4. Double Linked List

Insert

new node: after one Node First steps

data

data

data
data

data

data

data
data

data

data

data
data

4. Double Linked List

Remove
data

node: steps
data

data

data

data

data

data

data

data

data

data

data

4. Double Linked List

Example

Write function to remove first node (pHead)

Write function to insert a node after another node

Week 8
Exercises
Review: File
Review: String
Excercises

Review C/C++ programming

1.

Working with string

2. Working with file: read/write file
3. Exercise 6

1. String: structure

String

is array of char
Ending with null char \0 (size +1)
Example: store 10 chars:
char

str[11];

Example: string const. C/C++ add \0

automayically

1. String: declare

Declare

string

Using array of chars

char

str[] = {H,e,l,l,o,\0}; //declare with null

char str[] = Hello; //neednt null

Using char pointer

char

*str = Hello;

1. String: input
char

*gets(char *s);

Read every char

Until receive Enter
Adding Automatically \0

cin>>s;

1. String: output
int

puts(const char *s);

cout<<s;

1. String: Problem with buffer?

Keyboard

buffer

char szKey[] = "aaa";

char s[10];
do {
cout<<"doan lai di?";
gets(s);
} while (strcmp (szKey,s) != 0);
puts ("OK. corect");

If

user input: aaaaaaaaaaaaa???

1. String: functions
#include

<string.h>
strcpy(s1, s2)
strcat(s1, s2)
strlen(s1)
strcmp(s1, s2) -> (-1,0,1)
strchr(s1, ch)
strstr(s1, s2)

char s1[80], s2[80];

cout << "Input the first string: :";
gets(s1);
1.
String:
function
examples
cout << "Input the second string: ";
gets(s2);
cout << "Length of s1= " << strlen(s1);
cout << "Length of s2= " << strlen(s2);
if(!strcmp(s1, s2))
cout << "These strings are equal\n";
strcat(s1, s2);
cout << "s1 + s2: " << s1 << endl;;
strcpy(s1, "This is a test.\n");
cout << s1;
if(strchr(s1, 'e')) cout << "e is in " << s1;
if(strstr(s2, "hi")) cout << "found hi in " <<s2;

2. File: Creating a new file

#include
FILE

<io.h>

*fp;
fp=fopen(d:\\test.txt", "wb"))
fwrite(&Address, sizeof(TYPE), count, fp);
fclose(fp);

2.File: Creating a new file

int Arr[3]

Arr

Fwrite(Arr, sizeof(int), 1, fp);

fwrite(Arr, sizeof(Arr), 1, fp);

for (i=0;i<=3;i++)
Fwrite(&Arr[i], sizeof(int), 1, fp);

2. File: Reading a file

#include <io.h>
FILE *fp;
fp=fopen(d:\\test.txt", rb"))
while (fwrite(&Address, sizeof(TYPE), count, fp))
{

}
fclose(fp);

3.Excercises
Exercise

Week 9: Tree
1.

THE CONCEPT OF TREES

2. BINARY TREE AND REPRESENTATION

3.

BINARY TREE TRAVERSAL

4. BINARY SEARCH TREE

2
1

6
9

1. THE CONCEPT OF TREES

A tree is a set of one or more nodes T:

there is a specially designated node called a

root
The remaining nodes are partitioned into n
disjointed set of nodes T1, T2,,Tn, each of
which is a tree.

1. THE CONCEPT OF TREES

Example

1. THE CONCEPT OF TREES

Its

not a tree

Tree

1. THE CONCEPT OF TREES: Some

terminology

Root
Child (left,right)
Parent
Leaf node
Subtree
Ancestor of a node
Descendant of a node

1. THE CONCEPT OF TREES

Degree of a Node of a Tree

Degree of a Tree

The degree of a node of a tree is the number of subtrees

having this node as a root.
The degree of a tree is defined as the maximum of degree
of the nodes of the tree

Level of a Node

level of the root node as 1, and incrementing it by 1 as we

move from the root towards the subtrees.

2. BINARY TREE AND REPRESENTATION

BINARY TREE

no node can have a degree of more than 2.

The maximum number of nodes at level i will be

2i1

If k is the depth of the tree then the maximum

number of nodes that the tree can have is

2k 1 = 2k1 + 2k2 + + 20

2. BINARY TREE AND REPRESENTATION

BINARY TREE

A full binary tree is a binary of depth k having 2k

1 nodes.

If it has < 2k 1, it is not a full binary tree

What is the height h of a full tree

with N nodes?

2 1 N
h

2 N 1
h

The

h log( N 1) O (log N )

max height of a tree with N nodes is N

(same as a linked list)
The min height of a tree with N nodes is
log(N+1)

2. BINARY TREE AND REPRESENTATION

full binary
3=22-1

7=23-1

15=24-1

2. BINARY TREE AND REPRESENTATION

struct node
{ int data;
node *left;
node *right;
};

Tree traversal

Used to print out the data in a tree in a certain order

inorder (LDR )
Postorder (LRD )
preorder (DLR )

Pre-order traversal

Print the data at the root

Recursively print out all data in the left subtree
Recursively print out all data in the right subtree

Preorder, Postorder and Inorder

Preorder

traversal

node, left, right

prefix expression
++a*bc*+*defg

Preorder, Postorder and Inorder

Postorder

traversal

left, right, node

postfix expression
abc*+de*f+g*+

Inorder

traversal

left, node, right.

infix expression
a+b*c+d*e+f*g

Preorder, Postorder and Inorder

3. BINARY TREE TRAVERSAL

3. BINARY TREE TRAVERSAL

Inorder = DBEAC
Many trees

4. BINARY SEARCH TREE

A binary

search tree

is a binary tree (may be empty)

every node must contain an identifier.
An identifier of any node in the left subtree is less
than the identifier of the root.
An identifier of any node in the right subtree is
greater than the identifier of the root.
Both the left subtree and right subtree are binary
search trees.

4. BINARY SEARCH TREE

binary

search tree.

Binary Search Trees

A binary search tree

Not a binary search tree

Binary search trees

Two binary search trees representing
the same set: Why?

Performance

Consider a dictionary with n

items implemented by
means of a binary search
tree of height h

the space used is O(n)

methods find, insert and
remove take O(h)time

The height h is O(n)in the

worst case and O(logn) in
the best case

4. BINARY SEARCH TREE

Why

using binary search tree

traverse in inorder: sorted list

searching becomes faster

But..

Insert, delete: slow

Important

thing: Index in Database system

Using the right way of Index property

Search

AlgorithmTreeSearch(k, v)
if(v==NULL)
returnv
To search for a key k, we
if kkey(v)
trace a downward path
returnTreeSearch(k, T.left(v))
starting at the root
else if kkey(v)
The next node visited
returnv
depends on the outcome
else{kkey(v)}
of the comparison of k with
the key of the current node
returnTreeSearch(k, T.right(v))
If we reach a leaf, the key
6
is not found and we return

nukk
2
9
Example: find(4):

Call TreeSearch(4,root)

Insertion

To perform operation inser(k,

o), we search for key k (using
TreeSearch)
Assume k is not already in the
tree, and let let w be the leaf
reached by the search
We insert k at node w and
expand w into an internal node
Example: insert 5

w
6

2
1

9
4

8
5

4. BINARY SEARCH TREE

Insert

new node

4. BINARY SEARCH TREE

Insert new node
void InsertNode(node* &root,node *newnode)
{
if (root==NULL)
root=newnode;
else
if (root->data>newnode->data)
InsertNode(root->l,newnode);
else
if (root->data<newnode->data)
InsertNode(root->r,newnode);
}

Insert node

Insert node

Insert Order

4. BINARY SEARCH TREE

traverse

node

void preorder(node* r)
{
if (r!=NULL)
{ cout<<r->data<<" ";
inorder(r->l);
inorder(r->r);
}
}

4. BINARY SEARCH TREE

traverse

node

4. BINARY SEARCH TREE

traverse

node

Exercise 1
1.

Build Binary Search Tree from list

10 4 7 12 16 20 30 5 2 26 15
24 12 89 4 32 50 10 6 36 79 5 9 11

Exercise 2
1.

Order of: inoder, postorder, preorder of

Exercise 3
1.

Order of: inoder, postorder, preorder of

Week 10
Search

node

Count

Even/Odd
Leaf

Sum

Even/Odd

Height
Delete

node

1. SEACRCHING NODE
node* search(node* &r, int data)
{
if (r==NULL)
return NULL;
else
if (r->data==data)
return r;
else
if (data<r->data)
return search (r->l,data);
else
if (data>r->data)
return seach(r->r,data);
}

1. SEACRCHING NODE

H3
100

node* search(node* &r, int data)

{
if ( (r==NULL) || (r->data==data) )
return r;
else
if (data<r->data)
return search (r->l,data);
else
if (data>r->data)
return seach(r->r,data);

H20

H40

H20

H40
80

120

NULL NULL

NULL NULL

Node* S=search(r,80)
What does S stand for?

2. COUNTING THE NUMBER OF

NODES

int count(struct tnode *p)

Without Recursion
{
if( p == NULL)
With Recursion
return(0);
else
if( p->lchild == NULL && p->rchild == NULL)
return(1);
else
return(1 + (count(p->lchild) + count(p->rchild)));
}

2. COUNTING THE NUMBER OF

NODES

int count(struct tnode *p)

{
if( p == NULL)
return(0);
else
return(1 + (count(p->lchild) + count(p->rchild)));
}

3. Sum of all nodes

int

sum(node *p)

{
if( p == NULL)
return(0);
else
return( p->data+sum(p->l)+sum(p->r) );
}

4. COUNTING THE NUMBER OF EVEN

(ODD) NODES
int counteven(node* r)
{
if (r!=NULL)
if (r->data%2==0)
return
1+ counteven(r->l)+counteven(r->r);
else
return
counteven(r->l)+counteven(r->r);
else
return 0;
}

5. SUM OF EVEN (ODD) NODES

int counteven(node* r)
{
if (r!=NULL)
if (r->data%2==0)
????????????????????
else
????????????????????
else
return 0;
}

6. Count number of leaf nodes

Exercise

Count number of leaf nodes

6. Count number of leaf nodes

int countleaf(node* r)
{
if (r!=NULL)
if (r->l==NULL && r->r==NULL)
return
1;
else
return
countleaf(r->l)+countleaf(r->r);
else
return 0;
}

6. Count number of node had 1 child

int count1child(node* r)
{
if (r!=NULL)
if (????????????????????????????)
return
1+count1child(r->l)+count1child(r->r);
else
return
count1child(r->l)+count1child(r->r);
else
return 0;
}

6. Count number of node had 2

children
int count2child(node* r)
{
if (r!=NULL)
if (????????????????????????)
return
1+count2child(r->l)+count2child(r->r);
else
return
count2child(r->l)+count2child(r->r);
else
return 0;
}

7. Find height of tree

int

Height (node* n)

{
if(n==NULL) return 0;
else return 1+max(Height (n->l)),
Height (n->r));
}

8. Delete node
Divide

into 3 cases

Deletion of a Node with No Child

Deletion of a Node with one Child
Deletion of a Node with two Children

8. Delete node
Deletion

of a Node
with No Child

Set the left of y to

NULL
Dispose of the node
pointed to by x

8. Delete node
Deletion

of a Node with
One Child

Make the y->left=x->right

dispose of the node pointed
to by x

8. Delete node
Deletion

of a Node with two Children

8. Delete
node

rightmost child of the

subtree of the left
leftmost child of the
subtree of the right

But WHY???

Deletion (cont.)
1

We consider the case where the

key k to be removed is stored at
a node v whose children are both
internal

we find the internal node w that

follows v in an inorder traversal
we copy key(w) into node v
we remove node w and its left
child z (which must be a leaf) by
means of operation
removeExternal(z)

Example: remove 3

8
6

z
1
5

8
6

Deletion (cont.): exercise1: remove 16

Deletion (cont.): exercise1: remove 16

Deletion (cont.): exercise2: remove 16

Deletion (cont.): exercise2: remove 16

Exercise:
Write

program to delete node

Week 13

AVL Tree

AVL tree property

An AVL tree is a binary search tree with the
additional AVL tree property :
For any node x, the heights of left(x) and right(x)
differ by at most 1.
15
15

15

15
10

10

10

20
3

20
18

13
1
NOT an AVL tree. Why?

AVL trees

23

AVL Tree

BTS
Where did it come from?

Why?

two inventors, G.M. Adelson-Velsky and E.M. Landis

1962
paper "An algorithm for the organization of information."
Fast search, delete, insert 0(logn);

Operation

Insert
Delete
Look up

balance factor

height of its right subtree minus the height of its left subtree
-1

x
nh-1

nh-2

nh-1

nh-1

nh-1

nh-2

Rotations

The insert and delete operations of AVL tree are the

same as binary search tree (BST).

Since an insertion (deletion) involves adding

(deleting) a tree node, this can only increase
(decrease) the heights of some subtree(s) by 1.

Thus, the AVL tree property may be violated.

If the AVL tree property is violated at a node x, it

means that the heights of left(x) and right(x) differ by
exactly 2.

Rotations

After the insertion or deletion operations, we need to

examine the tree and see if any node violates the
AVL tree property.
If the AVL tree property is violated at node x, single or
double rotation will be applied to x to restore the AVL
tree property.
Rotation will be applied in a bottom-up manner
starting at the place of insertion (deletion).
Thus, when we perform a rotation at x, the AVL tree
property is restored at all proper descendants of x.
This fact is important.

Rotations

Insertion

Perform normal BST insertion.

Check and restore AVL tree property.

Trace from path of inserted leaf towards the root, and

check if the AVL tree property is violated.
Check to see if heights of left(x) and right(x) height
differ by at most 1.
If the AVL tree property is violated, there are 4 rotation
cases to restore the AVL tree property.

Insertion

Restore AVL tree property

Case
1 at x, let the height of x
If the AVL tree property
is violated
be
h+3 :

If the height of left(x) is h+2 then

Case 1: If the height of left(left(x)) is h+1, we

single rotate with left child.

Restore AVL tree property

Case 1
h+3
h+2

h+3

h+2

Case 1 : Single rotate with left child.

Restore AVL tree property

Case 1

Case 1 : Single rotate with left child

Restore AVL tree property

Case 1

Case 1 : Single rotate with left child.

Restore AVL tree property

Case
2 at x, let the height of x
If the AVL tree property
is violated
be
h+3 :

If the height of left(x) is h+2 then

Case 1: If the height of left(left(x)) is h+1, we

single rotate with left child.

Case 2: Otherwise, the height of right(left(x)) is

h+1, then we double rotate with left child.

Restore AVL tree property

Case 2
h+3

h+2

Case 2 : Double rotate with left child.

Restore AVL tree property Case 2

Case 2 : Double rotate with left child.

Restore AVL tree property

Case 2

Case 2 : Double rotate with left child.

Restore AVL tree property

Case
3 at x, let the height of x
If the AVL tree property
is violated
be
h+3 :

If the height of left(x) is h+2 then

Case 1: If the height of left(left(x)) is h+1,

Case 2: Otherwise, the height of right(left(x)) is

h+1, then we double rotate with left child.

Otherwise, height of right(x) is h+2

Case 3: (Mirror image of the case 1) If the height of

right(right(x)) is h+1, then we single rotate with
right child.

Case 4: (Mirror image of the case 2) Otherwise, the

height of left(right(x)) is h+1, then we double
rotate with right child.

Restore AVL tree property

Case 3
h+2

h+2

Case 3 : Single rotate with right

child.

Restore AVL tree property

Case 3

Case 3 : Single rotate with right

child.

Restore AVL tree property

Case
4 at x, let the height of x
If the AVL tree property
is violated
be
h+3 :

If the height of left(x) is h+2 then

Case 1: If the height of left(left(x)) is h+1,

Case 2: Otherwise, the height of right(left(x)) is

h+1, then we double rotate with left child.

Otherwise, height of right(x) is h+2

Case 3: (Mirror image of the case 1) If the height of

right(right(x)) is h+1, then we single rotate with
right child.

Case 4: (Mirror image of the case 2) Otherwise, the

height of left(right(x)) is h+1, then we double
rotate with right child.

Restore AVL tree property

Case 4

h+2

Case 4 : Double rotate with right

child.

Restore AVL tree property

Case 4

Case 4 : Double rotate with right

child.

Insertion

Trace from path of inserted leaf towards the root, and

check if the AVL tree property is violated. Perform
rotation if necessary.

For insertion, once we perform (single or double)

rotation at a node x, the AVL tree property is already
restored. We need not to perform any rotation at any
ancestor of x.

Why???

Thus one rotation is enough to restore the AVL tree

property.
There are 4 different cases (actually 2), so dont mix
up them!

Insertion

The time complexity to perform a rotation is O(1).

The time complexity to insert, and find a node that

violates the AVL property is dependent on the height
of the tree, which is O(log(n)).

So insertion takes O(log(n)).

Deletion

Delete a node x as in ordinary BST (Note that x is

either a leaf or x has exactly one child.).

Check and restore the AVL tree property.

Trace from path of deleted node towards the root,
and check if the AVL tree property is violated.

Similar to an insertion operation, there are four cases

to restore the AVL tree property.

Deletion

The only difference from insertion is that after we

perform a rotation at x, we may have to perform a
rotation at some ancestors of x. It may involve
several rotations.

Therefore, we must continue to trace the path until

we reach the root.

The time complexity to delete a node is dependent

on the height of the tree, which is also O(log(n)).

Deletion : no rotation

No need to
rotate.

Deletion : one rotation

Case 3 : Single rotate with right

child.

Deletion : several rotations

Case 4 : Double rotate with right

child.

Case 3 : Single rotate with right

child.

Summary of AVL Trees

Maintains a balanced tree by posing an AVL

tree property:

guarantees the height of the AVL tree be

O(log n)
implies that functions search, min, and max,
insert, and delete will be performed in
O(logn)

Modifies the insertion and deletion routine

Performs single or double rotation to restore

the AVL tree property if necessary.
Requires a little more work for insertion and
deletion.

Exercise 1
a. Insert 3

???

a. Insert 3

An: Exercise 1

Exercise 2
a. Insert 5

???

An. Exercise 2
a. Insert 5

Exercise 3
Insertion order:
10, 85, 15, 70, 20, 60, 30, 50, 65, 80, 90, 40, 5, 55

???

An Exercise 3
Insertion order:
10, 85, 15, 70, 20, 60, 30, 50, 65, 80, 90, 40, 5, 55

Exercise 4
Delete 40

An. Exercise 4
Delete 40

An. Exercise 4
Delete 40

Exercise 5
Delete 20

An. Exercise 5

Delete 20

Week 14
Sa bi tp

Exercise 1 /S 4
T chc v xy dng 2 hm :
GiiPT_bac1
GiiPT_bac2

a
b

x1
a
c
b

x2
Trng hp

Tnh ng gi?

x
Trng hp

Exercise 3 /S 4
Vit chng trnh tnh lng cho cc cng
nhn ti xng may. Mi cng nhn s c
gi vo v gi ra trong mt ngy. Tin
lng c tnh nh sau:
T 5h-8h: mi gi 20,000
T 8h-11h: mi gi 15,000
T 11h-14h: mi gi 30,000
T 14h-17h: mi gi 22,000
T 17h-24h: mi gi 40,000

Exercise 3 /S 4

11

14

17

24

Exercise 3 /S 4
v1

c1

11

c2

v2

14

Double TinhTien(c1,c2,v1,v2,dongia)

17

24

Exercise 3 /S 4
v1

c1

c2

V2<c1

v2
V2>c1 && v2<c2
V1<c1

11

V2>c2

14

V2<c2

V1>c1 && V1<c2

V2>c2
V1>c2

Double TinhTien(c1,c2,v1,v2,dongia)

Bi tp 1 /S 10
Sinh vin:
+M SV: char[10];
+M Lp : int
+Tn SV: char[255];
+DiemToan
+DiemLy
+DiemHoa

Lp gm cc thng tin:
+M Lp: int
+Tn Lp: char[10];
+Kha

1Tree - 1Tree

Struct SV
{
char ma[10];
Ten char[20];
Int malop;
Double toan,ly,hoa;
};

Struct lop
{
int ma;
Ten char[20];
};

1
NCD1A

123
Nguyn Th Nh
Lp: 1
im: 9,8,10

1Tree - 1Tree

Struct lop
{
int ma;
Ten char[20];
Lop* left,right;
};

1
NCD1A

Struct SV
{
char ma[10];
Lop* lop;
Int malop;
Double toan,ly,hoa;
SV* left,right;
};

123
Nguyn Th Nh
Lp: ?
im: 9,8,10

1Tree - nTree

Struct lop
{
int ma;
Ten char[20];
SV *ListSV;
Lop* left,right;
};

1
NCD1A

Struct SV
{
char ma[10];
Double toan,ly,hoa;
SV* left,right;
};

123
Nguyn Th Nh
Lp: ?
im: 9,8,10

Tree Single Linked List

Struct lop
{
int ma;
Ten char[20];
SV* listSV;
Lop* left,right;
};

1
NCD1A

Struct SV
{
char ma[10];
Double toan,ly,hoa;
SV* next;
};

123
Nguyn Th Nh
Lp: ?
im: 9,8,10

Tree Double Linked List

Struct lop
{
int ma;
Ten char[20];
SV* listSV;
Lop* left,right;
};

1
NCD1A

Struct SV
{
char ma[10];
Double toan,ly,hoa;
SV* next,pre;
};

123
Nguyn Th Nh
Lp: ?
im: 9,8,10

Double Linked List Double Linked List

Struct lop
{
int ma;
Ten char[20];
SV* listSV;
Lop* next,pre;
};

1
NCD1A

Struct SV
{
char ma[10];
Double toan,ly,hoa;
SV* next,pre;
};

123
Nguyn Th Nh
Lp: ?
im: 9,8,10

Bi tp ti lp
Qun l mua v hnh khch
V my bay (ID,gi)
Khch(PassID, ten)
Mi khch ch mua 1 v
1Tree-1Tree

1double LL-1Tree

1Tree-1 single L.L

1double LL-1 Double L.L

1Tree-1 double L.L

Week 15
Some Final Test questions
Problems only

 Part 1: Basic Programming

1
What will be the output of the following
code?

int x, y, z;
x=1; y=2; z=3;
int* a = &x;
*a = y;
cout << x << endl;

1G
What will be the output of the following
code?

int x, y, z;
x=1; y=2; z=3;
int* a = &x;
*a = y;
cout << x << endl;
2

2
After execution of the statement:
char *p = "Stuff";
what would be printed by following statement?
printf("%c",*p+3);
S
V
U
F
u

2G
After execution of the statement:
char *p = "Stuff";
what would be printed by following statement?
printf("%c",*p+3);

What is the output of the following program?

int main ()
{
int i, j, *p, *q;
p = &i;
q = &j;
*p = 5;
*q = *p + i;
printf("i = %d, j = %d\n", i, j);
}
i=5 j=10
i = 5, j = 5
i=10, j = 5
Nothing. The program will most likely crash.

3G

What is the output of the following program?

int main ()
{
int i, j, *p, *q;
p = &i;
q = &j;
*p = 5;
*q = *p + i;
printf("i = %d, j = %d\n", i, j);
}
i=5 j=10

4
If this code fragment were executed in an otherwise
correct and complete program, what would the output
be?
int a = 3, b = 2, c = 5
if (a > b)
a = 4;
if ( b > c)
a = 5;
else
a = 6;
cout << a < endl;

6
5
4
3

4g
If this code fragment were executed in an otherwise
correct and complete program, what would the output
be?
int a = 3, b = 2, c = 5
if (a > b)
a = 4;
if ( b > c)
a = 5;
else
a = 6;
cout << a < endl;

5
int whatIsIt (int x, int n)
{
if ( n == 1 )
return x;
else
return x * whatIsIt(x, n-1);
}
What is the value returned by whatIsIt(4, 4)?
256
64
4
16
128

5g
int whatIsIt (int x, int n)
{
if ( n == 1 )
return x;
else
return x * whatIsIt(x, n-1);
}
What is the value returned by whatIsIt(4, 4)?

256

What is the output of the following program?

#include <iostream.h>
int * f(int * p, int & x)
{ ++x; p = &x; return p; }
int main( )
{
int x = 2, y = 5;
int * p = &y;
int * q = f(p, x);
cout << x << y << *p << *q << endl;
return 0;
}

3355
---------------3553
---------------2553
---------------5553

7g

What is the output of the following program?

#include <iostream.h>
int * f(int * p, int & x)
{ ++x; p = &x; return p; }
int main( )
{
int x = 2, y = 5;
int * p = &y;
int * q = f(p, x);
cout << x << y << *p << *q << endl;
return 0;
}

3553

8
Giving code segment:
void mangle_numbers(int &a, int b)
{
int c,d,e;
a = 3;
b = a+2;
c = b++;
d = ++b;
e = a+5;
b *=5;
}
void main()
{ int sum,x=5, y=7;
mangle_numbers(x,y);
sum=x+y;}
After running code segment, value of sum is:

9
---------------8
---------------10
---------------12

8g
Giving code segment:
void mangle_numbers(int &a, int b)
{
int c,d,e;
a = 3;
b = a+2;
c = b++;
d = ++b;
e = a+5;
b *=5;
}
void main()
{ int sum,x=5, y=7;
mangle_numbers(x,y);
sum=x+y;}
After running code segment, value of sum is:

10

9
After the following code:
int i = 2;
int k = 4;
int *p1;
int *p2;
p1 = &i;
p2 = &k;
p1 = p2;
*p1 = 6;
*p2 = 8;
what is the value of i and k

28
---------------42
---------------68
---------------24

9g
After the following code:
int i = 2;
int k = 4;
int *p1;
int *p2;
p1 = &i;
p2 = &k;
p1 = p2;
*p1 = 6;
*p2 = 8;
what is the value of i and k

28

10
If myAge, a, and b are all int variables,
what are their values after this sample
program executes?

myAge = 39;
a = myAge++;
b = ++myAge;

myAge: 39, a: 39, b: 39

---------------myAge: 39, a: 39, b: 40
---------------myAge: 41, a: 39, b: 41
---------------myAge: 39, a: 40, b: 41

10g
If myAge, a, and b are all int variables,
what are their values after this sample
program executes?

myAge = 39;
a = myAge++;
b = ++myAge;

myAge: 41, a: 39, b: 41

 Part 2: Recursion

6
What does the following program output?
#include <iostream>
int test(int n){
if(n<=0)
return 0;
cout << n;
if(n%2==0)
return 1+test(n-3);
else
return 2+test(n-1);
}
void main(){
cout << endl << test(5) << endl;
}

541
5
---------------541
8
---------------541
7
---------------541
6

6g
What does the following program output?
#include <iostream>
int test(int n){
if(n<=0)
return 0;
cout << n;
if(n%2==0)
return 1+test(n-3);
else
return 2+test(n-1);
}
void main(){
cout << endl << test(5) << endl;
}

541
5

7g

int f(int x[], int n);

void main()
{
int a[5] = {1, 2, 3, 4, 5};
int b;
b = f(a, 5);
}
int f(int x[], int n)
{
if (n == 1)
return x[0];
else
return x[n 1] + f(x, n 1);
}

After running code segment, value of b is

15

8g
Giving code segment:
int f( int n )
{

if ( n==1 )

return 1;

else

return ( f(n-1)+n );
}
Select return result when call:

5151

f(101)?

9g
public int mystery(int k, int n)
{

if (n==k)

return k;

else if (n > k)

return mystery(k, n-k);

else

return mystery(k-n, n);

}

Based on the method defined, what is the value of

mystery(6,8)?

10g
Suppose that the following function.

int sss(int x) {
if (x % 2 == 0)
return x+1;
else
return (x - 1)*sss(x + 1);
}

10

Determine the output of the following statement.

println(sss(3));

11g
The following function.

static int ttt(int x, int y) {

if (x % y == 0)
return x/y + 2;
else
return x - ttt(y, x + 1);
}

Determine the output of the following statement.

println(ttt(7, 3));

12g
The following function.

int kkk(int x){

if((x % 3 == 0) && (x > 0))
return 1 + kkk(4 + kkk(x - 3));
else if (x % 2 == 0)
return kkk(x + 1);
return x + 2;
}

What value would the call kkk(2) return?

10

int Wow (int n ,m ) 13g

{
if (m ==1)
return n;
10
if ( n == m)
return 1;
return (Wow(n - 1, m - 1) + Wow (n - 1 , m);
}
Wow(5 , 2) will return which of the following?

 Part 3: search - sort

1
A searching algorithm requires at most
100n3log(n) + 25n^5 comparisons to
search an array of n elements. The worstcase time complexity for the algorithm is
O(n^3)
O(n^5)
O(n^3log(n))
O(n^8)

Assume that Algorithm Test has a time complexity O(n^3), and that
Algorithm Compute has time complexity O(n^2). What is the time
complexity of the following algorithm?
Execute Algorithm Test
For 5 trials, execute Algorithm Compute
Execute Algorithm Test
O(n^3)
O(n^2)
O(n^18)
O(n^16)

 Which of the following statements about the

standard binary search is valid?
A non-recursive implementation of binary search
requires a single loop containing a conditional
statement.
Insertion of a new element requires one step, a single
array access, not a loop.
Deleting one element requires one step, an array
access, not a loop.
In a search for one element X which is not in the array,
every element in the array is accessed to determine if
it equals X.

What does the following code fragment do? (All variables are of type int.)

position1 = -1;
position2 = -1;
for (j = 0; j < 50; j++)
for (i = 0; i < 50; i++)
if (arr[i][j] == searchValue)
{
position1 = i;
position2 = j;
}

It searches the array in row order for the first occurrence of searchValue
It searches the array in row order for the last occurrence of searchValue
It searches the array in column order for the first occurrence of searchValue
It searches the array in column order for the last occurrence of searchValue

 Part 3: Linked List

Let the following struct be used to create linked lists:

struct listnode {
int data;
listnode* next;
};
Let p point to the head of an existing linked list with more than one
element. The following code segment is supposed insert the node
pointed to by q at the end of the linked list pointed to by p?

listnode* temp;
temp = p;
while (**A**)
**B**;
temp->next = q;
What line of code should replace **B**?

p = p->next;
temp++;
temp = temp.next;
temp = temp ->next;

2
If there is a NodePtr named toDelete whose value points
to a valid node in the list, which of the following
statements would remove the node that follows toDelete
from the list and return that memory to the freestore?
tmp = toDelete -> link;
toDelete -> link = toDelete->link->link;
delete tmp;

tmp = toDelete -> link;

toDelete -> link = tmp -> link;
delete tmp;

tmp = toDelete->link->link;
toDelete -> link = toDelete->link->link;
delete tmp;

All of the others answers;

3
Which of the following statements is not
true?
Singly linked lists can increase their sizes
faster than arrays can increase their sizes
The singly-linked list does not allow you to
access the nth element in constant time
You can search for and find a value in an
array in constant time.
If you mistakingly mis-assign the head pointer
to NULL, you will lose the entire list

Suppose a Deque is implemented by a singly

linked list with a reference to the first node and
a reference to the last node. Which of the
following operations take O(n) time?
Add a new member at the beginning of a Deque.
Add a new member at the end of a Deque.
Remove a member from the beginning of a Deque.
Remove a member from the end of a Deque.

 Part 4: BST

 We say "postorder traversal of a tree"

when we visit a node
after we visit all its children
none of the others
before we visit all its children
in the middle of visiting all its children

 If I insert the integers 1 through n, in

increasing order, into an initially empty
Binary Search Tree, what is the height of
the tree?
O(n^1/2)
O(n * log n)
O(n)
O(log n)

 Consider this binary search tree in picture.

Suppose we remove the root, replacing it
with something from the left subtree. What
will be the new root?
5
6
7
4

 What is the minimum height of a binary

tree with 31 nodes?
31
5
6
7

 Suppose T is a binary tree with 300

nodes. Which one of the following is the
best estimation of the height of T?
The height of T is at least 8;
The height of T is at most 8;
The height of T is at least 9.
The height of T is at most 9;

If the inorder traversal of the binary tree T is

AD BGC FE

and each node of T has either 0 or 2 children, which of the following

nodes is NOT a leaf of that tree?

A
B
C
D

 What is the maximum height of a binary

tree with 31 nodes?
31
5
6
7

 Which of the following arrangements of

general-purpose data structures is from
slowest to fastest for the purpose of finding
objects according to a key value:
sorted arrays, unsorted linked lists, binary
search trees
sorted arrays, binary search trees, linked lists
binary search trees, unsorted arrays, sorted
linked lists
sorted linked lists, sorted arrays, binary search
trees

 Which of the following arrangements of generalpurpose data structures is from slowest to

fastest for the purpose of storing objects by key
value (not necessarily in order):
unsorted arrays, sorted linked lists, binary search
trees
sorted arrays, binary search trees, linked lists
binary search trees, sorted arrays, sorted linked lists
unsorted arrays, linked lists, binary search trees