Posts

CST-383 Week 2

This week, I learned to use Pandas to perform data analysis. Pandas felt very similar to using NumPy, however, the terms in Pandas can be different. In Pandas, a 1D list is considered a Series. A 2D list is called a DataFrame. One of the main differences between the two that I noticed is that you can explicitly specify the index for a Pandas Series. For example, we could specify the indexes in a Series containing names of students, with values corresponding to the student's grade. Another thing that I learned which I thought was interesting to use was aggregation in Pandas. If we wanted to calculate the mean value in a list data structure, we would likely have to iterate through the values using a for loop in other programming languages. However, in Pandas we can just use aggregate() on a Series' column and pass in a mean function, allowing us to perform this calculation in just one line. Something else that stood out to me, is that we can use groupby to get rows that share the...
Post a Comment
Read more

CST-383 Week 1

 This week I learned how to use the library, NumPy, to perform operations on numeric data. One thing about NumPy that stood out to me, was how its operations felt similar to operator overloading in C++. For example, if we wanted to add the contents of two NumPy arrays, A and B together, we would execute the expression: A + B. In C++, the operator, "+" could be overloaded to perform the equivalent expression on our own custom array data structure. This makes me curious if the implementation of NumPy uses some kind of operator overloading to perform these operations, or if it is just specific to the Python programming language. Another thing that stood out to me while completing this week's homework, was how similar NumPy felt to writing SQL queries. If we had a NumPy array, A, containing the values 7440, 12280, 11250, 12960, 7560, 13500, 13290, 13868, and we wanted to get the values greater than 8000, we would create a mask using the expression, "mask = (A > 8000)....
Post a Comment
Read more

CST-370 Week 8

 Dijkstra's Algorithm: Solves the problems of finding the shortest path from a single source. It is a Greedy algorithm. It dertermines the shortest path from a single source vertex to each of the other vertices. Has wide applications such as:     - Internet routing     - GPS navigation     - Transportation planning
Post a Comment
Read more

CST-370 Week 7

Image
 This week, I learned about Dynamic programming, which is algorithm design technique for improving the efficiency of certain recursive algorithms, such as Warshall's algorithm and Floyd's algorithm. I also learned about the Greedy technique, which is used to solve optimization problems, such as the Prim algorithm Dynamic Programming To avoid multiple calls for a sub-problem (ex: base case for fib), use an array to keep solutions of sub-problems. Example: Fib(n):     F[0] = 0;     F[1] = 1;      for (i = 2 to n):          F[i] = F[i-1] + F[i-2]     return F[n]; In General:     1. Set up a recurrence relation that describes a solution to a problem with smaller sub-problems.     2. Solve the smaller sub-problems and record the solutions in a table.     3. Solve the original problem using the table. Dynamic Programming - Solving Coin-Row Problem Coin-row problem: There is a row of n coin...
Post a Comment
Read more

CST-370 Week 6

Image
       This week, I learned about two different types of balanced trees and their associated algorithms: AVL Tree and 2-3 Tree. I also learned how to use the Heap data structure to efficiently find maximum and minimum values. Heap can be represented by the bottom-up algorithm. Finally, I learned to use Hashing for storing values in a dictionary/array to perform efficient search operations. AVL Trees Problem: Unbalanced trees result in operations that take O(n) time. AVL Tree : A balanced binary search tree. The difference between the heights on the left and right subtrees is either -1, 0, or 1. ( balance factor = height of left subtree - height of right subtree) Ex: Since each node has a balance factor of -1, 0, or 1, it is an AVL tree. AVL Tree Rotations Rotation : A local transformation of a subtree whose balance factor has become either +2 or -2. Four types of rotations: R(right)-rotation, L(left)-rotation, LR-rotation, RL- rotation Ex:     A   ...
Post a Comment
Read more

CST-370 Week 5

Image
 This week, I learned to apply the "Divide-and-conquer" technique in a sorting algorithm, known as "Quick-sort." I also learned about "Decrease-and-conquer", which is a similar technique to divide-and-conquer and is used in sorting algorithms, such as "Insertion sort" and Khan's algorithm. A third technique I learned is the "Transform-and-Conquer" technique, which is used in "Pre-sorting." I also began to understand the efficiency of the algorithms used for Binary Tree traversal and height calculation. Quicksort Uses the Divide-and-conquer technique. It is "in place", like insertion sort, but not like merge sort (does not take up extra space) Quicksort of an n-element array: 1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray < x < elements in upper subarray 2. Conquer: Recursively sort the two subarrays. 3. Combine Example of Partitioning Worst case: O(n^...
Post a Comment
Read more

CST-370 Week 4

Image
 This week, I learned about the merge sort algorithm, an algorithm that uses the divide-and-conquer technique for sorting. Basic Idea     1. Split the input array into two halves     2. Sort the first half of the input array recursively     3. Sort the second half of the input array recursively     4. Merge the two sorted halves together Merge of the two sorted array B and C: 1) Compare the first element in arrays B and C 2) The smaller element is added to array A 3) The index of the array with the smaller element is increased by one (pointing to the next element) 4) Repeat until all elements from B and C are copied into A (sorted) Example: Time Analysis Of Merge Sort Algo: Mergesort(A[0, ... n-1]) if n > 1     copy A[0..[n/2]] to B[0..[n/2]-1]     copy A[n/2.. n-1] to C[0.. [n/2] - 1]     Mergesort(B[0..[n/2]-1]     Mergesort(C[0..[n/2]-1])     Merge(B, C, A) Recurrence relation:  ...
Post a Comment
Read more