| home page - course objectives - practical info - handouts - lab exercises - LaTeX sources - Mike Jacobson - Renate Scheidler - links |
| Course Objectives |
In computer science, we are often presented with problems that are very similar to each other. Such as finding a record, multiplying two numbers, etc. We want to be able to solve such problems efficiently, which becomes more difficult as the input size becomes large (there are a lot of records to search through or the numbers to multiply have a large number of bits.) Hence, a lot of research is done in computer science to find efficient algorithms for common problems.
Even though designing algorithms is a very creative process, there are some techniques and approaches that often lead to efficient algorithms such as:
In this course we'll design Divide and Conquer, Dynamic Programming and Greedy algorithms.
Once an algorithm is designed, we must prove that the algorithm is correct (ie that it solves the problem it is supposed to solve) and we have to analyze the run time of the algorithm to show that it is efficient. (There are many ways to analyze the runtime of an algorithm, but most often asymptotic notation is used, which is what we'll use in this course.) We'll look at some basic techniques to analyze the run time of an algorithm and for several problems we'll design and examine multiple algorithms and compare to see which is the most efficient.
For some problems, however, no efficient solution are (suspected) to be possible. (Some of) these are the problems that are proven to be NP-Complete. Before spending (a lot) of time in trying to find an efficient solution, it is first important to know if an efficient solution exists at all (i.e., one that runs in polynomial time.) In this course we'll examine techniques that are used to prove that a problem is NP-Complete.
|
This page last modified:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc413/W05/goals.html |