About This Course

Some introductory computer science courses that are programming-intensive include a significant amount of material about the correctness of the algorithms that are being coded. On the other hand, this topic is often left for later courses: It may not even be possible to include it if the first course is part of an applied or multidisciplinary program or if the program does not include a significant amount of material about discrete mathematics and logic.

Similarly, some first courses in data structures include proofs of both the correctness and the efficiency of the algorithms that are presented in them. Others do not. Once again, it might not even be feasible to include this kind of material in a data structures course, if the course has no prerequisites in discrete mathematics and logic that emphasize the development of mathematical proofs. If the course includes a significant amount of material on the applications of data structures then there might not be room for material about correctness and efficiency even if the necessary mathematics prerequisites are in place.

Sometimes this material gets included as part of a first course in discrete mathematics, to provide applications of the more foundational material (on types of proofs, notably including proofs by mathematical induction) that is being discussed. However, the presentation of this material can be very different in a mathematics course than in a computer science course.

Computer Science 105 is a short course (with 12 lecture hours, running during block week) that introduces some of the material on the correctness and efficiency of algorithms that is mentioned above. It is intended primarily for students who have completed introductory courses in computer programming and data structures that are parts of applied or multidisciplinary programs and who wish to be better prepared for senior courses on the design and analysis of algorithms or, more generally, for senior courses in theoretical computer science.

The class will meet from 9:00am until 11:50am from Tuesday, January 3 until Friday, January 6 (during block week) in MS 217.

Required Background

Computer Programming

An introductory course in programming, in which students have learned to write simple “iterative” programs (with tests and loops) as well as simple “recursive” programs, is assumed as background. At Calgary, students who have successfully completed either Computer Science 231 or Computer Science 219 will have satisfied this requirement (Computer Science 217 has most, but not all, of the material that is needed here.)

Data Structures and Algorithms

An introduction to data structure that includes search trees and graphs, as well as classical algorithms for searching and sorting, is also required. At Calgary, students who have successfully completed either Computer Science 319 or 331 will have satisfied this requirement.

Note: Currently, only Computer Science 319 is listed as the prerequisite in data structures for Computer Science 105. Students who have completed Computer Science 331 instead but who are interested in Computer Science 105 should contact the course instructor for more information.

Discrete Mathematics and Logic

An introductory course in discrete mathematics in which students have been required to write mathematical proofs — notably including mathematical induction — is also required. At Calgary, a student who has successfully completed either Mathematics 271 or 273 will have satisfied this requirement.

Automata and Computability

A first course in automata and computability, that introduces finite state machines and context-free grammars, provides opportunities for students to write mathematical proofs to solve problems in computer science. The proofs that are needed here are similar to, but generally easier than, the proofs that will be discussed in Computer Science 105. Thus a first course in automata and computability can be quite valuable as preparation for a course like Computer Science 105, and Computer Science 313 is a prerequisite for it.

Note: A considerable number of computer science programs do not require (or even offer) a course like Computer Science 313 at all! Students who have met all of the other requirements for this course, but have not completed Computer Science 313 or an equivalent course, should contact the course instructor if they are interested in completing Computer Science 105 anyway.

Topics

The following topics will be discussed on each day of the course.

• Tuesday, January 3: Mathematical Proofs, and Proof Techniques Introduced in MATH 271
• Wednesday, January 4: Using Mathematical Induction to Solve Problems in Computer Science
• Thursday, January 5: On the Correctness of (Simple) Algorithms
• Friday, January 6: On the Analysis of Algorithms; A Review of Asymptotic Notation, and Useful Mathematical Functions

Assessment

Exercises will be assigned at the end of each of the meetings on Tuesday, Wednesday, and Thursday. Students will be required to hand in written solutions to these exercises (which the instructor will assess and return by the following day). Each one of these exercises must be submitted for assessment in order for credit for this course to be received.