General CS concepts

This is a post for general CS concepts. To make it easy to link to, i've posted each different concept under their own post. The emphasis will be on OOP (object oriented programming), and examples will either be in Java or some java-pseudo code. At the bottom of each section, i've put some simple questions that should test your understanding of the topic. Try to see how many you can get right. The answers are below them (in a slightly hidden color), just highlight the text to read the answer.

note: Please try to keep comments in this thread to a minimum, pm me about any changes you think should be made. This way the thread will be easier to navigate through. If you have a complete topic you want to add, feel free to post it :) I'll try to stay on top of this post and put any topics you add into the topics list in this post.

Topics in bold are done (and you can click on the link) Feel free to add on. Also, I've arranged these topics here in alphabetical order, but the posts below aren't because I don't know how to do that, and don't want to break any links...
Topics:
* Abstract Data Types
* Abstraction
* Algorithm Analysis
* Encapsulation
* Exceptions
* Inheritance
* Interfaces
* Methods (functions)
* Passing by Value or Reference?
* Polymorphism
* Recursion
* Static vs. Instanced
* Variables and Objects

Abstraction

Abstraction is the concept of hiding away the details. It can basically be summed up with this phrase: I don't care how it happens, just get it done.

There are many ways to abstract away the details. The main way is through methods/functions, or objects. Here's an example:

Let's say you want to test if a number is prime or not. How would you do this? You could execute this code:

Code :

---

int number = ...; // number you want to test if prime
boolean isPrime = true;
if (number < 2 || (number % 2 == 0 && number != 2))
{
     isPrime = false;
}
for (int i = 3; i < number && isPrime; i++)
{
     if (number % i == 0)
     {
          isPrime = false;
     }
}

---

But do you really want to put that code everywhere you need to test if a number is prime? No. Instead, you want to abstract away the details in a method, let's say called isPrime.

Code :

---

int number = ...; // number you want to test if prime
boolean isPrimeNumber = isPrime(number);

---

For us, it isn't necessary for us to know what the isPrime method is doing. All we need to know are this:
1. What is the name of the method? isPrime
2. What are it's inputs? an integer number you want to test if it's prime.
3. What is it's output? true if the number is prime, false otherwise. Numbers <= 1 are not prime

So, now you may be asking how do you know if isPrime works correctly, or what if it's run-time is horrible?

The answer to these is that in the perspective of the caller IT DOESN"T MATTER. When you want to mess around with the isPrime details, you can scroll over to the isPrime method and edit it's details INDEPENDENT of everything else.

This makes development and debugging much easier because you're creating an idea that people can work with. The first bit of code that calculated if a number was prime would be pretty hard to decipher quickly. If it's not, there will be ideas that you want to abstract away that will be difficult to understand. An example would be to calculate the next move a computer should make in a game of chess. I won't go into the details here (haha, that's suppose to be a pun) but wouldn't it be so much nicer if the area of code that manages turns had this code:

Code :

---

while (board.stillPlayable())
{
     numberboard.moveComputersPiece();
     board.getUsersMove();
}

---

Abstract classes

I decided this was important enough that it should go in its own sub-category under abstract. Abstract classes are those that are not completely defined on their own, but are defined for any concrete (non-abstract) inheriting classes. An example is if we had a Shape class. What is the area of a shape (aka, how do we compute this)? It's inherently undefined for a Shape, but if we inherit a class from shape, say Circle, it MUST define what the area is (unless, of course you declare that abstract as well, but that's just silly).

To make classes abstract, you simply need to put the abstract keyword in the class declaration. To declare methods abstract, you do the same thing for the methods you want to be abstract. Fields can never be abstract (can you see why?).

Abstract classes in most senses operate just like their concrete counterparts: You can have public/protected/private fields and methods, they can be static or instanced, and they can also be declared final (note: abstract methods can NOT be private or final). A special thing about abstract classes, though, is that they can NOT be instantiated directly. The reason is the class by itself is not completely implemented. What if you tried to find the area of a Shape? You will fail. The only way to use abstract classes is via Polymorphism (this is now a link, click on it!).

*Note: If a class has even 1 abstract method, it must have the abstract keyword in the class declaration.

Code :

---

public abstract class Shape
{
     public int x,y;
     public Shape(int x, int y)
     {
          this.x = x;
          this.y = y;
     }
     public abstract double Area();
}

---

So why is this above Shape class perfectly legal? I thought I said you couldn't instantiate abstract classes, yet this one has a constructor! The answer is that even though abstract classes can't be instantiated on their own, they are still a part of any inheriting classes. Thus, constructors should be and are used by inheriting classes to set up the inherited portion of the child class. For more info on this, see the Inheritance section (this is a link).

Q&A time:

Here are some simple questions regarding abstraction and abstract classes. If you can answer all these questions by yourself, you probably understand the concept of abstraction.

1. How do you declare a class abstract?

2. What is the difference between an abstract class and a non-abstract (concrete) class?

3. Why can't you instantiate an abstract class?

4. Can static methods be abstract?

5. What is the simplest way to abstract away details?

6. What must you provide in order to gain an entire concept that was abstracted away in a method without going into implementation details?

Here are the answers. I tried to conceal them some-what, i need to find a better way to do this... anyways, if you're having trouble reading them, just highlight them with your cursor.

Quote:

---

1. Put the abstract keyword in the class declaration

