4veintecoding-blog

[4veintecoding-blog]

Week 8~10

Amortized analysis is one of the things we’ve been working on, as well as some heaps (binomial and fibonacci to be specific). Learning about amortized analysis brought a pretty good understanding of how algorithms are analyzed. Its purpose is to calculate the costs of the algorithm (space and time) not just based on per operation, but looking at the algorithm as whole. Some algorithms tend to have an operation that is very expensive. By normal analysis, that algorithm can be concluded to be very expensive. However, the algorithm itself could be running at efficient standards, except for that one operation (which may or may not be used as often as expect). With amortized analysis, we can relabel that algorithm to be an optimal algorithm, and not solely because of its operation costs. There are two main ways I am most familiar with. The first one is called the aggregate analysis. This analysis has two main steps. First, it proves that given n number of sequences, it will execute in T(n) time. Then, we must show that each operation will cost T(n)/n time to execute. By doing this, we say that all the different operations in the algorithm will have the same cost. The second way is called the accounting method. This method borrows some principles from accounting in order to analyze the algorithms costs. Each operation is given a cost, called the amortized cost. Some operations can have more or less than what they normally cost, and if an operation’s amortized cost is more than what it normally costs, we can use the difference (named credit) and assign to any other part of the algorithm/data structure. This can also be used to pay for any operation whose amortized cost is much less than its actual cost. As well, binomial and fibonacci heaps were discussed. From my basic understanding, binomial heaps are binomial trees that can be connected together by their root nodes. So to understand a binomial heap, we need to understand a binomial tree. A binomial tree is a data structure where two binomial trees are connected. This tree is defined to be as a binomial tree with order 0 is a single node. A tree with order k is one that has a root node whose children are binomial trees of order k-1, k-2, ... , 2, 1 ,0. Binomial heaps are implemented in code using doubly linked lists. Each node contains the key information about the whole data structure and other nodes. They keep track of the parent pointer, the sibling pointers, left most child pointers, its key, and the amount of children that that tree has. By using a doubly linked list, constant time can be achieved for operations done on the data structure. A fibonacci heap on the other hand, is similar to the binomial heap, the only differing factor being that it is not as structurally strict as a binomial heap. A fibonacci heap, unlike a binomial heap, waits until the extract-min operation is executed before merging. Both heaps are used for priority queues, but binomial heap is still much faster than fibonacci heap. I need to brush up more on my understanding of these two data structures, but at least I understand the general concept.

[4veintecoding-blog]

Week 7

The first midterm was definitely not what I expected, and I feel that a lot of the other students in the class are just as taken aback as me. I wasn’t able to submit a solution to the dynamic programming problem, which will definitely cost me a lot in the long run. Let’s just hope I can catch up in the coming weeks. I was able to at least answer the growth of a function problem and the invariants with confidence, but the recurrence was something else. Due to my lack of understanding, I was not able to come up with a correct solution, and that along with the missing solution for the last problem, cost me a lot of points. I’m not too positive on the future, but I’m sure I can come back around. This week, we continued talking about greedy algorithms. The reason why they’re important is because dynamic programming solutions are great, but for some simple problems, one shouldn’t have to go through the same amount of trouble. That is where the greedy algorithms come in, much more simpler, efficient, and quick as dynamic programming solutions. The difference is that instead, they take a look at the current situation, and pick the best immediate solutions. This is both its pro and con. By doing so, it is able to solve simple problems just as easily as DP solutions, but instead they are usually simpler and quicker to write. One interesting problem of greedy algorithms that I came across is one that is very common in everyday life, which is the activity selection problem. The problem states that given n number of activities with their start and end time. We must find the maximum number of activities that can be done by the user, assuming that they can only perform one activity at a time. The greedy approach would simply be choosing the activity with the least finish time, so that the user will have room for more activities to do. This provides us with the maximum number of activities, and so the problem is solved through a greedy algorithm. This is very interesting, and something that I’m sure will come to be very useful in the future. For now, I need to prepare for the next test, in hopes that I don’t perform as badly as I did the last time. 

