GisoBuki Binusian

today lesson is gonna talk about heap ,tries ,hashing that will be explained by the lecturer pak sky.

Heap
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the heap.

There are 3 kind of heap

1.Max-heap
is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.The value of the root have to be greater than any other nodes.

2.Min-Heap
is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.The value of the root have to be smallest than any other nodes.

Min-Max Heap
is a double-ended priority queue implemented as a modified version of a binary heap. Like a binary heap, a min-max heap is represented as a complete binary tree.

Heap Majorly has 3 operations
-Insert Oper­a­tion
-Delete Oper­a­tion
-Extract-Min (OR Extract-Max)/not discussed on today lecture.

Insertion:
1. Add the element at the bottom leaf of the Heap.
2. Perform the Bubble-Up operation.
3.All Insert operations must perform the bubble-up operations (do it recursively).

Bubble-up Operation:

1.If inserted element is smaller than its parent node in case of Min-Heap OR greater than its parent node in case of Max-Heap, swap the element with its parent.
2.Keep repeating the above step, if node reaches its correct position, STOP.

Delete Operation:
1.Find the index for the element to be deleted.
2.Take out the last element from the last level from the heap and replace the index with this element 3.Perform Sink-down.

Sink-Down Operation:
1.If replaced element is greater than any of its child node in case of Min-Heap OR smaller than any if its child node in case of Max-Heap, swap the element with its smallest child(Min-Heap) or with its greatest child(Max-Heap).
2.Keep repeating the above step, if node reaches its correct position, STOP.

Tries
also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are not necessarily associated with every node. Rather, values tend only to be associated with leaves, and with some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.

Hashing
a hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

 

today lesson is gonna more talk about Red Black Tree(RBT) and 2-3 tree that will be explained by the lecturer miss rulyna.

red–black tree(RBT) is a kind of self-balancing binary search tree. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

RBT rules

1.Insertion
If you want to insert a node in a RBT is very similar insertion like BST only a minor changes like :

1. A root of a node have to be black.
2. the leaf of a RBT have to had red color
   *if you don’t follow these rules your tree must have a violation that have to be fixed in order to balance the tree.

2.Delete
to delete the nodes is use the same principal like BST but the difference is you have to follow those violation rules to balance out your RBT.

Clik here to see RBT visualization

2-3 Tree is a tree data structure, where every node with children (internal node) has either two children (2-node) and one data element or three children (3 nodes) and two data elements. According to Knuth, “a B-tree of order 3 is a 2-3 tree.” Nodes on the outside of the tree (leaf nodes) have no children and one or two data elements. 2−3 trees were invented by John Hopcroft in 1970. 2-3 tree is not categorized as a BST tree.

Rules:
1. 2-3 has 3 key in 1 node.
2. Max child of the tree is 3.
3.The calculation is (n-1/2).
4.every leaf have the same level
Insertion

to insert the nodes first you must determine witch key should be put correctly :
1.smallest amount key on the left.
2.the larger amount key put to the right.
3.the middle key is the amount between the smallest and the large ones

after the key is full you can add another node .
Note: to balance the 2-3 tree you need to pull some of the amount of key in the root to balance out the tree or you can push the amount of key to the root to fill the root node and balance it out .

Delete
To delete a tree first you must find the replacement for the deletion of the tree
1.If the leaf node is 2 – node , if the sibling is a 3 – node , then take one key from one parent and one sibling in a push data from node to a parent .
2.If the leaf node is a 3 – node the the key from the first parent.
3.If the sibling of the leaf node is a 3 – node , then do push 1 data from the sibling to parent.
4.If the sibling of the leaf node is 2 – node , then the parent should be changed to a 2- node , and then do a merge between leaf nodes and sibling nodes.

do it until the 2-3 tree is balance

Today topic is divided by 2 topic the first topic is AVL Tree lectured by Pa Sky and the second is lectured by Selvakumar Manickam

Before we know what AVL tree is first we have to know what is balanced binary search tree.

First Topic

Balanced Binary Search Tree

A self-balancing binary search tree or height-balanced binary search tree is a binary search tree (BST) that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically.

example:

Why do we have to learn Balanced Binary Tree?

Most operations on a BST take time proportional to the height of the tree, so it is desirable to keep the height small.