Code :

---

abstract class SomeClass{}

---

2. Abstract classes can have methods that aren't implemented yet (abstract methods). Concrete methods must not have any abstract methods, including those it may inherit from parent classes and those it implements from interfaces.

3. It is not completely defined. Think of what would happen if you tried calling an abstract method that hasn't been implemented yet:

Code :

---

abstract class someClass
{
     public abstract void doIt();
}

---

What should the computer do? To prevent this quandary, Java won't let abstract classes be instantiated, even if they contain no abstract methods (declaring a class abstract without any abstract methods is then of course, silly)

4. No. The reason is you call static methods from the class itself, so you could theoretically encounter the same problem as above: trying to run a method that hasn't been implemented yet.
5. With methods and classes/objects.

6. Name, parameters, and expected output. Note: how the method arrives to the expected output is incorrect (that's what the abstraction gets rid of)

---

Happy coding :)

Encapsulation

Encapsulation is a similar idea to Abstraction. It deals with restricting access to components of an object. A good analogy would be airport security. You're not allowed to bring certain things in (weapons), and you're not allowed to take (steal) certain things from the airport.

A programming example of this would be this:

Code :

---

public class ComputeSqrt
{
     private double number;
 
     public ComputeSqrt(double number)
     {
          setNumber(number);
     }
 
     public void setNumber(double number)
     {
          if (number >= 0)
          {
               this.number = number;
          }
     }
 
     public double getNumber()
     {
          return this.number;
     }
 
     public double computeSqrt()
     {
          return Math.sqrt(this.number);
     }
}

---

I realize that this is a completely pointless class, but It demonstrates in very simple terms a use of encapsulation. Here, the outside isn't allowed to access number because they could potentially set it to a negative number. Instead, Getters and Setters are used to determine what kind of access is allowed on number. In terms of Efficiency/Optimization, this technique is almost unnoticeable, and should be utilized as much as possible (obviously with different conditions based on the needs).

Pretty much anything can be encapsulated: fields, methods, constructors, even other classes.

The example for encapsulating a field was given above. Here, we'll encapsulate the constructors of a class. To do so, we use what are called "factory constructors". Factory constructors create an object when certain parameters are met, and don't when they aren't, as opposed to regular constructors which always create the object. for comparison, we'll compare it with the above ComputeSqrt class.

Code :

---

public class ComputeSqrt2
{
     private double number;
     private ComputeSqrt2(double nonNegativeNumber)
     {
          this.number = nonNegativeNumber;
     }
 
     public ComputeSqrt2 createObject(double number)
     {
          if (number < 0)
          {
               return null;
          }
          else
          {
               return new ComputeSqrt2(number);
          }
     }
     //... rest of methods
}

---

Here, we can see the advantage right away: the ComputeSqrt object is always created, but it's unknown what it means when a negative number is passed to the constructor. For ComputeSqrt2, the object is only created if a valid input is used. This can save some memory, especially if you have to create tons of objects, or objects that are quite large.

I won't talk too much about encapsulating classes here, just know that it's similar to encapsulating fields. You can declare classes inside a class, but there is this limitation:
You can't declare a purely public class inside another public class

Code :

---

public class DoIt1
{
     // Illegal!
     public class DoIt2
     {}
}

---

You can however, declare public static classes inside another public class.

I'm not sure if you can declare abstract classes or not, someone else want to shed light on this?

Here are some questions about encapsulation that should help you understand what you do and don't know about encapsulation. If you can answer all of them correctly, you probably have a good understanding of encapsulation

1. What is the primary purpose of encapsulation?

2. How do we encapsulate an idea?

3. Is this a proper way of encapsulating an idea:

Code :

---

public class SomeClass
{
     private int a;
 
     public SomeClass(int a)
     {
          this.a = a;
     }
 
     public int getA()
     {
          return a;
     }
}

---

Why or why not?

Here are the answers to the above questions.

Quote:

---

1. To direct access to a particular part of an object/class, generally fields, but methods and even classes can be encapsulated.

2. We can encapsulate with methods and classes.

3. Yes, it is. In this case, there is only a getter method for a. This means that the outside can not change the value of a. In this case, it isn't all that useful, but there will be cases where you want an internal field to be unchangeable to the outside, but changeable inside the class.

---

Inheritance

The concept of inheritance is similar to inheritance in real life: the child gets what the parent has. Also, the child still has what the child had, and can more-or-less do what it wants with what the parent had.

In computer science, there are some limitations. Remember declaring things private or protected, and thinking to yourself "these two keywords look like they're doing the same thing!"? Inheritance is why they're there. Private things are not given to the child, but protected and public are. There's not really a good analogy that I can think of for this, but hopefully it's not too hard to remember.

Another thing to keep in mind is that inheriting classes can override the methods of their parent class. An analogy could be say you have a Fararri. You inherit a Ford Cobalt. Which are you going to keep/use? Hopefully you said Fararri, because it's yours. In Java, the inheriting class always uses it's own methods/fields whenever possible. This is unlike real life, where we consider the opposite situation: you have an old 1980 pickup truck, and you inherit a Porshe 911. If you worked like Java did, you would keep using the 1980 pickup truck :P

