Project 4B: Wordnet (Design)

Lectures needed for this project:

  • Lecture 16 (Extends, Sets, Maps, and BSTs)
  • Lectures 20, 21 (Graph Traversals and Implementations)

Partner policy: No partners. Discussing ideas with other students is allowed, but code sharing is not allowed, and the solutions you submit should be your own work! More details on the policies page.

In this project, you’ll design your approach to Wordnet, the rest of the NGordnet tool.

Before getting started, please read the Project 4C: Wordnet (k == 0) and Project 4D: Wordnet (k != 0) specs. You won’t be able to begin either task without understanding the Wordnet spec first!

Task 1: Checkpoint

The Project 4B: Wordnet Checkpoint is a conceptual assignment testing your understanding of Wordnet. We recommend completing this before designing your project.

Complete the Project 4B: Wordnet Checkpoint. You have unlimited submissions until the deadline and correct answers will be shown upon selection.

Task 2: Technical Design Doc

What is a technical design document?

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.

TDDs are living documents. Software developers iterate on them as project demands change or new issues present themselves. While you’re only expected to submit a snapshot of your TDD for this Project 4B, we encourage you to use this document as a platform for brainstorming high-level ideas for the rest of the project in Project 4C and 4D.

TDDs are inherently collaborative. They act as a forum for communicating your ideas/solution to others on your team and to yourself, whether to manage complexity or to offload ideas for future reference. While this is an individual project, assume your audience is a group of 61B peers with similar programming knowledge as you.

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.

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

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

For an example TDD based on the Percolation mini-Project, see this example.

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. Designing software is a collaborative process. Logging your decision-making process provides essential context for others wishing to understand/contribute to your work.

As mentioned earlier, design docs are living documents. You (the designer) might not understand the entire project scope while drafting, and that’s fine. Including a section for questions can help track your thoughts for future iterations.

A “Questions” section is useful for collaboration. Your collaborators (in this case a staff member reviewing your implementation) may want to understand which assumptions you made or questions you had when designing.

Design Tips

We’ve included below a few questions for you to consider while brainstorming your design:

General Questions

  • Poke around the /browser and /main folders and observe what code exists. How do the examples in the /demo folder use existing classes/methods?
  • How are a user’s inputs (i.e. hyponyms of “cat”, k > 0) communicated to us from the ngordnet website? How do we communicate results back to the website?
    • You aren’t expected to know how the website works. However, it’s important to understand the boundaries of your implementation.
  • Where do tasks overlap? Are there opportunities to reuse methods across different cases? Think about helper methods or opportunities to overload methods.
  • Can you find groups of data structures and methods that serve a similar, clearly defined purpose? If so, consider moving them to a separate class. Building abstraction barriers may be helpful for managing code complexity.

Considering Edge Cases

  • How will your implementation handle words that exist within multiple hyponyms?
  • What output do we expect when a list of words are inputted? Under what circumstances is a synset a hyponym of two words? What about multiple words? How will your implementation determine the correct output?
  • What output do we expect when the user provides a k > 0? Does this relate to anything we’ve already built?

Template

We have provided a template for you to use if you’d like. See the Project 4B: Wordnet Design Template, which is also linked in the assignment below.

Write a TDD for Wordnet and submit it to the Project 4B: Wordnet Design assignment.

If you expect to work on this project during office hours, we may ask to see your design document to help understand your approach. As such, please put effort into this assignment! Grasping project requirements in the design phase will help immensely during the later implementation phases.

Submission

Once you have submitted to both assignments below, you’re done! The checkpoint will immediately display your score, and we’ll aim to have the TDD graded throughout the week.

  1. Project 4B: Wordnet Checkpoint (5 points)
  2. Project 4B: Wordnet Design (5 points)

The score you receive on Gradescope is your final score for this assignment (assuming you followed the collaboration policy).

A note on grading, we are looking for thoughtfulness and effort. In other words, you do not have to be correct in your design or your complexity analysis, but we expect you to have put in considerable time into designing your approach. As long as you attempt to describe your approach for the components in the rubric, you’ll receive full credit.

For the TDD, we have provided the rubric we’ll be grading submissions on below for your reference.

  1. Data (10%): Describes how the data will be used.
  2. Data Structures (40%): Describes what data structures will be used with the data.
  3. Algorithms (40%): Describes what algorithms will be used with the data structures and data.
  4. Complexity (10%): Describes the expected time and space complexity of the program.

Example Technical Design Document (TDD) based on Percolation Mini-Project

Below, we provide an example TDD for the Percolation assignment. Note that this solution is not fully correct. Your design for 4C and 4D will probably not be either.

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?

This spec was written by Daniel Wang and Ronnie Beggs as a new assignment in Fall 2025. The provided template was created by Kanav Mittal and Stella Kaval in Spring 2025 and edited by Daniel Wang.