CS 115| SCS | UW

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