Summary of CSC270 Course Notes

CSC270 Lecture Outline - September 9

Introduction to the course

• syllabus
• policies
• course Web page

Introduction to C

• editing
• compile - link - run
• template for a C program
• comments
• #include directives
• variables & basic types

CSC270 Lecture Outline - September 16

Tutorial: Unix & C

• Very, very brief introduction to Unix
• C numeric expressions & assignment statements
• C output with `printf'

Lecture 1: Introduction to Numerical Analysis

• mathematical functions
• roots
• intermediate value theorem
• bisection method of root finding
• rate of convergence

Lecture 2: More C

• logical expressions
• conditionals: if, if-else
• loops: do, while, for

CSC270 Lecture Outline - September 23

Tutorial: More C

• printf
• pre- and post- increment and decrement
• conditional expressions
• loops and break

Lecture 1: Numerical Analysis

• 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

Lecture 2: And even more C

• functions
  • function template
  • return statement
  • parameters
  • definition-before-use and `prototypes'
  • void functions

CSC270 Lecture Outline - September 30

Tutorial: More C

• conversion between types
• arrays
• switch

Lecture 1: Numerical Integration

• Approximating the integral with a sum
• Riemann Sums
• trapezoid rule
• Simpson's rule

Lecture 2: C functions and scope

• Constants with #define
• Subtleties of scanf
• more functions
  • parameters vs. arguments
  • call-by-value
• `scope' of variables

CSC270 Lecture Outline - October 7

Tutorial: Useful C for Assignment 2

• multidimensional arrays
• dynamic allocation of one-dimensional arrays
• structs

Lecture 1: Graph Representations

• graphs & their uses
• adjacency matrices
• adjacency lists

Lecture 2: Shortest Path Algorithm

• Dijkstra's single-source shortest path algorithm

CSC270 Lecture Outline - October 14

CSC270 Lecture Outline - October 21

Tutorial: Midterm

• Midterm 6:10 - 7:00 in tutorial rooms assigned in the syllabus.

Lecture 1: Shortest paths

• Floyd's shortest path algorithm

Lecture 2: Transitive closure

• Transitive closure as matrix multiplication

CSC270 Lecture Outline - October 28

Tutorial: C

• 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

Tutorial: C++

• 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

• deterministic vs. stochastic
• static vs. dynamic
• Monte Carlo methods: integration, ray shooting
• Random walks

Lecture 2:

• Time driven vs. event driven
• simulation loops
• Elevator simulation
  • PersonAppearance event
  • ElevatorArrival event
  • information available to controller

CSC270 Lecture Outline - November 11

Tutorial: C++

• inheritance
• virtual functions

Lecture 1: Probability for Simulation

• 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

Tutorial: Assignment 2 and C++

• Assignment 2 handed back and solutions discussed
• C++ operator functions

Lecture 1: Generating Pseudo-random Numbers

• Generating pseudo-random numbers uniformly in [0,1]
• Identifying components in a simulation

Lecture 2: Integer Representations

• unsigned ints
• one's complement
• two's complement
• subtracting with two's complement

CSC270 Lecture Outline - November 25

Tutorial: C++ Templates

• List Node example
• Linked List example
• How to use templates
• How to define templates

Lecture 1: Floating Point Numbers

• 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

• Floyd's algorithm
• Knapsack problem

CSC270 Lecture Outline - December 2

Tutorial: Dynamic Programming

• Optimal multiplication of matrix chains

Lecture 1: Dynamic Programming

• Review of knapsack problem
• Optimal binary search trees

Lecture 2: Exam preparation

• What's on the exam
• Elevator competition results