[4veintecoding-blog]

Week 4~6

This has been an intense few weeks, we’ve been dealing with a lot of dynamic programming examples and just trying to tackle the concept. It was very difficult to understand at first (with which my understanding even now isn’t as crystal clear), but it slowly began to make perfect sense. So dynamic programming works on the principles of recurrences and divide and  conquer. Recurrences from discrete math are functions that call themselves until a base case has been reached, with which case it can return that value and solve the previous case. In doing so, a problem can be sub-divided into smaller subproblems, until broken down into small enough pieces with which their solution is straightforward. This is then the concept of divide and conquer, diving the problem, and conquering each one. The conquer part requires the algorithm to then somehow combine the many different solutions into a single one, often having to solve some unrelated problems on the side in order to achieve success. One simple example I have taken from the book is the merge sort algorithm. This algorithm takes any array, and splits it in half, again and again, until it is left with sub-arrays of size 2. Once this has been achieved, it then begins the sorting process, placing the smallest value on the left side, and the highest value on the right side. It then merges with its neighboring arrays, repeating the same sorting process, until finally the original array is found to have been sorted completely. I still don’t fully understand how to properly apply this algorithm (in code), but at least understanding the bigger concept can help me iron out the different details that I need to move forward.

[4veintecoding-blog]

Week 3

We began discussing analysis of algorithms, and ran into the Big O notation once more. When picking which algorithms are best for which scenarios, it’s easier to eliminate a few rather than pick one. So, to actually figure out which algorithms are best, we look at aspects such as runtime. Runtime is simply just the number of operations that the algorithm makes in order to achieve its result. The worst case of an algorithm allows us to find an upper bound, and guarantees us that the algorithm will not run slower than that given bound. Other than that, when actually analyzing algorithms, we often only care about the growth of the leading term of the algorithm. Therefore, we drop coefficients and any other terms that isn’t the lead will be dropped as well. I need to look more into this specific topic of the book, but I feel that once I get some more experience with other algorithms, it will come as second nature.

[4veintecoding-blog]

Week 2

We finally talked about pseudo-codes and using them to describe certain algorithms, one of these algorithms was specifically the Insertion Sort algorithm. It works the same way as how someone would sort a hand of cards from a pile on a table. They start off with an empty hand, and pick the top most card on the pile. Each time, the person picks from the top pile, and depending on its value, it is immediately sorted amongst the other cards in the hand. Only difference however, is that insertion sort works within the array itself, not needing anything external in order to facilitate its function. We also began talking about loop invariants, which help us understand why an algorithm is correct (or incorrect). They consist of three different properties, the invariant, the maintenance, and the termination part. The invariant is a statement that can be said to be true even before the first iteration of the loop. Maintenance, is said to be true before every iteration. Lastly, the termination is said to be true after the loop has terminated. It is very similar to how mathematical induction works, where in order to prove something you must first declare a base case and prove it to be true. Afterwards, an ‘inductive step’ is done, which helps prove the argument. Difference between the two are that mathematical induction is ‘inducted’ infinitely, whilst the termination of a loop variant ends when it is proven true.This is pretty much a summary of what I’ve understood from the classes this week, I might go back and do a bit more research on the previous topics to help refine my knowledge.

[4veintecoding-blog]

Week 1

This week, just as the semester started, I decided to read ahead through the book to see if it can help me understand the topics in class. So far, we’ve discussed algorithms in general and their usefulness. As I read the book however, here are the main points that I felt were important to keep with me. The first being was the actual definition of an algorithm. An algorithm is a formula that when given an input, will produce a specific output. It consists of instructions that compute based on the input. Sorting is one of those important functions when it comes to algorithm, it is used in so many different real world applications. The book gave a few interesting examples regarding these applications, but specifically the internet was one that displayed the most use for algorithms. Search engines that can pick out web pages that contain information within it, and organize all of this in a list in terms of their respective filters. We have yet to look at some real algorithms, but I think its going to get difficult fast.

