Summary of CSC270 Course Notes
This is just an amalgamation of the Web pages for each day's lecture.
CSC270 Lecture Outline - September 9
Introduction to the course
- syllabus
- policies
- course Web page
Introduction to C
King, chapters 2 & 4; also read chapters 1 & 3
Example programs are in ~jstewart/csc270/Sept9 on CDF.
- editing
- compile - link - run
- template for a C program
- comments
- #include directives
- variables & basic types
CSC270 Lecture Outline - September 16
Tutorial: Unix & C
King sections 3.1, 4.1 - 4.4
- Very, very brief introduction to Unix
- C numeric expressions & assignment statements
- C output with `printf'
Lecture 1: Introduction to Numerical Analysis
Readings section 3, pages 49-53
- mathematical functions
- roots
- intermediate value theorem
- bisection method of root finding
- rate of convergence
Lecture 2: More C
King chapters 5, 6
- logical expressions
- conditionals: if, if-else
- loops: do, while, for
CSC270 Lecture Outline - September 23
King 4.3, 6.4, and page 72
- printf
- pre- and post- increment and decrement
- conditional expressions
- loops and break
Readings section 3, pages 62-64, 69-71
- Mean Value Theorem (MVT)
- Taylor series
- Newton's method of root finding
- derivation from Taylor series
- graphical intuition
- rate of convergence
- Secant method of root finding
- derivation from tangent approximation
- graphical intuition
- rate of convergence
King chapter 9
- functions
- function template
- return statement
- parameters
- definition-before-use and `prototypes'
- void functions
CSC270 Lecture Outline - September 30
King 7.5, 8, 5.3
- conversion between types
- arrays
- switch
Readings section 4, pages 432-437
- Approximating the integral with a sum
- Riemann Sums
- trapezoid rule
- Simpson's rule
King chapters 2.5, 2.6, 9, 10.4
- Constants with #define
- Subtleties of scanf
- more functions
- parameters vs. arguments
- call-by-value
- `scope' of variables
CSC270 Lecture Outline - October 7
King 8.2, 17.3, 16.1, 16.2, 16.3
- multidimensional arrays
- dynamic allocation of one-dimensional arrays
- structs
Readings 9.2, 9.3
- graphs & their uses
- adjacency matrices
- adjacency lists
Readings 9.8
- Dijkstra's single-source shortest path algorithm
CSC270 Lecture Outline - October 14
It's a holiday!
CSC270 Lecture Outline - October 21
Tutorial: Midterm
- Midterm 6:10 - 7:00 in tutorial rooms assigned in the syllabus.
Lecture 1: Shortest paths
Readings section 9.9
- Floyd's shortest path algorithm
Lecture 2: Transitive closure
Not covered in the Readings
- Transitive closure as matrix multiplication
CSC270 Lecture Outline - October 28
- Midterms back
- C pointers
- Makefiles (not covered in tutorial, but notes are here. You're expected to know this.)
Lecture 1: Graph Traversal
- Breadth-first search
- Depth-first search
Lecture 2: Introduction to Simulation
- Simultion is typically used to solve complex problems numerically
that can't be solved analytically
- Ballistic example using F=ma and air resistance
CSC270 Lecture Outline - November 4
King 19.4
- Abstract data types
- comments, storage allocation
- classes, public/private
- constructors
- stack example
- calling functions defined in a class
- the special variable `this'
- I/O
Lecture 1: Simulation
Readings, Simulation section: 2.1 - 2.4
- deterministic vs. stochastic
- static vs. dynamic
- Monte Carlo methods: integration, ray shooting
- Random walks
Lecture 2:
Readings, Simulation section: 2.5, 2.6
- Time driven vs. event driven
- simulation loops
- Elevator simulation
- PersonAppearance event
- ElevatorArrival event
- information available to controller
CSC270 Lecture Outline - November 11
King 19.4
- inheritance
- virtual functions
Lecture 1: Probability for Simulation
Readings, Simulation section: 2.7
- events
- random variables
- probability density function
- various distributions
- cumulative density function
- generating random variables for uniform distributions
- generating random variables for non-uniform distributions
Lecture 2: Poisson Processes
- Poisson process
- Poisson distribution
- Interarrival times with Poisson process
CSC270 Lecture Outline - November 18
King 19.4
- Assignment 2 handed back and solutions discussed
- C++ operator functions
Lecture 1: Generating Pseudo-random Numbers
Readings, Simulation 2.7.2, 2.6.1
- Generating pseudo-random numbers uniformly in [0,1]
- Identifying components in a simulation
Lecture 2: Integer Representations
Readings, "Computer Arithmetic and Errors" Chapter 1
- unsigned ints
- one's complement
- two's complement
- subtracting with two's complement
CSC270 Lecture Outline - November 25
Not in the King book!
- List Node example
- Linked List example
- How to use templates
- How to define templates
Lecture 1: Floating Point Numbers
Readings, Chapter 1
- mantissa and exponent
- nomalized representation
- hidden bit
- absolute and relative errors
- roundoff error, overflow, and underflow
- machine epsilon
- adding and multiplying
Lecture 2: Dynamic Programming
Readings, last section (it's short)
- Floyd's algorithm
- Knapsack problem
CSC270 Lecture Outline - December 2
Tutorial: Dynamic Programming
Readings, last section. See my notes in the library, too.
- Optimal multiplication of matrix chains
Lecture 1: Dynamic Programming
Readings, last section
- Review of knapsack problem
- Optimal binary search trees
Lecture 2: Exam preparation
- What's on the exam
- Elevator competition results