midterm-prep

============================
Test Contents (thanks, Kent)
============================
Composition: short-answer questions
Look at exercises in Prag Prog book
Contents:
  JS basics
  Class, object, sequence diagrams
  Basic OOP
  Use cases
    What's a good requirement?
  Types of requirements
  Program analyses -- relations, concepts
    Use a class diagram
  Implementation
    Models of concurrency
  Program concepts, patterns
  Equivalence classes
  Testing definitions, strategies

Shaun's notes from tutorial:
  Modeling:
    Draw class or object diagram based on "story" given -- quite like ER assignment we did in lab
    Pick out nouns, draw boxes as appropriate
      Go through passage, underline all nouns you see, incorporate them into diagram
    Know diamonds, multiplicities, etc.
    Don't agonize over it -- will be quite short, given hour-long exam length

  Requirements:
    Know difference between functional & nonfunctional (security, usability, performance)
      Identify examples of each
    Be able to produce actual definition of both terms, as well as identify requirements given in another story
      If you say "security is important nonfunctional requirement," tell why it is based on that particular story
    "Why is requirements gathering important?"
      We don't have domain knowledge, which we get by gathering requirements

  Testing:
    Almost always asked about equivalence classes
    Testing is about inputs & outputs -- if input doesn't produce expected output, there's a bug
      You can put in infinite number of inputs, potentially -- so you choose which to test based on equivalence classes
      Essentially partitioning space of all possible tests into equivalent classes
    Boundary testing: catch off-by-one errors, etc.
      Essentially, picking values from borders between equivalence classes
      Equivalence classes for an int: negative, 0, positive
      Shaun's guess: maybe the exam question wlil be about a function that takes a date parameter
        What are the possible equivalence classes?
          Dates with zeroes at the end
          Leap years
          Y2K stuff
          Dec 31, 23:59:59
          Boundaries at beginning/end of month

     Types of tests:
      Unit: testing units of functionality outside of context of rest of system
        Testing at method/function level
        Distinction between whitebox and blackbox testing
          Blackbox about testing specification -- does code match spec? (Bug may be in either code or spec)
          What is advantage of blackbox testing? Why not just do whitebox testing?
            If you overlook edge case when writing code, you may well do the same when writing tests
              You don't even consider that user might pass in null value
            You may not have access to the soruce
            Blackbox & whitebox are complementary
              Whitebox verifies that code is working properly
              Blackbox verifies that code meets specification

      Integration: ensure that units work correclty when combined
        Many bugs happen at interface between units -- nastiest bug that you'll encounter in real world
          Performance bugs are a pain in the ass -- unit alone will be perfectly fast in isolation, but exceedingly slow once integrated into system
        You know that individual units work fine because of unit testing
        Often used interchangably with system testing
        For this course, consider them to be the same thing
        May perform "big bang" testing where everything combined at once, or may combine things one-at-a-time (preferable)

      System testing: does entire system work as it should?

      System integration testing: does system integrate properly with other systems?

      Acceptance testing: you give system to customer, ask if it meets his needs
        You give almost-complete product to customer, see if he's happy

    'Tis first time Prag Prog book has been used for class at university
      "Tests at end of chapters are too easy to stick into exam!" --Dr. Sillito
        He also said to Shaun that a question or two from book would likely be on exam

  Types of defects: given source listing with bugs identified, list type of each
    http://en.wikipedia.org/wiki/Software_bug#Common_types_of_computer_bugs
    Off-by-one
    Arithmetic:
      Divide by zero
      Arithmetic overflow/underflow
    Multithreading:
      Deadlock
      Race condition
    Logic:
      Infinite loops/recursion
      Off-by-one
    Resource:
      Null pointer dereference
      Using uninitialized variable
      Access violation
      Resource leak
      Buffer overflow
      Excessive recursion causing stack overflow
    Misc:
      Loop existing too early
    Interfacing bugs:
      Incorrect API usage
      Incorrect protocol implementation
      Incorrect hardware handling
    Performance bugs:
      Excessive algorithm computational complexity
      Random disk or memory access
    Teamwork:
      Unpropagated changes (mitigated by DRY)
      Out-of-date or incorrect
      Differences between documentation and final product


