Data Structure

Recalling previous lessons on FOP

Module 1

Data Structure: is an arrangement of data in a computer’s memory or disk storage space.

Module 2

Tower of Hanoi = Tower of Brahma

Only one disk can be moved at a time.
No disk can be placed on top of the smaller disk.

MinMoves = 2ⁿ-1

Fibonacci Series - Leonardo of Pisa

Count all the (overall) pairs in rabbits.

Difference of Recursive and Iterative Code:

Iterative - have more efficiency in larger values of ‘n’. Iterative uses loops.

Recursive - function calls itself to calculate the Fibonacci numbers. Concise and elegant but can suffer from performance issues.

Recursive Code:

public static int FibonacciRecursive(int n)

{

if (n <= 1)

return n;

else

return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);

}

Iterative Code:

public static int FibonacciIterative(int n)

{

if (n <= 1)

return n;

int a = 0;

int b = 1;

for (int i = 2; i <= n; i++)

{

int temp = a;

a = b;

b = temp + b;

}

return b;

}

Euclid’s Algorithm

Activity 1 Prelim

A programming language that uses a strong abstraction from details of the computer.
Answer: High Level Language
A type of access modifier wherein the member can only be accessed by code in the same class or struct.
Answer: Private
Method in C# that compares two string and returns Boolean value as output.
Answer: String.equals
A programming language that provides little or no abstraction from a computer's instruction.
Answer: Low Level Language
A numeric value that is used to identify an object during equality testing.
Answer: Hash code
Returns the index position of first occurrence of specified character.
Answer: indexOf()
Converts String into Upper case based on rules of the current culture.
Answer: ToUpper
A type of access modifier wherein the member can be accessed by any other code in the same assembly or another assembly that references it.
Answer: Public
Which of these methods of class String is used to remove leading and trailing whitespaces?
Answer: Trim()
It is a string property that returns length of string.
Answer: Length()

Module 3

How to declare an Array?

Array: arrayType [] arrayName;

2D Array: arrayType [,] arrayName;

Multi: arrayType [, ,] arrayName;

Row: Left to right
Column: Downwards

Specifying size in array:

int [] ipoints; to int [] ipoints = new int [7];

How to initialize an Array?

arrayType [] arrayName = new arrayType [arrayLength/arraySize] {value list};

int [] ipoints = new int [7] {3, 7, 20, 54, 9, 12, 8};

Refers to accessing or retrieving elements from an array using their index values.

Answer: Referencing

How to reference an array?

int firstNumber = numbers[0]; // Retrieves the first element (index 0)

int thirdNumber = numbers[2]; // Retrieves the third element (index 2)

Quiz 2 (Arrays)

What are the 2 subscripts indexes of 2D?
Answer: column and row
What are the things need to be familiar with dealing with arrays?
Answer: Declaring, Initializing, Referencing
An element that is idea used for arrays with large sizes.
Answer: Loop
It is used if you want to access and display a single array element or a small list of elements.
Answer: Manual Referencing
A group of variables that has similar data type referenced by a common name.
Answer: Array
What are the two things that 2D and multidimensional are similar?
Answer: Dimension and Manipulation

Module 4: String Manipulation

String - is a sequence of characters stored in a certain address in memory. Enclosed with double quotation marks.

Declaring a string variable:

string myschool = “Adamson U”;

Manipulations

Returns a reference to this instance of String.
Answer: Clone()
Function converts string to uppercase.
Answer: ToUpper()
Function converts string to lower case.
Answer: ToLower()
Removes extra spaces from the beginning and the ending of string.
Answer: Trim()
Returns bool value, it checks whether specified string or character exist in string or not.
Answer: Contains()
Converts a string to array of character.
Answer: ToCharArray()
Returns substring of a string.
Answer: Substring()
Checks whether the first number of a string is same as specified character. It returns bool value.
Answer: StartsWith()
Splits the string on the supplied value. It returns the array of string.
Answer: Split()
Determine whether the end of this string instance matches a specified string.
Answer: EndsWith()
Reports the zero-based index of the first occurrence of specified Unicode character string within this instance. The method returns -1 if the character or string is not found in this instance.
Answer: IndexOf()
Reports the zero-based index of the last occurrence of specified Unicode character string within this instance. The method returns -1 if the character or string is not found in this instance.
Answer: LastIndexOf()
Returns a new string in which all occurrence of a specified Unicode character or string in the current string are replaced with another specified Unicode character or string.
Answer: Replace()

Module 4/5: SETS

Sets: A set is a data structure that can store any number of unique values in any order you so wish. Sets are different from arrays in the sense that they only allow non-repeated, unique values within them.

Roster Method: Listing the elements

A set must be properly defined so that we can find out whether an object is a member of the set.
The set can be defined by listing all its elements, separated by commas ( , ) and enclosed within braces ( { } ). This is called the Roster Method.

Example:

B = {2, 4, 6, 8, 10}; X = {a, b, c, d, e}

Set-builder Notation: Describing the elements

The set can be defined, where possible, by describing the elements.

Example:

S = {x : x is an integer, x > – 5}

“This is read as: “S is the set of elements x such that x is an integer greater than –5.”

• We should describe a certain property which all the elements x, in a set, have in common so that we can know whether a particular thing belongs to the set.

B = {2, 4, 6, 8, 10}; Y = {x ∈ B| x > 0 }

Module 6: STACKS

STACK - linear data structure wherein adding and removing of an element takes place on top of the stack. It follows the LIFO (Last In First Out) method.

Real Life Examples:

Pile of Plates
Deck of Cards
Cargo Containers

Stack Operations

PUSH Operation - inserting an element in the stack.
Since there’s only one position at which the inserted — Top new element is inserted at new element can be of the stack, the top of the stack.
POP Operation - removal of an element in the stack.
Again, since we only have access to the element at the top of the stack, there’s one element that we can only remove. We just remove the top of the stack.

PEEK Operation - allows the user to see the element on the top of the stack.
The stack is not modified in any manner in this operation.
isEmpty Operation - checks if the stack is empty or not.
isEmpty() conventionally returns a boolean value: True if size is 0, else False.

Stack Implementation

Stack Implementation: 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.

• These notations are:

• Infix Notation

• Prefix (Polish) Notation

• Postfix (Reverse-Polish) Notation

MODULE 7: QUEUE

Another common data structure that places elements in a sequence, similar to a stack. It uses the FIFO method (First In First Out), by which the first element that is enqueued will be the first one to be dequeued.

Real Life Examples: