Course Packet - CC 214 (Data Structures and Algorithms)

Disclaimer Statement:
This Course Study Guide is not intended to be presented as the original work of the module
compiler. It is meant to be the primary reference material for the course composed of the
flexible learning syllabus, learning plans, course content, and assessments compiled from
various sources. Accordingly, the sale and distribution of such outside the University of the
Visayas is strictly prohibited.
Data Structures
and Algorithm
College of Computer Studies

Course Study Guide Contents
Week No. Module Topic Page
1 Basic data structure 7
23
2 Trees
3 Hashing 46
4 Sorting Techniques 60
Editorial Office
Course Developer Susanette A. Dakay
Alan A. Felicano
Content Experts
Kent Ivan R. Unabia
Jacqueline S. Pondoc
Language Editor Crescenciana M. Calvario
Dr. Aileen B. Catacutan
Design/Media Specialist Emily L. Ong
2
Flexible Learning Course Syllabus
Flexible Learning Course Syllabus

College of Computer Studies
Bachelor of Science in Information Technology
First Semester, Academic Year 2020-2021
I. Course Information
Course Code CC 214
Course The objective of the course is to introduce the
Course Title Description fundamentals of Data Structures, Abstract concepts, and
Data Structures how these concepts are useful in problem solving.
and Algorithm
Prerequisite(s) CC 123
Course 1. Analyze step by step and develop algorithms to solve
Learning real world problems.
Credit Unit 3 Units Outcomes 2. Implementing various data structures.
3. Understanding various searching & sorting techniques.
II. Instructor's Information

Instructor Name Susanette S. Arriba Corporate [email protected]
Email
Title: CCS Faculty Phone +63 945 428 4010
III. Course Syllabus

Mode of
Week No. of Module Topic Intended Learning Materials and Resources Instruction/ Assessment
No. Hours Learning Delivery Task/ Graded
Outcomes Required Suggested Output
Tools
13.5 total Use and Lesson 1. Course Data Structure and Algorithms - Course 1. Source code
hours implement Module on Data Array Packet
and output
Basic Data Arrays, Stacks, Structures and https://  Printed
12 hours Structures Expressions Algorithm of www.tutorialspoint.com/  Digital 2. Source code
self- Parsing, and College of data_structures_algorithms/ Microsoft and output
1 directed Sub-topic: Queues Computer Studies. array_data_structure.htm Teams 3. Solutions on the
learning  Array University of the
problem given
&  Stacks Visayas Data Structure and Algorithms -
1.5 hours  Expressions Stack
of  Queues https://
assess- www.tutorialspoint.com/
ment data_structures_algorithms/
tasks stack_algorithm.htm
Data Structure & Algorithms -

Queues
https://
www.tutorialspoint.com/
data_structures_algorithms/
dsa_queue.htm
3
Trees Use and implement Lesson 2. Course Data Structure & Algorithms - Course 4. Simulation
2 13.5 total Trees, Tree Module on Data Trees Packet
hours Sub-topics: Traversal and Structures and https:// • Printed
www.tutorialspoint.com/ 5. Source code
Binary Search Tree Algorithm of • Digital
data_structures_algorithms/ and output
12  Tree Traversal College of tree_data_structure.htm Microsoft
hours  Binary Search Computer Studies. Teams
self- Tree University of the Data Structure & Algorithms –
directed Visayas Tree Traversal 6. Source code
learning https:// and output
& www.tutorialspoint.com/
1.5 hours data_structures_algorithms/ 7. Multiple-Choice
of tree_traversal.htm
Test
assess-
ment Data Structure & Algorithms –
tasks Binary Search Tree
https://
data_structures_algorithms/
binary_search_tree.htm
13.5 total Hashing Use and implement Lesson 3. Course Data Structure & Algorithms – Course 8. Problem
hours Hash Table Module on Data Hash Table Packet solutions
Structures and https://  Printed
12 Algorithm of www.tutorialspoint.com/  Digital
3 hours College of Computer data_structures_algorithms/ Microsoft
self- Studies. University hash_data_structure.htm Teams 9. Source code
directed of the Visayas and output
learning Data Structure & Algorithms –
& Graph Data Structure
1.5 hours https:// 10. Multiple
of www.tutorialspoint.com/ Choice
assess- data_structures_algorithms/
ment graph_data_structure.htm
tasks
13.5 Sorting Use and implement Lesson 4. Course Data Structure & Algorithms – Course
total Sorting Module on Data Sorting Packet
hours Sub-topics: Techniques, Bubble Structures and https://  Printed 11. Source code
Sort, Insertion Algorithm of
data_structures_algorithms/  Digital and output
12  Bubble Sort Sort, and Selection College of Computer sorting_algorithms.htm Microsoft
4 hours  Insertion Sort Sort Studies. University Teams 12. Multiple
self-  Selection Sort of the Visayas Data Structure & Algorithms – choice test
directed Bubble Sort
learning https://
& www.tutorialspoint.com/
1.5 hours data_structures_algorithms/
of bubble_sort_algorithm.htm
assess-
ment Data Structure & Algorithms –
tasks Insertion Sort
https://www.tutorialspoint.com/
data_structures_algorithms/inse
rtion_sort_algorithm.htm
IV-A. Points for Graded Output IV-B. Grade Equivalent Based on Points Earned
Course Week Module Topic Output Points Points Earned Grade
1 Minor Task 100 97%-100% 1.00
94%-96% 1.25
2 Minor Task 70 90%-93% 1.50
86%-89% 1.75
3 Minor Task 100 82%-85% 2.00
78%-81% 2.25
4 Major Task 150 74%-77% 2.50
71%-73% 2.75
Total 420 70% 3.00
69% below 5.00
INC is given if the final grade is 2.5 or better but missing any two of the course requirements listed above. INC should be complied within 365 days
immediately after the close of the Semester.
V. Approval
Prepared by Reviewed by Approved by
JACQUELINE S. PONDOC
CRESCENCIANA M. CALVARIO
SUSANETTE S. ARRIBA DR. AILEEN B. CATACUTAN ALAN A. FELICANO
Instructor OIC
Librarian
Lesson 1
BASIC DATA STRUCTURE
At the end of the lesson, the student should be able to:
 create and define Java arrays and provide real-world examples of their
use;
 understand and learn how a Stack works, including push and pop functions; and
 evaluate and convert between prefix, infix, and postfix notation.
5
College COLLEGE OF COMPUTER STUDIES (CCS)
Program BACHELOR OF SCIENCE IN INFORMATION TECHNOLOGY
Course Code DATA STRUCTURES AND ALGORITHM
Course Title CC 214
Credit Unit 3
Lesson 1 Week 1
Module Topic THE BASIC STRUCTURE

Intended Learning  create and define Java arrays and provide real-world examples of their use;
Outcomes
 understand and learn how a Stack works, including push and pop functions; and
 evaluate and convert between prefix, infix, and postfix notation.
Number of Hours 13.5 Hours (12 hours Self-directed learning and 1.5 hours Assessment Tasks)
1. What data types can an array contain?
2. What is stack with example?
Study Questions
3. What is parsing in data structure?
4. Where is stack used?
5. What are the basic operations of queue?
Required Suggested
Lesson 1. Course Module on Data Data Structures and Algorithms in Java, Second Edition
Structures and Algorithm, College of Copyright © 2003 by Sams Publishing. Robert Lafore
Learning Resources Computer Studies. University of the
Visayas https://everythingcomputerscience.com/books/schoolboek-
data_structures_and_algorithms_in_java.pdf
1. In activity 1, the student will write a Java program and give its solutions and output.
2. In activity 2, the student will write a Java program to perform push, pop, peep, etc.
using Stack and display its output.
Learning Activity 3. In Activity 3, the student will answer the Problem solving and show solutions on
Conversion, Evaluation, and Stacks.
Source code and output (3 problems)
Required Output Source code and output (Stacks operation)
Solutions on the given problem
1. Activity 1
Assessment Tasks
2. Activity 2
3. Activity 3
Assessment Tool Microsoft Teams - Presentation
Creative & Innovative Thinking, Flexibility, Initiative, Problem Solving, Development, &
Target Competency Continual Learning.
Prepared by: Reviewed by: Approved for use:
Jacqueline S. Pondoc
SUSANETTE S. ARRIBA Crescenciana M. Calvario ALAN A. FELICANO
Dr. Aileen B. Catacutan
Faculty Librarian OIC
6
Chapter I – THE BASIC STRUCTURE
Data Structures and Algorithms – Java Arrays
Java array enables the user to store the values of the same type in contiguous memory
allocations. Arrays are always a fixed length abstracted data structure which cannot be
altered when required.
Following are the important terms to understand the concept of Array.

 Element − Each item stored in an array is called an element.
 Index − Each location of an element in an array has a numerical index, which is
used to identify the element.
Advantages of Java Array:

 An array can hold primitive types data.
 An array has its size that is known as array length.
 An array knows only its type that it contains. Array type is checked at the compile-
time.
Disadvantages of Java Array:

 An array has fixed size.
 An array holds only one type of data (including primitive types).
 Structure of Java Arrays
