George Mason University
DEPARTMENT OF COMPUTER SCIENCE
CS 310, CS 330 and Math 114 (C or better in all).
Catalog Description:
Analysis of the computational resources required for important problem
types by alternative algorithms and their associated data structures, using
mathematically rigorous techniques. Specific algorithms are analyzed and
improved.
Instructor's Comments:
Algorithms capture fundamental ideas of computational systems. This course is about creating and explaining algorithms. It is also about proving that they really work in all possible cases, and showing how much time they take when confronted with a large version of the problem for which they were designed. If they're not so fast, then we also have to think about how to modify them. Sometimes properly organizing the data makes a crucial difference, so we will look at a variety of data structures and how they support related algorithms. The problems that the algorithms and data structures are designed to solve come from a wide variety of interesting and important application areas. Many of them may at first glance look like arbitrary mathematical puzzles, but that is because certain details have been abstracted away in the interests of clarity and generality.
An outline of 7 important sets of concepts that you will learn more about in
this course is available and can help orient you to what we are trying to
achieve and why. It's on a page called
"Key Ideas of CS 483."
Introduction to Algorithms, Second Edition
Thomas H. Cormen, Charles E. Lieserson, Ronald L. Rivest and Clifford Stein
MIT Press & McGraw Hill, 2001
From the Preface:
The updated new edition of the classic Introduction to Algorithms is intended primarily for use in undergraduate or graduate courses in algorithms or data structures. Like the first edition, this text can also be used for self-study by technical professionals since it discusses engineering issues in algorithm design as well as the mathematical aspects. [The new edition] continues to provide a comprehensive introduction to the modern study of algorithms. [It] presents a rich variety of algorithms and covers them in considerable depth while making their design and analysis accessible...
You will notice the column title "Study Material" at the top of the second column of the assignments. Referring to this as as study material rather than just reading material, suggests that it should be read slowly, carefully and more than once. Moreover the examples - which take the form of algorithms and figures with despcriptions in the text - should not merely be read. Rather you should put them aside and challenge yourself to reproduce them. For more on this see "How to Succeed in CS 483."
You will also notice that there are "recommended problems." This is a
strong recommendation. That is, you should always do the
recommended problems, in advance if possible. For example, upon arrival in
class on day 3 (the first class of the second week) you should certainly
have completed the problems for day 2 and you should have made some attempt
at those for day 3, whether or not there has been any announcement about
collecting either of these. Some of the problems will never be collected,
but you can expect things in the homework to turn up on quizzes or exams,
possibly in an altered form. For more on how to study and make use of the
recommended problems, see
"How to Succeed in CS
483."
Homework & Quizzes 30% Midterm Exams 30% Final Exam 40%On most Thursdays, class will begin either with handing in assigned homework or with a quiz on that homework. Quizzes are closed book with no notes.
The final will cover the whole course but will place enough additional emphasis on the material studied after the second exam to compensate for the fact that this last material has not been on either of the two exams.
All testing is closed book. However, you may use notes, subject to the following Rules for exam note sheets:
Please be sure that you are aware of all provisions of
the GMU Honor Code.