====
Misc
====
Think of int/char/float as abstraction on top of binary data
Object: something with attributes (aka data, state) and behaviour (operations)
When "obj.method" called, you don't know exactly what *function* call will be made -- depends on what obj's class is

DSLs:
Rails' routes.rb is a DSL
  match "/tasks/:id" => "tasks#show", constraints => {:id => /.../}
SASS is a DSL for CSS

Improve performance through temporal decoupling

Orthogonal software = high cohesion, low coupling
Cohesion: if component is cohesive, it does only small number of (related) tasks
Coupling: how much interdependence there is between components

Crash early -- minimize distance between source of problem and where you notice its effects

Choosing between throwing exception and producing error:
  Produce error when program can conceivably continue operating
    Throw exception when it can't

Prototypes: good for illustrating whether your design choices make sense
  May be quick-and-dirty code; may even be just UI mockup

Issues with caching:
  Invalidating stale objects
  Memory usage -- don't want to keep infrequently used objects in memory


======
JS OOP
======
What happens when you reference obj.something in JS?
  If "something" is attribute on obj, then its value is returned
  If not:
    Does obj.__proto__.something exist?
      If so, return
      If not, look at obj.__proto__.__proto__ ...
var car = new Car(a, b, c)
  Create new object (i.e., "{}")
  Bind that new object to "this"
  Set this.__proto__ to Car.prototype
  call Car(a, b, c)


============
Requirements
============
Requirement: describes what system must do, or a constraint of its development
Types of requirements:
  1. Functional
    Inputs accepted
    Outputs generated
    Data stored
    Timing and synchronization

  2. Quality
    Response time
    Throughput
    Resource usage (CPU, RAM, network, disk space, power)
    Reliability -- average time before failures, probability of failure
    Availability -- "how many 9s?"

  3. Platform
    Run on server? phone?

  4. Process
    Development methodology
    Cost & delivery date

Requirement gathering = iterative
  Devs must be flexible -- client's understanding of needs evolves
  Clients must be flexible -- maybe devs underestimated cost of functionality

Ranking requirements:
  Write each requirement on index card
  Client writes priority (A=must-have, B=important, C=nice-to-have)
  Dev writes best/median/worst dev time
Then, figure out which cards stay in the project stack

Domain model: conceptual model of system including its key concepts and vocabulary
  Includes main entities (objects) & relationships
  Can capture using UML class diagrams
    Types of UML to know: class, object, sequence diagrams

UML:
  Class diagrams:
    Association/aggregation:
      Though aggregation is a type of association, it's stronger
      Aggregation = "part-of" relationship -- when one class fully "contains" another
        e.g., consider Forum to be aggregation of Topics, as Topics are "contained by" Forum -- they don't have independent existence
    Aggregation/composition:
      Aggregation is weaker than composition
      Use composition if container being destroyed also means that its composed objects will be destroyed in process
      Composer must have multiplicity of 0 or 1 -- department can compose only a single university
        e.g., if Forum is composed of Posts, they can't compose another Forum
    Dependency/association:
      Dependency is weaker than association
      Dependency indicates that one class uses another as a local variable or method parameter
        Association indicates that a class' instance is a member variable of another
    Notation:
      Dependency  = dotted line, open triangular arrowhead
      Association = open triangular arrowhead
      Inheritance = closed triangular arrowhead
      Aggregation = open diamond
      Composition = closed diamond (think "c" for closed/coloured)
    Examples:
      Carburetor composes Car, but Duck aggregates Pond

  Sequence diagrams:
    Notation:
      Synchronous call: solid line, full triangular head
      Asynchronous call: solid line, stick triangular head
      Return value: dashed line, stick triangular head
    Line can originate from edge of diagram to initiate message exchange
    Lifelines don't necessarily indicate object lifetime -- just that active operations are being performed by object

  
=========
Use Cases
=========
Parts of use case:
  Scope
  Actor
  Stakeholder -- has vested interest in system's behaviour
  Preconditions
  Postconditions
  Main success scenario
    Can branch to error scenarios, alternative success scenarios

