CS 138 Functional Programming and Data Abstraction

Objectives

This course introduces software engineering students to elementary data structures, and to the functional programming paradigm.

Intended Audience

Software Engineering undergraduates who have taken SE 1A. It is assumed that students have experience programming in an imperative language such as C or C++.

Related Courses

Prerequisite: CS 137

Antirequisites: CS 116, 135, 136, 145, 146

Successor: CS 241.

Hardware and Software

Used in course:

  1. An integrated development environment (IDE) for C++ (such as xCode for Mac OS X).
  2. An IDE for Scheme (such as Dr. Scheme).

References

  1. Absolute C++, 4th edition, by Walter Savitch. Addison Wesley.
  2. How to Design Programs: An Introduction to Computing and Programming, by Mathias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi. MIT Press. This text is available free online at http://www.htdp.org/

    3. Schedule

    Three hours of lecture per week, plus a one-hour tutorial. Normally available in Winter only.

    Outline

    Introduction to functional programming (4.5 hours)

    Functional programming paradigm. Scheme grammar and syntax, functions, predicates, expressions, values, recursion on integers.

    Structured data (6 hours)

    Scheme memory model, lists, recursion on lists, mutual recursive data definitions, trees.

    Functional Abstraction (3 hours)

    Local definitions, lexical scope, functions as values, abstract list and tree functions.

    Advanced Recursion (3 hours)

    Design recipes for recursive algorithms.

    Mutation and encapsulation (1.5 hours)

    Mutation, sequencing of statements, state encapsulation, structures.

    Abstract Data Types and classes (3 hours)

    Abstract data types (ADTs) in C++: interfaces vs. implementation, access specification, classes, objects, object instantiation.

    List, Stack, and Queue ADTs (6 hours)

    Implementation in C++ using arrays and dynamic storage, implementation in Scheme, space and time complexity of operations, applications (nested procedure calls, parsing of arithmetic expressions).

    Tree ADT (6 hours)

    Trees and binary trees, binary search trees, preorder and postorer traversals, space and time complexity of operations, applications (dictionaries).

    Campaign Waterloo

    David R. Cheriton School of Computer Science
    University of Waterloo
    Waterloo, Ontario, Canada N2L 3G1

    Tel: 519-888-4567 x33293
    Fax: 519-885-1208

    Contact | Feedback: cs-uops@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics

    Valid HTML 4.01!Valid CSS! Last modified: Wednesday, 15-Feb-2012 10:20:08 EST


    Menu:ShowHide