Array is the most widely used data structure in java. It can contain multiple values of the
same type. Moreover, arrays are always of fixed length i.e. the length of an array cannot
be increased or decreased.
Array contains the values which are implicitly referenced through the index values. So, to
access the stored values in an array we use indexes. Suppose an array contains "n”
integers. The first element of this array will be indexed with the "0" value and the last
integer will be referenced by "n-1" indexed value.
Presume an array that contains 12 elements. Each element is holding a distinct value. Here
the first element is referenced by a[0] i.e. the first index value. We have filled the 12
distinct values in the array each referenced as:
a[0]=1
a[1]=2
...
a[n-1]=n
...
a[11]=12
7
Java Array Declaration
As we declare a variable in Java, an Array variable is declared the same way. Array variable
has a type and a valid Java identifier i.e. the array's type and the array's name. By type we
mean the type of elements contained in an array. To represent the variable as an Array, we
use [] notation. These two brackets are used to hold the array of a variable.
By array's name, we mean that we can give any name to the array, however it should follow
the predefined conventions.
Below are the examples which show how to declare an array:
int[] array_name; //declares an array of integers

String[] names;
int[][] matrix; //this is an array of arrays
It is essential to assign memory to an array when we declare it. Memory is assigned to set the
size of the declared array. for example:
int[] array_name = new int[5];
Here is an example that creates an array that has 5 elements.

public class Array{
public static void main(String[] args) {
int[] a = new int[5];
}
}
Java Array Initialization
After declaring an array variable, memory is allocated to it. The "new" operator is used for the
allocation of memory to the array object. The correct way to use the "new" operator is
String names[];
names = new String[10];
Here, the new operator is followed by the type of variable and the number of elements to be
allocated. In this example [] operator has been used to place the number of elements to be
allocated.
public class Sum {
int[] x = new int [101];
for (int i = 0; i<x.length; i++ )
x[i] = i;
int sum = 0;
for(int i = 0; i<x.length; i++)
sum += x[i];
System.out.println(sum);
}
}
8
In this example, a variable 'x' is declared which has a type array of int, that is, int[]. The
variable x is initialized to reference a newly created array object. The expression 'int[] =
new int[50]' specifies that the array should have 50 components. To know the length of the
Array, we use field length, as shown.
Output for the given program:

C:\tamana>javac Sum.java
C:\tamana>java Sum
5050
Java Array Usage
We have already discussed that to refer an element within an array, we use the [] operator.
The [] operator takes an "int" operand and returns the element at that index. We also
know that the array indices start with zero, so the first element will be held by the 0 index.
For Example:
int month = months[4]; //get the 5th month (May)
Most of the times, it is not known in the program that which elements are of interest in an
array. To find the elements of interest in the program, it is required that the program must
run a loop through the array. For this purpose, "for" loop is used to examine each element
in an array.
For example:-
String months[] =
{"Jan", "Feb", "Mar", "Apr", "May", "Jun",
"July", "Aug", "Sep", "Oct", "Nov", "Dec"};
//use the length attribute to get the number of elements in an array
for (int i = 0; i < months.length; i++ ) {

System.out.println("month: " + month[i]);
Here, we have taken an array of months which is,
String months[] =
{"Jan", "Feb", "Mar", "Apr", "May", "Jun",
"July", "Aug", "Sep", "Oct", "Nov", "Dec"};
Now, we run a for loop to print each element individually starting from the month "Jan".
for (int i = 0; i < months.length; i++ )
9
In this loop int i = 0; indicates that the loop starts from the 0th position of an array and goes
up to the last position which is length-1, i < months.length; indicates the length of the
array and i++ is used for the increment in the value of i which is i = i+1.
Two-Dimensional Arrays
Two-dimensional arrays are defined as "an array of arrays". Since an array type is a first-class
Java type, we can have an array of ints, an array of Strings, or an array of Objects. For
example, an array of ints will have the type int[]. Similarly we can have int[][], which
represents an "array of arrays of ints". Such an array is said to be a two-dimensional
array.
The command
int[][] A = new int[3][4];
declares a variable, A, of type int[][], and it initializes that variable to refer to a newly created
object. That object is an array of arrays of ints. Here, the notation int[3][4] indicates that
there are 3 arrays of ints in the array A, and that there are 4 ints in each of those arrays.
To process a two-dimensional array, we use nested for loops. We already know about for
loop. A loop in a loop is called a Nested loop. That means we can run another loop in a
loop.
Notice in the following example how the rows are handled as separate objects.
int[][] a2 = new int[10][5];

// print array in rectangular form
for (int i=0; i<a2.length; i++) {
for (int j=0; j<a2[i].length; j++) {
System.out.print(" " + a2[i][j]);
}
System.out.println("");
}
In this example, "int[][] a2 = new int[10][5];" notation shows a two-dimensional array. It

declares a variable a2 of type int[][],and it initializes that variable to refer to a newly
created object. The notation int[10][5] indicates that there are 10 arrays of ints in the
array a2, and that there are 5 ints in each of those arrays.
Example: Creating twoDimensional array
public class twoDimension{
int[][] a2 = new int[10][5];
for (int i=0; i<a2.length; i++) {
for (int j=0; j<a2[i].length; j++) {
a2[i][j] = i;

10
System.out.print(" " + a2[i][j]);
}
System.out.println("");
}
}
}
Output:
0 0 0 0 0
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
6 6 6 6 6
7 7 7 7 7
8 8 8 8 8
9 9 9 9 9
Example: Write a Java program to sum values of an array
Solutions:
public class Example {

int my_array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int sum = 0;
for (int i : my_array)
sum += i;
System.out.println("The sum is " + sum);
}
}
Output:
The sum is 55
Data Structures and Algorithms – Stacks
A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is
11
named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of
plates, etc.
A real-world stack allows operations at one end only. For example, we can place or remove a
card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations
at one end only. At any given time, we can only access the top element of a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the element
which is placed (inserted or added) last, is accessed first. In stack terminology, insertion
operation is called PUSH operation and removal operation is called POP operation.
Stack Representation
The following diagram depicts a stack and its operations.
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can
either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to
implement stack using arrays, which makes it a fixed size stack implementation.
At all times, we maintain a pointer to the last PUSHed data on the stack. As the pointer always
represents the top of the stack, is called top. The top pointer provides top value of the
stack without actually removing it.
12
Stack may have the two states while pushing and popping is occurred.
 Overflow : Overflow is the state in which the stack is reached when the push operation
is performed on the stack and it has no more space to be pushed in.
 Underflow : Underflow is the state in which the stack is reached when the pop operation
is performed on the stack and there is no more element is to be removed i.e. the stack
is empty.
In Java Stack may be implemented using the java.util.Stack class. This class provides methods
for performing the operations on Stack like push, pop, peek(peek is the operation in which
the top element is retrieved without removing it from stack), check for the empty stack,
search for an item in the stack and its position from the top element.
Constructor Detail
This class has one constructor.
Stack() : This constructor is used to create an object of empty stack.
Method Detail
This class provides methods for performing various operations on stack.
These are as follows:
 boolean empty() : This method is used to check the availability of element in the
stack. It returns true if the stack is empty otherwise returns false.
Syntax : public boolean empty()

 E peek() : This method is used to look the element at the top of the stack. It
returns the top element but not removes that element. This method may throw an
EmptyStackException if the stack has no element to look up.
Syntax : public E peek()

 E pop() : This method returns the top element of the stack as well as removing it
from the stack. Generally, this method is used to delete the top element of the
stack. This method may throw an EmptyStackException, if the stack has no elements
to remove.
Syntax : public E pop()

 E push(E item) : This method is used to push the element into the stack. The newly
pushed element resides on the top of the stack.
Syntax : public E push(E item)

 int search(Object o) : This method is used to search an item into the stack with its
position from the top item of the stack. The position of the top most item in the
stack is to be returned as 1. It returns the position of an item in the stack as
positive integer value and the value -1 shows there is no item available in the stack.
13
Syntax : public int search(Object o)
Here, an example is being given which will demonstrate you about how to use the stack
collection in Java programming. In this example you will see how the item can be pushed,
popped, searched, peek, etc.
Example:
import java.util.Stack;
public class Main {
public static void main(String args[]) {
Stack stack = new Stack();

stack.push("Shane");//pushed first into the stack so it will be the last item in stack
stack.push("100");
stack.push("41");
stack.push("63");
stack.push("70");
stack.push("83");
stack.push("33");
stack.push("15");
stack.push("29");//pushed last into the stack so it will be the first item in stack
//check whether the stack is empty or not

System.out.println("Is stack empty ? "+stack.isEmpty());
//display stack
System.out.println("Stack contains the following:" +stack);
//Retrieve the top item of the stack without removing it from the stack
System.out.println("Top item of Stack : "+stack.peek());
//Search for the items position in the stack
System.out.println("Position of item '70' in the stack is : "+stack.search("70"));
// remove top item of the stack
stack.pop();//remove 'Shane' from the stack
//display stack
//check whether the top element is removed or not
System.out.println("Position of item '100' in the stack : " +stack.search("100"));
// remove top item of the stack
stack.pop();
stack.pop();
//display stack
//clear stack
stack.clear();
14
System.out.println("Is stack empty?"+stack.isEmpty());
}
}
Output:
Is stack empty ? false

Stack contains the following:[Shane, 100, 41, 63, 70, 83, 33, 15, 29]
Top item of Stack : 29
Position of item '70' in the stack is : 5
Stack contains the following:[Shane, 100, 41, 63, 70, 83, 33, 15]
Position of item '100' in the stack : 7
Stack contains the following:[Shane, 100, 41, 63, 70, 83]
Is stack empty? true
Data Structure - Expression Parsing
The way to write arithmetic expression is known as a notation. An arithmetic expression can
be written in three different but equivalent notations, i.e., without changing the essence or
output of an expression. Infix, Postfix and Prefix notations are three different but equivalent
ways of writing expressions. It is easiest to demonstrate the differences by looking at
examples of operators that take two operands.
These notations are:
 Infix notation: X + Y
