Computer Science: First Year
The courses in the first year of a computer science curriculum must serve the purpose of laying the foundation for the curriculum as a whole. Formal Methods is one such course. It is designed to teach a sound understanding of proof and a skill in formal manipulation. Its immediate application is to programming methodology. Students will discover that to know how and why a program works, they need to view a program beyond its operational semantics. Understanding how and why a program works is equivalent to proving its correctness. Proof of correctness of a program requires the program itself to be defined as a mathematical entity. Formal Methods provides students with a methodology to set up a program as a mathematical object, build it, prove its correctness, and in the process understand it. It also teaches students to think rigorously, a skill that is valuable in all courses.
A combination of operational and mathematical thinking is needed to solve programming problems. In order for the Formal Methods course to be effective, it is necessary to complement it with a course in programming where students learn the operational aspect of programs. This role is fulfilled by the Computer Science I course, which will make use of programming methodology and will serve to re-enforce students' understanding of formal methods. The content and purpose of Computer Science I and Formal Methods are integrated. Such integration is designed to provide students with a concrete framework on which they can build and develop their problem solving skills.
Currently, the programming environment for Computer Science I and II is the Qt 4 object-oriented class library based on the C++ language. The Qt 4 class library has features that reinforce the ideas from the Formal Methods course. In particular, the library is well documented and includes the Qt 4 assert macro that supports the implementation of pre- and post-conditions for Hoare triples from Formal Methods. The library permits students to begin with the procedural approach to programming, continue through successively higher levels of abstraction, and culminate with the object-oriented paradigm. It therefore satisfies our goal of students learning multiple paradigms in the curriculum. Qt 4 also provides a powerful graphical user interface designer. With this tool, students construct programs that look like professionally developed commercial software. In addition, the Qt 4 system is provided as a free open-source system that runs on MSWindows, MacOS, and Linux computers.
Calculus is a fundamental mathematical tool for the sciences. The calculus course begins a three-semester sequence whose goal is proficiency in using this tool.
Discrete Structures presents the abstract mathematical view of fundamental data structures that form the building blocks of an algorithm. The course uses the methodology of its prerequisite course, Formal Methods, to perform complexity analysis and proof of correctness on the algorithms that manipulate data structures. It complements the concurrent Computer Science II course, which teaches the concrete implementation of data structures and algorithms in a specific programming language.
The purpose of Computer Science II is to make the transition from the procedural paradigm to the object-oriented paradigm. The steps include recursion, dynamic storage allocation, inheritance, and polymorphism. The course culminates with the implementation of abstract classes using the state design pattern as an application of object-oriented programming. Consequently, students learn abstraction by experiencing layers of abstraction, starting at the lower procedural level and progressing to the higher object-oriented level.