So, let's inherit some things! Java's keyword for inheritance is extends, which makes sense because you are "extending" the capability of the parent class. In Java, it is important to note that you can ONLY inherit from one source. However, that source can inherit from another parent, which in turn can inherit from its parent, and so on and so forth so long as each only inherits from one source. Note that EVERYTHING in java inherits from the class Object.

Code :

---

public class A
{
     public int a;
     public A()
     {
          a = 5;
     }
 
     public int DoIt1()
     {
          return 2*a+DoIt2();
     }
 
     protected DoIt3()
     {
          return 4*a;
     }
 
     private int DoIt2()
     {
          return a;
     }
}

---

Code :

---

public class B extends A
{
     public B()
     {
          super();
     }
 
     public int doIt4()
     {
          return doIt1()+doIt3()+3;
     }
 
     public int doIt1()
     {
          return a;
     }
}

---

So, what will happen when we call doIt1 from B? It should return a, because we had overriden the doIt1 method in A.

What if you tried calling doIt4 from B? It would return a+4*a+3, because the doIt1 was overrided, but doIt3 was inherited from A.

The last concept I'll put is the super concept. I used it above, so what does it mean? This is a tricky way to say you want to use the Porshe 911: you're using the parent's method :) There are some limits on this:
* If in the constructor, the super method MUST be the first line if it's used. Also, if your parent class doesn't have a constructor that can be called by super() (no parameters), you MUST specify the super constructor.
* Inside other methods, the super method can ONLY be used to specify the method that it is over-riding, not any method in the parent class.
* I'm assuming here that the super can be used anywhere in other methods, but don't take my word for it.

Here are some simple questions about inheritance:

1. What is a super class?

2. What is a super constructor? How is it different from a regular constructor?

3. What does a class inherit from it's parents? What does it not inherit?

Answers are coming later :)

Happy coding :)

Interfaces

Interfaces are also known as purely abstract classes: they contain only abstract methods. An abstract method is one that has not been implemented, but defines how that method is called and what to expect back as output. It is the job of inheriting classes to implement the abstract methods.

A quick note about interfaces: while Java doesn't allow you to have one class that inherits from multiple sources, that one class can implement multiple interfaces. There are reasons for this, but I won't discuss it here (personally, I wish Java did allow multiple inheritance and got rid of the interfaces, but that's just me).

Interfaces may have fields and methods, but they can ONLY have the following modifiers on them: public, static (fields only), abstract (methods only), and/or final (fields only). The reason why you can't have private fields/methods is because they can never be used, because your interface is basically a dummy class. The same holds for protected: they can only be used by inheriting classes, but in java only interfaces can inherit from another interface, thus the protected fields/methods can never be used.

Special note about declaration modifiers (Thanks to Json):

If you leave off the modifiers public,static, and/or final, Java will implicitly add them. All fields must be public, static, and final, and all methods must be public. All methods must be public and abstract.
Example: say you typed this in:

Code :

---

public interface A
{
     int a = 5;
     void doIt();
}

---

Java will implicitly change it to this:

Code :

---

public interface A
{
     public static final int a = 5;
     public abstract void doIt();
}

---

Classes must implement interfaces, not inherit from them. This means exactly that: any class that says they will implement an interface must include all the methods within that interface. It doesn't matter if the implemented method does nothing, though.

*Special note (thanks to Json): Abstract classes don't need to implement all the methods in an interface. However, any concrete (non-abstract) class that either inherits from an abstract class, or implements that interface MUST implement all the methods.

Ex:

Code :

---

public interface Doable
{
     public final int myInt = 10;
     public boolean canDoIt1();
     public int doIt2(int num);
}

---

Notice how in the above interface you don't need to put the abstract modifier (but you can if you want) in the method signiture. This is because by definition, they must be abstract to be in an interface. Now, let's create a class that implements this interface:

Code :

---

public class Poco implements Doable
{
     // This method won't do anything
     public boolean canDoIt1()
     {
          return false;
     }
 
     public int doIt2(int num)
     {
          return 2*num;
     }
}

---

Here, class Poco must have declared inside all the methods within the interface it implements. However, we can implement the methods any way we want. Good programming practice dictates that we stick with the documentation in the interface of how the method SHOULD behave, though. That's the point of interfaces. An analogy is a Drivable interface. If we had a method called turnLeft that turned our vehicle left, we wouldn't want an implementing class to decide that the turnLeft method actually accelerates the car, though the compiler can't and won't prevents this from happening.

Here are some questions concerning interfaces:

1. What is an interface?

2. How do interfaces differ from purely abstract classes in Java?

3. What can and can't go in an interface?

Answers are coming later :)

Happy coding :)

Another note to interfaces.

When you have an interface declared like this.

Code :

---

public interface Doable
{
     int myInt = 10;
     boolean canDoIt1();
     int doIt2(int num);
}

---

The code will implicitly look like this.

Code :

---

public interface Doable
{
     [b]public static final[/b] int myInt = 10;
     [b]public[/b] boolean canDoIt1();
     [b]public[/b] int doIt2(int num);
}

---

Notice that any variables declared in the interface will become static and final because you can only define constants on an interface.

According to the rules of implementation the first concrete class has to implement the interface. This means that abstract classes do not have to implement the methods on the interface.

Code :

---

public abstract class DoStuff implements Doable {
 
}

---

// Json

Methods and Functions

