Data structures
P.J. Drongowski
13 September 2004

Data structures

  * Data structures are motivated by real-world applications
  * Data structures and good, efficient algorithms go hand-in-hand
  * Data structures are computer representations of mathematical concepts
    + Arrays and vectors
    + Sets and bags
    + Functions (maps)
    + Graphs (trees, networks)
  * Example: Graphs
    + Is grounded in mathematical graph theory
    + Graph consists of nodes and (directed) arcs
    + Nodes store data while arcs represent relationships
    + Graphs models real-world entities
    + Different kinds of graphs, and their resulting data representation,
      depend on their different topology
    + Graphs must be traversed and the traversal order determines the
      associated algorithm
  * Data structures are part of the body of knowledge that every software
    engineer must know and be ready to apply
  * This core theory allows a direct tie in to material to be learned in
    the discrete mathematics course

Practical software engineering

  + Modular approach to software development: abstraction, encapsulation
    (information hiding, transparency)
  + Design software systems to address the other "-ilities," not just
    correctness and speed
  + Learn and apply idioms and patterns that increase uniformity,
    regularity and consistency
  + Practice defensive programming
    - Define and test assumptions and pre-conditions
    - Define and test post-conditions
    - Detect and handle errors and exceptions
  + Basic automated build process (make)
  + Basic testing
  + Good coding style and code review
  + Basic toolkit for crafting solutions
    - Language processing (parsing, recursive descent)
    - Modelling, especially discrete event simulation and queueing systems
    - Elementary computer graphics

Learning philosophy

  * Learn to teach yourself, learn how to learn
  * When you don't understand something, write a program (build a model)
  * Build a portfolio for job hunting, not a GPA
  * Art school analogy
    + Foundation studies -- what every artist must know and be able to do
      (drawing, 2-D design, 3-D design)
    + Emphasis on practice
    + Develop technique through long term study and professional growth
    + Maintain a portfolio of past and current work in order to quickly show
      or demonstrate what the artist can do

Additional goals for software design
From "Unlocking the Clubhouse" by Margolis and Fisher

  * Compatibility: working together with other programs
  * Composability: being able to be combined with other programs to create
    new, more complex programs
  * Durability: outlasting changes in surrounding systems
  * Extensibility: making it easy to add new features and functions
  * Flexibility: being able to operate in many environments
  * Maintainability: allowing programmers to make changes in a straight-forward
    and reliable fashion
  * Portability: being able to run on multiple different systems
  * Readability: being comprehensible by somebody wishing to read and
    understand the program
  * Reliability: being free of bugs and capable of coping with unexpected
    conditions
  * Reusability: allowing reuse of program code in other settings and
    applications
  * Scalability: being able to run across many machines in a network
    with high efficiency
  * Usability: providing an intuitive and error-free interface to human users
  * Utility: providng a useful solution to a problem