Operators are written in-between their operands. This is the usual way we write expressions. An
expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B
and C together, then multiply the result by A, then divide by D to give the final answer."
Infix notation needs extra information to make the order of evaluation of the operators clear:
rules built into the language about operator precedence and associativity, and brackets ( ) to
allow users to override these rules. For example, the usual rules for associativity say that we
perform operations from left to right, so the multiplication by A is assumed to come before
the division by D. Similarly, the usual rules for precedence say that we perform
multiplication and division before we perform addition and subtraction.
 Postfix notation (also known as "Reverse Polish notation"): X Y +

Operators are written after their operands. The infix expression given above is equivalent
to A B C + * D /
The order of evaluation of operators is always left-to-right, and brackets cannot be used to
change this order. Because the "+" is to the left of the "*" in the example above, the
addition must be performed before the multiplication.
15
Operators act on values immediately to the left of them. For example, the "+" above uses
the "B" and "C".
We can add (totally unnecessary) brackets to make this explicit:
( (A (B C +) *) D /)
Thus, the "*" uses the two values immediately preceding: "A", and the result of the addition.
Similarly, the "/" uses the result of the multiplication and the "D".
 Prefix notation (also known as "Polish notation"): + X Y

Operators are written before their operands. The expressions given above are equivalent
to / * A + B C D
As for Postfix, operators are evaluated left-to-right and brackets are superfluous. Operators act
on the two nearest values on the right. I have again added (totally unnecessary) brackets to
make this clear:
(/ (* A (+ B C) ) D)
Although Prefix "operators are evaluated left-to-right", they use values to their right, and if
these values themselves involve computations then this changes the order that the
operators have to be evaluated in. In the example above, although the division is the first
operator on the left, it acts on the result of the multiplication, and so the multiplication has
to happen before the division (and similarly the addition has to happen before the
multiplication).
Because Postfix operators use values to their left, any values involving computations will
already have been calculated as we go left-to-right, and so the order of evaluation of the
operators is not disrupted in the same way as in Prefix expressions.
The following table briefly tries to show the difference in all three notations
No. Infix Notation Prefix Notation Postfix Notation
1 a+b +ab ab+
2 (a + b) ∗ c ∗+abc ab+c∗
3 a ∗ (b + c) ∗a+bc abc+∗
4 a/b+c/d +/ab/cd ab/cd/+
5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗
6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-
Parsing Expressions
As we have discussed, it is not a very efficient way to design an algorithm or program to parse
infix notations. Instead, these infix notations are first converted into either postfix or prefix
notations and then computed.
16
To parse any arithmetic expression, we need to take care of operator precedence and
associativity also.
Precedence
When an operand is in between two different operators, which operator will take the operand
first, is decided by the precedence of an operator over others.
As multiplication operation has precedence over addition, b * c will be evaluated first. A table
of operator precedence is provided later.
Associativity
Associativity describes the rule where operators with the same precedence appear in an
expression. For example, in expression a + b − c, both + and – have the same precedence,
then which part of the expression will be evaluated first, is determined by associativity of
those operators.
Here, both + and − are left associative, so the expression will be evaluated as (a + b) − c.
Precedence and associativity determine the order of evaluation of an expression. Following is

an operator precedence and associativity table (highest to lowest)
No. Operator Precedence Associativity
1 Exponentiation ^ Highest Right Associative
2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative
3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative
Activity No. 1
Direction: Write the following Java program. Show your solutions and display
17
your output. Every correct solution is equivalent to ten (10) points.
Problem 1. Write a program using Arithmetic operators.
Problem 2: Write a program to compute 4 major exams and display the average.
Problem 3: Write a payroll program that calculates the employee’s weekly

pay after employee’s, name, hourly rate and number of hours worked.
Activity No. 2
18
Stacks operation
Direction: Write a Java program to perform PUSH, POP, PEEP, IsEMPTY operations using
Stack. Display your solutions and output. Every correct code is equivalent to ten (10)
points.
 Create a stack named Virus

 Push the following:[this, is , our, new, normal, life, stay , safe]
 Retrieve the top item of the stack
 Search for the item position of 'normal' in the stack :
 Remove the top item off the stack :
 Display the new contents of stack:
 Check whether the top item is removed or not :
 Check Stack if its empty :
 Remove 2 items off the stack
 Display the new items of the stack
 Clear the stack:
 Check Stack if its empty :
