-

 

Week 6 – CST370 – Design and Analysis of Algorithms

This week we learned about AVL trees, 2-3 trees, heap, and hashing.

An AVL tree is a binary search tree that has a balance factor for each node that is either 0, 1, or -1. This means that the height of a node’s left subtree minus the height of the node’s right subtree must be either 0, 1, or -1. When inserting a new node into an AVL tree, you must recheck that the balance factor of each node is still within range. If the tree is unbalanced, you must perform either right, left, double right left, or double left right rotations to balance the tree.

A 2-3 tree is a tree that can have nodes that are 2-nodes or 3-nodes. A 2-node contains a single key with two children. The left child is less than the key and the right child is more than the key. A 3-node contains two ordered keys and three children. The left child is less than the two keys, the right child is more than the two keys, and the middle child is between both keys.

A heap is a structure that is partially ordered and suited for priority queues. It is very efficient for finding the max value, deleting the max value, and inserting a new item. You can use an array to represent a heap. The max value will always be the value at the lowest index, typically we use index 1 for the first value in the heap. To find the children of a node in a heap, you multiply the index of that node by two for the left child and add 1 for the right child. If the index of a node multiplied by two equals the length of the array, that means that the node does not have a child.

Lastly, we covered hashing. Hashing is based on the idea of distributing keys among a one-dimensional array called a hash table. To distribute the keys, you must use a hash function which will assign an index to the key. When two keys are hashed to the same index, this is called a collision. You can deal with collision by using separate chaining, which sorts the keys in linked lists and each list contains all the keys hashed to that index. You can also use linear probing to deal with collisions. Linear probing allows you to store the key in the next available index if the initial hashed index is taken.

Comments

Post a Comment

Popular posts from this blog

-
  Week 2 – CST370 – Design and Analysis of Algorithms This week we covered asymptotic notations, non-recursive algorithms, and recursive algorithms. We use the order of growth to determine an algorithm’s efficiency. We also use three notations to rank the order of growth: big oh, big omega, and big theta. Big oh, is the set of all functions with a lower or same order of growth as g(n), a simple function to compare the count with. Big omega is the set of all functions with a higher or same order of growth as g(n). Lastly, big theta is the set of all functions that have the same order of growth as g(n). Non-recursive algorithms solve problems by repetition through loops to execute instructions until a condition is met. An example of a non-recursive algorithm is a Max Element algorithm where you must find the value of the largest number in an array. A recursive algorithm calls itself with smaller values and returns the result for the current input by carrying out basic operati...
Read more
-
  Week 1 – CST370 – Design and Analysis of Algorithms This week was a combination of week 0 and week 1. We were required to set up a GitHub account, if we did not have one already, to complete our homework assignments with GitHub Classroom. Homework 0 required us to write a program that reads two integer numbers from a user and displays the sum and difference of the two numbers. We also needed to make sure that the difference between the two numbers is always 0 or positive. The purpose of Homework 0 was to get familiar with GitHub Classroom, set up our IDE environment, and submitting to Canvas. The topics covered this week included Euclid’s Algorithm for GCD calculation, important problem types, fundamental data structures, and algorithm analysis framework. Euclid’s Algorithm for GCD calculation is an algorithm that takes two numbers and finds the greatest common divisor by repeating the equality gcd(m, n) = gcd(n, m mod n) until m mod n is equal to zero. The last value of m wi...
Read more
-
  Week 1 – CST – 363 Introduction to Database Systems 1.       Relational database tables and spreadsheets look similar with both having rows and columns. What are some important differences between the two? Some important differences between database tables and spreadsheets are the way data is formatted and how data is stored. In a spreadsheet, every cell can store any type of data like a date, integer, or string. These data types can also have their unique format. In a database, each cell must contain only one data type helping to prevent data mismatch mistakes. In a spreadsheet, the data is stored in each cell. In a database, the data is stored in a row made up of columns. 2.       Installing and configurating a database and learning how to use it is more complicated than just reading and writing data to a file. What are some important reasons that make a database a useful investment of time? Learning how to install and c...
Read more