[4veintecoding-blog]

[4veintecoding-blog]

Week 11 - Ending? This Is Just One Iteration Of The For Loop

June 18th, 2017

So, after a week of clutching exams and grinding for homeworks, I’m writing this from New York, JFK Airport. Flight is in about 30 more minutes, and I’m just writing this to summarize what’s happened since the last post. Lab partner and I handed in Lab 6, but we didn’t get much points in. I’m not bothered at all to be honest, because I’m proud of what I’ve written so far for Lab 6 Problem 1. Sure, it wasn’t complete, but given a bit more time, I could’ve completed it. I honestly feel that that problem has made me use every single thing I knew about programming, and forced me to orchestrate them all together in unison to take down that beast of a problem, and I loved it. That problem has honestly made me have the most fun I’ve ever had with programming ever, and I don’t care that I didn’t get a good grade for it. It makes me want to learn more, practice more, code more, and just keep programming because of how fun and amazing it can be. I have never felt more passionate about anything in my life ever. Also, the 2nd mid term didn’t go as bad as I thought. I messed up in the littles things that costed me a lot of points, but I knew a majority of it so I feel happy inside. The 2nd problem of the exam screwed me over in my opinion. I had a gut feeling that there was no syntax error, and that it would actually output something, but I hesitated and put in a wrong answer. I also lost points for the definitions that the Professor asked us, which I completely blame myself for, for not learning the definitions much better. I was able to somewhat complete the incomplete program (despite having a TON of errors lol), so at least I can take some sort of happiness from that. I passed the test, but I know I could’ve done better. I’ve done what I can and reaped what I’ve sown, and I feel good about it. Looking at Lab 7, it’s like the mythological hydra beast. I’ve struck down the first head (Lab 6 Problem 1), but now it’s grown more heads. If I don’t finish these Labs, it wouldn’t bother me as much, because I know I’ll continue working on them way after their due date. I want to solve them, I want to learn different ways to go about them. Flight attendants are starting to call us into the plane, boarding begins in 5 minutes. Lab 7, I’m coming for you.

[4veintecoding-blog]

Week 10 - The End Is Nigh

June 8th, 2017

Won’t be able to go to classes the next few days, have to run errands in the capital to prepare myself and documents for my Visa renewal about a week or two from now. On the bright side, I’ve finally found the time to make some progress on Lab 6 Problem 1. Planned out the randomizer on paper, but it’s gonna take such a long time to code. The plan is to take the same switch cases from the function I made which checks where the blank space/0 is on the grid, and replace their cases with an rand() function that chooses between the options that are available. Example: if the 0 is in the very bottom right corner of the grid, then its possible moves are to move a whole row above it down, or whole row beside it to the right. Since it can move whole rows, it means it can also move single or double units, but only in the down or right direction. From here, the function will choose a number between 1 or 2 (down or right), then a number depending on the available option it chose (in this case, since both options allow for whole rows, it can just choose from 1-3). From here, I can place this function in a for loop that will randomize the grid using only legal moves. One optional thing to implement is to ask the user how many times it wants the grid to be randomized, but this is rather trivial and probably won’t be necessary. On a different note, the 2nd mid term is coming up, so I’ve got to start relearning Stream I/O Files again. It’s been nearly a month since I’ve read this topic, but I think I can manage.

Wish me luck blog, because I feel like Leonidas in 300 in his last stand. Let’s see how this goes.

[4veintecoding-blog]

Week 9 - Ohmygodthatwassuchalongspringbreak

June 2nd, 2017

