CSC 270: Topics covered so far, evening section

Tuesday September 10:

• course info sheet (available in html, postscript, or PDF)
• computer accounts
  • CDF
  • passwords
  • "Student Guide to CDF" (available in postscript or PDF)
• Introducing the C programming language: gcd example
  • where C differs from Java and where it doesn't
  • #include <stdio.h>
  • C definition of "main()" (returns int)
  • declarations versus definitions
    • declaration: tells the compiler how to access the item
    • definition: creates the item (and in C, is also a declaration, but not vice versa)
  • declarations must appear at the beginning of a scope (before any non-declaration statements)
  • An uninitialized local variable has no default value, and to use its value before assigning one is an error. Furthermore, the error is not diagnosed!
    • In general, no run-time checking.
  • use "int" for boolean in C
  • no objects; no polymorphism
• compiling C programs ("gcc -Wall -ansi -pedantic file.c")

Tuesday September 17:

• C data types: int, long
• double (rarely use "float")
• char (just small ints)
• in fact most things in C are ints (booleans, char literals, ...)
• "literals"
  • 38 -- int
  • 38L -- long
  • 0x2a -- int (42) (base 16)
  • 033 -- int (27) (base 8)
    • Careful not to make ints accidentally octal! It's the leading 0 which does it.
    • Cute fact: the literal "0" is therefore, technically, an octal constant. (doesn't actually matter)
  • can combine base and 'L'
  • if number contains decimal point or 'e', it's a "double" (floating-point) literal
    • 0.3
    • 3.0
    • 6.02e23
  • char literals are ints (as opposed to strings, later)
    • 'a' (97)
    • '\033' -- same as 033 (27)
    • '\n' -- 10 in unix
• default promotions
  • char to int, float to double
• mixed-mode arithmetic
  • 5.3 / 60 is of type double
    and it does real division.
  • double + double -> double (obviously)
  • int + int -> int (obviously)
  • double + int -> double
  • int + double -> double
  (for any operator)
• integer data representation (first section of representation.html)
• arrays
  • memory is a vast array of "bytes"
  • each byte has an "address"
  • objects (such as ints) are made up of multiple consecutive bytes
  • If we want a 32-bit int, that's four bytes. In a row. A particular int variable might occupy memory locations 1234, 1235, 1236, and 1237. (If ints are four bytes, which is not guaranteed.)
  • int a[10];
    • Suppose ints are four bytes, and 'a' starts at location 1234.
    • Then the integer a[i] starts at location 1234 + 4 * i.
  • "pointer": high-level version of an "address"
    • has type information
  • pointer declarations and values
    • int i;
    • int *p;    -> declare p to be of type pointer-to-int
    • i = 3;
    • p = &i;    -> assign p to point to i
    • printf("%d\n", *p);    -> "dereference" -- follow a pointer
    • i = 4;
    • printf("%d\n", *p);    -> prints 4
  • Thus '&' and '*' are opposites.
  • pointer arithmetic
    • p + 3 -- yields the address which is three ints later, i.e. address(p) + 12
    • So if p contains the address of a[0], p+i is the address of a[i].
    • For two expressions x and y, x[y] is defined as *((x) + (y))
  • So, how is this going to work with arrays, if we haven't declared any pointer variables?
    • An array name in an expression context decays into a pointer to the zeroth element.
    • e.g. a[3]:
      • the 'a' becomes a pointer to the zeroth element, e.g. of type pointer-to-int
      • add three to get pointer to element number 3
      • dereference

Tuesday September 24:

• comment syntax: /* ... */
• array parameters: array parameter example
  • Special weird rule for formal parameters only: You can write void setsquares(int a[])!
  • I strongly recommend against this.
  • It is still a pointer!
  • This weird conversion rule is specific to formal parameter lists!
• printf and scanf format letters
• structs (first section of struct.html): declaration syntax, struct "tags", assignment and parameter passing (passes/assigns the entire object, not a pointer!)
  • also read second section of struct.html
• floating-point representation

Tuesday October 1:

• numerical methods (readings listed from first two sections of readings booklet)
  • truncation error (section 1.5)
  • relative and absolute error (parts of section 1.4)
  • root-finding (sections 5.2, 5.4, 5.6)
  • quadrature (numerical integration) (section 8.1; skim 8.2.1)
  • don't compare floating-point numbers for equality; don't subtract near-equal quantities ("catastrophic cancellation" in section 1.4)
    • code examples used
  • round-off error and "bias" (section 1.4)
  • Also read notes on "machine epsilon", section 1.3
  • Mentioned polynomial evaluation -- read poly.html.

Tuesday October 8:

• Graph theory (second major readings contents)
  • Basic definitions
  • Graph isomorphisms
  • Graph colouring
  • Application: "register colouring" in a compiler
  • Data representation of graphs
  • ... to be continued
• More about structs in C: dynamic allocation, linked lists and similar structures. Achieving abstract data types through "typedef".

Tuesday October 15:

• continue graph theory
  • Graph traversal algorithms (readings section 8.2)
  • Path-finding and weighted graphs (readings section 8.3)
• The C pre-processor.

Tuesday October 22:

• C++
• Begin simulation

Tuesday October 29:

• Midterm. No class.

Tuesday November 5:

• Simulation (notes to be posted soon)
• see readings
• later on I posted an example of the difference between time-driven and event-driven simulations

Tuesday November 12:

• Dynamic programming (probably get through about two fifths of that document)
• see readings; also, fairly complete notes above
• also see directory of example code presented

Tuesday November 19:

• Finish dynamic programming.
  • directory of example code presented
• Further C topics: strings

Tuesday November 26:

• Further C topics: files

Tuesday December 3:

• More C or C++ topics (finish files? funny C++ stuff?)
• Review