Revised May 12, 2016
CS 115: Introduction to Computer Science 1
General description
- This course introduces students to key concepts in the field of Computer Science through the use of a functional programming language.
Logistics
Audience
- 1A students in the Faculty of Mathematics
- Students interested in pursuing a Computer Science minor
- Students interested in learning more about Computer Science
Normally available
- Fall, Winter, and Spring
Related courses
- Predecessors: None
- Successors: CS 116
- Co-requisites: None
- Conflicts: CS 135, CS 145, CS 137, and other courses in introductory computer science
For official details, see the UW calendar.
Software/hardware used
- Racket programming language
- DrRacket programming environment
Typical reference(s)
- M. Felleisen, R. Findler, M. Flatt, S. Krishnamurthi, How To Design Programs, MIT Press (First edition)
Required preparation
At the start of the course, students should be able to
- Demonstrate a basic understanding of mathematical concepts, including functions
No programming background is assumed.
Learning objectives
At the end of the course, students should be able to
- Given a clear and concise statment of a problem or task, write a program from scratch of up to fifty lines of properly-formatted, tested, and documented Racket code to solve the problem or carry out the task
- Use elementary data structures, such as lists and trees, in programs
- Use abstract list functions in programs
Typical syllabus
An introduction to functional progamming (24 hours)
- Basics of Racket: function application and definition in mathematics and in Racket, formal grammar and syntax, the substitution model, primitive data types (numbers, strings, characters, Boolean)
- Conditional expressions, including nested conditionals
- Design recipe for moving from problem description to code that processes data
- Structures and their semantics in the substitution model
- Lists of primitive types, lists of structures, and nested lists
- Structural recursion on lists and integers and on two recursive values using the design recipe
Data abstraction (7.5 hours)
- Basic dictionaries (number keys and string values) implemented using association lists and binary search trees
- Binary trees and general trees
- Applications, including the evaluation of arithmetic and Racket expressions (involving the use of mutual recursion)
Functional abstraction (4.5 hours)
- Functions as values, including parameters to other functions
- Abstract list functions (with a focus on map, filter, foldr, and build-list)
- Local definitions for both constants and functions
- Scope
- Lambda
