As usual, create a directory to hold today's activities:
$ mkdir ~/cs170/labs/lab15 $ cd ~/cs170/labs/lab15
For any given problem, there are usually many, many different ways to solve it. Some solutions, however, are better than others. In computer science, this is doubly so. There can be multiple different algorithms for solving a problem (like linear vs. binary search). When would we chose one algorithm over the other?
Our mechanism for this comparison is Big-O analysis. This encapsulates the worst-case running time of an algorithm. We will briefly talk about what that looks like for linear vs. binary search.
For the most part, every single thing we read from the user in our computer comes in as a string of characters. However, we often want to treat what we read from the user as a number, be it an integer or a floating point number. In order to accomplish this, we need some mechanism that can read and interpret what the characters of the string represent.
In a file called parseInt.cc, write a function
called int parseInt(string numberString)
. This
function takes a single parameter: A string of characters. It
should return an integer, which is the numeric representation of the
integer stored within the numberString. You can assume that the
numberString contains only digit characters, or the '-' symbol.
Step one of this process is designing your algorithm. How will you proceed? Once you've defined your algorithm, try to figure out what you believe the Big-O class of your function is. What is N? How does the run time change depending on N? Write the answers to these questions in comments within the parseInt.cc file before you get checked off.
What test cases do you need for this function? What are the edge cases? How many test cases should you define? Define your own test cases (preferably before you start coding!), and be prepared to defend whether or not they are adequare test cases.
You are going to use our classic accumulator pattern for this algorithm. Create an accumulator that starts at 0, and incrementally add numbers to it.
Everything in a computer is stored as a number, even characters of a string. Characters in a string are stored encoded using ASCII notation. This means that we can add and subtract characters of a string. If you know that your character is a digit, you just need to subtract the ASCII value of '0' from it.
You need powers of 10 for this. However, you shouldn't need a power function!
Parsing an integer doesn't have too many weird edge cases to
consider. However, parsing a floating point number is a little
bit trickier. Write a function called float
parseFloat(string numberString)
, which returns the floating
point representation of numberString. You can assume that the
string contains only '-', digit characters, and a single '.'.
Everything in your computer is stored as a series of 1's and 0's. Every time the computer goes to display something, the computer determines what it should be displayed as, and converts it into a number we recognize. However, it's sometimes useful to think about what is going on behind the scenes.
In a file called toBinary.cc, write a function
called string intToBinary(int toBinary)
. This
function takes a single parameter: a positive integer. It
should return a string, which is the binary representation of the
integer parameter. Your returned string should always contain 32
characters.
Step one of this process is designing your algorithm. How will you proceed? Once you've defined your algorithm, try to figure out what you believe the Big-O class of your function is. What is N? How does the run time change depending on N? Write the answers to these questions in comments within the parseInt.cc file before you get checked off.
What test cases do you need for this function? What are the edge cases? How many test cases should you define? Define your own test cases (preferably before you start coding!), and be prepared to defend whether or not they are adequare test cases.
The process defined here works for positive integers, but will behave weirdly for negative integers. Modify your program so that it correctly processes negative numbers.