Oh my god, the strike finally ended. After nearly a month of strike, the college decided to stop the strike and return to classes. The beauty of it? I’m still not done with the first problem of Lab 6. I’ve been working on it this whole time, and I’ve made a ton of progress, but it drains so much of my mental power to get an efficient method. I know that there’s a shorter way, I know there is, but I fear that the moment I deviate from my current trail of thought, I’ll end up messing up all the progress I’ve made. I’m committing to this super long, slightly inefficient, but working program. I started off with a function that outputs a grid based on an array that can be manipulated within the main program (and is also independent from any other functions, so that it can be easier to work with). Next, I made a function that checks where the ‘blank space’ or 0 is on the array, then depending on its position, outputs from different switch cases that let the user know what are the ‘legal’ moves it can make (I understand that a much more efficient way of dealing with this exists, and I honestly did not care during the time of writing the code. I regret not caring, I wish I figured out an easier way lol). Then, I made a number of functions that can move down single, double, or whole rows of numbers down into the blank space. Next issue I want to tackle is randomizing the whole thing and setting the program to stop running once the array has been set in ascending order. For now, classes are starting again, so the grind begins again. Gotta deal with a lot of other exams from my other classes, so sadly I have to put this project on hold. See you soon blog!

[4veintecoding-blog]

Week 8 - if(aprilfools(true)) prank_someone(person);

April 1st, 2017

Finished Lab 5. Jesus, that took a lot out of me, and it isn’t because they were difficult, rather I’ve been flooded with work from all my other classes. The stress is getting to me, but I can’t give up yet. First problem from Lab 5 was fine, had to play around a bit with some pow() functions. Went to the Professor’s office to help me understand the whole math behind it. Starting to get used to Call-by-Reference parameters, they do wonders and the possibilities are endless. Second problem was just a matter of setting up multiple functions (3 to be precise) to work in conjunction to converts radians into grad measure. Third one was more fun to work with though, similar to the time problem from the previous lab, but this one just asks to calculate the hour difference between two different times (military) that are given by the user. Other than that, a 2 week should be coming up soon, but I’ve been hearing a lot of rumors lately that there’s going to be a general assembly to decide whether the college goes on strike or not. Political situation in Puerto Rico had caused this, so we’ll have to see what happens soon. Either way, going to start working on Lab 6, because the first problem actually caught my interest.

[4veintecoding-blog]

Week 7 - Small Update, Trying To Hold On

March 20th, 2017

Been a real busy week, submitted Lab 4 finally. Keep handing them in late now, problems starting to get more time consuming. Had major issues with the hours problem, certain values tend to give large negative values (such as -7000~). Couldn’t seem to figure it out, might be a problem with certain values when called within the functions. Despite that, program works just fine. Lecture started leaning towards I/O of Stream Files. Going to try and get an early start on Lab 5 this time, in case I might have some stuff come up this week. Sorry for the short post .doc file, I’ll try make up for it next time.

[4veintecoding-blog]

Week 6 - How Do I Become A Programming God?

March 10th, 2017

Handed in Lab 3, took longer than expected due to some personal, family, and other college classes getting in the way. Oh well, better late than never! Quick update on this week, followed the class a bit and started finishing last sections of this chapter. This chapter was pretty great, seeing as to how it’s actually put me on another level of programming, being able to create my own functions and such. The part that interested me the most is the whole procedural abstraction, or “Black Box” as I prefer to use. It’s the whole notion where a programmer must write their functions like a Black Box, where another programmer would only need to a) know what it does b) know how to declare it and use it, without having to know how it works or coded. I think this is where a good programmer is separated from a great programmer. A good programmer can solve a problem, but writes messy code that no one else can understand, as opposed to a great programmer whom everybody can learn from thanks to his/her readable code. That’s just me though, I’m just a rookie, I’m still learning what it means to be great. Going to start working on Lab 4. Looking over it, the calorie/meal serving problem seems a bit confusing, but the time difference seems like fun (no sarcasm there). Might pickup some new things to help with these problems, so just gonna start reading ahead again as normal.

[4veintecoding-blog]

Week 5 -  Episode 5: Attack Of The Functions!

