History
What drove the development of the computer? Who invented the computer? What was the first computer? What is the difference between a computer and a calculator?Algorithms
Central to computer science is the notion of algorithm. An algorithm is a "formal method for solving any problem" or to be more precise an algorithm is "a sequence of unambiguous well defined instructions for performing a task in a finite amount of time". Computer programming is all about algorithms since computer programs are algorithms implemented in a computer language. To write computer programs that work, you must first write the algorithm (the hard part) then translate the algorithm into code (the easy part).
Looking at the algorithm instead of the program code allows us to concentrated on the essentials of why the chosen solution works and allows usto ignore the details of the program code. It also allows us to measure how effficient the solution is. Efficiency is measured in terms of speed and code size.
Binary Numbers: Integer and Floating Point Representation
Computer are constructed out of "bi-stable electronic components", namely
components that maintain one of two states : off or on (sort of like a
lightbulb). Because of this we use binary numbers (base 2) are used to represent
quantities.
Binary Numbers : Representing numbers in base 2 notation as opposed to
our base 10 notation and methods to convert between decimal and binary
representations.
Representing Data on the Computer
Binary Integer Representation
Floating Point Representation
ASCII Code
System Software and Operating Systems
A computer is more than just hardware. There is the software which is what really makes the computer useful and powerful. Software falls into two generally catagories : application software which "produces" information (i.e. input raw data and output the results) and system software which controls the operation of a computer. The primary example of the latter is an operating system -"the program(s) that control the allocation and usage of hardware resources and function as an interface between the user, application programs, and the hardware". When you buy a computer, you're not buying just hardware, you're also buying the operating system that allows you to use the hardware. We'll look some of the things operating systems do and look at how operating systems developed historically.
Programming Lanugages
Because of the way computers are constructed, a computer can only execute instructions encoded as binary numbers, so-called machine code. Machine code for humans is very difficult to understand and very "low-level" meaning that individual instructions are neither powerful nor complex. So computer scientists have developed "high-order languages" (HOL) which are easier for humans to work with and which have powerful and complex instructions. Programs are written in HOL's and translated into machine code. We'll look at two area of interest
Models of Computation - Finite State Machines and Turing Machines
What does it mean to "compute" and what kinds of problems can a computer solve? We'll briefly look at two "theoretical" computer constructs : Finite State Machines which are very "weak" but can easily solve a number of useful problems, and Turing Machines which can solve any problem a "real" computer can. Turing machines are used to define that it means "to compute".
Computational Complexity - Measuring Efficiency
How can we measure how good a program (i.e. algorithm) is? We use time and space measures - how long the program takes and/or how much memory is needed. To measure the speed of a program, you could measure the time it takes a program to run for different sized "inputs" except the speed of the processor has a direct bearing on how fast the program runs. A better way it to count the "critical" operations done by the program. When we do this we see that the number of times a critical operation is done is often function of the size, n, of the input. Sometimes we see linear growth (we call this "big O of n" - written O(n)). Other times we see quadratic growth, "big O of n2" written O(n2). In the worst cases we see exponential growth "big O of bn" - O(bn) which means (ultimately) that is takes too much time to run the program.
Networks and the World Wide Web
During much of this course you will be writing application software in C++. But application software also includes wordprocessors, spreadsheets, databases, e-mail, presentation software, graphics packages etc. We'll look briefly at two interesting applications areas : networks since the Internet and the World Wide Web occupy a large part of today's world.
Societal and Ethical Issues
An entire course could be designed around the social impact of computers and information technology. We'll briefly examine just a few issues.