Advanced Programming I Lecture Notes

13 April 2006 • Assignment 5 Code Review

Outline

• Assignment 4 review.

• The problem.

• Some solutions.

• Testing

• Results

• Coding observations.

Assignment 4 Review.

• Assignment 4 wrapped an n-neighbor ADT around a concordance.

  • The major operation returned the n-neighbors of a word.

  class n-neighbors
  
    n-neighbors(text-file)
  
    word-list get-n-neighbors(n, word)
  

Assignment 4 Review..

word-list
get-n-neighbors(n, word)

  pages = conc.get-pages({ word })
  neighbors = { }

  for pno in pages
    neighbors ∪=
      conc.get-words({pno ... pno+n-1})

  return neighbors

The Problem

• Build a concept graph.

  • An undirected, node- and edge-weighted graph.

  • Edge weights (maximal n-neighbors) indicate compatibility.

  • Node weights (average neighborliness) indicate importance.

The Solution

• Build a concept graph in three steps:

  1. Collect neighborhood data.

  2. Build a complete edge- and node-weighted graph (optional).

  3. Build the concept graph.

• Bottom-up design as presented.

  • But danger: what is a concept graph?

Design Steps

• Bottom-up is out because the target is unclear.

• Top-down is out because concept graphs are too abstract.

• That leaves middle-out or exploratory design.

  • It's what you do when you don't know what you're doing.

Exploratory Design

• Step 1: build a complete graph of all possible nodes and edges.

• Step 2: process the complete graph to create the concept graph.

  • Using the lexical-classification algorithm.

• Step 3: Implement Step-1 data collection.

  • Step 1 doesn't need complete or real data.

• Step 4: Iterate to adjust Steps 1, 2, and 3.

The Complete Graph

• Find all n-neighbors.

• If w₁ and w₂ are n-neighbors and are unconnected, add them with edge weight n.

  • If they are connected with edge weight n' < n, replace n' with n.

• Start at n = the minimum, end at the page count.

• Compute the node weights when fully linked.

The Concept Graph

• Unsupervised lexical acquisition is not a cumulative algorithm.

  • There's no need to keep track of, for example, path lengths.

• Dijkstra's algorithm isn't needed; a simple depth-first component finder will do.

• The only trick is picking one of the highest weighted nodes.

Data Collection

• This is what's needed:

  word-list neighbors(first, last, n)
  

  • Find all n-neighbors in the pages first to last.

• This is how it's used.

  for n = min to last - first + 1
    words = neighbors(first, last, n)
    graph.add(words, n)
  

Finding Neighbors

• Implementing neighbors() using Assignment 4 is simple.

  word-list neighbors(first, last, n)
    neighbors = get-n-neighbors(first, n)
    for i = first + 1 to last - n
      neighbors ∪= get-n-neighbors(i, n)
    return neighbors
  

• This is, all told O((P - n)n) behavior.

  • Is there a better (that is, cheaper) way?

An Observation

get-n-neighbors(i, n) =
    get-n-neighbors(i, n - 1) 
  ∩ get-n-neighbors(i + n - 1, 1)

• Having computed n - 1 neighbors, n neighbors can be computed in "constant time" (measured in intersections).

  • get-n-neighbors(i + n - 1, 1) is equivalent to a word slice at page i in the concordance.

An Improvement

• Keep a scratch concordance around to store n - 1 neighborhoods.

  • scratch.query(i) contains the (n - 1)-neighbors starting at page i.

• neighbors() can now be implemented as

  word-list neighbors(first, last, n)
    scratch.query(first) ∩= conc.query(last)
    return scratch.query(first)
  

Another Observation

• It's wasteful to throw scratchaway when the query's finished.

• Instead, save it in an array of concordances.

  • neighbors[i] is the concordance containing all i-neighbors

• Now neighbors() is

  word-list neighbors(first, last, n)
    return neighbors[n].query(first)
  

  • Initialization neighbors does get messy.

Test Cases

• The empty and garbage tests.

• A chain of three nodes.

• A cycle of three nodes.

• A node that should be pruned

• Separate but equal neighborhoods.

• Separate and unequal neighborhoods.

• No graph at all.

Test Results

• Two assignments didn't compile.

  	Tests
  	1	2	3	4	5	6	7	8
  1
  2
  3
  4

Coding Notes

• Don't repeat yourself.

• Use templates.

• Program defensively.

• No STL containers.

• The Rule of Three.

Duplicate Code

• Duplicate code is bad code.

~MyLinkedList( ) Node* temp while head != NULL temp = head head = head->next delete temp

make_empty() Node* temp while head != NULL temp = head head = head->next delete temp position = 0 size = 0

Procedural Abstraction

• Extract common code into procedures.

~MyLinkedList( ) free_nodes() make_empty( ) free_nodes() position = 0 size = 0

free_nodes() Node* temp while head != NULL temp = head head = head->next delete temp

Duplicate Code

• No, really - don't repeat yourself.

  class ListStr {
    // 14 methods, 220 lines
    private:
      string * array
    }
  
  class ListInt {
    // 16 methods, 230 lines
    private:
      int * array
    }
  

Use Templates

• Use templates to abstract types and reduce code.

  template <typename T>
  class List {
    private
      T * array
    }
  

Program Defensively

• How many things are wrong with this code?

  int cvt(string * pgs, int qry[], int n)
    count = 0
    for (i=0; i <= n; i++)
      char * ch = new char[100]
      string s = pgs[i]
      for (j = 0; j < s.size(); j++)
        ch[j] = s[j];
      qry[count++] = atoi(ch)
    return count
  

The STL

• Don't use STL containers.

• Any code using STL containers will be ripped up and tossed.

  • No second chances.

Don't Bet With Your Grade

• A colleague of yours bet their grade on this code:

  struct linkedlist
    node* head
    linkedlist()
    void addnode(string)
    void printnode ()
    bool search(string)
    bool returndata(int, string &)
    bool checkData(const string &)
  

• What was the bet?

The Rule of Three

• Your colleague bet that the Rule of Three wasn't necessary.

  • No copy constructor, no destructor, no assignment operator, but

  • a pointer instance variable (head).

• Did your colleague win that bet?

  • Well, no; no destructor loses immediately.

  • O.k., but aside from that?

Sadly, No

• Your colleague lost otherwise too.

  
  $ ./cgraph text.1
  Segmentation fault
  
  $ 
  
  

  	Tests
  	1	2	3	4	5	6	7	8
  1

Verify Assumptions

• Verify that you don't need the Rule of Three.

  struct llist
    llist()
    // blah blah blah
    private:
      llist(const llist &) { }
      llist operator = (const llist &) { }
  
  $ g++ -c cgraph.cc
  In function void increaseCap(llist*, int&):
  error: llist& llist::operator=(const llist&)
  error: is private within this context
  
  $