Self-balancing binary trees solve this problem by performing transformations on the tree at key times, in order to reduce the height. Although a certain overhead is involved, it is justified in the long run by ensuring fast execution of later operations.

AVL Tree

AVL tree (Georgy Adelson-Velsky and Evgenii Landis’ tree, named after the inventors) is a self-balancing binary search tree. It was the first such data structure to be invented.[2] In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

well to put it simple on how to use a avl tree is to compare the nodes that we want to input and put it in the left side or the right side depends of it’s value of input nodes.

Class AVL Tree supports the following functionality:
1.insertion of a new entry in the tree.
2.removal of any entry in the tree.
3.search for any entry in the tree.
4.”sanity check” for the tree (sanity check is a basic test to quickly evaluate whether a claim or the result of a calculation can possibly be true)
5. 4 various tree traversals
– preorder
– inorder
– postorder
– inorder non-recursive.

How to make a unbalanced BST into Balance BST(AVL)

the main point to make a AVL Tree is to minimum the height of the BST and make the BST stabilize own it self .

1.Calculate the height

-Max (HeightLeft , HeightRight)+1

-Leaf that doesn’t have anymore branch = NULL or 0

2.Balance factor

-Balance factor = HeightLeft – HeightRight
Note:
– if the balance factor is equal to  (-1) that means your balance tree is advancing to the right.
-if the balance factor is equal to (+1) that means that your balance factor is advancing to the left.
-if the balance factor is equal to (0) that means that your balance factor is in balance position
*to be categorized on balance factor the calculation has to be at a number of (-1,0,1)

3.Rotation

Rotation is needed if the total of balance factor is not equal to (-1,0,1)

example

from this picture we know that after we insert the number 7 on the BST the tree becomes unbalanced.

To properly rotate a BST Tree in to a Balanced Tree(AVL)  we hav to the these two rotations :
1.Single Rotation

A single rotation is required when the node just added is on the right sub-tree of the right node of the unbalanced node or the left sub-tree of the left node of the unbalanced node.

2.Double Rotation

A double rotation is required when the node just added is on the right sub-tree of the left node of the unbalanced node or the left sub-tree of the right node of the unbalanced node.

4.Delete

to delete a AVL tree is a little similar like deleting a BST Tree but after you delete your nodes make sure you balance the tree again so the tree stays AVL not BST

Thing you have to watch when you delete a node on AVL tree

-Check the height and the balance factor.
-do a rotation if necessary

These examples have been greatly simplified from the actual amount of work required. All of these examples could have more children on almost every node, which would require a greater deal of reassigning pointers.

For more understanding how these concept that i have shown you open here
->AVL Tree Visualzation

Second Topic

As for the second topic the lesson is about the general meaning of data structure , introduction of tree , and discuss about binary tree. These topics is lectured by a guest lecture named Selvakumar Manickam .

for these materials it generally talks about the point of studying data structure as the basic for studying Tree and the principal of studying all kind of tree in programming for more detailed information you can see my older post below:

Summary Session 1 Data Structures
(The general meaning of Data Structures in computer Programming)
Summary Session 4 Data Structures
(Tree indroduction)
Summary Session 5 Data Structures
(More information about tree)

Today lesson is gonna more to talk about binary tree that will bi explain by the lecturer pak sky

Binary Tree

A binary tree is made of nodes, where each node contains a “left” pointer, a “right” pointer, and a data element. The “root” pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller “subtrees” on either side. A null pointer represents a binary tree with no elements — the empty tree

Binary Search Tree

A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree.

 

Unbalanced Tree

an unbalance tree is a binary search three that doesn’t  follow the theory of a balance tree that can couse the binary tree un balanced .

To solve this problem there are two wasy to fix an unbalanced tree there are:

1.AVL Tree

AVL tree (Georgy Adelson-Velsky and Evgenii Landis’ tree, named after the inventors) is a self-balancing binary search tree. It was the first such data structure to be invented.[2] In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

well to put it simple on how to use a avl tree is to compare the nodes that we want to input and put it in the left side or the right side depends of it’s value of input nodes.

2.Red Black Tree

A red–black tree is a kind of self-balancing binary search tree. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

Balance is preserved by painting each node of the tree with one of two colors (typically called ‘red’ and ‘black’) in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.

 

 

 

 

 

 

 

 

 

For this meeting the main material is introduction of tree in data structures and this material is lectured by miss rulyna .

