Learning on the Job

Asymptotic Notation, or Landau Notation Asymptotic Notation is used to describe the limiting behavior of a function as it approaches a particular value or infinity. We have already seen a glimpse of this in the last post when we were discussing Order of Growth of functions.  Ex: O(n) When discussing asymptotic notation, there are three key terms: Theta Notation - A function that bounds a function within constant factor after a particular n. Big O Notation - represents the upper bound of Theta-Notation. Big Omega Notation - represents the lower bound of theta-notation. Taken from:  Florida State University In the graph above, (c2 g(n)) represents Big O Notation, because for each n after n0, O(g(n)) >= f(n).   (c1 g(n)) represents Big Omega Notation because for each n after n0, Omega(g(n)) <=  f(n). There is an O-notation and Omega-notation, so therefore there exists a Theta-notation for the function f(n). For O-notation and Omega-notation are both the

Chapter 2 - Getting Started Loop Invariant, Case Analysis, Order of Growth Checking the loop invariant When analyzing an algorithm using a loop invariant (which consists of the elements originally in positions that have been sorted already) to see if it is correct, we check 3 properties: Initialization - Loop invariant must be true prior to the first iteration of the loop. Maintenance - Must be true before the beginning of a loop, and remain true before the next iteration of the loop. Termination - When the loop terminates, the loop invariant must yield correct results that helps shows that the algorithm is correct. The first two properties helps to shows that the loop of the algorithm is correct.  The third properties is a confirmation that the algorithm has worked. Lets put this into a better understanding now, by using insertion sort. List given:  4 3 1 2 5 6 Initialization - Since insertion sort starts at the second element, the only part that is in the lo

Late post b/c vacation and stuff, but I'm back now. One of my algorithm books came in today.  I decided to order two, one for my class coming up this quarter, and another that I found regarded as the standard in the field. Algorithm Design: Foundations, Analysis, and Internet Examples   by Michael T. Goodrich (class) Link:  http://amzn.com/0471383651 Introduction to Algorithms   by Thomas H. Cormen Link:  http://amzn.com/0262033844 Introduction to Algorithms just came in and so far it a pretty good read.  It comes across very accessible to newbies like myself, but has a rigor and complexity to it still.  For the next couple of weeks, I think I will focus on burning through the first few chapters of this book, which will help me with my class this quarter.  I'll probably still work on Java projects, but I think that it will be a side thing I do in my spare time for now. Ch 1 - Foundations 1.1 Role of Algorithms in Computing Algorithms take an input an

I brought up the topic of concurrency in the Sorting post(concurrent merge sort), but never really got to explain properly what it actually was.  So in this blog post, I will go into what concurrency means, Java's tools approach to enabling this concept, and some common problems that arise when dealing with concurrency. The Concept Concurrency is the ability to be able to do more than one task at a time.  Sometimes the word parallelism is also intertwined in this definition, but depending on who you talk to, may not always be the same definition.  The way I see the difference between the two terms, concurrency is the idea that different programs can overlap and interleave with one another to create an experience that appears to the user that multiple applications are being run at the same time, but is actually a trick played that gives small time slices of processing usage.  Parallelism is the idea that two programs can actually run at the exact same time, enabled by the CPU s

I decided to do something different for this post.  As much fun as it is to research and study programming concepts, sometimes you just feel like coding something up that does something!  In my case, I was inspired by a card dealing method that appeared in one of my previous blog posts and I decided to make the simple game of BlackJack. For those unfamiliar, BlackJack is the casino game of 21, where you play against the dealer to try and get as close as you can to the card value 21 as possible without going over.  Originally, you start out with two cards, and you may draw a card or stay with your current cards. The dealer must play with one card up and one card down to begin with.  I decided to go with hard 17, where the dealer must draw until he has 17 or more card value.  To win money, you must beat the dealer, without busting(going over 21).  Face cards are worth 10, while Aces can be 1 or 11.  I purposely left out splitting and the gambling aspect, which I will return to in the

Introduction to Sorting and Searching Arrays In this blog post, we will be going over simple implementations for sorting and searching lists.  Learning to write fast search and sort algorithms will have an immense impact in the performance of all programs, as many real world applications deal with huge sets of data.  In this post, I will not include Big-Oh notation, which I will write in a later post.  Just worry about speed in a relative sense for now. Sorting using Selection Sort Let us take a look sorting an array first. You are given a random list of numbers in an array, and are told to sort them in ascending order. 9 5 7 3 2 1 8 There are 7 numbers in total in the array.  Now the most basic way of approaching this problem would be to find the smallest number swap it with the front position, but in an unordered list, you have no idea of where that number will be.  Therefore you must traverse the entire list to find the smallest element, besides the elements you have a

Introduction to Collections Today I am going to dive into a concept known as "Collections" in Java.  This blog post will be guided by the Collections chapter of Java Tutorials book denoted in the introduction. Collections are defined as an object that groups multiple elements into a single unit. Some of the actions that are associated with Collection are Store - Collections are used to store many elements into one place Retrieve - To retrieve data stored inside of the Collection and return it to who asked for it Manipulate - To manipulate data stored inside of the Collection, but to not change other data. The Java Collections Framework allows us to easily recreate and utilize different data structures so programmers don't have to.   A few benefits includes... Reducing Programming effort Increases Programming speed and Quality Allows communication between unrelated APIs Fosters code reuse You may find yourself asking, "This sounds like some

Control Flow and Branching Statements 6.27.2013 I was flipping through the Java Tutorial Book looking for interesting topics, and I found a section called "Branching Statements".  What I found was a different way in how to approach loops.  In this section, it uses 'break' and 'continue' to traverse through the loop.  When breaking from a 'for loop', it will immediately exit from the current loop, ignoring 'if statements' if there are any. Using a break statement in a set of nested for-loops Something that I immediately learned from this is that break only affects loops.  Good on me for paying attention in class!  In addition, the non-labeled break statements will only leave the inner most loop. Take for example this simple code: for(int i = 0; i < 2; i++) { System.out.print("Sam "); for (int j = 0; j < 5; j++) { System.out.print("John "); if (j == 3) break; } } It s

Today is the official start of my mission to improve my coding skills.  I've been busy getting settled back at home, and finally had time to sit down and start coding. Just for reference, the whole point of this blog is to let me record progress for myself and to keep track of the coding concepts that I learned this summer.  Definitely at the start of this blog, the coding will focus on very rudimentary concepts, but this is only too reinforce my understanding for myself of how to program properly. My goal of this blog is to provide an easy way for myself and others to understand basic and advanced topics in learning computer science. To be clear, I will mainly be focusing on Java.  I will use several different sources including the internet, and book material from: http://amzn.com/0321334205 - Java Tutorial by Sun Microsystems http://amzn.com/0470509473 - Java Concepts by Cay Horstmann will update more sources as they come along... With that, this is the introduction