Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Computer Science Tripos Syllabus - Introduction to Algorithms
Computer Laboratory > Computer Science Tripos Syllabus - Introduction to Algorithms

Introduction to Algorithms next up previous contents
Next: Java Case Study Up: Michaelmas Term 2004: Part Previous: Group Project   Contents


Introduction to Algorithms

Lecturer: Dr M. Richards

No. of lectures: 4


Aims


This course is a brief introduction to discrete mathematics. It covers core elements of the subject to make the Data Structures and Algorithms course accessible to people who have not seen any significant discrete mathematics before. In particular, it covers topics which are covered in Part IA which are useful for the Data Structures and Algorithms course.


Lectures

  • Common mathematical notation.

  • Sets, tuples, functions.

  • Relations (e.g. telephone directory) and Graphs (e.g. air routes). Induction.

  • Combinations and permutations.

  • O(f) notation, sorting as example.

Objectives


At the end of the course students should

  • be familiar with the mathematical notation used in several areas of discrete mathematics

  • be able to find O(f) notation representations of the growth rates of functions defined by certain recurrence relations

  • be able to construct mathematical proofs involving induction

  • be familiar with set notation and how to reason about sets and relations over sets

Recommended books


For many people the best advice is simply to read the books in the Data Structures and Algorithms course. The book
Lipschutz, S. (1976). Schaum's outline of theory and problems of discrete mathematics. McGraw-Hill.
has a good ``solved problems'' approach which may be useful for students who have not seen discrete mathematics before.


Those who would like to know much more about discrete mathematics can try:

Stanat, D.F. & McAllister, D.F. (1977). Discrete mathematics in computer science. Prentice-Hall.
Mattson, H.F. Jr (1993). Discrete mathematics with applications. Wiley.
Skvarcius, R. & Robinson, W.B. (1986). Discrete mathematics with computer science applications. Benjamin/Cummings.
Graham, R.L., Knuth, D.E. & Patashnik, O. (1989). Concrete mathematics. Addison-Wesley.



next up previous contents
Next: Java Case Study Up: Michaelmas Term 2004: Part Previous: Group Project   Contents
Christine Northeast
Wed Sep 8 11:57:14 BST 2004