TREE
A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root.

EXP:

Terminologies used in Trees

Path − Path refers to sequence of nodes along the edges of a tree.

Root − Node at the top of the tree is called root. There is only one root per tree and one path from root node to any node.

Parent − Any node except root node has one edge upward to a node called parent.

Child − Node below a given node connected by its edge downward is called its child node.

Leaf − Node which does not have any child node is called leaf node.

Subtree − Subtree represents descendents of a node.

Visiting − Visiting refers to checking 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 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.

HOW TO DETERMINE

2^k = Is to determine the nodes can be fit in a tree.

n-1= Is to determine the max number of level in a tree(n=nodes).

2log(n)= Is to determine  the max number of level in a tree(n=nodes).

2^kh-1= Is to determine max number of nodes in a tree.

BINARY TREE

A binary tree is made of nodes, where each node contains a “left” pointer, a “right” pointer, and a data element. The “root” pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller “subtrees” on either side. A null pointer represents a binary tree with no elements — the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a triple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set.

EXP

 

 

 

 

 

 

 

 

 

This third meeting the material will be hosted by pa sky . The main topic of today meeting is linked list 2 .

Linked List

Linked list is a linear collection of data elements, called nodes pointing to the next node by means of pointer. It is a data structure consisting of a group of nodes which together represent a sequence.

There are two modifiers that can modifies the node there are push(its use for adding a node value and push to create the node ) and pop(delete a node ) .

Linked List is divided by 2 kinds there are single linked list and double linked list .

Single linked list

Single Linked Lists are a type of data structure. It is a type of list. In a single linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node. It is called a single linked list because each node only has a single link to another node. To store a single linked list, you only need to store a reference or pointer to the first node in that list. The last node has a pointer to nothingness to indicate that it is the last node.

Double Linked List

double linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.

1.Queue

Queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. Linked list is a data structure consisting of a group of nodes which together represent a sequence. Here we need to apply the application of linked list to perform basic operations of queue.

There are two kind of queue that can be used for programming there are circular queue and priority queue

Circular queue

• Single Circular queue linked list:
  It  is an extension for the basic single linked list. In circular linked  list Instead of storing a Null value in the last node of a single linked  list, store the address of the 1st node (root) forms a circular linked  list. Using circular linked list it is possible to directly traverse to  the first node after reaching the last node.

This shows a single circular queue on liked list

• Using circular queue on double linked list
  In  double linked list the right side pointer points to the next node  address or the address of first node and left side pointer points to the  previous node address or the address of last node of a list. Hence the  above list is known as circular double linked list.

This shows a single circular queue on double liked list

 

Priority queue

• priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority.

2.Stack

Stack is a type of queue that in practice is implemented as an area of memory that holds all local variables and parameters used by any function, and remembers the order in which functions are called so that function returns occur correctly. Each time a function is called, its local variables and parameters are “pushed onto” the stack. When the function returns,these locals and parameters are “popped.” Because of this, the size of a program’s stack fluctuates constantly as the program is running, but it has some maximum size. stack is as a last in, first out (LIFO) abstract data type and linear data structure. Linked list is a data structure consisting of a group of nodes which together represent a sequence. Here we need to apply the application of linkedlist to perform basic operations of stack.

IF you want to now the details about how stack implementation really works here i found a really cool website that can let you experiment on stack liked list :

click here –>Stack (Linked List Implementaion)

3.Evaluation on prefix notation

To operate this evaluation there are three tings that you have to know :

1. Inflix : the normal operation that we normally use to calculate our math problems .
2. Prefix : a calculation of math problems that operator have to be on the left followed by right operand and left operand . usually its use for programming purpose because computer can detect math problems more easier in prefix .
3. postfix : is the opposite of prefix that the operator have to be on the right followed before operand right and perand left .

EXP:

inflix : 4+6*(5-20)/3

