Monday, February 9, 2015

How to Solve Computer Science Problems


Computer Science is a fairly new discipline to education, and as it slowly integrates itself into common curricula, students can gauge not only how computers (which they so avidly utilize) work, but also how to critically follow procedure, using correct syntax, for any given problem. It sounds a little like mathematics, doesn't it?


Below you will find a small program I have written in Java that allows for user input of any integer (for as large as integers go in Java, you can look that up,) and returns all integer factors for that number. You can see that it will convert negative integers to positive, and will output a statement for prime numbers. This program was in request of the following word problem:

Write a program that prints all integer factors of an integer. If negative, use the absolute value.

It's important to see how to solve a problem before you tackle it. What should we expect from the code, especially if it has some sort of output? Ask yourself these questions:
  • Does the program require a specific input? What kind of input?
  • Does the program require a specific output? What kind of output?
  • Can I describe or write what I can expect from the program?
The last question is important. It's the first step in test-driven development. This is a "buzz word", as my CS professor called it. Before even writing any kind of code, make a table of cases, or possible inputs and outputs of the program. Again, what can we expect to see printed out if we input something?
Test Cases
possible inputs expected output
-3 1, 3
0 ???
1 1
6 1, 2, 3, 6
... ...

So you see where this is going. If you do not know the output of a possible input, that's okay. That means you should think a little bit harder about the problem and what it truly is asking, or that you've run into something that's a special case. These special cases, or border cases, typically have to do with inputs that may do weird things or have peculiar characteristics. In this situation, the number zero is a special integer, in that it is neither positive nor negative. It does not have any factors, besides itself and every real number! So, as the programmer, you should decide: will my program deal with this special case, will it choose to ignore it, or will I ignore it entirely and let my code be a waste? Up to you to decide. It's also interesting to note the amount of test cases you are writing. You could technically have an infinite amount of them, one for each corresponding integer. But that would be inefficient. I wrote four - one for each kind of input. This is like a math problem: the domain of what I am inputting (the x values) is:
  • All negative integers,
  • Zero (a border case),
  • One (a border case),
  • and all positive integers.
You could write more to consider prime numbers, for instance. This is my take on the problem. The bottom line is, writing, or at least thinking about, test cases is crucial to your understanding of what kind of program you're going to be writing.

Once you have an understanding of what the problem wants, you should now think about how you're going to write the code. It does not have to be in any formal syntax, just a general idea of what the steps are for the computer to take. Math has a predetermined process, and if you follow them exactly and correctly, you will reach the correct result. In Computer Science, the programmer creates that list of instructions.This pseudocode can even be in plain English.

1. input = get an integer from the user
2. print all integer factors of input

Okay, fine, so it's not that easy. Let's try again. Remember the modulus operator (%)? This is a very powerful tool in many computer languages. It returns the REMAINDER amount from a division operation. For example, 6 % 3 = 0, because 3 divides into 6 cleanly, with no remainder. 6 % 5 is 1, because 5 goes into 6 once, with a remainder of 1.

 1. input = get an integer from the user
2. if (input % 1 is 0)
      print 1
3. if (input % 2 is 0)
      print 2
4. if (input % 3 is 0)
      print 3
...

This is a fair way to approach the problem, but as you can probably tell, this code is inefficient. You have a computer that can make decisions for you, very quickly. These conditions are giving it only ONE decision to make at a time. It is lengthy, not to mention it will go on forever. What if the user inputs 100? Or even 20, for that matter? That's a lot of conditions. I appreciate the thought of approaching the problem this way, but in these situations, you should think of different kinds of conditional statements or loops that the programming language has to offer. The for-loop is especially strong for this.

1. input = get an integer from the user
2. walk through every number less than input, if (input % x is 0)
      print x, then increase x by 1 until x = input

This looks like it will work. Try your test cases against your psuedocode. Does it work? Then see if you can convert it to the syntax of the language you would like to write in.

Execute:


#include <iostream>
#include <cmath>
using namespace std;

/*
 * Prints the factors of an integer.
 */
void findFactors(int n) {
    
    //unsigned integer x is assigned to the absolute value of the parameter, n
    uint x = std::abs(n);
    
    //for loop walks through every integer less than x
    for(uint i = 1; i <= x; i++) {
        if(x % i == 0)                   //if the loop variable is a factor,
            std::cout << i << " ";       //print it out, as well as a space
    }
}


I hope this helps!   
Posted by