Solutions:
19
Activity No.3
Arithmetic expressions
Direction: Given the following arithmetic expressions, convert, evaluate, and show
stacks from the following. Every correct answer is equivalent to five (5) points.
1. Infix – Prefix :
2*6+4/2+8^2
2. Infix – Postfix :
5^2+6*3–8/4
3. Postfix – Infix:
8 2 ^ 6 6 * + 5 -2
4. Prefix – Infix :
-+3/^525*46
5. Prefix – Infix – Postfix :
+/*5^55555
6. Postfix – Infix – Prefix :
642*+32^3/-
20
Lesson 2
Lesson 2
 learn about binary search trees and examine their representations and study
their different modes of operation including searching for keys and adding
and removing nodes;
 apply the Tree standard data structure; and
 perform and evaluate pre-order, in-order, and post-order traversals.
21
Course Code DATA STRUCTURE AND ALGORITHM
Course Title CC 214
Credit Unit 3
Lesson 2 Week 2
22
Module Topic TREES
Intended Learning  learn about binary search trees and examine their representations and study
Outcomes their different modes of operation including searching for keys and adding and
removing nodes;
 apply the Tree standard data structure; and
 perform and evaluate pre-order, in-order, and post-order traversals.
1. What is a tree and its types?
Study Questions 2. How are binary trees used?
3. Why are binary search trees important?
4. What are the applications of binary search tree?
5. Does a binary search tree have to be balanced?
Required Suggested
Lesson 2. Course Module on Data StructuresData Structures and Algorithms in Java, Second Edition
and Algorithm, College of Computer Copyright © 2003 by Sams Publishing. Robert Lafore
Studies. University of the Visayas
https://everythingcomputerscience.com/books/schoolboek-
Learning Resources
1. In Activity 4, Student will create or draw a BST and perform Tree Traversals like
PreOrder, InOrder, PostOrder, and its Level order.
2. In Activity 5, Student will write a Java program to find the Maximum Depth or
Height the given Tree and display the output.
3. In Activity 6, Student will create a Java Program that performs Tree Traversals
Learning Activity (PreOrder and PostOrder) and display its output.
4. In Activity 7, Student will answer the Multiple-choice test based on Lesson 3,
“Trees”.
 Simulation
Required Output  Source code and output
 Source code and output
 Multiple-Choice Test
 Activity 4 - Simulation
Assessment Tasks  Activity 5 – Source code and output
 Activity 6 – Source code and output
 Activity 7 – Multiple-Choice Test
Assessment Tool Microsoft Teams - Presentation
Creative & Innovative Thinking, Flexibility, Initiative, Problem Solving,
Target Competency Development, & Continual Learning.
SUSANETTE S. ARRIBA JACQUELINE S. PONDOC ALAN A. FELICANO

CRESCENCIA M. CALVARIO
DR. AILEEN B. CATACUTAN
Faculty Librarian OIC
Chapter 2– TREES
What is a Tree?
A tree is consisting of:

• a set of nodes;
23
• a set of edges, each of which connects a pair of nodes;
• each node may have one or more data items;
• each data item consists of one or more fields;
• key field = the field used when searching for a data item;
• multiple data items with the same key are referred to as duplicates; and
• the node at the “top” of the tree is called the root of the tree.
What is a Binary Tree?
A binary tree is made of nodes, where each node contains a "left" reference, a "right"
reference, and a data element.
Binary Tree is a special data structure used for data storage purposes. A binary tree has
a special condition that each node can have a maximum of two children. A binary tree
has the benefits of both an ordered array and a linked list as search is as quick as in a
sorted array and insertion or deletion operation are as fast as in linked list. The topmost
node in the tree is called the root.
Every node (excluding a root) in a tree is connected by a

directed edge from exactly one other node. This node is
called a parent. On the other hand, each node can be
connected to arbitrary number of nodes, called children.
Nodes with no children are called leaves, or external nodes.
Nodes which are not leaves are called internal nodes.
Nodes with the same parent are called siblings.
More tree terminologies:
 The depth of a node is the number of edges from the root to the node.
 The height of a node is the number of edges from the node to the deepest leaf.
 The height of a tree is a height of the root.
 A full binary tree is a binary tree in which each node has exactly zero or two children.
 A complete binary tree is a binary tree, which is completely filled, with the possible
exception of the bottom level, which is filled from left to right.
24
What is a complete binary tree?
A complete binary tree is very special tree, it provides the best possible ratio between
the number of nodes and the height. The height h of a complete binary tree with N
nodes is at most O(log N). We can easily prove this by counting nodes on each level,
starting with the root, assuming that each level has the maximum number of nodes:
25
Following are the important terms with respect to tree.
 Path − Path refers to the sequence of nodes along the edges of a tree.
 Root − The node at the top of the tree is called root. There is only one root per tree and
one path from the root node to any node.
 Parent − Any node except the root node has one edge upward to a node called parent.
 Child − The node below a given node connected by its edge downward is called its child
node.
 Leaf − The node which does not have any child node is called the leaf node.
 Subtree − Subtree represents the descendants of a node.
 Visiting − Visiting refers to checking the value of a node when control is on the node.
 Traversing − Traversing means passing through nodes in a specific order.
 Levels − Level of a node represents the generation of a node. If the root node is at level
0, then its next child node is at level 1, its grandchild is at level 2, and so on.
 Keys − Key represents a value of a node based on which a search operation is to be
carried out for a node.
Advantages of trees
Trees are so useful and frequently used, because they have some very serious advantages:
 Trees reflect structural relationships in the data.
 Trees are used to represent hierarchies.
 Trees provide an efficient insertion and searching.
 Trees are very flexible data, allowing to move subtrees around with minimum effort.
What is a Binary Search Tree?
A BST is a binary tree where nodes are ordered in the following way:
 each node contains one key (also known as data).
 the keys in the left subtree are less than the key in its parent node, in short L < P;
 the keys in the right subtree are greater the key in its parent node, in short P < R;
 duplicate keys are not allowed.
26
In the following tree, all nodes in the left subtree of 10 have keys < 10 while all nodes in
the right subtree > 10. Because both the left and right subtrees of a BST are again
search trees; the above definition is recursively applied to all internal nodes.
Insertion
The insertion procedure is quite similar to searching. We start at the root and recursively
go down the tree searching for a location in a BST to insert a new node. If the element
to be inserted is already in the tree, we are done (we do not insert duplicates). The new
node will always replace a NULL reference.
Exercise.
Given a sequence of numbers: 11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31

Draw a binary search tree by inserting the above numbers from left to right .
27
Searching
Searching in a BST always starts at the root. We compare a data stored at the root with the key
we are searching for (let us call it as toSearch). If the node does not contain the key we proceed
either to the left or right child depending upon comparison. If the result of comparison is
negative we go to the left child, otherwise - to the right child. The recursive structure of a BST
yields a recursive algorithm.
Deletion
Deletion is somewhat trickier than insertion. There are several cases to consider. A node to be
deleted (let us call it as toDelete)
 is not in a tree;
 is a leaf;
 has only one child;
 has two children.
If toDelete is not in the tree, there is nothing to delete. If toDelete node has only one child the
procedure of deletion is identical to deleting a node from a linked list - we just bypass that node
being deleted
28
Deletion of an internal node with two children is less straightforward. If we delete such a node,
we split a tree into two subtrees and therefore, some children of the internal node won't be
accessible after deletion. In the picture below we delete 8:
Deletion strategy is the following: replace the node being deleted with the largest node in the
left subtree and then delete that largest node. By symmetry, the node being deleted can be
swapped with the smallest node is the right subtree.
Exercise.
Given a sequence of numbers: 11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31
Draw a binary search tree by inserting the above numbers from left to right and then show the
two trees that can be the result after the removal of 11.

29
What is a Tree Traversal?
A traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear data
structure, there is no unique traversal. We will consider several traversal algorithms with our
group in the following two kinds:
 depth-first traversal
 breadth-first traversal
There are three different types of depth-first traversals
 PreOrder traversal - visit the parent first and then left and right children.
 InOrder traversal - visit the left child, then the parent and the right child.
 PostOrder traversal - visit left child, then the right child and then the parent.
Level Order Traversal
Level order traversal processes the nodes level by level. It first processes the root, and then its
children, then its grandchildren, and so on. Unlike the other traversal methods, a recursive
version does not exist.
A traversal algorithm is similar to the non-recursive preorder traversal algorithm. The only
difference is that a stack is replaced with a FIFO queue.
In the next picture we demonstrate the order of node visitation. Number 1 denotes the first node
in a particular traversal and number 7 denotes the last node.
30
These common traversals can be represented as a single algorithm by assuming that we visit
each node three times. An Euler tour is a walk around the binary tree where each edge is treated
as a wall, which you cannot cross. In this walk, each node will be visited either on the left, or
below, or on the right.
The Euler tour in which we visit nodes on the left produces a preorder traversal. When we visit
nodes from below, we get an InOrder traversal. And when we visit nodes on the right, we get a
PostOrder traversal.
InOrder Traversal
In this traversal method, the left subtree is visited first, then the root and later the right sub-
tree. We should always remember that every node may represent a subtree itself.
31
If a binary tree is traversed InOrder, the output will produce sorted key values in an ascending
order.
We start from A, and following in-order traversal, we move to its left subtree B. B is also
traversed InOrder. The process goes on until all the nodes are visited.
The output of InOrder traversal of this tree will be:

D→B→E→A→F→C→G
Algorithm:
Until all nodes are traversed

Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.
PreOrder Traversal
In this traversal method, the root node is visited first, then the left subtree and finally the right
subtree.
32
We start from A, and following pre-order traversal, we first visit A itself and then move to its left
subtree B. B is also traversed PreOrder. The process goes on until all the nodes are visited.
The output of pre-order traversal of this tree will be:
A→B→D→E→C→F→G
Algorithm:
Until all nodes are traversed:

PostOrder Traversal
In this traversal method, the root node is visited last, hence the name. First, we traverse the left
subtree, then the right subtree and finally the root node.
33
We start from A, and following PostOrder traversal, we first visit the left subtree B. B is also
traversed PostOrder. The process goes on until all the nodes are visited.
The output of PostOrder traversal of this tree will be:

D→E→B→F→G→C→A
Algorithm:
Until all nodes are traversed −

Example: Perfoming InOrder Traversal
public class BinaryTreeExample {

34
new BinaryTreeExample().run();
}
static class Node {
Node left;
Node right;
int value;
public Node(int value) {
this.value = value;
}
}
public void run() {
Node rootnode = new Node(25);
System.out.println("Building tree with rootvalue " + rootnode.value);
System.out.println("=================================");
insert(rootnode, 11);
System.out.println("Traversing tree in order");
System.out.println("=================================");
printInOrder(rootnode);
}
public void insert(Node node, int value) {
if (value < node.value) {
if (node.left != null) {
insert(node.left, value);
} else {
System.out.println("Inserted " + value + " to left of node " + node.value);
node.left = new Node(value);
}
} else if (value > node.value) {
if (node.right != null) {
insert(node.right, value);
} else {
System.out.println("Inserted " + value + "to right of node " + node.value);
node.right = new Node(value);
}
}
}
public void printInOrder(Node node) {

if (node != null) {
35
printInOrder(node.left);
System.out.println(" Traversed " + node.value);
printInOrder(node.right);
}
}
}
Output:
Building tree with rootvalue 25

=================================
Inserted 11 to left of node 25
Inserted 15to right of node 11
Traversing tree in order
=================================
Traversed 11
Traversed 15
Traversed 16
Traversed 23
Traversed 25
Traversed 79
36
There is only one kind of breadth-first traversal--the level order traversal. This traversal
visits nodes by levels from top to bottom and from left to right.
As an example consider the following tree and its

four traversals:
PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3

InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11
PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8
LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2
Find height or depth of a binary tree
The length of the longest path from the root of a binary tree to a leaf node is the height
of the binary tree. It is, also, known as depth of a binary tree.
 The height of the root is the height of the tree.
 The depth of a node is the length of the path to its root.
We need to find the number of edges between the tree's root and its furthest leaf to
compute the height of tree.
37
In above example, the number of edges between root and furthest leaf is 3. Hence,
height of the tree is 3.
We will compute the height of tree by recursively computing the height of left and right
subtree and then maximum of this two is the height of the tree.
Steps to find height of binary tree
Following are the steps to compute the height of a binary tree:

 if tree is empty then height of tree is 0;
 else Start from the root and;
 find the maximum depth of left sub-tree recursively;
 find the maximum depth of right sub-tree recursively;
maximum depth of this two is (left and right subtree) height of binary tree;
 start with root node, and recursively find maximum depth of left and right
subtree;
 so, our next node is 20. 20 is leaf node. leaf node has no child. height of left
subtree is 1;
 now recursively traverse to right subtree. next node is 30. 30 have both left and
right node;
 first traverse to left side so next node is 27. 27 is leaf node leaf have no more
child. left subtree of 30 will return 1;
 next apply same process for right subtree of node 30. it will return 1;
 height of node 30 is 1. number of edges between root to node 30 is 1.
so total height of right subtree is 1+1=2; and
 here height of right subtree is greater than left subtree. so, height of tree=height
of right subtree=2.
Example:
38
Following is the pseudocode of the algorithm:
int height(Node root) { // return the height of tree
if(root == null)
return -1;
else {
int left=height(root.left);
int right=height(root.right);
if (left > right)
return left+1;
else
return right+1;
}
}
Following is the implementation in Java:

class Node { // construct a node for binary tree
Node left; //left pointer
Node right; //right pointer
int data; // key
Node(int data) {
this.data=data;
left=null;
right=null;
}
}
public class HeightOfBinaryTree {
public static int heightoftree(Node root) { // return the height of tree
if(root==null)
return -1;
else {
int left=heightoftree(root.left); // return the height of leftsubtree
int right=heightoftree(root.right); // return the height of rightsubtree
if (left>right) // compare the height of left and right subtree
return left+1;
else
return right+1;
}
39
}

Node root =new Node(10);
root.left = new Node(20);
root.right = new Node(30);
root.left.left = new Node(40);
root.left.right = new Node(28);
root.right.left =new Node(27);
root.right.right =new Node(50);
root.right.left.right=new Node(29);
System.out.println("Height of given binary tree is "+heightoftree(root));
}
}
Output:
Height of given binary tree is 3
40
Activity No. 4
Direction: Draw the BST and insert the following nodes. Perform Tree traversals
and its level order. Every correct solution is equivalent to fifty (50) points.
a. Given: 43, 10, 79, 90, 12, 54, 11, 9, 50, 89, 62, 34
Solutions:
Preorder:
Inorder:
Postorder:
Level order:
b. Given: S, H, A, N, E, R, I, T, C, U, W, Q, G, K, Y
Solutions:
Preorder:
Inorder:
Postorder:
Level order:
41
Activity No. 5
Direction: Write a program to find the maximum depth or height with this given
Tree and display the output. Perfect answer is equivalent to one hundred (100)
points.
Solution:
42
Activity No. 6
Direction: Create a Java Program that perform Tree Traversals (PreOrder and
PostOrder) and display its output. Perfect answer is equivalent to one hundred
(100) points.
Given:
Building tree with root value 25

====================
Inserted 11 to left of node 25
Inserted 15 to right of node 11
43
Activity No. 7
Direction: Multiple choice. Encircle your best answer. Every correct answer is equivalent to
two (2) pts.
1. In Figure 1, what is the value stored in the parent node of the node containing 30?
A. 10 B. 11 C. 14 D. 40 E. 7 F. None of the above
2. In Figure 1, how many descendants does the root have?
3. In Figure 1, what is the depth of the tree?
4. In Figure 1, how many children does the root have?
5. In Figure 1, what is the order of nodes visited using a pre-order traversal?
A. 1 2 3 7 10 11 14 30 40
B. 1 2 3 14 7 10 11 40 30
C. 1 3 2 7 10 40 30 11 14
D. 14 2 1 3 11 10 7 30 40
F. None of the above
6. In Figure 1, how many leaves does it have?
7. In Figure 1, what is the order of nodes visited using an in-order traversal?
A. 1 2 3 7 10 11 14 30 40
B. 1 2 3 14 7 10 11 40 30
C. 1 3 2 7 10 40 30 11 14
D. 14 2 1 3 11 10 7 30 40
8. In Figure 1, how many of the nodes have at least one sibling?
9. In Figure 1, what is the order of nodes visited using a post-order traversal?
A. 1 2 3 7 10 11 14 30 40 C. 1 2 3 14 7 10 11 40 30
B. 1 3 2 7 10 40 30 11 14 D. 14 2 1 3 11 10 7 30 40
E. None of the above
44
10. In Figure 1, which statement is correct?
A. The tree is neither complete nor full.
B. The tree is complete but not full.
C. The tree is full but not complete.
D. The tree is both full and complete.
11. What is the minimum number of nodes in a full binary tree with depth 3?
12. What is the minimum number of nodes in a complete binary tree with depth 3?
13. Select the one true statement.
A. Every binary tree is either complete or full.
B. Every complete binary tree is also a full binary tree.
C. Every full binary tree is also a complete binary tree.
D. No binary tree is both complete and full.
14. Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T?
15. Select the one FALSE statement about binary trees.
A. Every binary tree has at least one node.
B. Every non-empty tree has exactly one root node.
C. Every node has at most two children.
D. Every non-root node has exactly one parent.
16. In Figure 1, node 3 is
A. root B. leaf C. parent D. ancestor E. tree F. None of the above
17. In Figure 1, nodes 2 and 11 are
I. descendants of 14 II. Ancestors of 14
III. siblings of 14 IV. leaves
A. I only B. I and III only C. I, III and IV only
D. IV only E. II and III only F. None of the above
18. In Figure 1, nodes 14, 11, and 30 are:
A. siblings B. leaves
C. ancestors of 40 D. descendants of 40
E. tree F. None of the above
19. In Figure 1, nodes 11, 10, 30, 40, and 7 are:
A. ancestors of node 14 B. descendants of node 14
C. leaves D. root
E. siblings F. None of the above
20. In Figure 1, nodes 1 and 3 are
I. descendants of 2 II. Ancestors of 2
III. siblings of 2 IV. leaves
A. I only B. I and II only C. I, III and IV only

D. IV only E. II and III only F. None of the above
45
Lesson 3
 solve hashing problems using collision techniques; and
 design and implement an appropriate hashing function for an

application.
46
Course Title CC 214
Credit Unit 3
Lesson 3 Week 3
Module Topic HASHING

Intended Learning At the end of the lesson, the student should be able to:
Outcomes  solve hashing problems using collision techniques; and
 design and implement an appropriate hashing function for an application.
 Why we use hashing in data structure?
Study Questions
 Are hash values unique?
 Where are hash functions used?
 What is hashing collision in Java?
 What are the different hashing techniques?
Required Suggested
Lesson 3. Course Module on Data Data Structures and Algorithms in Java, Second
Structures and Algorithm, College of Edition Copyright © 2003 by Sams
Computer Studies. University of the Publishing. Robert Lafore
Learning Resources Visayas
https://everythingcomputerscience.com/books/
schoolboek-
1. In Activity 8, the student will solve the Hashing problem using Collision
Techniques (Linear probing, double hashing and Quadratic probing)
2. In Activity 9, the student will create a Java Program to Implement Hash
Tables with Linear Probing, Double hashing and Quadratic probing.
Learning Activity
3. In Activity 10, the student will answer the Multiple-Choice test.
 Problem solutions
Required Output  Source code and output
 Multiple Choice
1. Activity 8 - Problem solutions
2. Activity 9 - Source code and output
Assessment Tasks 3. Activity 10- Multiple Choice
Assessment Tool Microsoft teams - Presentation
Target Competency Development & Continual Learning.

JACQUELINE S. PONDOC
SUSANETTE S. ARRIBA CRESCENCIA M. CALVARIO ALAN A. FELICANO
Faculty Program Coordinator OIC
47
Chapter 3 – HASHING
What is Hashing?
In Java, it is a technique that is used for mapping values to the key, which in turn
makes it easy to retrieve values by just entering the key. Hashing is a technique that
is used to uniquely identify a specific object from a group of similar objects.
Some examples of how hashing is used in our lives include:

 In universities, each student is assigned a unique roll number that can be used
to retrieve information about them.
 In libraries, each book is assigned a unique number that can be used to
determine information about the book, such as its exact position in the library
or the users it has been issued to etc.
In both of these examples, the students and books were hashed to a unique number.
The main advantage of using HASHING in java is that it reduces the time complexity
of any program and allows the execution time of essential operation to remain
constant even for the more significant side given.
But the main problem of the hashing function is that it leads to the collision as two or
more keys can point to the same values.
If we want to avoid this chain, hashing is mainly used. So, to insert a value in a hash
table, the main requirement is a hash index which is calculated using the formula.
Assume that you have an object and you want to assign a key to it to makes
searching easy. To store the key/value pair, you can use a simple array like a data
structure where keys (integers) can be used directly as an index to store values.
However, in cases where the keys are large and cannot be used directly as an index,
you should use hashing.
In hashing, large keys are converted into small keys by using hash functions. The
values are then stored in a data structure called hash table. The idea of hashing is to
distribute entries (key/value pairs) uniformly across an array. Each element is
assigned a key (converted key).
By using that key, you can access the element in O(1) time. Using the key, the
algorithm (hash function) computes an index that suggests where an entry can be
found or inserted.
48
Hashing is implemented in two steps:
An element is converted into an integer by using a hash function. This element can be
used as an index to store the original element, which falls into the hash table.
The element is stored in the hash table where it can be quickly retrieved using hashed
key.
 hash = hashfunc(key)
 index = hash % array_size
In this method, the hash is independent of the array size and it is then reduced to an
index (a number between 0 and array size − 1) by using the modulo operator (%).
Hash function
A hash function is any function that can be used to map a data set of an arbitrary
size to a data set of a fixed size, which falls into the hash table. The values returned
by a hash function are called hash values, hash codes, hash sums, or simply hashes.
To achieve a good hashing mechanism, it is important to have a good hash function

with the following basic requirements:
 Easy to compute: It should be easy to compute and must not become an

algorithm in itself.
 Uniform distribution: It should provide a uniform distribution across the hash
table and should not result in clustering.
 Less collisions: Collisions occur when pairs of elements are mapped to the same
hash value. These should be avoided.
Note: Irrespective of how good a hash function is, collisions are bound to occur.
Therefore, to maintain the performance of a hash table, it is important to manage
collisions through various collision resolution techniques.
49
Closed- vs open-bucket hash tables
Closed-bucket hash table:

• Each bucket may be occupied by several entries.
• Buckets are completely separate.
Open-bucket hash table:
• Each bucket may be occupied by at most one entry.
• Whenever there is a collision, displace the new entry to another bucket.
Separate chaining (open hashing)
Separate chaining is one of the most commonly used collision resolution techniques. It
is usually implemented using linked lists. In separate chaining, each element of the
hash table is a linked list. To store an element in the hash table you must insert it into
a specific linked list. If there is any collision (i.e. two different elements have same
hash value) then store both the elements in the same linked list.
General insertion method for open addressing on a table of size N:

x = 1
keyHash = H(k)
index = keyHash
while table[index] !=null:
index=(keyHash + P (k,x)) mod N
x=x+1
insert (k,v) at table [index]
where H(k) is the hash for key k and P(k,x) is the probing function
50
Linear probing (open addressing or closed hashing)
In open addressing, instead of in linked lists, all entry records are stored in the array itself.
When a new entry has to be inserted, the hash index of the hashed value is computed and
then the array is examined (starting with the hashed index). If the slot at the hashed index is
unoccupied, then the entry record is inserted in a slot at the hashed index, else it proceeds in
some probe sequence until it finds an unoccupied slot.
The probe sequence is the sequence that is followed while traversing through entries. In
different probe sequences, you can have different intervals between successive entry slots or
probes.
When searching for an entry, the array is scanned in the same sequence until either the target
element is found or an unused slot is found. This indicates that there is no such key in the
table. The name "open addressing" refers to the fact that the location or address of the item is
not determined by its hash value.
Linear probing is when the interval between successive probes is fixed (usually to 1). Let’s
assume that the hashed index for a particular entry is index. The probing sequence for linear
probing will be:
Formula:
probe [(h(k)) mod M]

probe [(h(k) + i) mod M]
index = index % hashTableSize

index = (index + 1) % hashTableSize
and so on…
In linear probing,
51
 When collision occurs, we linearly probe for the next bucket.
 We keep probing until an empty bucket is found.
Advantage:
 It is easy to compute.

Disadvantage:
 The main problem with linear probing is clustering.
 Many consecutive elements form groups.
 Then, it takes time to search an element or to find an empty bucket.
The cost of a lookup is that of scanning the entries of the selected linked list for the required
key. If the distribution of the keys is sufficiently uniform, then the average cost of a lookup
depends only on the average number of keys per linked list. For this reason, chained hash
tables remain effective even when the number of table entries (N) is much higher than the
number of slots.
For separate chaining, the worst-case scenario is when all the entries are inserted into the
same linked list. The lookup procedure may have to scan all its entries, so the worst-case
cost is proportional to the number (N) of entries in the table.
Implementation of hash table with linear probing
 There are no more than 20 elements in the data set.

 Hash function will return an integer from 0 to 19.
 Data set must have unique elements.
Quadratic Probing
Quadratic probing is similar to linear probing and the only difference is the interval between
successive probes or entry slots. Here, when the slot at a hashed index for an entry record
is already occupied, you must start traversing until you find an unoccupied slot.
The interval between slots is computed by adding the successive value of an arbitrary
polynomial in the original hashed index.
Let us assume that the hashed index for an entry is index and at index there is an occupied
slot. The probe sequence will be as follows:
Formula:
given ( h(k) ) mod M
given ( h(k1 ) + i * i ) mod M
Implementation of hash table with quadratic probing
52
 Hash function will return an integer from 0 to 19.
Double hashing
Double hashing is similar to linear probing and the only difference is the interval
between successive probes. Here, the interval between probes is computed by using
two hash functions.
Let us say that the hashed index for an entry record is an index that is computed by
one hashing function and the slot at that index is already occupied. You must start
traversing in a specific probing sequence to look for an unoccupied slot.
The probing sequence will be:
(hash1(key) + i * hash2(key)) % TABLE_SIZE

Here hash1() and hash2() are hash functions and TABLE_SIZE is size of hash table.
(We repeat by increasing i when collision occurs)
Implementation of hash table with double hashing

 Hash functions will return an integer from 0 to 19.
Insertion of keys into hash table using linear probing as collision resolution
technique
In linear probing technique, collision is resolved by searching linearly in the hash table
until an empty location is found.
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table
of length 10 using open addressing with hash function h(k) = k mod 10 and linear
probing. What is the resultant hash table?
53
Solution: Keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted in hash table as:
For key 12, h(12) is 12%10 = 2. Therefore, 12 is placed at 2nd index in the hash table.
For key 18, h(18) is 18%10 = 8. Therefore, 18 is placed at 8th index in the hash table.
For key 13, h(13) is 13%10 = 3. Therefore, 13 is placed at 3rd index in the hash table.
For key 2, h(2) is 2%10 = 2. However, index 2 is already occupied with 12. Therefore, using
linear probing, 2 will be placed at index 4 as index 2 and 3 are already occupied.
For key 3, h(3) is 3%10 = 3. However, index 3 is already occupied with 13. Therefore, using
linear probing, 3 will be placed at index 5 as index 3 and 4 are already occupied.
Similarly, 23, 5 and 15 will be placed at index 6, 7, 9 respectively.
Therefore, correct option is (C).
Comparison of above three:
 Linear probing has the best cache performance but suffers from clustering. One
more advantage of Linear probing is easy to compute.
 Quadratic probing lies between the two in terms of cache performance and
clustering.
 Double hashing has poor cache performance but no clustering. Double hashing
requires more computation time as two hash functions need to be computed.
Separate Chaining Open Addressing
Keys are stored inside the hash All the keys are stored only inside the
table as well as outside the hash hash table.
table. No key is present outside the hash table.
The number of keys to be stored in The number of keys to be stored in the

the hash table can even exceed the hash table can never exceed the size of
54
size of the hash table. the hash table.
Deletion is easier. Deletion is difficult.
Extra space is required for the pointers

to store the keys outside the hash No extra space is required.
table.
Cache performance is poor.

Cache performance is better.
This is because of linked lists which
This is because here no linked lists are used.
store the keys outside the hash table.
Some buckets of the hash table are

Buckets may be used even if no key maps to
never used which leads to wastage of
those particular buckets.
space.

Activity No. 8
55
Direction: Solve the Hashing problem using Collision Techniques (Linear probing,
Double hashing, and Quadratic probing) Every correct solution is equivalent to fifty
(50) points.
a. Linear Probing
Given: 50, 700, 76, 85, 92, 73, 101 mod 7
b. Double hashing
Given: 76, 93, 40, 47, 10, 55 mod 7
c. Quadratic Probing
Given: 23, 13, 21, 14, 7, 8, 15 mod 7 c1= 2 c2=3
56
Activity No. 9
Direction: Create a Java Program to Implement Hash Tables using Linear

probing, Double hashing and Quadratic probing. Every perfect code is
equivalent to fifty (50) points.
Given : 23, 13, 21, 14, 7, 8, 15 mod 7 c1= 2 c2=3
57
Activity No. 10
Direction: Multiple-Choice: Choose your best answer from the given choices. Every
correct answer is equivalent to two (2) points.
1. Which of the following schemes does quadratic probing come under?

a) rehashing
b) extended hashing
c) separate chaining
d) open addressing
e) none of the above
2. What kind of deletion is implemented by hashing using open addressing?
a) active deletion
b) standard deletion
c) lazy deletion
d) no deletion
3. Which of the following is the correct function definition for quadratic probing?
a) F(i)=i2
b) F(i)=i
c) F(i)=i+1
d) F(i)=i2+1
4. Which among the following is the best technique to handle collision?
a) Quadratic probing
b) Linear probing
c) Double hashing
d) Separate chaining
5. What is the formula used in quadratic probing?
a) Hash key = key mod table size
b) Hash key=(hash(x)+F(i)) mod table size
c) Hash key=(hash(x)+F(i2)) mod table size
d) H(x) = x mod 17
e) None of the above
6. The condition that occurs when a hash function maps two or more distinct search
keys into the same location is called a(n) ______.
a) disturbance
b) collision
c) rotation
d) congestion
58
7. What is known as a collision-resolution scheme that searches the hash table
sequentially, starting from the original location specified by the hash function, for an
unoccupied location?
a) Linear probing
b) Quadratic probing
c) Double hashing
d) Separate chaining
8. How the load factor of a hash table is calculated?
a) table size + current number of table items
b) table size – current number of table items
c) current number of table items * table size
d) current number of table items / table size
9. What is the hash function used in the division method?
a) h(k) = k/m
b) h(k) = k mod m
c) h(k) = m/k
d) h(k) = m mod k
10. What is the best technique when the amount of data is not well-known?
a) double hashing
b) separate chaining
c) linear probing
d) quadratic probing
59
Lesson 4
 implement and compare different sorting algorithms;
 understand graph terminology and algorithms; and
 represent a graph as adjacency matrix, adjacency list.
60
Course Title CC 214
Credit Unit 3
Lesson 4 Week 4
Module Topic SORTING

Intended Learning  implement and compare different sorting algorithms;
Outcomes  understand graph terminology and algorithms; and
 represent a graph as adjacency matrix, adjacency list.
1. What is sorting algorithm?
Study Questions
2. What are the different types of sorting?
3. What is the importance of sorting in data structure?
4. What is a graph data structure?
5. How graph plays a vital role in our daily lives?
Required Suggested
Lesson 4. Course Module on Data Data Structures and Algorithms in Java, Second Edition
Structures and Algorithm, College of Copyright © 2003 by Sams Publishing. Robert Lafore
Computer Studies. University of the
Visayas https://everythingcomputerscience.com/books/
Learning Resources
schoolboek-data_structures_and_algorithms_in_java.pdf
1. Activity 11, the student will create a Java program to implement any sort algorithm.
Learning Activity
2. Activity 12, the student will answer the Multiple-Choice test.
Required Output 1. Source Code and output.
2. Multiple choice test.
Activity 11 - Create a Java program.
Assessment Tasks Activity 12 - Multiple-Choice test.
Assessment Tool Microsoft Teams – Presentation

Target Competency Development, & Continual Learning.
SUSANETTE S. ARRIBA JACQUELINE S. PONDOC ALAN A. FELICANO

CRESCENCIA M. CALVARIO
Faculty Program Coordinator OIC
61
Chapter 4 – SORTING
What is Sorting?
Sorting refers to arranging data in a particular format. Sorting algorithm

specifies the way to arrange data in a particular order. Most common orders
are in numerical or lexicographical order.
The importance of sorting lies in the fact that data searching can be
optimized to a very high level, if data is stored in a sorted manner. Sorting
is also used to represent data in more readable formats.
Following are some of the examples of sorting in real-life scenarios −

 Telephone Directory − the telephone directory stores the telephone
numbers of people sorted by their names, so that the names can be
searched easily.
 Dictionary − the dictionary stores words in an alphabetical order so
that searching of any word becomes easy.
In-place Sorting and Not-in-place Sorting

Sorting algorithms may require some extra space for comparison and
temporary storage of few data elements. These algorithms do not require
any extra space and sorting is said to happen in-place, or for example,
within the array itself.
This is called in-place sorting. Bubble sort is an example of in-place

sorting.
However, in some sorting algorithms, the program requires space which is
more than or equal to the elements being sorted. Sorting which uses equal
or more space is called not-in-place sorting. Merge-sort is an example of
not-in-place sorting.
Stable and Not Stable Sorting

If a sorting algorithm, after sorting the contents, does not change the
sequence of similar content in which they appear, it is called stable
sorting.
62
If a sorting algorithm, after sorting the contents, changes the sequence of
similar content in which they appear, it is called unstable sorting.
Stability of an algorithm matters when we wish to maintain the sequence of

original elements, like in a tuple for example.
Adaptive and Non-Adaptive Sorting Algorithm
A sorting algorithm is said to be adaptive, if it takes advantage of already

'sorted' elements in the list that is to be sorted. That is, while sorting if the
source list has some element already sorted, adaptive algorithms will take this
into account and will try not to re-order them.
A non-adaptive algorithm is one which does not take into account the elements
which are already sorted. They try to force every single element to be re-
ordered to confirm their sortedness.
Important Terms
Some terms are generally coined while discussing sorting techniques, here is a
brief introduction to them −
Increasing Order
 A sequence of values is said to be in increasing order, if the successive
element is greater than the previous one. For example, 1, 3, 4, 6, 8, 9 are
in increasing order, as every next element is greater than the previous
element.
 Decreasing Order
A sequence of values is said to be in decreasing order, if the successive
element is less than the current one. For example, 9, 8, 6, 4, 3, 1 are in
decreasing order, as every next element is less than the previous
element.
63
 Non-Increasing Order
A sequence of values is said to be in non-increasing order, if the
successive element is less than or equal to its previous element in the
sequence. This order occurs when the sequence contains duplicate values.
For example, 9, 8, 6, 3, 3, 1 are in non-increasing order, as every next
element is less than or equal to (in case of 3) but not greater than any
previous element.
 Non-Decreasing Order
A sequence of values is said to be in non-decreasing order, if the
successive element is greater than or equal to its previous element in the
sequence. This order occurs when the sequence contains duplicate values.
For example, 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next
element is greater than or equal to (in case of 3) but not less than the
previous one.
What is Bubble Sort Algorithm?

Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-
based algorithm in which each pair of adjacent elements is compared and the
elements are swapped if they are not in order. This algorithm is not suitable for
large data sets as its average and worst case complexity are of Ο(n 2) where n is
the number of items.
How Bubble Sort Works?

We take an unsorted array for our example. Bubble sort takes Ο(n 2) time so we're
keeping it short and precise.
Bubble sort starts with very first two elements, comparing them to check which one
is greater.
In this case, value 33 is greater than 14, so it is already in sorted locations. Next,
we compare 33 with 27.
64
We find that 27 is smaller than 33 and these two values must be swapped.
The new array should look like this −
Next we compare 33 and 35. We find that both are in already sorted positions.
Then we move to the next two values, 35 and 10.
We know then that 10 is smaller 35. Hence they are not sorted.
We swap these values. We find that we have reached the end of the array. After
one iteration, the array should look like this −
To be precise, we are now showing how an array should look like after each
iteration. After the second iteration, it should look like this −
Notice that after each iteration, at least one value moves at the end.
And when there's no swap required; bubble sorts learn that an array is completely
sorted.
65
Data Structure and Algorithms Insertion Sort
This is an in-place comparison-based sorting algorithm. Here, a sub-list is

maintained which is always sorted. For example, the lower part of an array
is maintained to be sorted. An element which is to be inserted in this sorted
sub-list, has to find its appropriate place and then it has to be inserted
there.
Hence the name, insertion sort.

The array is searched sequentially and unsorted items are moved and
inserted into the sorted sub-list (in the same array). This algorithm is not
suitable for large data sets as its average and worst case complexity are of
Ο(n2), where n is the number of items.
How Insertion Sort Works?
We take an unsorted array for our example.
Insertion sort compares the first two elements.
It finds that both 14 and 33 are already in ascending order. For now, 14 is
in sorted sub-list.
Insertion sort moves ahead and compares 33 with 27.
And finds that 33 is not in the correct position.
66
It swaps 33 with 27. It also checks with all the elements of sorted sub-list.
Here we see that the sorted sub-list has only one element 14, and 27 is
greater than 14. Hence, the sorted sub-list remains sorted after swapping.
By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with

10.
These values are not in a sorted order.
So we swap them.
However, swapping makes 27 and 10 unsorted.
Hence, we swap them too.
Again we find 14 and 10 in an unsorted order.
We swap them again. By the end of third iteration, we have a sorted sub-list
of 4 items.
67
This process goes on until all the unsorted values are covered in a sorted sub-
list. Now we shall see some programming aspects of insertion sort.
Algorithm
Now we have a bigger picture of how this sorting technique works, so we
can derive simple steps by which we can achieve insertion sort.
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
Data Structure and Algorithms Selection Sort
Selection sort is a simple sorting algorithm. This sorting algorithm is an in-

place comparison-based algorithm in which the list is divided into two parts,
the sorted part at the left end and the unsorted part at the right end.
Initially, the sorted part is empty and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with
the leftmost element, and that element becomes a part of the sorted array.
This process continues moving unsorted array boundary by one element to
the right.
This algorithm is not suitable for large data sets as its average and worst
case complexities are of Ο(n2), where n is the number of items.
How Selection Sort Works?
Consider the following depicted array as an example.
For the first position in the sorted list, the whole list is scanned sequentially.
The first position where 14 is stored presently, we search the whole list and
find that 10 is the lowest value.
68
So we replace 14 with 10. After one iteration 10, which happens to be the
minimum value in the list, appears in the first position of the sorted list.
For the second position, where 33 is residing, we start scanning the rest of
the list in a linear manner.
We find that 14 is the second lowest value in the list and it should appear at
the second place. We swap these values.
After two iterations, two least values are positioned at the beginning in a
sorted manner.
The same process is applied to the rest of the items in the array.
Following is a pictorial depiction of the entire sortin g process
69
Now, let us learn some programming aspects of selection sort.
Algorithm
Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted
70
What is a Graph?
A graph is a data structure for storing connected data like a network of people on

a social media platform.
A graph consists of vertices and edges. A vertex represents the entity (for

example, people) and an edge represents the relationship between
entities (for example, a person's friendships).
Graphs are used to represent many real-life applications: Graphs are used to
represent networks. The networks may include paths in a city or telephone
network or circuit network. Graphs are also used in social networks like linkedIn,
Facebook. For example, in Facebook, each person is represented with a vertex(or
node). Each node is a structure and contains information like person id, name,
gender, and locale. See this for more applications of graph.
Following is an example of an undirected graph with 5 vertices.
Let's define a simple Graph to understand this better:
71
Here, we've defined a simple graph with five vertices and six edges. The circles
are vertices representing people and the lines connecting two vertices are edges
representing friends on an online portal.
Directed Graph
The graph we've defined so far has edges without any direction. If these edges
feature a direction in them, the resulting graph is known as a directed graph.
An example of this can be representing who send the friend request in a friendship
on the online portal:
Here, we can see that the edges have a fixed direction. The edges can be bi-
directional as well.
Weighted Graph
Again, our simple graph has edges which are unbiased or unweighted. If instead
these edges carry relative weight, this graph is known as a weighted graph.
72
An example of a practical application of this can be representing how relatively old
is a friendship on the online portal:
Here, we can see that the edges have weights associated with them. This provides
a relative meaning to these edges.
Graph Representations
A graph can be represented in different forms like adjacency matrix and adjacency
list. Each one has their pros and cons in a different set-up.
We'll introduce these graph representations in this section.
Adjacency Matrix
An adjacency matrix is a square matrix with dimensions equivalent to the

number of vertices in the graph.
The elements of the matrix typically have values ‘0' or ‘1'. A value of ‘1'
indicates adjacency between the vertices in the row and column and a value of ‘0'
otherwise.
73
Let's see how the adjacency matrix looks like for our simple graph from the
previous section:
This representation is fairly easier to implement and efficient to query as well.

However, it's less efficient with respect to space occupied.
What is an Adjacency List?
An adjacency list is nothing but an array of lists. The size of the array is
equivalent to the number of vertices in the graph.
The list at a specific index of the array represents the adjacent vertices of the
vertex represented by that array index.
Let's see what the adjacency list looks like for our simple graph from the previous
section:
74
This representation is comparatively difficult to create and less efficient to query.
However, it offers better space efficiency.
Traversing a Graph
Now that we have graph data structure and functions to create and update it
defined, we can define some additional functions for traversing the graph. We
need to traverse a graph to perform any meaningful action, like search within the
graph.
There are two possible ways to traverse a graph, depth-first traversal and
breadth-first traversal.
Depth-First Traversal
A depth-first traversal starts at an arbitrary root vertex and explores vertices as

deeper as possible along each branch before exploring vertices at the same
level.
Breadth-First Traversal
Comparatively, a breadth-first traversal starts at an arbitrary root vertex and explores

all neighboring vertices at the same level before going deeper in the graph.
75
Activity No. 11
Direction: Write a Java program to implement bubble sort algorithm and sort integer
array using this method. Perfect answer is equivalent to one hundred (100) points.
Solutions:
Output:
76
Activity No. 12
Direction: Identify the answers for the statements below by filling in the gaps provided
before each number. Each correct answer is equivalent to two (2) points.
____________1. Which refers to the starts at an arbitrary root vertex and explores vertices
as deeper as possible along each branch before exploring vertices at the same time.
____________2. Which refers to a square matrix with dimensions equivalent to the
number of vertices in the graph.
____________3. Which refers to the starts at an arbitrary root vertex and explores all
neighboring vertices at the same level before going deeper in the graph.
____________4. Which refers to a data structure for storing connected data like a network
of people on a social media platform.
____________5. Which refers to the graph has edges without any direction.
____________6. Which refers to the sequence of values, if the successive element is
greater than the previous one.
____________7. Which refers to edges that are unbiased or unweighted.
____________8. Which refers to a graph that can be represented in different forms like
adjacency matrix and adjacency list.
____________9. Which refers to a sequence of values, if the successive element is less
than the current one.
____________10. Which refers to represent networks, may include paths in a city or
telephone network or circuit network.
____________11. Which refers to the sorting algorithm is in place comparison-based
algorithm in which the list is divided into two parts, the sorted part at the left end and the
unsorted part at the right end.
____________12. Which refers to the arrangement of data in a particular format.
____________13. Which refers to the sorting algorithm, after sorting the contents, does
not change the sequence of similar content in which they appear.
____________14. Which refers to the sorting algorithm is comparison based algorithm in
which each pair of adjacent elements is compared and the elements are swapped if they are
not in order.
____________15. Which refers to an example of in-place sorting.
77
References
Data Structures and Algorithms in Java, Second Edition Copyright © 2003 by Sams Publishing. Robert Lafore
https://everythingcomputerscience.com/books/schoolboek-data_structures_and_algorithms_in_java.pdf
Silva-Coira, F., Paramá, J. R., Ladra, S., López, J. R., & Gutiérrez, G. (2020). Efficient processing of raster and
vector data. PLoS ONE, 15(1), 1–35. https://doi.org/10.1371/journal.pone.0226943
Mutluergil, S. O., & Tasiran, S. (2019). A mechanized refinement proof of the Chase-Lev deque using a proof
system. Computing, 101(1), 59–74.
https://doi.org/10.1007/s00607-018-0635-4
Mhaskar, N., & Smyth, W. F. (2018). Frequency Covers for Strings. Fundamenta Informaticae, 163(3), 275–289.
https://doi.org/10.3233/FI-2018-1744
Santos, P. G. 1. phillipgs@gmail. co., Ruas, P. H. B. 1. juliocesar. neves@gmail. co., Neves, J. C. V. 1.

sergiomariano@gmail. co., Silva, P. R. 2. paula. csraissa@gmail. co., Dias, S. M. 1,3. zarate@pucminas. b.,
Zárate, L. E. 1. song@pucminas. b., & Song, M. A. J. . (2018). ImplicPBDD: A New Approach to Extract Proper
Implications Set from High-Dimension Formal Contexts Using a Binary Decision Diagram †. Information (2078-
2489), 9(11), 266. https://doi.org/10.3390/info9110266
Dürr, C., & Vollmer, H. (2018). Preface of STACS 2016 Special Issue. Theory of Computing Systems, 62(1), 1–3.
https://doi.org/10.1007/s00224-017-9830-5
Alstrup, S., Dahlgaard, S., & Knudsen, M. B. T. (2017). Optimal Induced Universal Graphs and Adjacency
Labeling for Trees. Journal of the ACM, 64(4), 1–22. https://doi.org/10.1145/3088513
Edelkamp, S., Elmasry, A., & Katajainen, J. (2017). Optimizing Binary Heaps. Theory of Computing
Systems, 61(2), 606–636.
https://doi.org/10.1007/s00224-017-9760-2
Best, E., Devillers, R., & Schlachter, U. (2018). Bounded choice-free Petri net synthesis: algorithmic issues. Acta
Informatica, 55(7), 575–611.
https://doi.org/10.1007/s00236-017-0310-9
Calciu, I., Sen, S., Balakrishnan, M., & Aguilera, M. K. (2018). How to implement any concurrent data
structure. Communications of the ACM, 61(12), 97–105.
https://doi.org/10.1145/3282506
Alstrup, S., Dahlgaard, S., & Knudsen, M. B. T. (2017). Optimal Induced Universal Graphs and Adjacency
Labeling for Trees. Journal of the ACM, 64(4), 1–22. https://doi.org/10.1145/3088513
Edelkamp, S., Elmasry, A., & Katajainen, J. (2017). Optimizing Binary Heaps. Theory of Computing
Systems, 61(2), 606–636. https://doi.org/10.1007/s00224-017-9760-2
Rodríguez-González, A. Y., Martínez-Trinidad, J. F., Carrasco-Ochoa, J. A., Ruiz-Shulcloper, J., Alvarado-Mentado,

M., Pinto, D., & Singh, V. (2019). Frequent similar pattern mining using non Boolean similarity functions. Journal
of Intelligent & Fuzzy Systems, 36(5), 4931–4944. https://doi.org/10.3233/JIFS-179040
Mutluergil, S. O., & Tasiran, S. (2019). A mechanized refinement proof of the Chase-Lev deque using a proof
system. Computing, 101(1), 59–74. https://doi.org/10.1007/s00607-018-0635-4
Van, T. T., & Le, T. M. (2018). Content‐based image retrieval based on binary signatures cluster graph. Expert
Systems, 35(1), 1. https://doi.org/10.1111/exsy.12220
78
Images
https://www.geeksforgeeks.org/top-algorithms-and-data-structures-for-competitive-programming/
https://www.geeksforgeeks.org/hashing-data-structure/
https://dev.to/javinpaul/how-to-implement-inorder-traversal-in-a-binary-search-tree-1787
https://brilliant.org/wiki/sorting-algorithms/
79

Course Packet - CC 214 (Data Structures and Algorithms)

Uploaded by

Copyright:

Available Formats

Course Packet - CC 214 (Data Structures and Algorithms)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Course Packet - CC 214 (Data Structures and Algorithms)

Uploaded by

Copyright:

Available Formats

Disclaimer Statement:

College of Computer Studies

1 Basic data structure 7

Course Developer Susanette A. Dakay

Design/Media Specialist Emily L. Ong

Flexible Learning Course Syllabus

II. Instructor's Information

III. Course Syllabus

Data Structure & Algorithms -

BASIC DATA STRUCTURE

At the end of the lesson, the student should be able to:

 evaluate and convert between prefix, infix, and postfix notation.

Module Topic THE BASIC STRUCTURE

 evaluate and convert between prefix, infix, and postfix notation.

Prepared by: Reviewed by: Approved for use:

Data Structures and Algorithms – Java Arrays

Following are the important terms to understand the concept of Array.

Advantages of Java Array:

Disadvantages of Java Array:

Below are the examples which show how to declare an array:

int[] array_name; //declares an array of integers

int[] array_name = new int[5];

Here is an example that creates an array that has 5 elements.

Java Array Initialization

Output for the given program:

Java Array Usage

int month = months[4]; //get the 5th month (May)

//use the length attribute to get the number of elements in an array

for (int i = 0; i < months.length; i++ ) {

Here, we have taken an array of months which is,

int[][] a2 = new int[10][5];

In this example, "int[][] a2 = new int[10][5];" notation shows a two-dimensional array. It

Example: Creating twoDimensional array

Example: Write a Java program to sum values of an array

public class Example {

Data Structures and Algorithms – Stacks

Stack() : This constructor is used to create an object of empty stack.

These are as follows:

Stack stack = new Stack();

//check whether the stack is empty or not

Is stack empty ? false

Data Structure - Expression Parsing

These notations are:

 Postfix notation (also known as "Reverse Polish notation"): X Y +

 Prefix notation (also known as "Polish notation"): + X Y

1 a+b +ab ab+

4 a/b+c/d +/ab/cd ab/cd/+

6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-

Precedence and associativity determine the order of evaluation of an expression. Following is

1 Exponentiation ^ Highest Right Associative

2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative

3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative

Problem 1. Write a program using Arithmetic operators.

Problem 3: Write a payroll program that calculates the employee’s weekly

 Create a stack named Virus

5. Prefix – Infix – Postfix :

6. Postfix – Infix – Prefix :

At the end of the lesson, the student should be able to:

 apply the Tree standard data structure; and