Prefix : +4/*6-5 3

Postfix: 4652-*3/+

4. DFS and BFS

• Depth–first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.
• Bread-first search(BFS)This can be through of as being like Dijkstra’s algorithm for shortest paths, but with every edge having the same length. However it is a lot simpler and doesn’t need any data structures. We just keep a tree (the breadth first search tree), a list of nodes to be added to the tree, and markings (Boolean variables) on the vertices to tell whether they are in the tree or list.

 

IF you want to now the details about how BFS and DFS  implementation really works here i found a really cool website that can let you experiment on method of seach:

click here –>BFS Implementation

click here –>DFS Implementation

 

 

For this session meting is delivered bay a guest lecture named Bong Defendy . He’s binusian 2007 and he’s a entrepreneur his job mainly around database like creating a system based on cloud , system design  , and many things that involve creating  a structure database system .

This meting the lecturer talk’s about structure data that can be use for work . Mainly when we work on all fields of work that base on database we have to follow these three main point’s which is :

1. Mobility
2. Big Data
3. Cloud

1.Mobility

Mobility in technology is a way to minimize the cost and resource then maximize the function and the life span of the technology it self . Mobility always evolving through time to time .

2.Big Data

Big Data is a variant of data sets so large and complex they are impractical to manage with traditional software tools. Specifically, Big Data relates to data creation, storage, retrieval and analysis that is remarkable in terms of volume, velocity, and variety .

3. Cloud

For understanding what cloud means we first have to understand the three meaning of clouds which is Cloud computing  , Cloud storage , Cloud database .

cloud computing, also on-demand computing, is a kind of Internet-based computing that provides shared processing resources and data to computers and other devices on demand. It is a model for enabling ubiquitous, on-demand access to a shared pool of configurable computing resources.

Cloud storage is a model of data storage in which the digital data is stored in logical pools, the physical storage spans multiple servers (and often locations), and the physical environment is typically owned and managed by a hosting company.

A cloud database is a database that typically runs on a cloud computing platform. There are two common deployment models: users can run databases on the cloud independently, using a virtual machine image, or they can purchase access to a database service, maintained by a cloud database provider.

This session also talk’s about things in the world of technology .

1. Machine Learning

Machine learning is the science of getting computers to act without being explicitly programmed. In the past decade, machine learning has given us self-driving cars, practical speech recognition, effective web search, and a vastly improved understanding of the human genome. Machine learning is so pervasive today that you probably use it dozens of times a day without knowing it. Many researchers also think it is the best way to make progress towards human-level AI. In this class, you will learn about the most effective machine learning techniques, and gain practice implementing them and getting them to work for yourself. More importantly, you’ll learn about not only the theoretical underpinnings of learning, but also gain the practical know-how needed to quickly and powerfully apply these techniques to new problems. Finally, you’ll learn about some of Silicon Valley’s best practices in innovation as it pertains to machine learning and AI.

2.Augmented Reality

Augmented reality (AR) is a live, direct or indirect, view of a physical, real-world environment whose elements are augmented by computer-generated sensory input such as sound, video, graphics or GPS data. It is related to a more general concept called mediated reality, in which a view of reality is modified (possibly even diminished rather than augmented) by a computer. As a result, the technology functions by enhancing one’s current perception of reality. By contrast, virtual reality replaces the real world with a simulated one. Augmentation is conventionally in real-time and in semantic context with environmental elements, such as sports scores on TV during a match. With the help of advanced AR technology (e.g. adding computer vision and object recognition) the information about the surrounding real world of the user becomes interactive and digitally manipulable. Artificial information about the environment and its objects can be overlaid on the real world.

3.Business Intelligence

Business intelligence (BI) is a technology-driven process for analyzing data and presenting actionable information to help corporate executives, business managers and other end users make more informed business decisions.

4. Home Automation

Home automation is the use of one or more computers to control basic home functions and features automatically and sometimes remotely. An automated home is sometimes called a smart home .

To learn about all the thing involve with AI or machine learning first we have to know about what are microprocessor is .

Microprocessor

A microprocessor is an electronic component that is used by a computer to do its work. It is a central processing unit on a single integrated circuit chip containing millions of very small components including transistors, resistors, and diodes that work together.

we can learn them by using  arduino and raspberry pi . It’s very easy to use and very basic to learn about AI and hardware coding . The price variations is between around 60.000 to 500.000 Rupiah for arduino and for raspberry pi is between around 500.000 to 1.000.000 rupiah . The price range is very different between arduino and raspberry pi because arduino is for beginners or just want to know about AI on the other hand the raspberry pi is more expensive because more complex .

if you interested in buying microprocessor there’s the link :

https://www.tokopedia.com/warungarduino/etalase/arduino-board

https://www.tokopedia.com/search?st=product&q=raspberry+pi+&sc=0