CS 115 Introduction to Computer Science 1
Objectives
This course introduces the principles of program design and the fundamentals of computation through functional evaluation.
Intended Audience
CS 115 is intended for students who are familiar with the use of a computer (Web browsing, etc.) but who have no experience with programming.
Related Courses
Prerequisites: None.
Antirequisites: CS 121, 122, 123, 125, 131, 132, 133, 135, 137, 138, 145, CHE 121, CIVE 121, ECE 150, GENE 121, PHYS 139, SYDE 121
Successor: CS 116.
Hardware and Software
Used in course: Programs are written in subsets of the language Scheme. Student labs are equipped with the DrScheme integrated development environment running on networked personal computers. Versions for Windows, Mac OS, Unix/X and Linux are freely downloadable for use on computers owned by students.
References
How To Design Programs by Felleisen, Findler, Flatt, and Krishnamurthi, MIT Press, 2001. This book is available in its entirety on the Web, though students are encouraged to purchase a physical copy.
Course notes are also required.
Schedule
Three hours of lecture per week, plus a lab, and a tutorial.
Outline
Introduction (4 hours)
Course philosophy and logistics. Numbers and arithmetic. Prefix notation for expressions. Simplifying expressions by substitution. Definition of functions: syntax and terminology. Helper functions.
A First Design Recipe (4 hours)
A design recipe for a function, with a contract, purpose, examples, definition, and tests.
New Forms of Data (4 hours)
Boolean functions and conditions; conditional expressions. Symbols and strings. Compound data and user-defined structures. Data definitions. Functions that operate on compound data. Type predicates. The design recipe for mixed data.
Lists (4 hours)
Constructing lists; functions for operating on lists. The recursive definition of a list. Visualizations of lists as nested boxes and as box-and-pointer diagrams. Functions which process lists. The design recipe for self-referential data definitions. Lists which contain structures.
Working With Recursion (4 hours)
A recursive definition of a natural number. Analogies to lists. Processing natural numbers: counting down, counting up. Auxiliary recursive functions. List abbreviations.
Combining Structures and Lists (4 hours)
Data definitions with more than one recursive clause, leading to trees (example: ancestor family trees). Representation of trees using structures and using lists. Leaf-labelled trees (list representation) and node-labelled trees.
Mutually Referential Data Definitions (4 hours)
Design recipe for functions using mutually referential data definitions. Development through iterative refinement. Three patterns for processing two lists simultaneously.
Local Definitions (4 hours)
Local definitions and their use in organizing code and improving efficiency. Encapsulating auxiliary functions and definitions. Lexical scope and block structure.
Functional Abstraction (4 hours)
Functions as values. Abstracting from examples. The use and design of abstract list functions: map, filter, reduce.
