(*^
::[ Information =
"This is a Mathematica Notebook file. It contains ASCII text, and can be
transferred by email, ftp, or other text-file transfer utility. It should
be read or edited using a copy of Mathematica or MathReader. If you
received this as email, use your mail application or copy/paste to save
everything from the line containing (*^ down to the line containing ^*)
into a plain text file. On some systems you may have to give the file a
name ending with ".ma" to allow Mathematica to recognize it as a Notebook.
The line below identifies what version of Mathematica created this file,
but it can be opened using any other version as well.";
FrontEndVersion = "Macintosh Mathematica Notebook Front End Version 2.2";
MacintoshStandardFontEncoding;
fontset = title, inactive, noPageBreakBelow, nohscroll, preserveAspect,
groupLikeTitle, center, M7, bold, e8, 24, "Times";
fontset = subtitle, inactive, noPageBreakBelow, nohscroll, preserveAspect,
groupLikeTitle, center, M7, bold, e6, 18, "Times";
fontset = subsubtitle, inactive, noPageBreakBelow, nohscroll,
preserveAspect, groupLikeTitle, center, M7, italic, e6, 14, "Times";
fontset = section, inactive, noPageBreakBelow, nohscroll, preserveAspect,
groupLikeSection, grayBox, M22, bold, a20, 18, "Times";
fontset = subsection, inactive, noPageBreakBelow, nohscroll,
preserveAspect, groupLikeSection, blackBox, M19, bold, a15, 14, "Times";
fontset = subsubsection, inactive, noPageBreakBelow, nohscroll,
preserveAspect, groupLikeSection, whiteBox, M18, bold, a12, 12, "Times";
fontset = text, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7,
12, "Times";
fontset = smalltext, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 10, "Times";
fontset = input, noPageBreakInGroup, preserveAspect, groupLikeInput, M42,
N23, bold, B65535, L-5, 12, "Courier";
fontset = output, output, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, L-5, 12, "Courier";
fontset = message, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, R65535, L-5, 12, "Courier";
fontset = print, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, L-5, 12, "Courier";
fontset = info, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, B65535, L-5, 12, "Courier";
fontset = postscript, PostScript, formatAsPostScript, output, inactive,
noPageBreakInGroup, preserveAspect, groupLikeGraphics, M7, l34, w282, h287,
12, "Courier";
fontset = name, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7,
italic, 10, "Geneva";
fontset = header, inactive, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
fontset = leftheader, inactive, L2, 12, "Times";
fontset = footer, inactive, noKeepOnOnePage, preserveAspect, center, M7,
12, "Times";
fontset = leftfooter, inactive, L2, 12, "Times";
fontset = help, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7,
10, "Times";
fontset = clipboard, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = completions, inactive, nohscroll, noKeepOnOnePage,
preserveAspect, M7, 12, "Times";
fontset = special1, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special2, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special3, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special4, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special5, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
currentKernel;
]
:[font = smalltext; inactive; preserveAspect]
Copyright (C) 1997 Rich Neidinger, John Swallow, and Todd Will. Free for
distribution to college and university instructors for personal,
non-commercial use. If these notebooks are used in a course, the authors
request $20 per student.
:[font = title; inactive; preserveAspect]
28. Review for Final
:[font = smalltext; inactive; preserveAspect]
Last revision: October 13 1996
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Review for Final
:[font = text; inactive; preserveAspect]
There is no new material in this section; we simply list topics and
functions with which you should be familiar, and we present ways in which
you should tie the material together .
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Topics
:[font = text; inactive; preserveAspect; endGroup]
Arithmetic Operations (+, -, *, /, ^, etc.)
Boolean Operations (>, <, etc.)
Operator Precedence and Associativity
Exact Values, Approximate Values
Machine-Precision Integers, Machine-Precision Approximations, Bits
Data Types (Integer, Rational, Real, List, String, etc.)
Scientific Functions (Sin[ ], Cos[ ], etc.)
Plotting (functions, lists of points)
Source Code, Interpreted vs. Compiled Languages
Defining Functions
Formal and Acutal Parameters
Bottom-Up Analysis, Top-Down Analysis
List-based Programming; Programming Paradigms
Iterators
Programming as Grammar: Nouns, Verbs, Adverbs
Strings, String Functions, Special Characters in Strings
Modules, Organization
Local Variables, Side Effects, Scope, Initialization of Constants
Programming Style, Comments, Readability
Anonymous Functions, Inline Functions
Data Type Checking, Pattern Matching in Arguments, Conditional Evaluation
Usage Lines
Structured Patterns for Conditional Evaluation
Conditional Structures
Recursion
Dynamic Programming
Control Structures: While, Do, For, with Error Handling
Short-Circuit Evaluation
Arrays: Sizes, Initialization, Modification
Functional Calls: Call-by-value, Call-by-reference
Compilation: Speed, Data Type Checking, Inline Functions
Contexts, Packages, Declaring Names
Object-Oriented Programming
Files: Directories, Opening, Reading, Writing, Checking File Correctness
with a Flag
The C Language: Data Types, Function Definitions, Control and Conditional
Structures, main(), File Access
Fits
Graphics: Primitives and Directives
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Functions
:[font = text; inactive; preserveAspect; endGroup]
Sin[ ], Cos[ ], Tan[ ], Exp[ ], Sqrt[ ], Arcsin[ ], Arccos[ ], Arctan[ ],
N[ ], Plot[ ]
Plus[ ], Times[ ], Subtract[ ], Log[ ], Clear[ ], Expand[ ],
Simplify[ ], Solve[ ], NSolve[ ], FindRoot[ ] Set[ ], Greater[ ], Less[ ],
GreaterEqual[ ], LessEqual[ ], Equal[ ], NotEqual[ ], Not[ ], AddTo[ ],
SubtractFrom[ ], MultiplyBy[ ], DivideBy[ ], Increment[ ], Decrement[ ],
PreIncrement[ ], PreDecrement[ ], SetDelayed[ ], Part[ ], Random[ ], Table[
], Union[ ], Length[ ], Sum[ ], ListPlot[ ], Position[ ], Map[ ], Reverse[
], Sort[ ], Transpose[ ], First[ ], Last[ ], Rest[ ], Partition[ ], List[
], Range[ ], Take[ ], Drop[ ], Inner[ ], Outer[ ], Apply[ ], MapThread[ ],
Join[ ], Nest[ ], NestList[ ], Fold[ ], FoldList[ ], StringLength[ ],
ToCharacterCode[ ], FromCharacterCode[ ], Characters[ ],
StringJoin[ ], StringTake[ ], StringReverse[ ], StringDrop[ ], ToUpperCase[
], TableForm[ ], Module[ ], With[ ], Select[ ], Trace[ ], Count[ ],
RotateLeft[ ], RotateRight[ ], If[ ], Which[ ], Switch[ ], Dimensions[ ],
Flatten[ ], ?, ??, Append[ ], Prepend[ ], Intersection[ ], Complement[ ],
<, >, <=, >=, ==, !=, !, +=, -=, *=, /=, ++, --, ->, /., [[ ]], ; , +, -,
*, / , ^, &&, ||, "", []
IntegerQ[ ], DigitQ[ ], Positive[ ], Insert[ ], UpperCaseQ[ ], LowerCaseQ[
], NumberQ[ ]
OddQ[ ], EvenQ[ ], PrimeQ[ ], MatchQ[ ]
GCD[ ], Mod[ ], Quotient[ ]
Timing[ ], Attributes[ ], Compile[ ]
$Context, $ContextPath, Contexts[ ], Begin[ ], End[ ], BeginPackage[ ],
EndPackage[ ]
OpenRead[ ], OpenWrite[ ], Streams[ ], Read[ ], ReadList[ ], Write[ ],
WriteList[ ], Close[ ], $Path, SetDirectory[ ], Directory[ ], FileNames[ ]
Fit[ ]
Show[ ], Graphics[ ], Polygon[ ], Circle[ ], Disk[ ],
Rectangle[ ], Points[ ], Text[ ], Line[ ], Dashing[ ], PlotStyle
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Mathematica Programming Alternatives
:[font = text; inactive; preserveAspect; endGroup]
Repetition: List-based functions OR Recursion OR Iterative Loops
Array handling: List-based functions for entire rows OR Iterative loops for single entry modification
Names: Variables ("Nouns"), local or global OR Functions ("Verbs"), local,
global, anonymous, compiled OR Parameters, call-by-value or
call-by-reference
Conditional Choices: If-Then-Else, Which OR Pattern-matching in function
definitions
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
General Programming Paradigms
:[font = text; inactive; preserveAspect]
You may find it useful to structure your thinking of the various topics we
have learned around the following programming paradigms. Each is extreme
in its own way, and typically a standard programming language will allow
aspects of several paradigms, although rarely the full
generality of a language such as Mathematica.
:[font = text; inactive; preserveAspect; endGroup]
Functional programming:
In functional programming each function is thought of as a "formula",
which takes as input certain values in its parameters. The function, like
a mathematical formula, cannot modify variables or parameters. Functional
programs are then lists of definitions, together with function calls. No
modifications to local or global variables are allowed; hence all function
calls use "call-by-value". In fact, once a variable is defined with a
value, it is no longer considered a modifiable variable but instead a
defined function which always returns that value. In this
sense values and functions are identified. In functional programming
repetition is usually accomplished by recursion, and conditionals are
implemented using If statements which return different values depending on
the boolean test. At the very beginning of our course, we used "functional
programming" to solve equations, plot graphs, and so on. Scheme and LISP
are examples of functional programming languages.
Procedural, Imperative, or Structured Programming
Procedural programming is one of several names for a paradigm in which
program units are thought of as little algorithms, or procedures, that are
allowed to change the external environment---namely, global data in the
form of variables---as well as their own internal environment---the local
variables. Variables are not thought of as functions as in functional
programming but instead are identified with memory locations, which may be
changed, while procedures are compiled into machine code for execution and
are not typically changed during execution. Procedures are allowed to use
call-by-value or call-by-reference, since references to memory locations
are allowed. Repetition is usually accomplished by iteration, say with a
While construct, although recursion is sometimes employed; conditionals are
implemented with If statements. C, Pascal, and Fortran are examples of
procedural programming languages.
List-based, or Array-oriented Programming
This paradigm of programming could be functional or procedural in
type, the difference being that repetition is usally accomplished by list-
or array-manipulation procedures, say from a package, which allows the
programmer to think in terms of processing entire arrays in one step. This
sort of programming has advantages in parallel programming, where a
programmer writes one program which has several computing units at its
disposal and the challenge is to have the computing units work together to
complete algorithms very quickly. If a package of array or list routines
is developed which cleverly use the computing units together, the final
programmer will have the advantage of speed without having the complexity
of having to decide how to instruct each computing unit.
Logical Programming
In logical programming all program units are boolean-valued functions
which return "true" or "false", and the program units are allowed to change
the external environment. For conditionals, multiple definitions of one
function are distinguished by different conditions on the arguments.
Logical programming is uncommon but an interesting exercise in exploring
the relationship between logic and computer science.
Symbolic Programming
Symbolic programming, which is the primary paradigm for Mathematica
programming, is functional in nature, with names referring not directly to
memory locations but to "symbolic expressions", which may occupy many or
few memory locations. This distinction has been somewhat vague in our
course, since Mathematica performs the work of translating names which
contain values into their particular memory locations; in C, however, the
need to declare every single variable arises from the necessity of
assigning particular memory locations to each variable. In symbolic
programming, repetition can be accomplished not only by using iteration or
recursion but also by employing "repeated symbolic replacement".
Conditional expressions frequently use If or Switch constructs and can also
use pattern matching.
Object-Oriented Programming
The paradigm of object-oriented programming, in its full form (as
distinguished from the form we presented in the course) is primarily
procedural but forces the programmer to bind together variables and the
functions which will modify them into an "object". Thus, only certain
functions are allowed to modify certain data, and only certain data are
allowed to be used with certain functions; this distinction is supported by
notions of "public" and "private" data and functions within a given
"object".
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Fundamental Concepts of CS
:[font = text; inactive; preserveAspect]
What have we learned? What would you learn in the next computer science
course? Here are a list of general concepts commonly covered in the
introductory two- or three-course computer science sequence, with
indications of which we've seen. The list is taken from "A Revised Model
Curriculum for a Liberal Arts Degree in Computer Science", a panel of
SIGCSE, the special interest group on computer science education of the
ACM.
:[font = text; inactive; preserveAspect; endGroup; endGroup]
Algorithms and algorithmic problem-solving: YES.
Problem-solving paradigms: procedural, object-oriented, functional, with
examples: YES.
Control structures, recursion, and iteration: YES.
Classical algorithms: sorting, searching, and pattern-matching: NO. (We
haven't written algorithms to do any of these algorithms.)
Time and space analysis: SOME. (We've touched on the trade-offs.)
Concepts of modularity, decomposition, procedural and data abstraction,
program libraries: YES.
Formal specification of abstract data types: NO. (We've seen lists and so
on, but haven't discussed how to specify them.)
Major data structures (arrays, records, stacks, queues, lists, simple
trees) and examples of their use: NO. (We've seen only arrays and lists.)
Software development, including program specifications, design, coding,
debugging, testing, verification, and documentation: SOME. (We've touched
on several of these topics.)
Brief introduction to internal representation of data: YES. (We've talked
about machine-precision integers and approximate numbers, although further
study would be
desirable.)
Social issues: intellectual property, liability, privacy, ethical
behavior, access: NO.
^*)