Example use case: cook food with microwave for specified time
  Primary actor: cooker (C)
  Preconditions: microwave (M) plugged in
  Postconditions: food has been cooked
  Main success cenario:
    1. C opens door
    2. M turns on light
    3. C puts in food and closes door
    4. C presses numerical buttons, M display time on LCD
    5. C presses start button, M starts cooking
    6. M counts down time
    7. When specified time has elapsed, M stops cooking, sounds 3 beeps
    8. C opens door, retrieves food
  Extensions:
    At step 6, C opens door
      6a. M stops cooking
      6b. C closes door and presses start button
      6c. Continue main succses scenario at step 6


===================
Equivalence Classes
===================
Choose one input as representative of whole class of inputs
  Assume that software processes all inputs in class in same manner
  Provides shortcut -- don't need to test every possible input, as you collapse all equivalent inputs into single class
    Note you must have classes for both valid & invalid inputs
  Can also apply equivalence classes to outputs, but much rarer than doing so for inputs
  Equivalence classes chosen in black-box manner, without access to underlying source -- only spec

  Combine equivalence classes with boundary value analysis
    When choosing precise values from classes to test, often choose ones lying just below, on, or just above boundaries

  Example: "widget name must be 3-15 alphanumeric characters, of which first two must be letters"
    Yields three requirements, each of which has multiple ECs:
      1. Name must be alphanumeric
        EC1: Name is alphanumeric (valid)
        EC2: Name isn't alphanumeric (invalid)

      2. Name must be 3-15 characters in length
        EC3: Name length < 3 (invalid)
        EC4: 3 <= name length <= 15 (valid)
        EC5: Name length > 15 (invalid)

      3. First two characters must be letters
        EC6: First two characters are letters (valid)
        EC7: First two characters aren't letters (invalid)
    Multiple ECs may be covered by one test case; still, don't collapse separate ECs into a single EC


===============
Design Patterns
===============
Observer:
  One-to-many dependency defined such that when the "one" changes, the "many" are notified
  If it's a one-to-one dependency, then it's the "command" pattern

Factory: allows creation of objects without specifying their exact classes
  Subclasses can override class of object that will be created
  Complex code related to creation can be rolled into factory
  Abstract factory example:
    DocumentCreator has createLetter(), createResume()
    DocumentCreator subclassed by FancyDocumentCreator, ModernDocumentCreator, etc.

Composite: allow you to treat a single object or multiple objects the same way
  e.g., in BST, treat nodes and leaves the same

State:
  Behaviour of object depends on its state
  State machines don't necessarily imply the use of this pattern
  Example: paint program
    AbstractTool subclassed by PenTool, SelectionTool, etc.
    Cursor then has "tool" variable that stores instance of one of those
      Cursor calls mouseUp(), mouseDown(), etc. on tool

Adapter: wrapper -- translate from one interface to another
  Object adapter: adapter contains instance of class it wraps
  Class adapter: extend parent class(es) whose functionality you're wrapping, then call methods as appropriate
    Doesn't need multiple inheritance -- can be done in Java by implementing interfaces


===========
Concurrency
===========
Models:
  Single process, single thread, synchronous
  Single process, single thread, asynchronous
    Requires that *all* time-intensive calls be implemented as callbacks
  Single process, multiple threads, synchronous
    Synchronicity makes for easier programming, but requires that you deal with cross-thread issues

Interesting architecture:
  Spin up a single process, single threaded, asynchronous server on each core
    Implement additional "load balancer" process that dispatches requests in round-robin fashion
  Problem: what if one of the async server instances is serving a huge request?
    That's where having more knowledge about exactly what the server instances are doing allows you to serve more intelligently

Grocery store:
  Customers care only about response time
  Managers care about mean response time (how long does average customer wait?) and throughput (how many customers am I getting through?)

