CST370 - Week 6

This was our sixth week in CST 370 - Design and Analysis of Algorithms.

AVL Tree

An AVL Tree is a balanced binary search tree where the difference in height between the left and right subtrees is either -1, 0, or 1. The difference between subtrees is called a balance factor or balancing factor.

 

What do we do if a Binary Tree is unbalanced (not an AVL Tree)? We can perform a R, L, RL, or LR rotation to make it balanced.

 

This AVL Tree Visualizer may be helpful.

2-3 Tree

A 2-3 Tree is a type of search tree where each node can have one or two values.

 

 If a node has three values, we promote the middle value to the parent node (or make it the new root node).

 

Visualizations:

Heaps

A heap is a type of Complete Binary Tree. There are two types of heaps: a Max Heap and a Min Heap.

  • Max Heap: The number of each node is greater than or equal to the numbers of its children. 
  • Min Heap: The number of each node is smaller than or equal to the numbes of its children.
  • Complete Binary Tree: a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

A heap can be represented as an array using the following conventions:

  • Left child of node j is at 2j.
  • Right child of node j is at 2j + 1.
  • Parent of node j is at j/2.
  • Parental nodes are represented in the first n/2 locations. 

 

 

 

Visualizations:

Heapsort

Heapsort is a sorting algorithm with a time efficiency of O(n*logn). It is a two stage algorithm:

  1. Construct a heap for a given array.
  2. Apply the root-deletion operation n-1 times to the remaining heap. 

 

Heap Sort Visualization 

Hashing

This week we discussed hashing. The basic principle of hashing is that we use the modulo of a number, such as an ID number, as the index of an array. Hashing is very effecient, with a O(1).

 

But what if two IDs have the same modulo value? (1234 % 100 = 34 & 3434 % 100 = 34) When two different values have the same hash, we call it a collision. We have two solutions for this problem, Separate Chaining and Linear Probing:

Visualizations:

Separate Chaining

With Separate Chaining we use a linked list to store values with the same hash value. When a new value is added, we append it to a linked list.

Linear Probing

With Linear Probing we insert a value into the next available entry if there is a collision. Then when we lookup a value we start a sequential search from the original hash value.

Load Factor

The load factor of a hash table is the number of keys divided by the size of the hash table (n/m). With Separate Chaining, each index has about n/m keys if the keys are evenly distributed. With Linear Probing, the load factor should be less than 1.

Example:

  • Number of Keys: 50, Hash Table Size: 100
  • Load Factor: 0.5 (50/100) 

 Load Factor is used to determine the efficiency of hashing.

  • Too High: May result in too many collisons and less efficient in searching a key.
  • Too Low: May not be efficient use of space.
  • Load Factor increases as more elements/keys are added to a hash table. Efficiency may decrease. 

Rehashing

The objective of Rehashing is to reduce the load factor to be within a pre-defined load factor.

To rehash we first increase the hash table's size, often to be the first prime number that is twice as large as the previous table size. Then the values in the old table are hashed and moved to the new table.

Comments

Post a Comment

Popular posts from this blog

Week 11

CST-338 Week 3  This week was the third week of CST-338. In this week we continued to learn more design and Java concepts. Black Box & White Box Testing This week we learned about two methodologies used for testing programs, black box and white box testing. Black box tests only focuses on the input, output, and functionality of a program, and not the internal code, logic, or structure of a program. One of the advantages of black box tests is that they are simple and easy to run. White box tests focus on the code, logic, and structure of a program. One of the advantages of white box tests is that can find logical errors, security vulnerabilities, or inefficiencies in code. Coupling & Cohesion This week we learned about coupling and cohesion in objects and methods. Coupling refers to how much different classes rely on each other. If two classes have tight coupling then they are more dependent, and changes in one are more likely to affect the other. If two classes have loose c...
Read more

Week 12

CST 338 - Week 4 This week was the fourth week is CST 338, also known as Software Engineering. In this week we began to learn about android development. Project 1 Review This week we finished a large project in CST 338. We have been asked to work with one or more classmates, and answer some questions about the project. With whom did you work? I worked with Nasser. What was your strategy for solving the assignments? My strategy was to read all of the method descriptions before I wrote any code. As I read them I created method stubs, and detailed TODO comments for each method. Afterwards, I started writing the methods from top to bottom in the assignment prompt. If a method called another method that I had not written yet, I would go ahead and write that method first so I better understood how they interacted. What was their strategy for solving the assignments? Their strategy was to follow the instructions closely as is, by following the UML diagrams and prompt as closely as possible. ...
Read more

Week 19

Image
 CST-363: Week 3 This is the third week of CST-363, also known as Intro. to Databases. Questions What is an SQL view.  How is it similar to a table? In what ways is it different? An SQL View stores a SELECT statement for later use, allowing the statement to be easily accessed in the future. A View functions similarly to a table, because SELECT statements return tables. However, the values that a View shows aren't being stored in the View, but the actual tables. This means that when one of those tables is updated, the View has to be as well. This also means that one needs to be very careful with updating or deleting rows using the View. Take a minute to think about how SQL compares to other programming languages like Java. What features are similar, and which are present in one language but not the other? The first and most clear difference is the syntax. SQL syntax is very different from that of Java and other programming languages. I think this makes basic SQL commands easy t...
Read more