28. Review for Final

Last revision:  October 13 1996

Review for Final

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 .

Topics

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

Functions

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

Mathematica Programming Alternatives

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

General Programming Paradigms

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.

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".

Fundamental Concepts of CS

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.

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.