CMSC 105 Syllabus: Fall 1997
We expect to cover the following topics in
CMSC 105
in the Fall of 1997:
Unit 1: Algorithms (chapter 1, week of 9/1)
- specifications, algorithms, programs, and abstractions
- discrete and continuous problems
- describing specifications or facts (using mathematical logic) vs. describing algorithms (using programming languages)
Unit 2: Programs and Functions (chapters 2 and 3 (except 2.10 and 3.4), week of 9/8)
- programs, functions, parameters and returns
- arithmetic expressions
- output
- if statements
- introduction to recursion
Unit 3: Recursion and Complexity (chapters 2.10 and 4 (except 4.6), week of 9/15)
- input, separation of i/o from the functional core of a program
- preconditions and postconditions for functions
- variables and assignments
- arithmetic operations revisited: precedence & precision
- recursion revisited, more about complexity
- proof by induction
Unit 4: Loops (vs. Recursion) and Scope (chapter 5.3-5.5 and 10, weeks of 9/22 and 9/29)
- loops
- when to use loops vs. recursive functions
- local and global variables
- trees and traversing trees
Unit 5: Reasoning About Programs (weeks of 10/6 and 10/20)
- single assignment form and mathematical reasoning
- pre and postconditions for statements
- loop invariants
- loops, recursion, and inductive proofs
- A list of proof techniques is available
in postscript
or text form.
Unit 6: Data Abstraction (chapter 3.4, 4.6 and 5, 10/24 and 10/29)
- data abstraction
- using classes (review) and creating classes
- reference parameters
- operator functions
Exam 1, on 10/31, covers Units 2-5 (there will
be a review instead of lab on 10/27 - the review questions are
available in postscript or text form.)
Unit 7: Coordinated Classes (chapter 7, week of 11/3)
- more about data abstraction
- type casting
- references again
Unit 8: Collection Classes (chapter 6, week of 11/10))
- streams
- lists
- trees
- graphs
Unit 9: Arrays and "Scientific" Programs (chapters 8 and 9.8, week of 11/17)
- floating-point representation of real numbers
- arrays
- multi-dimensional arrays
- simulating a continuous system via computer
Unit 10: Algorithm Development and Sorting (chapter 11, week of 12/1)
- algorithm development revisited
- complexity revisited
- sorting arrays
Final Projects will be demonstrated in lab on 12/7
Final Exam covers Units 1-10
Return to the page of
This page maintained by
davew@cs.haverford.edu