This course introduces software engineering students to elementary data structures, and to the functional programming paradigm.
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++.
Prerequisite: CS 137
Antirequisites: CS 116, 135, 136, 145, 146
Successor: CS 241.
Used in course:
Three hours of lecture per week, plus a one-hour tutorial. Normally available in Winter only.
Functional programming paradigm. Scheme grammar and syntax, functions, predicates, expressions, values, recursion on integers.
Scheme memory model, lists, recursion on lists, mutual recursive data definitions, trees.
Local definitions, lexical scope, functions as values, abstract list and tree functions.
Design recipes for recursive algorithms.
Mutation, sequencing of statements, state encapsulation, structures.
Abstract data types (ADTs) in C++: interfaces vs. implementation, access specification, classes, objects, object instantiation.
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).
Trees and binary trees, binary search trees, preorder and postorer traversals, space and time complexity of operations, applications (dictionaries).