Technical Design Documents

A technical design document (TDD) describes an approach to a specific technical problem. In the context of software engineering, it serves as the blueprint and specification for a software program or feature. TDDs are useful in both communicating and organizing your approach, while also being dynamic drafts that encompass the abstract details of the project.

You will be using design documents for Projects 4 and 5.

It may be useful to include snippits of psuedocode or other portions of plain-text outlining your ideas. Don’t get too carried away with this. If you find yourself writing every method line-for-line in psuedocode, you’re likely straying away from the high-level brainstorming process that a TDD is meant for.

Design Document Format

For this class, TDDs will consist of the following components:

  1. Data
  2. Data Structures
  3. Algorithms
  4. Complexity
  5. Questions
  6. Diagram

Data

What data will you be using? What does the data consist of and how will you parse it for your program? How will your program use the data?

Data Structures

What data structures will you be using? How will your data structures use the data? How will your program use the data structures?

Algorithms

What algorithms will you be using? How will your algorithms use the data structures and data? How will your program use the algorithms?

Complexity

What is the input? How does the time and space complexity change with the input? What are the bounds?

Questions

Open Questions

What questions have come up while brainstorming your design? Consider asking them in assignment section or office hours!

Closed Questions

Move questions here once you’ve found an answer. Logging your decision-making process provides essential context for others wishing to understand/contribute to your work.

Diagram

Visualize your data structures and algorithms into a diagram, such that someone seeing your document for the first time could instantly get a general idea of your implementation. You can use any drawing tool you like, but if you are unsure and looking for one, you can use draw.io

Example

Here is an example TDD based on the Percolation mini-Project

Below, we provide an example TDD for the Percolation assignment. Note that this solution is not fully correct.

Data

Not applicable for the Peroclation assignment.

Data Structures

  • UF percUF of size N*N + 2 (grid plus virtualTop and virtualBottom).
    Used to answer percolates() efficiently.
  • boolean[][] open tracks open sites.

Algorithms

Constructor

  • Set up:
    • open[N][N] = false
    • percUF = new WeightedQuickUnionUF(N*N + 2) with virtualTop = N*N, virtualBottom = N*N + 1
  • Don’t open or pre-connect anything.

open tile method:

  • open(int row, int col)
  • High-level pseudocode below (Note to self: Order of union calls doesn’t matter.)
checkBounds(row, col)
if open[row][col] is true: return because already open
open[row][col] = true

// convert to one dimensional index
int id = xyTo1D(row, col)

// if opened site at the top, connect to the virtual top
if row == 0:
    percUF.union(id, virtualTop)

// if at the bottom, connect to the virtual bottom
// note: don't connect the fullUF because we want
// to avoid backwash
if row == N-1:
    percUF.union(id, virtualBottom)

for each neighbor (nr, nc) in {up, down, left, right}:
    if inBounds(nr, nc) and open[nr][nc]:
        int nid = xyTo1D(nr, nc)
        percUF.union(id, nid)

Check if tile is open:

  • isOpen(int row, int col)
  • If in bounds, just return open[row][col].

Check if tile is full:

  • isFull(int row, int col)
  • If in bounds, just return percUF.connected(xyTo1D(row, col), virtualTop).

    Check if board percolates:

  • percolates()
  • Return percUF.connected(virtualTop, virtualBottom).

Complexity

Let M = N² be the number of sites.

  • Constructor: Θ(N²) time, to build the arrays and union find objects, Θ(N²) space to store open[][] and the union find objects.
  • open: Θ(1) work to do up to 4 neighbor checks, also takes a up to 4 UF union/connected calls, each of which is very close to constant time. In class we said that a union find object with path compression takes on average inverse-Ackermann time per operation with weighted quick-union. So overall time for those four calls is almost constant.
  • isOpen: Θ(1) time to check open[][]
  • isFull and percolates: Θ(1) connected calls, so basically constant time.

Questions

Open Questions

Will my percolation design work to avoid backwash? How do I check the bounds in a nice way?