How does cost grow as a function of throughput (i.e., # of active users)?
  Logarithmic?
    High initial dev cost, but adding each subsequent user costs less and less
  Linear?
  Quadratic?
    This is most likely -- given architecture can scale only so far
      At certain point, adding more users causes cost to go to infinity
  Exponential?
  Likely to observe not smooth curve, but sharp "phase transitions" -- must invest substantial amount to rearchitect system at certain stages

In testing concurrency, three metrics to consider:
  Total time
  Requests/s (throughput)
  Mean time per request (mean response time)


================
Pragmatic Advice
================
Ch. 7: Requirements gathering:
  51: Don't gather requirements -- dig for them.
  52: Work with a user to think like a user.
  53: Abstractions live longer than details.
    Don't represent years with literal two-digit value
    Instead, build "YEAR" abstraction -- even though underlying representation can be two-digit value
  54: Use a project glossary.
  55: Don't think outside the box -- find the box.
    You might think constraints exist that aren't preset in reality
  56: Listen to nagging doubts -- start when you're ready.
    Try to build prototype to overcome procrastination -- will tell you what you're missing, if you're ready to begin
  57: Some things are better done than described.
    e.g., describe how to tie your shoes.
  58: Don't be a slave to formal methods.
  59: Expensive tools do not produce better designs.

Ch. 2: A pragmatic approach:
  12: Make it easy to reuse.
    Easier your code is to resuse, less likely you/others will duplicate the knowledge it represents
  13: Eliminate effects between unrelated things.
  14: There are no final decisions.
    Reversibility is key
  15: Use tracer bullets to find the target.
    "Ready, fire, aim" rather than "Ready, aim, aim, aim, ..."
  16: Prototype to learn.
    Ignore correctness, completeness, robustness, style
    Make sure client understands this is prototype -- it will be crap, so must not go into production
  17: Program close to the problem domain.
    DSLs are key -- includes data languages (Windows .rc files) and imperative languages
  18: Estimate to avoid surprises.
    Look back at your estimates to improve future estimate accuracy
    Best source for estimates is someone who's already built similar system
  19: Iterate the schedule with the code.

Ch. 5: Bend or break:
  37: Configure, don't integrate.
    Use metadata to describe configuration
  38: Put abstractions in code, details in metadata
  39: Analyze workflow to improve concurrency.
    Avoid temporal coupling
  40: Design using services.
    Service = independent, concurrent objects behind well-defined, consistent interface
  41: Always design for concurrency.
    Allows you to deploy application as standalone, client-server, n-tier ...
    Converting noncurrent application to concurrent one is really hard
  42: Separate views from models.
    Ideally, can add new views without changing underlying model
  43: Use blackboards to coordinate workflow.
    Post objects to board when they're ready, then retrieve based on type or parameters

Ch. 4: Pragmatic paranoia:
  30: You can't write perfect software.
    Deal with it, bro
  31: Design with contracts.
    Preconditions, postconditions, class invariants
  32: Crash early.
    Don't let problem propagate through system
  33: If it can't happen, use assertions to ensure that it won't.
    Leave turned on in production to ensure you'll crash early on problems
  34: Use exceptions for exceptional problems.
    Don't use for normal processing -- essentially a cascading "goto", which makes for bad code
  35: Finish what you start.
    Code section that allocates resource must also be responsible for deallocating it

Ch. 3: The basic tools (just "debug" section)
  24: Fix the problem, not the blame.
  25: Don't panic.
    *Think* about what could be causing bug
    Don't say "that's impossible" -- obviously, problem is possible
  26: "select" isn't broken.
    Problem is likely in your code
    Use "rubber ducking" (explain problem to rubber duck) to find fallacious assumptions
  27: Don't assume it -- prove it.

Ch. 6: While you are coding
  44: Don't program by coincidence.
    Know *why* your code works -- understand everything you write
    Document assumptions
  45: Estimate the order of your algorithms.
  46: Test your estimates.
    Use code profilers
  47: Refactor early, refactor often.
    Bad code leads to more bad code -- "broken window" theory
  48: Design to test.
    Put tests alongside application code; make running tests easy, so you do so frequently
  49: Test your software, or your users will.
  50: Don't use wizard code you don't understand.


=======
Testing
=======
Fixtures: provide test data for repeated use
Code inspections: extremely effective at finding bugs
  No code at Google checked in until it's passed code review
    In study, of bugs implanted in code base, code review found 80% of them, while unit testing found 50%