# 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

#### Tutorial: More C

King 4.3, 6.4, and page 72
• printf
• pre- and post- increment and decrement
• conditional expressions
• loops and break

#### Lecture 1: Numerical Analysis

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

#### Lecture 2: And even more C

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

## CSC270 Lecture Outline - September 30

#### Tutorial: More C

King 7.5, 8, 5.3
• conversion between types
• arrays
• switch

#### Lecture 1: Numerical Integration

Readings section 4, pages 432-437
• Approximating the integral with a sum
• Riemann Sums
• trapezoid rule
• Simpson's rule

#### Lecture 2: C functions and scope

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

#### Tutorial: Useful C for Assignment 2

King 8.2, 17.3, 16.1, 16.2, 16.3
• multidimensional arrays
• dynamic allocation of one-dimensional arrays
• structs

#### Lecture 1: Graph Representations

Readings 9.2, 9.3
• graphs & their uses
• adjacency matrices
• adjacency lists

#### Lecture 2: Shortest Path Algorithm

Readings 9.8
• Dijkstra's single-source shortest path algorithm

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

#### 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++

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

#### Tutorial: C++

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

#### Tutorial: Assignment 2 and C++

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

#### Tutorial: C++ Templates

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