CS111F. Introduction to Functional Programming

Introduces the basic concepts of programming in the context of a functional language that emphasizes algorithmic strategies over syntactic detail.

Prerequisites: none

Syllabus:

Overview of the history of computing
Procedural abstraction: Simple functions; parameters and results; composition; conditional expressions
Recursion: The concept of recursion; recursive mathematical functions; simple recursive procedures
Data abstraction: List structure; hierarchical data; symbolic data; the importance of data abstraction
Algorithms and problem-solving: Problem-solving strategies; the role of algorithms in the problem-solving process; implementation strategies for algorithms; debugging strategies; the concept and properties of algorithms
Algorithmic strategies: Brute-force algorithms; greedy algorithms; divide-and-conquer; backtracking; numerical approximation algorithms
Basic computability theory: Tractable and intractable problems; the existence of noncomputable functions
Basic computational complexity: Asymptotic analysis of upper and average complexity bounds; big-O notation; standard complexity classes; empirical measurements of performance
Overview of programming languages: History of programming languages; brief survey of programming paradigms; the role of language translation in the programming process
Evaluation strategies: Representing computation state; streams; lazy evaluation; nondeterminism; the construction of an interpreter
Machine level representation of data: Bits, bytes, and words; numeric data representation and number bases; signed and twos-complement representations; representation of nonnumeric data

Units covered:

DS5 Graphs and trees   3 core hours (of 4)

PF1 Fundamental programming constructs   3 core hours (of 9)

PF2 Algorithms and problem-solving   2 core hours (of 6)

PF3 Fundamental data structures   6 core hours (of 14)

PF4 Recursion   5 core hours

AL1 Basic algorithmic analysis   2 core hours (of 4)

AL2 Algorithmic strategies   2 core hours (of 6)

AL3 Fundamental computing algorithms   4 core hours (of 12)

AL5 Basic computability   1 core hour (of 6)

OS3 Concurrency   2 core hours (of 6)

PL1 Overview of programming languages   1 core hour (of 2)

PL4 Declarations and types   1 core hour (of 3)

PL5 Abstraction mechanisms   1 core hour (of 3)

PL7 Functional programming   4 hours

SP1 History of computing   1 core hour

SE1 Software design   1 core hour (of 8)

SE3 Software tools and environments   1 core hour (of 3)

Notes:
[to be supplied]

Online resources for CS111F

CC2001 Report
December 15, 2001

DS5	Graphs and trees	3	core hours (of 4)
PF1	Fundamental programming constructs	3	core hours (of 9)
PF2	Algorithms and problem-solving	2	core hours (of 6)
PF3	Fundamental data structures	6	core hours (of 14)
PF4	Recursion	5	core hours
AL1	Basic algorithmic analysis	2	core hours (of 4)
AL2	Algorithmic strategies	2	core hours (of 6)
AL3	Fundamental computing algorithms	4	core hours (of 12)
AL5	Basic computability	1	core hour (of 6)
OS3	Concurrency	2	core hours (of 6)
PL1	Overview of programming languages	1	core hour (of 2)
PL4	Declarations and types	1	core hour (of 3)
PL5	Abstraction mechanisms	1	core hour (of 3)
PL7	Functional programming	4	hours
SP1	History of computing	1	core hour
SE1	Software design	1	core hour (of 8)
SE3	Software tools and environments	1	core hour (of 3)