Computing Science Basics
Computing Science Basics
If we're here to study computer science
, what is it?
Before we can answer that…
Algorithms
First, let's talk about what an algorithm is.
Simple definition: a set of instructions that can be used to solve a problem.
A non-computing example of an algorithm…
Algorithms
- Combine the room-temperature butter and the sugar. Mix until light and fluffy.
- Add the eggs to the creamed butter and mix to combine.
- In another bowl, combine the liquid ingredients and mix to combine.
- Sift together the flour and other dry ingredients.
- Alternately add the dry and liquid ingredients to the butter-egg mixture. Mix just enough to combine.
Algorithms
Of course, we're more interested in the kinds of algorithms that can be completed by computers, but this isn't so different. It has some problems, though:
Alternately add the…
. How many times should you alternate? 2? 3? 20?- What are we making? What if we don't want cake?
- What is
room-temperature butter
? What if your room is so warm the butter melts?
Algorithms
Here's a better definition that we can work with:
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time. Anany Levitin, Introduction to The Design & Analysis of Algorithms
Algorithms
Some words to note from that definition:
Unambiguous
: when you read an algorithm, there should be no question about what should be done.
Problem
: an algorithm should be a solution to a particular problem. Each algorithm is designed with a particular group of problems in mind.
Legitimate input
: an algorithm might need some kind of input to do its job. If we give it non-sensical input, we can't expect it to work.
Algorithms
One more qualifer to note: finite amount of time
.
Suppose we had one more step in the recipe:
- Stir until it turns red.
No amount of stirring is ever going to make that happen: that step can't be completed in a finite amount of time.
Algorithms
Computers are good at following algorithms, if they're expressed correctly and have the kinds of steps computers can do.
i.e. calculations expressed in a programming language.
Data Structures
Many of the we will deal with will be manipulating some kind of information/data. How we store this data will have an effect on the algorithm we use.
More later.
Computer Science
Computer science isn't about fixing computers or learning to use computers. It not even really about programming.
Computer science is no more about computers than astronomy is about telescopes, biology is about microscopes or chemistry is about beakers and test tubes. Science is not about tools, it is about how we use them and what we find out when we do. Anany Levitin, Computing Research News, January 1993
Computer Science
A reasonable definition of computer science:
The study of algorithms, includingG. Michael Schneider and Judith L. Gersting, An Invitation to Computer Science
- Their formal and mathematical properties.
- Their hardware realizations.
- Their linguistic realizations.
- Their applications.
Some notes on that definition…
Computer Science
Their formal and mathematical properties: this includes asking questions like what problems can be solved with algorithms,
for what problems can we find solutions in a reasonable amount of time,
and is it possible to build computers with different properties that would be able to solve more problems?
Computer Science
Their hardware realizations: One of the goals when building computers is to make them fast. That is, they should be able to execute algorithms specified by the programmer quickly.
This problem has mostly been ceded to computer engineering.
Computer Science
Their linguistic realizations: There are many ways to express algorithms so a computer can understand them. These descriptions must be written by a person and then followed by a computer.
This requires some language
that can be understood by both people and computers.
Computer Science
Their applications
: What actual useful things can be done algorithmically? Is it possible for a computer to understand a conversation? Can it find fraudulent credit card transactions? If the answer to any of these is yes
, then how?
Computer Science
Or roughly: computer science is about algorithms, including how to implement them (e.g. programming).
Expressing Algorithms
There are many ways to express algorithms. Sometimes specifically for people. Sometimes specifically for computers (but maybe readable/writable by people).
You have probably seen some, e.g. recipes or…
Expressing Algorithms
Expressing Algorithms
Expressing Algorithms
Sometimes it's useful to express an algorithm in a way similar to a programming language, but without as many rules so it's more convenient for people.
Pseudocode is often used for this: pseudo-
almost.
Pseudocode is an informal description of steps that could be turned into a program.
Expressing Algorithms
I don't usually write pseudocode, but it can be useful to describe an algorithm without having to worry about every detail.
An example…
Expressing Algorithms
- Tell the user to pick a number between 1 and 100.
- The smallest possible number is 1; the largest is 100.
- Until we guess correctly…
- Make a guess halfway between the smallest and largest.
- Ask if your guess is too large, too small or correct.
- If they say you're correct, the game is over.
- If they say your guess is too small, the smallest possible number is now the guess plus one.
- If they say your guess is too large, the largest possible number is now the guess minus one.
Let's play.
Expressing Algorithms
But all of these ways to express an algorithm have a really big drawback: computers can't understand or follow them…