< Back

Lecture 15- Algorithms and Architecture


As usual, create a directory to hold today's activities:

  $ mkdir ~/cs170/labs/lab15 
  $ cd ~/cs170/labs/lab15

Big-O Notation

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.


Lab Activity 1
Parse Int

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.

Details

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.

Test Cases

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.

Hint

  • 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!

 

Challenge

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 '.'.


Lab Activity 2
Integer to Binary

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.

Details

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.

Test Cases

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.

 

Challenge

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.