| home page - news - syllabus - topics - schedule - assignments - tutorials - tests - java - references - Mike Jacobson |
| Introduction - Correctness of Algorithms - Analysis of Algorithms - ADTs, Stacks, Queues - Dictionaries - Searching and Sorting - Graph Algorithms |
| Introduction |
As defined in the textbook, an algorithm is “any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.”
Numerous algorithms will be studied in this course. We will often begin by describing what an algorithm does in English. The algorithm will be presented in more detail in “pseudocode” after that. The algorithm can and often will be implemented as programs using some programming language. Most of the time, in this course, the algorithms will be written as Java programs.
An algorithm is generally a tool that can be used to solve some well specified computational problem. The statement of the problem specifies a desired input/output relationship that must be satisfied.
Most of the time, there are many different algorithms that can be used to solve the same computational problem. Some algorithms are better than others. Furthermore, there are different ways to measure the usefulness of an algorithm including (to give two examples),
the time that it uses when it is run with a particular input, or
the amount of storage space (computer memory) that it uses when it is run on a particular input.
One algorithm might be better than another algorithm if you consider time, but worse when you measure space. So, choosing the algorithm that should be used to solve a given problem can be tricky, because there is no one “best” algorithm that should be selected all the time — it depends on what is important.
A data structure (or “information structure”) is a way to store and organize data that allows you to access and modify this data in a specific way. Again, no single data structure works best for all purposes. Algorithms often need to make use of data structures, and the choice of a data structure that you make can effect the performance of the algorithm that uses it.
A large proportion of computing time is spent solving a surprisingly small number of very fundamental problems. In this course you will learn about some of the algorithms and data structures that are frequently used to solve these fundamental problems. You will learn about the performance of these algorithms and data structures. You will also acquire knowledge and skills that will help you to learn about other data structures and algorithms on your own.
Section 1.1 of the course textbook includes much of the above information along with some examples. Note, however, that the textbook includes far more material than we will be able to cover in this course. Some of the material on “techniques” and “hard problems,” that is mentioned in this section of the text, will be studied in CPSC 413 instead.
The course syllabus includes quite a bit more information about the goals for this course, expectations about students’ background in computer science and mathematics, and course administration.
An exercise that will help you to get started in this course is now available. You should try to work through this exercise before the end of the first week of classes. You should know the answers to all the following (and many other similar) questions after you have done this.
What is a computational problem?
What is an algorithm?
What is a data structure?
Given an example of a “computational problem” that might be described as “fundamental.” What does this mean, and why is it important?
Why is it important to know about more than one algorithm or data structure for the same problem?
Is it permissible to talk to other students or use other reference material when working on assignments in this course? What else do you need to do, if you do talk to other students or look at other material?
Is CPSC 331 a “programming course” (in the sense that CPSC 231 and 233 are)? What does this imply about what will happen in lectures and tutorials in this course?
How many tests are there in this course? Where and when will these take place?
How do you compile and run a Java program with the computing environment that you will use at school for this course?
We will continue with a discussion of the notion of “correctness” of an algorithm as well as things that can be done in order to try to decide whether an algorithm, or a computer program, really is “correct.”
|
This page last modified:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/W07/topics/introduction.html |