CSC 270 exam

One 8½x11" aid sheet permitted. Non-programmable calculators permitted. No electronic device capable of storing arbitrary text is permitted, nor programmable devices, wristwatches running unix, etc. Please turn off cell phones, pagers, ...

Coverage: whole course. Details below. All assignments.

Format: "short answer":

• some answers in English, e.g. why is this or that this way, analyze this or that
• write C programs.

To prepare for this exam, I suggest you go through your notes, assignments, and so on; but you can't learn this stuff by just reading about it, you have to do it. Look at bits in your assignments which didn't work, pursue additional problems, write code.

Find things you don't understand about the material, read, think, write programs; come to understand them. Ask other students, ask your instructor, come to office hours, bring non-working programs or programs whose behaviour you don't understand and we can go through them.

Review

Here are the topics which comprise CSC 270.

• C
  • basic C stuff (the stuff that's mostly but not all the same as java -- if, loops, etc)
  • basic C data types: int/double/etc; structs; arrays; pointers; pointer arithmetic and array-pointer relationship; array parameters (which use pointers and pointer arithmetic, whether implicitly or explicitly)
  • functions, parameters, extern, storage classes (extern/auto/file-static/function-static)
  • .h files and .c/.cpp files, compiling, linking
  • C pre-processor: #include, #define (won't ask about macros with parameters), won't ask about #ifdef
  • strings (details not on the exam)
  • files (not on the exam)
  • relevant parts of all assignments
• C++
  • class, public, constructor
  • a java object variable is like a C++ pointer-to-a-class, not C++ instance
  • the java-like syntax for writing functions is inline in C++
  • new/delete
  • virtual
  • relevant parts of all assignments
• Numerical methods
  • data representation: binary, sign-and-magnitude, IEEE 754 (you won't have to do a detailed IEEE 754 conversion on the exam but you could have to answer questions about one, with reminders of formats etc -- see an example such question from a previous year's midterm)
  • polynomial evaluation
  • don't compare floating-point numbers for exact equality (and what you do instead)
  • truncation error, round-off error, absolute versus relative error
  • root-finding (bisection method, secant method, Newton's method)
    • you may want to write the formulas for these on your aid sheet (very short)
  • quadrature (basic concepts)
  • didn't do order of convergence material
  • assignment one
• Graph theory
  • basic definitions
  • graph colouring
  • graph representation (adjacency matrix / adjacency list)
  • traversal (BFS/DFS), path-finding
  • Dijkstra's algorithm (may be worth writing on aid sheet)
  • Floyd-Warshall(-Ingerman) algorithm (may be worth writing on aid sheet)
  • didn't do: stuff after section 8.3 (but it may be of interest in your future life!)
  • assignment two
• Simulation
  • basic idea
  • techniques:
    • probability; random variables
    • probability distribution function (discrete)
    • probability density function (continuous)
    • cumulative probability distribution function (either)
    • uniform random number distribution, variants (maybe write on aid sheet)
    • exponential distribution not to be tested on the exam, nor Poisson, ....
  • assignment three, including randomization notes
• Dynamic programming
  • basic idea, techniques
  • knapsack problem example, matrix chain multiplication example, optimal BST example
  • assignment four
  • a dynamic programming example on your aid sheet might be very helpful.