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