February 28th, 2017

This is gonna be a rather long post, and I’m sorry (not really). I have a lot to get off my chest. Got my feedback from my professor on the 2nd lab. First and third problems were very easy, just a matter of dealing with cin’s and cout’s, using variables and their declarations, some C++ multiplications and divisions, no big deal. Second problem took a bit more brain juice for me to deal with than the previous one, but luckily the professor was nice enough to walk us through the math part (God bless his soul). The fourth one had some mistakes in its process, apparently the gross pays were calculated to be too high and the values following it. The rest of the program was fine, with the initial gross pay being the only error. Fifth question, I had forgotten to include some parentheses around the Boolean arguments for the if statements. Also, forgot to state which player wins, oops! Started working on pre-defined functions, but more importantly user made functions. I think this is as far as I’ve gotten from my previous experience with programming, so this is where I officially start learning. Lab 3 is due in a few days… struggling with the parking ticket problem. Having a bit of trouble with sorting out the week days from the weekends, but my main issue stems from the damn hours. Maybe if I use military time? What if I just ask the user to input it specifically in military time? What if he/she doesn’t do that? Will the program run? What ever happened to Amelia Earhart? Do dogs dream of walks and fetch? All good questions. Joking aside, I’m sure using the above strategy could help simplify the problem. Speaking of problems, the damn roman numeral hours problem took so much of my time.  Had to advance a few chapters ahead, learned arrays, gave two of those arrays their designated roman numerals and value, threw ‘em in a loop, added a couple of if statements to check whether the previous numeral was smaller than the current, if so, subtracting the previous value to the current to create their new number (DragonBall’s Fusion Kai anyone) and voila! After days of procrastinating—I mean working, I finally managed a working Roman Numeral – Arabic Numeral converter! Going to attempt the rest, and see how it all turns out. See you in a week blog!

[4veintecoding-blog]

Week 4 - Round, and Round, and Round...

February 19th, 2017

Got comfortable using if-else statements and Boolean arguments again. Just like riding a bike. Found out that the labs could be submitted with partners after I had done the first two solo. That should really help cut the work load in half and learn better. Not much going on this week, handed in the final version of the 2nd lab a bit late, I fell asleep that night so I forgot to send lol. Hope the professor didn’t mind, going to start working on the infamous do/while and for loops! How much I loved (and hated) these guys. So simple, yet they can be so complex (a for loop, in a for loop, in a for loop… LOOP-CEPTION).

[4veintecoding-blog]

Week 3 - Nostalgia Hittin’ Hard

February 10th, 2017

I started reading ahead from the lectures, since I hear that the class needs a bit of independent study. Began learning how to make variables in C++, makes me feel real nostalgic of my Java days. Inputs and outputs are relatively simpler, especially with the whole command “using namespace std;”. I remember my old high school programming teacher had created a whole keyboard class file which we had to call every time just for input. It was great. Anyway, this week I learned about some more data types (like char, int, double, and String), and flow of control, which is just the PEMDAS of C++. Did a bit more reading ahead, into chapter 3, but just briefly though. Seeing more familiar things from Java like the Boolean arguments (&& and ||) and if-else statements. The programs from here on out are about to get more difficult, yay.

[4veintecoding-blog]

Week 2 - Why Do I Need So Much Software For One Compiler

February 6th 2017

First lab handed in, it was just mostly about being accustomed to emacs (the compiler we’re using for C++). Also, learning the different types of errors and what they mean. Now that’s important. Expect to make a ton of those in the future, hehe. Had to use BootCamp on my Macbook to install a copy of Windows, to then install a virtual machine, which I would then run Ubuntu on. Beautiful. Totally was not a hassle to setup. Had some trouble remembering “g++ -o -wall <name of program> <name of source code>” at first, but after a couple practice runs I got it down. Easy peasy. Kind of difficult to handle this kind of editor though, maybe it’s because I’m used to Dr. Java or Eclipse.