For all intensive purposes, methods and functions are exactly the same. Somehow, along the way Java programmers decided they wanted to call functions as methods. Also, if you go back far enough, you might hear the term sub-routine. Again, for all intensive purposes this is the same as methods and functions, but because of the way programs worked back then (especially if you get into assembly coding), this entailed different limits sometimes. We're going to ignore these differences because with respect to Java, they can't be done (actually, most modern OS's and programming languages don't allow the use of the tricks/flaws of sub-routines).

If you've read the abstraction section, methods are the black boxes that do something. You put something in, and it gives you something out. How it works from the outside doesn't matter, so long as it does work as expected. Another section I'd suggest reading is the section on Variables and Objects, as they have some important information on variable scope and how they're used in methods.

Methods have 2 main components:

1. Method Signature: This is where you specify the method name, parameters, outputs, and various modifying keywords. Allowed keywords in Java are static, public/private/public (1 per method), and abstract. The output is any type you please (or void), but please note that methods can only have 1 official output, though there are some tricks we can do to get around this. The parameters are like the output, except you can have none or more. There are certain limits on what the name of a method can be: see the Variables and Objects section for allowed names (they're the same between methods and variables).

Code :

---

// Some standard Java method signitures
public static void doNothing() {}
public abstract boolean canDoIt();
protected SomeType doIt(int a, boolean b);

---

A special feature implemented in Java SE 5 (not quite sure on the version of this, it may be SE6) is the implementation of "variable arguments list". This basically allows the user to call the method by sending in an arbitrary number of parameters. Note however, there are some limits:
* The arbitrary number of parameters must all be of the same type. However, you may have other parameters with different types in addition to the variable arguments list
* It must be declared last in the signature

Here's some valid examples of using variable arguments list:

Code :

---

int average(int... a){}
int doAverage(boolean doIt, int... a) {}

---

The last thing the method signature must do is tell everyone what handled exceptions could possibly come up. These are exceptions that aren't caught by this method and aren't unhandled exceptions (ones that don't need to be caught by your program). Note that you can declare that your program will throw unhandled exceptions, but this doesn't force the caller to somewhere handle catching that exception. You can specify multiple types of exceptions that could be thrown by separating them with a comma.

Code :

---

public void doIt() throws FileNotFoundException
{}
public void doIt2() throws FileNotFoundException, IOException
{}

---

2. Method Body

This is where all the meat of the method is. When actually writing the method, it's important to now how the method should be implemented, since just providing the method signature with JavaDoc doesn't guarantee it will work (that'd be really nice, though). The method body is surrounded by curly brackets:

Code :

---

{
}

---

Inside the method body, you are allowed to do anything you please so long as every possibly path of execution ends in either a return statement of the correct type, or ends in throwing an exception.

Special note for void return types:

Since void specifies that your method returns nothing, it's not necessary to specify any return statement. However, if you do, just put the code return;. This tells Java you want to return, but don't want to output anything. Alternatively, if a void function reaches the closing brace, it automatically returns to the caller.

Code :

---

public void sucker()
{
     int a, b, c;
     return;     // what java implicitly does to the end of every void method
}

---

Here are some questions about methods/functions:

1. Which of the following are valid method declarations?

Code :

---

public static void 1to1(){}
public doIt(){}
protected abstract int malformed_url();

---

2. What purpose do methods/functions serve?

3. In some programming languages, variables aren't hidden when a method is used. Why would Java (and in fact, most modern languages) choose to hide variables not in scope?

Answers are coming later :)

happy coding :)

Polymorphism

Polymorphism means to view an object as several different things. Here's a simple example: A Fararri Enzo is a Fararri, which is a car, which is an automobile, which is a vehicle, which is an object. Depending on what you need to do with the object, you can view it in many different ways. In the above example, you don't really need to know all to much about the Fararri Enzo itself to drive it (err, I think. I've never actually driven one).

In programming, polymorphism arises from inheritance/interface implementation. In the above example, the Fararri Enzo is some descendant of all the other objects. However, it's not possible to go the other way. A vehicle is not necessarily an automobile, it could be an airplane. However, if you really do have an automobile, you can by definition view the vehicle as an automobile.

So why would we want this in programming?

The key idea here is abstraction. When you're operating a Fararri Enzo, it's slightly important to know some of the features specific to that object, but in general it's just like driving any other car, so why not view it as just a car? It would make coding a lot easier. Also, the idea of polymorphism helps with code re-use. Code re-use was the original reason Java was developed. Instead of creating code for a robot to drive a Fararri Enzo, and then creating more code for the robot to drive a Porshe 911 etc., you can create code code for the robot to drive a car and be done.

There are some important notices that come about when using polymorphism:

Say you had 3 classes: Shape, rectangle, and circle. Rectangle and circle both are children of shape, shape has an area method, and rectangle and circle both implement it.

Code :

---

public Shape
{
     public double area()
     {
          return 0;
     }
}

---

Code :

---

public Rectangle extends Shape
{
     double width, int height;
     public Rectangle(double width, double height)
     {
          this.width = width;
          this.height = height;
     }
     public double area()
     {
          return width * height;
     }
}

---

Code :

---

public class Circle extends Shape
{
     double radius;
     public Circle(double radius)
     {
          this.radius = radius;
     }
     public double area()
     {
          return radius*radius*Math.PI;
     }
}

---

What should happen when you try to do this?

Code :

---

public static void main(String[] args)
{
     Shape shape = new Rectangle(5.0,3.5);
     System.out.println(shape.area());
     shape = new Circle(3.4);
     System.out.println(shape.area());
}

---

Hopefully you can see that it will first print out the area of that rectangle, then print out the area of the circle. It's using the child's methods instead of the class's methods that we are viewing it as! Doesn't this seem silly? We're viewing it as a shape, but it's using the Rectangle's/Circle's method!

On closer examination, it becomes clear why this is the case: Even though you are viewing the Rectangle/Circle as a Shape, in reality they are still Rectangles/Circles, and thus their area must be computed in a specific way for each object. However, Shape tells us that for any given Shape/Shape sub-class, we can find the area using the .area() method.

This is the case when driving cars: You turn the wheel to steer, press the pedal to accelerate, and press the brake to stop. However, how much you turn the wheel and how hard you press on the pedals depends on the type of car you're in, and these details are within that specific model's declaration.

Happy coding :)

i really like this post..
more simple and basic examples please..... please....:">=D>

Recursion

For those who don't know what recursion is (and like a good laugh), click on this link: Google search: Recursion and click on the "did you mean..." item.

Hopefully you've finally figured out that recursion is anything that refers to itself (if not, then you may be stuck browsing google forever trying to find out what recursion is!). A fairly common example of recursion is the Fibonacci numbers. The pattern for Fibonacci numbers is to add the 2 previous terms together for the next term, starting with one and one.

Below is the recurrence relationship for Fibonacci numbers:

F(1) = F(2) = 1
F(n) = F(n-1)+F(n-2)

A recurrence relationship is any relationship where the original function refers to itself. So how do we find F(5)?

F(5) = F(4) + F(3)
F(5) = [F(3)+F(2)] + [F(2)+F(1)]
F(5) = [F(2)+F(1)] + 1 + 1 + 1
F(5) = 1+1+1+1+1
F(5) = 5

Seem like a lot of work? Well, to the computer it's fairly fast most of the time. Later on, I'll tell you about Dynamic Programming so we can speed this up when you want to compute large Fibonacci numbers.

So what are all the parts of a recursive function? First of all, what is a recursive function? A recursive function is any function that calls itself (either directly or indirectly). Here's a simple example in Java:

Code :

---

public static void doIt()
{
    doIt();
}

---

Of course, this will eventually cause a stack-over flow error, so it's not recommended you try this code for real.

All useful recursive functions have this general property: reduce the problem until it's so easy the computer can solve it. To fulfill this, recursive functions must have:

1. Base cases defined (cases where the solution is obvious, and can't be reduced any further)
2. Reduction step (place to simplify the given problem)
3. Recursion call to itself (basically solve the simpler case)

In the Fibonacci recursive function above, you can see that it was recursing until it was just adding up 1's. This is because in the Fibonacci sequence 1 is the base case, so we just had to add up 1 some number of times to get F(n).

In theory, all recursive functions can be written iteratively, and all iterative functions can be written recursively. However, in practice you'll find that one or the other of these philosophies will work better depending on the case.

Let's look at the Factorial function recursively, and compare it to its iterative relatives.

Factorial(N) = 1*2*3*...*N
Basically, multiply all the integers from 1 to N to get the factorial of N.

Implemented iteratively, your code would look something like this:

Code :

---

public static int iterativeFactorial(int n)
{
     int answer = 1;
     for (int i = 1; i < n; i++)
     {
          answer *= i;
     }
     return answer;
}

---

We can also write the recursive equivalent of this function:

F(1) = 1
F(N) = F(N-1)*N

can you see how this would yield the same results as the iterative factorial? Here's the code to compute factorials recursively:

Code :

---

public static int recursiveFactorial(int n)
{
     if (n == 1)
     {
          return 1;
     }
     else
     {
          return n * recursiveFactorial(n-1);
     }
}

---

So, in terms of performance, how does recursion stack up against the iterative solution here? Sadly, the answer is quite poorly. Recursive function here requires lots of memory to store the method stack and keep track of all the variables in each recursive call, while iterative solutions only have to keep track of the current state. So why even bother with recursion? Because many times when recursion is used correctly it's performance can out-strip that of iterative solutions, and recursive functions can also be easier to write (sometimes).

Dynamic Programming
Dynamic programming is a form of recursion, but it's implemented iteratively. Remember our Fibonacci computer above?

F(5) = F(2) + F(1) + F(2) + F(2)+F(1)
F(5) = 3 * F(2) + 2 * F(1)

We have quite a few "over-computations" here. It was only necessary to compute F(2) once, and F(1) once. In this case, it wasn't too computationally tasking to compute these few terms, but there will be some situations where it will become almost impossible to recompute the solutions hundreds of times. So instead of re-computing, we store the answer away.

Code :

---

public static int dynamicFibonacci(int n)
{
     int[] prevSolutions = new int[n];
     if (n == 1 || n == 2)
     {
          return 1;
     }
     prevSolutions[0] = 1;
     prevSolutions[1] = 1;
     for (int i = 2; i < prevSolutions.length; i++)
     {
          prevSolutions[i] = prevSolutions[i-1] + prevSolutions[i-2];
     }
     return prevSolutions[n-1];
}

---

So, take F(5) again. If we did it the recursive way, it would have been 8 calls to recursiveFibonacci. However, here we only computed F(1),F(2),F(3),F(4), and F(5) once. This gain of 3 less calls may not seem like much, but what if we tried computing F(50)? dynamicFibonacci will only compute 50 numbers, but recursiveFibonacci could take over 1000 (of course, I haven't counted so I don't know if it's over 1000 or not).

The last note on dynamic programming is that it only helps in cases were we have tons of over-lap. Remember the recursiveFactorial function? If we called recursiveFactorial(50) and dynamicFactorial(50), they will take roughly the same time to run because we're making the same number of computations. This is because there's no over-lap what-so ever. This is also why sorting algorithms are a poor choice to implement with dynamic programming: if you analyze most sorting algorithms, they have almost no overlapping solutions, thus is a poor candidate for dynamic programming.

Here are some questions about recursion and dynamic programming:

1. Implement the recursiveFactorial method (and you thought I had forgotten to put this in there :D )

For problems 2-5, use this recursive relationship:
F(1) = 1
F(N) = F(N-1) + N

2. For the given recursive relationship, write a recursive method that will find F(N)

3. What does this recursive relationship mean in iterative terms? Write an iterative solution to this problem.

4. Is this recursive relationship a good candidate for dynamic programming? Why/why not?

5. Is there a better way to solve this problem than the iterative or recursive solutions? What is it (if there is one)? Hint: think of Carl Gauss

Answers are to come :)

Happy coding :)

Variables and Objects

Variables and objects are basically things you can hold (err, that the computer can hold in memory). They store some sort of data that represents something. We'll start by focusing on variables.

Variables have 5 properties: data, name, type, scope, and lifetime.

Variables can be thought of as buckets. Each bucket can hold something (an object). Importantly, variables can only hold 1 item in their bucket at any one time, but that item can be changed (unless the variable is final). The item that bucket is holding is the data/value of that variable.

A variable's name is pretty self explanatory. Imagine you have a big black marker, and you wrote on the variable a name. Then, anytime someone needed that bucket (whether to put something in or take something out), they'd get the bucket labeled with that name.

A variable's type is what kind of things that variable can hold. If you had a bucket for milking cows for example, you wouldn't want to use it to change the oil in you engine.

A variable's scope is anywhere the variable can be used. Say you had a bucket on a farm in Kansas. You can use that bucket anywhere on that farm in Kansas. However, if you decide you want to milk cows in Nebraska but happen to forget your bucket, you wouldn't be able to use that bucket. However, when you come back to your farm in Kansas, you can use that bucket again.

The last characteristic of variables is lifetime. Lifetime is when the bucket physically exists. If one day you decide you want to set off dynamite in your bucket, it will cease to exist, and can't be used again.

So enough with the analogies, let's discuss variables in Java. Java variables can have any standard name that you can give to anything else:

must start with any unicode character so long as it isn't a defined operator or a digit, and anything after that can be any unicode character that isn't a defined operator. (Thanks Json :P Maybe I should actually learn something about Java before trying to help others). Quotes (single or double), brackets/braces/parenthesis, reserved Java keywords, and whitespaces are also dis-allowed.

Code :

---

//valid variable names:
Hello
i
_
$
p_3
Á

---

While any of these are valid variable names, there is a convention that is is followed in Java:

Try to find descriptive variable names. They should describe what it is that variable is for. Names like "sum", "index", and "average" are fairly common. Bad names would be "_", "$#@", etc.

It's important to note that Java is case sensitive. so the variable "Hello" would be different from the variable "hello". Conventionally, variables start with a single lower-case word, then subsequent words would have their first character capitalized. It's also fairly common to find variable names with subsequent words separated by underscores. In the latter case, all the letters are lower case.

Code :

---

public int averageHeight;
public int average_height;
public int index;

---

The type of a variable defines what that variable can hold. All variables in Java must be declared with their type and their name:

Code :

---

int someInt; // type int, name someInt
double x; // type int, name x

---

If you want a variable to be constant, or final, use the final keyword:

Code :

---

final double pi = 3.141592;

---

final variables MUST have a value set to them right away, and that value cannot change for the lifetime of that variable.

There are two main data types in Java: primitive, and objects. Objects will be discussed later. The primitive Java data types are: byte, char, short, int, long, float, double, and boolean. Note: sometimes String is considered a primitive data type because of the way the JVM handles strings, but String here will be considered objects because it will be easier to understand them as objects (and also because they technically are objects).

Primitive variables are those that hold their value directly. Object variables are those that contain a reference to an object. Object variables will be discussed later.

Scope is a bit tricky to explain. I will find a good way to explain this and post it later. For now, here are some examples.

ex:

method scope

Code :

---

public static void main(String[] args)
{
     int x = 0;
     doIt();
// point 1
}
 
public static void doIt()
{
     int y = 1;
// point 2
}

---

Here, on our original sheet (main method), the variable x is in scope and is available for use anywhere in main. When doIt is called, x goes out of scope because we got out a scratch sheet to do work for the doIt method. On that new sheet, we have y in scope. When doIt ends, y goes out of scope (actually, it disappears completely in this case) and is not available to the original main method.

Curly bracket scope

Code :

---

int a=0, b=1;
if (true)
{
     int c = 3;
// point 1
}
// point 2

---

Here, at point 1, we still have everything available from the original scope, in addition to anything available in our current scope denoted by the curly braces. At point 2, the inner curly-brace stuff goes out of scope, and we only have a and b available.

Lifetime in Java is when the variable actually exists. It's probably even more confusing than scope, and a lot of people get it confused with scope. Because of Java's garbage collector, the lifetime of any variable is from when it's first instantiated to when all references to it are gone. Ex:

Code :

---

public static void doIt()
{
     String a = "hello";
     doNothing();
}
 
public static void doNothing()
{
     String b = "goodbye";
}

---

When someone calls the doIt method, the string a will be created (and it's lifetime has started). It is also in scope because it's in the little curly brackets of the doIt method. However, when the doNothing is called, a goes out of scope, but there is still a reference to it (due to the implementation of recursion, I won't discuss the details here). The string b is then created and is in the scope of the doNothing method. The doNothing method then returns, and b goes out of scope, and is also destroyed because there are no more references to it, thus ending its lifetime. The String a comes back in scope, and because there is nothing left to do int the doIt method, it too immediately goes out of scope and is destroyed.

Hopefully this makes sense, this is probably the most confusing part about computer science (memory management/keeping track of variables).

Here are some questions about variables and objects:

1. For each of the lettered comments, describe which variables are in scope and which are out of scope. Also, give the lifetime of all the variables (when are the created, and when are they destroyed).

Code :

---

public static void main(String[] args)
{
     for (int i = 0; i < 5; i++)
     {
          System.out.println("Determining stats...");     // a
          doIt(i);
          // c
     }
     System.out.println("Done");     // b
}
 
public static void doIt(int number)
{
     if (i % 2 == 0)
     {
          System.out.println(i + " is even"); // d
     }
     else
     {
          System.out.println(i + " is odd"); // e
     }
}

---

2. What is the output of this program?

Code :

---

public static void main(String[] args)
{
     int i = 1;
     int j = 2;
     System.out.println(myFunc(i,j));
}
 
public static int myFunc(int j, int i)
{
     if (i > j)
     {
          return j;
     }
     else
     {
          return i;
     }
}

---

3. Describe in your own words the 4 defining features of a variable: name, value, scope, and lifetime.

Answers are to come sometime :)

To clarify some points above I here have two classes which will look really stupid.

Both of them are valid syntax and they show that you can use certain symbols as variable names as well as class names. It also shows you that you can create a final instance member without setting it straight away, but you HAVE to set it in the constructor or in an instance block but like above, you can only set it ONCE.

Now for the freaky stuff.

CAUTION: This is not best practise, DO NOT do this when programming

Code :

---

public class _ {
 
    public int _ = 0;
 
    public final int __;
 
    public _() {
        this._++;
        this.__ = 5;
    }
 
    public static void main(final String... arguments) {
        final _ _ = new _();
        System.out.println("_ = " + _._);
    }
}

---

Code :

---

public class $ {
 
    public final int £;
 
    public int $ = 0;
 
    public $() {
        this.$++;
        this.£ = 5;
    }
 
    public static void main(String... arguments) {
        final $ $ = new $();
        System.out.println("$ = " + $.$);
    }
}

---

And also the conclusion to the post above this one is that all Java developers are farmers :D

Happy coding! Enjoy!

// Json

Exceptions

Exceptions are special things that interrupt normal program flow. They're used to create robust methods that follow their contracts exactly. Here's a small example:

Code :

---

// * note: this code won't compile as-is, but will demonstrate our purposes here
public int doOperation(int a, int b, char operator)
{
     if (operator == '+')
     {
          return a+b;
     }
     else if (operator == '-')
     {
          return a-b;
     }
     else if (operator == '*')
     {
          return a*b;
     }
     else if (operator == '/')
     {
          return a/b;
     }
}

---

What happens if the operator given isn't +,-,*, or / ? What if they input doOperation(1,3,'@') (perfectly legal to the compiler)? Should you return 0? -1? Both of these values are valid return arguments, so there is no way for the calling method to distinguish between a valid output and one that's used to denote an error.

The answer is to use exceptions. Exceptions are thrown, and then must be caught. There are two types of exceptions: unchecked, or checked. The difference is who has to catch the exception. Unchecked exceptions don't have to be caught, and checked ones do. Note: the JVM will end up catching all exceptions that get passed to it, but this is quite nasty and means your program is completely terminated.

To throw an exception:

Code :

---

throw new Exception();

---

Generally, it's best not to just throw an exception, but actually inherit from the Exception class.
Note: the Exception class is a checked exception, so it must be caught. If you want an unchecked exception, inherit from the RuntimeException class.

So how do you catch an exception? The answer is with try/catch blocks.

Code :

---

try
{
    // code
}
catch(Exception e)
{
     // stuff to do if an Exception is caught
}

---

This format will catch all exceptions (even RuntimeExceptions, which inherit from Exception). If you only want to catch a certain branch of exceptions:

Code :

---

try
{
     // code
}
catch(NullPointerException e)
{
    // stuff to do if a NullPointerException is caught
}

---

Here, the catch block will catch NullPointerException's, and all children classes of NullPointerException.

So what if you don't want your method to catch the exception, but throw it up to the caller? For unchecked exceptions, you don't have to do anything, but for checked exceptions you have to declare in the method header that your method will throw certain types of exceptions

Code :

---

// note: InvalidOperatorException isn't a default Java Exception, but here pretend it extends the Exception class.
//There is class called UnsupportedOperationException, but to demonstrate our purposes, I chose not to use it here
public int doOperation(int a, int b, char operator) throws InvalidOperatorException
{
    ...
}

---

Here, the doOperation declaration has a checked exception, but there's also another unchecked exception that could be thrown: the ArithmeticException, which could be thrown if the user tries to divide by 0. Note that it doesn't have to be declared that the doOperation method throws this exception, but declaring that it does doesn't force the caller to catch it.

Code :

---

// will do the exact same thing as the above code
public int doOperation(int a, int b, char operator) throws InvalidOperatorException, ArithmeticException
{
   ...
}

---

The last section here (yes, finally got around to finishing it!) is about information you should include in your inherited exception class. For the most part, the Exception class will handle almost all of your needs. However, you may reach a time you will want to pass extra information back for debugging purposes such as the values of certain variables. Note that I haven't really had to do this, but it may become necessary when you start to work on larger Java projects. Doing this is exactly the same as it is for any other class, because Exception is a regular class that just happens to have the property of Throwable, as well as some other nice properties like getting the stack trace, but for all intensive purposes, there's nothing special about it beyond this.

Passing by Value or Reference?

First, let's review what values and references are.

A value is the actual data of bits and bytes which contains useful information (such as the amount of money you have in your bank account). These values are passed as copies, so any changes made to one copy don't effect the other copies. So, for example take a bank statement. The bank had to print out a copy with how much money I have and how much I owe them. I can make any changes to this bank statement (say I want to add a few zeros to the end of how much I have), but at the end of the day these changes don't affect how much I actually have.

A reference is analogous to an address. The values which are useful to us have to reside somewhere in memory, and the reference tells us where in the memory this object is. An example is a house address. If someone gets a hold of my address and decides that my door should be red, they could paint it and it would physically affect what the color of my door is.

So how is this used in Java?

In Java, all primitive values are modified by value. All objects are modified by reference. The reasons why objects are passed by reference is because some objects are actually quite large, and making a copy of these objects would take a lot longer than passing a simple 4-byte reference (or 8-byte if you have a 64-bit OS), and it may even be impossible if the object is large enough.

Now let's examine some of the consequences of these design choices:

1. When you pass a primitive, you can't change the original variable's value. This means that you must either re-design to pass an object so the value can be modified, or use a return value and then re-assign the value of the primitive.

Code Java:

---

public static void changeIt(int value)
{
    value = 5;
}
 
public static void main(String[] args)
{
    int v = 3;
    changeIt(v);
    System.out.println(v); // should print out 3
}

---

2. When you pass an object, you can change the original value. This means that the method could potentially make changes to the object that you don't want. The obvious fix to this is to manually create a copy of the object you have and pass that instead so your original object doesn't get messed up (you'll need to make a deep copy in order to ensure that everything about the original object remains the same).

Code Java:

---

public static void changeIt(int[] value) // arrays are not considered primitives
{
    value[0] = 5;
}
 
public static void main(String[] args)
{
    int[] v = new int[1];
    v[0] = 3;
    changeit(v);
    System.out.println(v[0]); // should print out 5
}

---

Some things to be careful about when using references:

TODO

Quote:

---

Originally Posted by helloworld922

The reasons why objects are passed by reference

---

Hey, I don't mean to be nit-picky, but I think this might be a bit misleading. In Java, everything, including Objects, is passed by value. More accurately, the Object's reference is passed by value (stick with me, it might sound like I'm splitting hairs but this matters).

We all know that primitives are passed by value, proved by this:

Code java:

---

public class PassByValueTest(){
 
   public static incrementVariable(int x){
      x = x + 1;
   }
 
   public static void main(String... args){
      int i = 2;
      incrementVariable(i);
      System.out.println(i); //outputs 2
   }
}

---

And it might look like Objects are passed by reference, because we can change what's passed, like so (not tested, might contain syntax errors, but hopefully gets the point across):

Code java:

---

public class PassByValueTest(){
 
   public static class WrapperClass{
      public int wrappedInt = 2;
   }
 
   public static incrementVariable(WrapperClass x){
      x.wrappedInt = x.wrappedInt+1;
   }
 
   public static void main(String... args){
      WrapperClass wc = new WrapperClass();
      incrementVariable(wc);
      System.out.println(wc.wrappedInt); //outputs 3
   }
}

---

However, that does not mean that wc is being passed by reference. If it were, we could do this:

Code java:

---

public class PassByValueTest(){
 
   public static class WrapperClass{
      public int wrappedInt;
 
      public WrapperClass(int w){
         wrappedInt = w;
      }
   }
 
   public static incrementVariable(WrapperClass x){
      x = new WrapperClass(x.wrappedInt+1);
   }
 
   public static void main(String... args){
      WrapperClass wc = new WrapperClass(2);
      incrementVariable(wc);
      System.out.println(wc.wrappedInt); //outputs 2
   }
}

---

I don't think I'm explaining it very well, so instead, maybe just read:
JavaRanch Campfire - Cup Size: a Story About Variables
and its follow-up:
JavaRanch Campfire - Pass By Value, Please

Sorry to be a nitpicker, but this is something that a lot of intermediate or even advanced Java programmers get confused. I just wanted to clear up any confusion before we perpetuate the misconception that Java passes primitives by value and Objects by reference.

In Java, everything is passed by value. Even references. That's not as confusing as it sounds.