Computer Go Boom!?!

Oracle Execution Plans

2011-06-14T14:01:00.005-05:00

Oracle Execution Plans

I have the privilege of working with a really great DB architect who taught me a superior method for viewing the detailed execution plan used to satisfy an Oracle query. I'm posting the details here for anyone else that needs to get such a detailed execution plan.

-- configure sqlplus output
set linesize 120
set pagesize 100
set serveroutput off

-- alter session to grab all stats for execution plan
alter session set statistics_level = 'ALL';

-- run your query of interest here
-- SELECT * FROM ???

-- revert your session
alter session set statistics_level = 'TYPICAL';

-- output the execution plan
select * from table (dbms_xplan.display_cursor(null, 0, 'ALLSTATS'));

Here's a sample of what you'll see when viewing execution plans using the strategy outline above:

SQL> -- output the execution plan
SQL> select * from table (dbms_xplan.display_cursor(null, 0, 'ALLSTATS'));

PLAN_TABLE_OUTPUT                                                                                                       
------------------------------------------------------------------------------------------------------------------------
SQL_ID  bj0mxk7kf0dyn, child number 0                                                                                   
-------------------------------------                                                                                   
WARNING: User has no SELECT privileges on V$SQL                                                                         
                                                                                                                        
Plan hash value: 2024250754                                                                                             
                                                                                                                        
---------------------------------------------------------------------------------------------------                     
| Id  | Operation             | Name            | Starts | E-Rows | A-Rows |   A-Time   | Buffers |                     
---------------------------------------------------------------------------------------------------                     
|   1 |  NESTED LOOPS         |                 |      1 |      2 |      2 |00:00:00.01 |       6 |                     
|   2 |   INDEX FAST FULL SCAN| SYS_C0046475723 |      1 |      2 |      2 |00:00:00.01 |       4 |                     
|*  3 |   INDEX UNIQUE SCAN   | SYS_C0046475720 |      2 |      1 |      2 |00:00:00.01 |       2 |                     
---------------------------------------------------------------------------------------------------                     
                                                                                                                        
Predicate Information (identified by operation id):                                                                     
---------------------------------------------------                                                                     
                                                                                                                        
   3 - access("B"."FOO_ID"="F"."FOO_ID")

There are a few things you should note in the execution plan above:

The Operation column shows you, at a high level, what sorts of operations were used to satisfy your query. You'll want to be on the look out for slow operations, like full table scans.
A large discrepancy between the estimated (E-Rows) and actual (A-Rows) rows can often reveal that oracle selected a poor execution plan because of stale statistics. In such cases, you may get some relief by running the ANALYZE TABLE command to recalculate table statistics.

Hello, jQuery Form Plugin

2011-02-04T19:57:00.012-06:00

Hello, jQuery Form Plugin

Lately I've been working on a lot of ajaxy projects and have found the jQuery Form Plugin to be indispensable for such work. It's a super clean plugin for applying ajaxy behaviors to a regular ol' HTML form. To showcase the plugin here on my blog, I wrote a little "Hello, World" snippet that uses the plugin to pull images from Flickr's image feed.

HTML Markup

First, let's get our markup on. We'll build a vanilla HTML form that asks the user for a tag to be searched on Flickr. After the form, we'll also declare an empty <div> that will eventually be updated with the results of our Flickr tag search.

<form id="flickrSearchForm" method="get" action="">
    <label for="tags">Photos tagged with </label>
    <input id="tags" name="tags" placeholder="any Flickr tag" />
    <input type="submit" value="Find" />
</form>

<div id="flickrSearchResults"></div>

jQuery Dependencies

Next we need to include jQuery and the jQuery Form Plugin. The base jQuery library is available via Google's CDN. The form plugin is hosted on github.

<script type="text/javascript" 
 src="https://ajax.googleapis.com/ajax/libs/jquery/1.4.4/jquery.min.js"></script>
<script type="text/javascript" 
 src="http://malsup.github.com/jquery.form.js"></script>

Unobtrusive Goodness

Now we can finally get down to the business of unobtrusively wiring some ajax operations into the otherwise unremarkable HTML form.

// apply form plugin
jQuery('#flickrSearchForm').ajaxForm({
 url: 'http://api.flickr.com/services/feeds/photos_public.gne',
 data: { 
  tagmode: 'any', 
  format: 'json', 
  jsoncallback: 'displayFlickrSearchResults'
 },
 type: 'get',
 dataType: 'script',
 beforeSubmit: function(formDataArray, form, options) { 
  disableSubmitAndClearPreviousResults(); 
 }
});

How easy was that? With just a few lines of code we decorated the form to fire off an ajax request to Flickr when the user presses the submit button. The form plugin took care of a lot of little details like ...

providing a pre-submit hook for clearing out previous search results
serializing the form's inputs into the ajax request's query string
appending some constant data values to the ajax request's query string
automatically invoking the result of the JSONP response as a JavaScript function

End Result

Here's the end result once the code snippets above are put together.

What Have You Done for Me, Latency?

2011-01-17T16:10:00.010-06:00

When developing web applications, it's not uncommon to develop and deploy the application on different network topoligies. During development, for example, you might be running a database server, web server and web browser all on localhost. Your application is running well and the performance is snappy. But user experience starts to lag when the application is deployed to production where web server and database reside on different boxes. What's to blame? Latency.

But fear not, intrepid programmer! Here's a simple command line hack that you can use to make network performance on localhost more closely resemble WAN or LAN performance.

#!/bin/bash

# This script adds a tc rule to the loopback device to 
# help developers approximate WAN performance on their 
# loopback device.

# add a delay rule to the loopback device
sudo tc qdisc replace dev lo root handle 1:0 netem delay 10msec 5msec 10%

# list current state of the loopback device
echo 'Loopback device is now configured to simulate a high latency network route.'
echo ''
echo "Current dev lo rules ... `tc qdisc show dev lo`"
echo ''
echo ''

# demonstrate delay by pinging localhost
ping -c 3 localhost

I run the above commands on login so that overly chatty code doesn't sneak past.

Hello, CSS3

2011-01-09T23:31:00.024-06:00

Hello, CSS3

This week I'm all about embracing new-ish web standards. In a prior post, I marked up an HTML5 "Hello, World!" document using new semantic tags. Today I'm going to apply some CSS2 and CSS3 styles to that document to demonstrate the awesome new design features that are available in CSS3.

First, let's start by checking out how the HTML5 "Hello, World!" document renders without any styling applied:

No surprises in the screenshot above. The document gets rendered with just a bit of formatting for headers, lists & links. Let's add some CSS2 styles to spruce things up a bit.

article,aside,figure,footer,header,hgroup,nav,section {
 /* setup for browsers that don't yet recognize HTML5 
    block elements */
 display:block
}
p {
 /* add a bit of margin above and 
    below all paragraphs */
 margin: 0.5em 0em;
}
html {
 /* stretch body to fill extra browser height */
 height: 98%;
 /* define color for dead space on 
    left and right of page body */
 background-color: #D0D3A6;
}
body {
 /* stretch body to fill extra browser height */
 min-height: 98%;
 /* define content width */
 width:46em;
 /* center content in the browser window */
 margin: 0 auto;
 /* background color for body content */
 background-color: #FFFFFF;
 /* and a wee bit of padding for all 
    top-level elements in the body */
 padding: 0.5em 1.5em;
}
body > header {
 /* keep the header from being crowded */
 margin-bottom: 0.25em;
}
body > header > hgroup { 
 /* style the page's header */
 padding: 0.25em;
 margin-bottom: 0.5em;
 background-color: #BC9C73;
 text-align: center;
}
body > header > nav { 
 /* style the page's navigation content */
 background-color: #486997;
 /* define bottom border to force render of 
   child ul's bottom margin */
 border-bottom: 0.1em solid #486997;
}
body > header > nav a {
 /* style the page's navigation content */
 color: #FFFFFF;
 text-decoration: none;
}
body > header > nav ul { 
 /* style the page's navigation content */
 background-color: #688AB6;
 margin: 0em 0em 0.3em 0em;
 padding: 1em 0.75em 0em 0.75em;
}
body > header > nav ul li {
 /* style the page's navigation content */
 background-color: #486997;
 padding: 0.3em 1em;
 margin: 0em 0.15em;
 display: inline;
}
body > footer {
 /* render the footer in the center, below 
    all other content */
 text-align: center;
 clear: both;
}
h1 {
 text-transform: capitalize;
}
h1,h2 {
 font-size:medium;
 margin: 0.5em 0em 0.25em 0em;
}
div#main {
 /* float main content to the left */
 float: left;
 width: 74%;
}
div#sidebar {
 /* float sidebar content to the right */
 float: right;
 width: 24%;
}

body aside,
body section {
 /* keep content containers from feeling crowded */
 padding: 0.25em;
 margin: 0.25em 0em;
}

Well, that's certainly an improvement. But we can do even better by progressively enhancing the page with some additional CSS3 rules. Let's give the page some depth and texture.

/*  many of these rules generated with 
    the awesome http://css3generator.com/ or
    http://www.colorzilla.com/gradient-editor/ tools */

body { 
 /* round the corners of the body element's border */
 -moz-border-radius: 4px;
 border-radius: 4px; 
 
 /* apply inset box shadow to body element to 
    create the illusion of depth */
 -webkit-box-shadow: inset 2px 0px 25px #333333;
 -moz-box-shadow: inset 2px 0px 25px #333333;
 box-shadow: inset 2px 0px 25px #333333; 
}

h1, h2 {
 /* apply drop shadow to header text */
 text-shadow: 1px 1px 2px #333333;
 filter: dropshadow(color=#333333, offx=1, offy=1); 
}

body > header * { 
 /* by default, round the border corners of 
    all elements in the header */
 -moz-border-radius: 4px;
 border-radius: 4px; 
}

body > header > hgroup,
body > header > nav { 
 /* apply box shadows to top-level header containers 
    to create the illusion of depth */
 -webkit-box-shadow: 2px 4px 6px #333333;
 -moz-box-shadow: 2px 4px 6px #333333;
 box-shadow: 2px 4px 6px #333333; 
}

body > header > hgroup { 
 /* add a subtle gradient to header's background */
 background: -moz-linear-gradient(top, #BC9C73 0%, #D3BFA5 100%); /* firefox */
 background: -webkit-gradient(linear, left top, left bottom, color-stop(0%,#BC9C73), color-stop(100%,#D3BFA5)); /* webkit */
 filter: progid:DXImageTransform.Microsoft.gradient( startColorstr='#BC9C73', endColorstr='#D3BFA5',GradientType=0 ); /* ie */
}

body > header > nav ul {
 /* "square" the dividing line between navigation 
    tabs and their background */
 -moz-border-radius-bottomright: 0px;
 -moz-border-radius-bottomleft: 0px;
 border-bottom-right-radius: 0px;
 border-bottom-left-radius: 0px; 
}

body > header > nav ul li {
 /* round the top corners of the navigation links */
 -moz-border-radius-topleft: 10px;
 -moz-border-radius-topright: 10px;
 -moz-border-radius-bottomright: 0px;
 -moz-border-radius-bottomleft: 0px;
 border-top-left-radius: 10px;
 border-top-right-radius: 10px;
 border-bottom-right-radius: 0px;
 border-bottom-left-radius: 0px; 

 /* add a gradient to the background of our 
    navigation links */
 background: -moz-linear-gradient(top, #c3d9ff 0%, #486997 37%, #486997 100%); /* firefox */
 background: -webkit-gradient(linear, left top, left bottom, color-stop(0%,#c3d9ff), color-stop(37%,#486997), color-stop(100%,#486997)); /* webkit */
 filter: progid:DXImageTransform.Microsoft.gradient( startColorstr='#c3d9ff', endColorstr='#486997',GradientType=0 ); /* ie */
 
 /* apply a more drop shadow to navigation link text */
 text-shadow: 1px 2px 8px #ffffff;
 filter: dropshadow(color=#ffffff, offx=1, offy=2); 
}

body section,
body aside {
 /* round the corners of top-level semantic elements */
 -moz-border-radius: 4px;
 border-radius: 4px; 

 /* apply a gradient background "smear" 
    to top-level semantic elements */
 background: #FFFFFF; /* use white background if gradient not available*/
 background: -moz-linear-gradient(top, #D3BFA5 0%, #FFFFFF 33%); /* firefox */
 background: -webkit-gradient(linear, left top, left bottom, color-stop(0%,#D3BFA5), color-stop(33%,#FFFFFF)); /* webkit */
 filter: progid:DXImageTransform.Microsoft.gradient( startColorstr='#D3BFA5', endColorstr='#FFFFFF',GradientType=0 ); /* ie */
}

Many of the CSS3 rules used above were generated with the awesome CSS3 Generator and ColorZilla Gradient Generator tools. I highly recommend checking them out!

Hello, HTML5

2011-01-09T23:30:00.011-06:00

Hello, HTML5

This week I've been skimming Mark Pilgrim's HTML5: Up and Running book with a keen interest in the new semantic elements that are being formalized as part of the HTML 5 spec. There are some great new semantic elements being proposed to replace pervasive, unformalized web developer memes like ...

 <!-- This is _so_ 2008. -->
 <div id="header">
  <ul id="navigation"></ul>
 </div>
 <div id="content"></div>
  <div id="main"></div>
  <div id="sidebar"></div>
 </div>

Notice in the above markup that the semantic info about each <div>'s purpose is captured in its id attribute. This is totally valid markup and will produce a well organized document, but it does have some serious drawbacks. While such a id-as-semantic-messenger anti-pattern is easily understood by a human web developer, it's not easily parsed by machines.

So why, you may ask, should we care whether machines can understand the semantics of our web pages? Aren't web pages designed to be read and understood by humans? No. Not, all humans read web pages. People with visual impairments have the web read to them by screen readers.

Screen readers aren't that great. Yet. For example, whereas a human can easily and reliably find the main navigation content of a web page, screen readers don't yet support jumping straight to a page's main navigation content. Consider the myriad HTML4 variations that a screen reader would have to handle in order to support a jump-straight-to-navigation feature:

<ul id="navigation"></ul>
<ul id="nav"></ul>
<div id="navigation"></div>
<ul id="navigacion"></ul>
<ul id="menu_bar"></ul>
etc.

HTML5 to the rescue! Writing screen readers that can find the <nav> element in a HTML5 document will be much easier than coding to handle the tag soup detailed above. And <nav> is not the only new semantic element that will make it easier to write better screen readers. HTML5 also defines <header>, <footer>, <section> and <aside>.

That's great news. As a father of a visually impaired child, I'm hoping that future screen reader software can provide my daughter with web interactions that are as rich as those that I enjoy. With that vision of the future in mind, I'm embracing HTML5 and have authored a quick "Hello, World!" example of HTML5 semantic elements in action.

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="utf-8" />
  <title>Hello, HTML5 Semantic Elements!</title>
  <!--[if lt IE 9]>
    <script 
      src="http://html5shiv.googlecode.com/svn/trunk/html5.js">
    </script>
  <![endif]-->
</head>

<body>

  <header>
    <hgroup>
      <h1>Lorem ipsum ...</h1>
      <h2>dolor sit amet, consectetur adipiscing.</h2>
    </hgroup>
    <nav>
      <ul>
        <li><a>Donec hendrerit</a></li>
        <li><a>Pellentesque eget turpis</a></li>
        <li><a>Quisque facilisis porttitor</a></li>
      </ul>
    </nav>
  </header>

  <div id="main">

    <section>
      <header>
        <h2>Morbi a posuere magna</h2>
      </header>
      <p>Etiam feugiat pellentesque dapibus...</p>
      <p>Phasellus ullamcorper condimentum urna...</p>
    </section>

    <section>
      <header>
        <h2>Donec posuere lobortis ipsum</h2>
      </header>
      <p>Cras tellus odio, facilisis nec porttitor...</p>
      <p>Donec blandit suscipit urna ac luctus...</p>
    </section>

  </div>

  <div id="sidebar">

    <aside>
      <header>
        <h2>Ut tincidunt tincidunt</h2>
      </header>
      <p>Suspendisse varius, lacus a egestas...</p>
    </aside>

    <aside>
      <header>
        <h2>Praesent massa sapien</h2>
      </header>
      <p>Phasellus porttitor auctor sapien at...</p>
    </aside>

  </div>

  <footer>
    <p>&copy; 2010 Dave Wingate</p>
  </footer>  

</body>

</html>

Course Notes -- Design of Programming Languages (CS5318)

2010-11-28T15:23:00.023-06:00

This week I'm revisiting some old course notes that I originally published on www.big-oh.net. I'm moving away from self-hosting content on that domain, migrating blog-style content into the cloud ... Blogger in this case.

Following are notes that I used to study for the Design of Programming Languages section of the Texas State University Computer Science graduate comprehensive examination.

Language Design Criteria

The sub-headings below catalog some of the most important language design criteria.

Efficiency

The efficiency of a programming language relates to the speed/cost of performing basic activities of a language's lifecycle. Many facets of a programming language can be evaluated with respect to efficiency.

Efficiency of Execution - Influenced by language features like recursion and dynamic memory allocation.
Efficiency in Translation - How many passes does the compiler need?
Efficiency in Implementation - Influenced by the number of features provided and by level of orthogonality.
Efficiency in Programming - Time to train programmers and time to solve problems in the language.
Efficiency in Maintenance - Largely determined by readability.

Regularity

The regularity of a language relates to the interaction of its features. A language's regularity can be further decomposed into the following characteristics.

Generality - A language is general if there are no special cases in the availability or use of the language's operators. An example of failed generality in the C language is that individual items can be compared with the "==" operator, but entire structs cannot be compared using that operator.
Orthogonality - The constructs of a language are orthogonal if they do not behave differently in different contexts and can be easily combined in all meaningful ways. An example of failed orthogonality in the C language is that local variables can only be defined at the beginning of the block.
Uniformity - In a uniform language, things that are similar should look similar and things that are different should look different. An example of failed uniformity in the C language is that the difference between "=" and "==" is confusing.

Simplicity

Simple languages have the following properties.

Simple languages have fewer features, which makes them easier to implement.
Simple languages may have increased implementation efficiency, but decreased programming efficiency and decreased expressiveness.

Abstraction

Abstractions hide unnecessary details, those that are only relevant to the internal implementation. For example, the String data type is an abstraction in that it hides the implementation details of storing and manipulating character data. Another example abstraction is that the "if" statement is an abstraction in that it eliminates the need to consider logic-based jump commands.

The table below describes a taxonomy of abstraction levels in programming languages.

Abstraction Level	Data	Control
Basic	Variables as abstractions for memory locations.	Variable assignment and jump statements.
Structured	Arrays, records, structs, classes, lists, etc.	Guarded commands.
Unit	Packages, components, libraries, etc.
Parallel	Threads, processes, tasks, etc.

Computational Paradigms

A single programming language may support one or more computational paradigms. The sub-headings below details some of the computational paradigms covered by the comprehensive exam.

Imperative

The imperative computational paradigm is closely tied to the structure of the von Neumann computer model.

A.k.a. procedural.
Examples include Fortran, C, Pascal and Algol
Characterized by sequenced instruction execution, loops, and variables that represent memory locations.

Functional

The functional computational paradigm structures programs in a manner that mirrors the structure of lambda-calculus.

A.k.a. applicative.
Examples include Lisp, Miranda and Scheme.
Reasoning about this type of programs is easier because it is based on recursive function theory.
Characterized by (recursive) function calls as the basis for program control. Instead of having variables that represent memory locations, this paradigm has function parameters that accept input values.

Logic

The logical computational paradigm is a higher-level paradigm that abstracts away the need to describe "what to do," requiring that the programmer describe only "what s/he wants."

A.k.a. declarative.
Examples include Prolog and SQL.
Characterized by variables that represent partial computations, which are inputs to Horn clause resolution.

Programming Language Levels

When writing a program in any language, errors can arise at many different levels:

Lexical - identifiers, operators, separators, comments
```
// not a valid operator or identifier
int x#1 = 2;
```
Context-Free Syntax - dictates the form of statements, functions, modules, etc.
```
// missing parentheses violates 
// if statement syntax
if x == y { a=b; }
```
Context-Sensitive Syntax - type checking, forward references, variable declaration, etc.
```
// duplicate variable declaration
double a;
...
int a; 
  
```
Dynamic Semantics - divide by zero, use of un-initialized variable, etc.
```
double a = 0;
double b = 12 / a;
  
```

Grammars

Definition

A grammar is defined by:

A finite set of non-terminal symbols.
A finite set of terminal symbols.
A single start symbol.
A finite set of production rules.

Context-Free Grammars

A Context-free grammar consists of a series of grammar rules that observe the form:

Non-terminal -> {terminals and non-terminals}

This type of grammar is context-free because each left-hand-side non-terminal can always be replaced by any right-hand-side choice, no matter where the non-terminal might appear.

Additionally, a context-free grammar also has a distinguished non-terminal called a start symbol. The language for the grammar is the set of all strings of terminals that can be derived from the start symbol.

By defining a programming language using a context-free grammar, the grammar also implicitly defines the steps that a parser must take to construct a parse tree for a string.

Attribute Grammars

Attribute grammars are an extension of context-free grammars. Because context-free grammars describe only the lexical and syntax levels of a language, they are unable to describe many features of modern programming languages. For example, context-free grammars are unable to enforce type checking. Attribute grammars provide the ability to enforce static semantic rules, like type checking.

An attribute grammar has these properties:

Each grammar symbol has a set of (inherited or synthesized) attributes.
Each grammar rule has a set of (semantic of predicate) functions, which are defined over the attributes of the symbols in the rule.

Course Notes -- Algorithm Design and Analysis (CS5329)

2010-11-28T15:22:00.021-06:00

Following are notes that I used to study for the Algorithm Design and Analysis section of the Texas State University Computer Science graduate comprehensive examination.

Sorting Algorithms

Quick Reference

Here is a quick summary of the features offered by some of the most important sorting algorithms.

Algorithm	Worst Case	Average Case	In Place?	Stable?
Quick Sort	n²	n lg n	Yes	No
Merge Sort	n lg n	n lg n	No	Yes
Heap Sort	n lg n	n lg n	Yes	No
Insertion Sort	n²	n + d	Yes	Yes
Counting Sort	n + k	n + k	No	Yes

The table above uses several variables. The variable n represents the number of items to be sorted. The variable d represents the number of inversions required by the algorithm. The variable k represents an upper bound on the values to be sorted.

Quick Sort

Quick sort is a classic divide-and-conquer algorithm in which the input array is split into left and right subsets such that all elements in the left subset are <= a pivot value and all elements in the right subset are >= a pivot value.

Quicksort(A,p,r)
  if (p<r)
    q = Partition(A,p,r);
    Quicksort(A,p,q-1);
    Quicksort(A,q+1,r);

Partition(A,p,r)
  x = A[r];
  i = p-1;
  for j = p to r-1
    if A[j] <= x
      i++;
      swap(A[i],A[j]);
  i++;
  swap(A[i], A[r]);
  return i;

To achieve the best-case run time for quick sort, the partition function must evenly divide the input array each time that it is called. T(n) = 2T(n/2) + O(n) --> T(n) is O(n lg n)

In the worst-case runtime for the algorithm, each call to the partition function creates sets of size n-1 and 1. T(n) = T(n-1) + T(1) + O(n) --> T(n) = O(n2)

Merge Sort

Merge sort is also a divide-and-conquer algorithm. The algorithm relies on the fact that fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists.

In the merge sort algorithm, unsorted lists are recursively divided in half until they can be divided no further. At that point, the ordered lists are merged together, forming ever-larger ordered lists.

Heap Sort

Heaps are complete binary trees (with possible exception of rightmost nodes on the lowest level) in which all non-root nodes observe the heap property: parent(i) >= i. Heap sort operates by building a heap from the input elements and then iteratively removing the top element from the heap.

Insertion Sort

Insertion sort is an easy to implement comparison sort that builds a sorted array one element at a time. The first k iterations of the algorithm produce an ordered k-element sub-list. The algorithm requires n such iterations, each of which may need to perform k comparisons in the worst case.

Insertion sort has good performance on an almost-sorted input list. Despite poor worst-case performance of the algorithm, it can out-perform other more sophisticated comparison sorting algorithms when operating on very small input sets.

Counting Sort

Counting sort is NOT a comparison sort. Counting sort takes an input of n integers whose values range from 1 to k. The general strategy for each input element x is to determine the number of inputs <= x and then put x directly into the correct output position.

Solving Recurrences

Useful Mathematical Properties

Summation of 1..n = n(n+1)/2
x = log_a y --> (a to some power x equals y) --> y = a^x
log_a a = 1

Asymptotic Notation

Big-Oh - An upper bound:
f is Ο(g) if for some c and n₀, 0 <= f(n) <= c * g(n) for all values of n >= n₀
Big-Omega - A lower bound:
f is Ω(g) if for some c and n₀, 0 <= c * g(n) <= f(n) for all values of n >= n₀
Big-Theta - An asymptotically tight bound:
f is Θ(g) if for some c₁, c₂ and n₀, 0 <= c₁ * g(n) <= f(n) <= c₂ * g(n) for all values of n >= n₀

Recursion Trees

Each node in the tree is labeled with its complexity (excluding recursive calls).
The complexity of recursive calls is represented by child nodes in the tree.
The total complexity is determined by summing the work done at each level in the tree.

Master Method

Many (but not all) recurrences can be solved using the master method. Consider recurrences of the form:
T(n) = a * T(n/b) + f(n)
where a >= 1 and b > 1 and f(n) is an asymptotically positive function.

Case 1 - If for some constant e > 0,
f(n) = Ο(n ^{(log_b a - e)})
then T(n) = Θ(n ^{(log_b a)})
Case 2 - If f(n) = Θ(n ^{(log_b a)})
then T(N) = Θ(n ^{(log_b a)} lg n)
Case 3 - If for some constant e > 0,
a) f(n) = Ω(n ^{(log_b a + e)})
and
b) a * f(n/b) <= c * f(n) for some c < 1
then T(n) = Θ(f(n))

Divide-and-Conquer Techniques

Divide-and-conquer is a recursive algorithm design technique in which subproblems are divided until they are small enough to solve directly. Solutions to subproblems are then combined to solve the problem at-large.

Divide-and-conquer algorithms have a related recurrence relation that can be used to determine the run time complexity of the algorithm.

The quick sort algorithm is an example of a divide-and-conquer algorithm.

Dynamic Programming

Elements of Dynamic Programming

Dynamic programming is applicable when subproblems share subsubproblems. It is typically utilized in solving optimization problems.

There are four steps to developing a dynamic programming algorithm:

Characterize the structure of an optimal solution.
Recursively define the value of an optimal solution.
Compute the value of an optimal solution in a bottom-up fashion.
Construct an optimal solution from computed information.

Assembly Line Scheduling - An Example

Two lines, each containing n stations. The problem is to determine which stations to choose from line 1 and which to choose from line 2 in order to minimize the total time through the factory.

We observe that the problem has optimal substructure: The optimal path to station Si,j contains an optimal path to either station S1,j-1 or S2,j-1.
Recursive definition: f1[j] = min(f1[j-1] + a1,j; f2[j-1] + t2,j-1 + a1,j)
Compute bottom-up with a table of the following form:

Station 1 Station 2 .. Station n

line1 f/l f/l f/l f/l

line2 f/l f/l f/l f/l

Where f is the cost to get to that station and l records the line number of the j-1th station we used to achieve the optimal solution.
Optimal solution is constructed from table produced in prior step.

Greedy Strategies

Elements of Greedy Strategies

Greedy strategies are a special case of dynamic programming. In addition to exhibiting optimal substructure, problems that are appropriately solved by a greedy strategy have the greedy choice property:

A globally optimal solution can be obtained by making a locally optimal (greedy) choice.

Greedy algorithms differ from traditional dynamic programming solutions in that they are a top-down strategy.

Activity Selection - An Example

Problem is to select a max size set of mutually compatible activities. The key to solving with a greedy strategy is to sort activities in order of finish time. The greedy solution always chooses the first compatible activity (i.e. the one with the earliest finish time). That solution is greedy in that it maximizes the remaining available time.

Note that the greedy strategy described above is appropriate for soling the activity selection problem because the problem exhibits:

Optimal substructure
Greedy choice property

Coin Changing - An Example

The coin changing problem highlights the fact that greedy strategies are not always optimal. In that problem, we are asked to produce the minimal number of coins representing a dollar amount.

By way of example, consider the scenario in which we are asked to compose $0.31 from these available denominations: $0.25, $0.10, $0.01. In that case, the Greedy solution would be:
25,1,1,1,1,1,1
However, the optimal solution is:
10,10,10,1

Course Notes -- Data Base Theory and Design (CS5332)

2010-11-28T15:22:00.018-06:00

Following are notes that I used to study for the Data Base Theory and Design section of the Texas State University Computer Science graduate comprehensive examination.

Elementary DBMS Concepts

Functional Dependencies, Attributes and Keys

A database management system (DBMS) promotes data integrity through elimination of data repetition, referential integrity and transactional operations.
An attribute B has a functional dependency on attribute A (A -> B) if for each value of attribute A there is exactly one value of attribute B.
A super key is a collection of attributes that uniquely identifies a row in a table -- i.e. the set of attributes in the table is functionally dependent on the super key.
A candidate key is a minimal super key.
A primary key is selected from all possible candidate keys.
A non-prime attribute is one that is not part of any candidate key.

Normalization of Tables

1NF, 2NF, 3NF, and BCNF

A table with a unique key is in first normal form (1NF). All tables with a primary key are, by definition, in 1NF.
A 1NF table is in second normal form (2NF) if all functional dependencies of non-prime attributes depend on a complete candidate key (or another non-prime attribute). If a non-prime attribute has a functional dependency on a proper subset of a candidate key, then the table is not 2NF. Note that if no candidate keys are composite, then the table is 2NF by definition.
For example, in an EMPLOYEE_SKILLS entity comprised of (EMPLOYEE_ID, EMPLOYEE_ADDRESS, SKILL), the EMPLOYEE_ADDRESS is functionally dependent on EMPLOYEE_ID, which is a proper subset of the only candidate key (EMPLOYEE_ID, SKILL). This is an intuitively undesirable situation because the EMPLOYEE_ADDRESS attribute will contain repetitive data that may become inconsistent due to update anomalies.
A 2NF table is in third normal form (3NF) if all non-prime attributes are non-transitively dependent on every candidate key. As with 2NF, 3NF protects against logical inconsistencies brought on by update anomalies.
BNCF is a slightly stronger version of 3NF in which for all non-trivial functional dependencies A -> B, A must be a super key. Most 3NF and BCNF tables are free of update, insertion and deletion anomalies.
Normalization protects against three types of data anomalies.

Data Anomalies

Update anomalies may arise when the same information is stored in multiple locations, thus potentially allowing an update to create inconsistent data.
Insertion anomalies may arise when two pieces of unrelated information (A and B) are stored together in the same entity, thus potentially leading to a situation in which A cannot be defined in the DB because B does not yet exist in the DB.
Deletion anomalies may arise when two pieces of unrelated information (A and B) are stored together in the same entity, thus potentially leading to a situation in which information about A will be (incorrectly) deleted because the last related B has been deleted.

Entity-Relationship Modeling

Diagram Basics

Entities are typically nouns that are depicted in a rectangle.
Relationships are typically verbs that are depicted in a diamond.
Both entities and relationships can have attributes, which are depicted in ellipses. The names of attributes that form an entity's primary key are underlined.
An arrow indicates an "at most one" relationship.
A double line indicates mandatory participation.
Wikipedia has an excellent example of an entity-relationship diagram.

Course Notes -- Advanced Artificial Intelligence (CS5346)

2010-11-28T15:21:00.012-06:00

Following are notes that I used to study for the Advanced Artificial Intelligence section of the Texas State University Computer Science graduate comprehensive examination.

Conventional Search

Quick Reference

Conventional search strategies utilize only the facts provide in the problem definition. They are dumb searches in the sense that they are only capable of generating successors and distinguishing goal states from non-goal states.

Here is a quick summary of the features offered by some of the most important conventional search strategies.

Strategy	Summary	Complete?	Optimal?	Space
Breadth First Search	Uses a queue to manage successor nodes.	Yes	Yes	Ο(b^d+1)
Depth First Search	Uses a stack to manage successor nodes.	No (when the search space is infinitely deep)	No	Ο(bm)
Depth Limited Search	A derivation of depth first search that treats nodes at some cutoff maximum depth as though they had no successors.	No	No	Ο(bl)
Iterative Deepening Depth Limited Search	Iteratively runs depth limited search with increasing cutoff values until a goal state is found.	Yes	Yes	Ο(bd)

The table above uses several variables. The variable b represents the branching factor of the search space. The variable d represents the depth of the shallowest solution in the search space. The variable m represents the maximum depth of the search tree.

Informed Search

Best-First Strategies

Informed searches use problem-specific knowledge to find solutions (goal states) more efficiently. An important subclass of informed searches, best-first searches navigate the search space by choosing the next (best) node for expansion based on an evaluation function. The efficiency of a best-first search algorithm depends entirely on the accuracy of the evaluation function -- i.e. how often it can recommend the node that is next in leading us to a goal state. There are many best-first search algorithms, differing only in the evaluation functions that they use.

A priority queue is useful data structure in implementing best-first search algorithms.

Greedy Best-First Search

The greedy best-first search strategy uses the evaluation function f(n) = h(n), where h(n) is a heuristic that judges how close the current node is to a goal state. Solutions found by this evaluation strategy may not be optimal. Moreover, the strategy is not complete.

A* Search

The A* search strategy is a best-first search strategy that uses the evaluation function f(n) = g(n) + h(n), where g(n) is the cost to get to the current node and h(n) is a heuristic estimate of the cost from the current node to a goal state. If h(n) is an admissible heuristic, then A* is both complete and optimal. An admissible heuristic is one that never overestimates the cost to reach a goal state.

Problem relaxation and combination are both important methods for developing admissible heuristics for the A* search strategy.

Local Search

Overview

Local search strategies can be used when we seek only a goal state, but not a path to the goal state. In general, local search algorithms operate by starting with start with a goal state and then moving to a neighbor state. Local search strategies typically use much less memory than both the conventional and informed search methods described in the sections above.

Examples

Here is a list of some important local search strategies.

Hill climbing is the most basic local search technique. In hill climbing, we iteratively move to neighbor states with greater value until we hit a local maximum.
Random-restart hill climbing performs the hill climbing algorithm several times from random starting states.
In simulated annealing, the strategy is to pick a random successor move. If the move is an improvement, it is kept. Otherwise, if the move is not an improvement, it is only kept with some probability less than 100%.

Minimax Adversarial Search

Overview

The minimax search strategy seeks to minimize the maximum possible loss a player will incur when playing a turn-based multiplayer game. The minimax search strategy assumes that the opposing player will always make optimal moves. The strategy also relies on having a utility function that can be used to score game states as well as a terminal-test function that can be used to identify terminal game states.

We typically describe the players of the game as A (who is trying to maximize the score) and B (who is trying to minimize the score. At each step in the minimax search tree, we assume that A and B make optimal choices, meaning that A selects the child with the largest score and B selects the child with the smallest score.

Example

Wikipedia has an excellent example of a 2-ply minimax search tree in which circles represent "A's turn" and squares represent "B's turn." Notice that circles (A) are filled-in with the largest child value and squares (B) are filled-in with the smallest child value.

Pseudo Code

The implementation of the minimax search strategy is very simple, requiring only two nearly identical recursive control functions:

function MaxValue(state) returns a utility value
 if Terminal-State(state) 
  return Utility(state); 
 v = -infinity;
 for s in Successors(state) 
  v = Max(v, MinValue(s));
 return v;
 
function MinValue(state) returns a utility value
 if Terminal-State(state)
  return Utility(state);
 v = +infinity;
 for s in Successsors(state)
  v = Min(v, MaxValue(s));
 return v;

Alpha-Beta Pruning

Alpha-Beta pruning is a technique that allows us to calculate a correct minnimax decision without considering every node in the game tree. Specifically, alpha-beta pruning trims away sub trees that cannot possibly influence the final value calculated by the minimax search strategy.

To apply the alpha-beta pruning concept to our minimax functions, we need only introduce two new parameters to the pseudo-code cataloged above:

a - the best (largest) value in the search path for Max
b - the best (smallest) value in the search path for Min

function MaxValue(state, a, b) returns a utility value
 if Terminal-State(state) 
  return Utility(state);
 v = -infinity;
 for s in Successors(state) 
  v = Max(v, MinValue(s, a, b));
  if v >= b
   return v;
  else
   a = Max(a, v);
 return v;
function MinValue(state, a, b) returns a utility value
 if Terminal-State(state)
  return Utility(state);
 v = +infinity;
 for s in Successsors(state)
  v = Min(v, MaxValue(s, a, b));
  if v <= a
   return v;
  else
   b = Min(b, v);
 return v;

Imperfect Search

The minimax search procedure (with or without alpa-beta pruning) is an optimal search strategy. However, the large search space of most games prohibits execution of the minimax search procedure down to terminal nodes. In order to search for a good solution to an adversarial problem, an evaluation function can be used to turn non-terminal nodes into terminal nodes. To conduct imperfect searches, we must make two modifications to the minimax search routine:

The utility function is replaced by a heuristic evaluation function.
The terminal test is replaced by a cutoff test that decides when to call the evaluation function.

Knowledge Representation

Motivation

Logics (propositional or first-order predicate) are useful for building knowledge bases that can be used by logical agents to infer the answers to submitted problems. Such systems are generally declarative (as opposed to procedural) and are implemented by inference algorithms that are both sound (truth preserving) and complete.

Propositional Logic

The syntax of propositional logic is characterized by atomic sentences comprised of propositional symbols (e.g. R P Q), negations (-), conjunctions (^), disjunctions (or), implications (->) and biconditionals (<->). Truth tables are one way of defining the meaning of the above operators.

Propositional sentences can be classified according to validity and satisfiability:

A valid proposition is one that is true in every model.
A satisfiable proposition is one that is true in some model.
A non-satisfiable proposition is one that is true in no model.

Inference rules can be applied to propositional sentences to soundly derive new sentences.

Modus Ponens:
* a->b
* a
entails b
And-Elimination:
* a ^ b
entails a
Unit Resolution:
* a or b
* -b
entails a
Resolution:
* a or b
* -b or c
entails a or c

Horn clauses are propositional logic clauses that are limited to being disjunctions of literals, of which at most one is positive. Every Horn clause can be rewritten as an implication. For example, the Horn clause (-a or -b or c) can be rewritten as the implication a ^ b -> c. Horn clauses support forward chaining and backward chaining.

Another standard format for propositional logic sentences is conjunctive normal form. All propositional logic sentences can be translated to conjunctive normal form, which is a conjunction of disjunctions: (A or -B or C) ^ (-D or E) ^ (F or G or H)

De Morgan's laws are useful when converting to CNF:

-(A ^ B) can be rewritten as (-A or -B)
-(A or B) can be rewritten as (-A ^ -B)

First-Order Predicate Logic

Propositional logic is not sufficient to succinctly represent complex environments. First-order predicate logic is more powerful because it deals with objects and their relations, not just propositional facts. The syntax of first-order predicate logic is comprised of:

Constants, which stand for objects -- e.g. John
Predicates, which stand for relations -- e.g. Brother(John, Tom)
Functions

First-order predicate logic also allows the use of the logical connectives we saw in propositional logic: ^, V, -, ->, <->. In addition, first-order predicate logic also allows the use of quantifiers, which allow us to make single statements that apply to collections of objects. The universal quantifier (∀) and the existential quantifier (∃) can be used to rewrite multiple propositional logic sentences as a single first-order predicate logic sentence. For example, we can capture the idea that "everyone loves someone" using this first-order predicate logic sentence: ∀x ∃y Loves(x,y)

Expert Systems

The techniques of forward chaining and backward chaining can both be used to construct expert systems.

Forward Chaining

Forward chaining is an example of data-driven reasoning -- i.e. reasoning in which the focus of attention begins with all known facts.

The forward chaining algorithm seeks to determine whether a query q is entailed by the (Horn clause) sentences in a knowledge base. Forward chaining begins by collecting all of the know facts (positive literals) in the database. Next, using implication, if all premises of a knowledge base sentence are known, its conclusion is added to the collection of facts. That process is repeated until either the query q is derived as a fact or until no further facts can be generated.

Backward Chaining

Backward chaining is an example of goal-directed reasoning -- i.e. reasoning in which the focus of attention begins with the query statement.

The backward chaining algorithm works backward from the query statement. The algorithm attempts to prove true a set of statements from which the query q is entailed. For each statement s needed to entail q, backward chaining is recursively applied to prove s.

Course Notes -- Survey of Software Engineering (CS5391)

2010-11-28T15:20:00.006-06:00

Following are notes that I used to study for the Survey of Software Engineering section of the Texas State University Computer Science graduate comprehensive examination.

Software Development Lifecycle Models

Waterfall Model

This model is document-driven and is also known as the "linear sequential" model.
Activities in this model are structured in a linear cascade of phases in which the output of the previous phase is the input to the next phase.
Phases are: Feasibility Study -> Requirements Analysis -> Technical Design -> Code and Unit Test -> Integration and System Test -> Deployment and Maintenance.
The linear structure of this model provides no feedback to prior phases. This is often impractical since, for example, it is not always possible to identify all requirements at the beginning of a project.

Incremental Model

The stages of this model consist of expanding increments of an operational software product.
Increments are delivered to customers as they are completed.
Each delivered unit is a self-contained functional unit.
This methodology allows for continuous validation (as opposed to a final validation phase).
This model retains all steps defined in the waterfall model, but performs those steps multiple times in an iterative fashion.

Spiral Model

This model iteratively utilizes the steps below to identify and mitigate high-risk issues in the development of high-quality software.

Step 1 - Identify quality objectives for a portion of the product.
Step 2 - Identify risks in achieving objectives and evaluate alternative mitigation strategies.
Step 3 - Develop and verify a unit of functionality.
Step 4 - Review development results and plan for next iteration.

Capability Maturity Model

The Capability Maturity Model (CMM) has the following characteristics:

The CMM is an application of process management and quality improvement concepts to software development and maintenance.
The CMM doesn't describe how to create an effective software organization. Rather it simply describes the features of such an organization.
The CMM defines an ordinal scale of five levels used to measure the capabilities of an organization's software process.

Each level of the CMM is composed of a set of key process areas for which related activities are defined:

Level 1 - Chaotic/Initial. Processes are unpredictable and poorly controlled. Success results from individual efforts.
Level 2 - Repeatable. Projects can repeat previously mastered tasks. Basic project management processes are established to track cost, schedule and functionality.
Level 3 - Defined. Processes are defined and understood by staff. The software process activities are standardized and documents.
Level 4 - Managed. Processes are measured and controlled (since you can only manage what you can measure).
Level 5 - Optimized. Organization is focused on process improvement.

Software Design Methodologies

Structured Analysis and Design

Structured analysis and design attempts to harness complexity through a hierarchical design created by iteratively decomposing program segments until the program is completed.
The algorithm is the fundamental building block of this design methodology.
Abstraction is used to focus on subproblems, ignoring the overall strategy of the algorithm.

Object-Oriented Analysis and Design

Classes and objects are the fundamental building blocks of this design methodology; they are extracted from the vocabulary of the problem domain.
Abstraction is applied to reuse the features of related classes that are already part of the object model.
Reuse is enabled by language features: inheritance and polymorphism.

Software Testing Strategies

Program Inspection

Goal: Ensure the program element follows the specification. Ensure the program element supports stated non-functional requirements.
Method: A review group (comprising the roles of Moderator, Author, Reviewer and Recorder), uses a checklist to review a program elements to ensure the above goals.
Phase: Implementation.

Black-Box Testing

Goal: Verify that a system or sub-system behaves as expected.
Method: Derive test cases from the public interface specification. May use equivalence partitioning and boundary value analysis strategies.
Phase: System and Integration Testing.

White-Box Testing

Goal: Verify that a software unit behaves as expected.
Method: Derive test cases from the internal structure of the program.
Phase: Implementation.

Load or Stress Testing

Goal: Gain confidence that software meets non-functional performance requirements.
Method: Find mean time to failure using an input set that is appropriately varied.
Phase: Integration Testing.

Regression Testing

Goal: Ensure that previously released features have not been broken by new software updates.
Method: Execute functional test cases to gain confidence that key software features have not been broken.
Phase: Maintenance.

Logging HttpServletRequests

2010-11-07T23:32:00.006-06:00

Motivation

Whereas observing ServletResponses is non-trivial, ~~Sun~~ Oracle makes it much easier to observe HTTP requests via the ServletRequestListener interface. ServletRequestListeners are awesome; they make it super easy to record and log requests, thereby improving the undestandability of your web applications. Recording and logging ServletRequests with a listener is preferable to doing that same work in the requested resource (Servlet, JSP, etc.) since the former strategy achieves an improved separation of concerns.

Implementation

Big-Oh Software's CommonWeb Framework provides RequestObserverListener, an abstract implementation of the ServletRequestListener interface that can be extended to observe ServletRequests in myriad meaningful ways. That abstract implementation of the listener interface collaborates with the ObservedHttpServletRequest class, which adapts an original ServletRequest into an object that is more easily observed, recorded and logged.

An Example: Servlet Request Logging

Using the RequestObserverListener to log incoming Servlet requests is shamefully easy. Only a few lines of Java and XML are needed:

package foo.bar;

import net.big_oh.common.web.listener.request.*;

public class MyRequestLoggerListener extends RequestObserverListener
{

 @Override
 protected void doOnServletRequestInitialized(ObservedServletRequest observedServletRequest)
 {
  System.out.println(observedServletRequest);
 }

}

... and ...

<!-- web.xml snippet -->

<listener>
  <listener-class>foo.bar.RequestLoggerListener</listener-class>
</listener>

By applying the above logging listener to a web application, you'll see that new ServletRequests are logged in this format:
Received a HTTP/1.1 request from localhost (127.0.0.1) for resource http://127.0.0.1:8080/CommonWeb/ (GET) -- jSessionId: B46435C89F9FABCE571AF701E0BC6820 -- userName: unknown

Observing HttpServletResponses

2010-10-17T18:54:00.005-05:00

Motivation

Filters are a great way to observe (or even modify) the response generated for an HTTP request. This post will present a handy application of the observer pattern from within a Java web Filter, allowing developers to monitor responses to HTTP requests as they are constructed.

Implementation

The response observer filter I want to describe is part of Big-Oh Software's CommonWeb Framework. That framework defines a ResponseObserver interface that models the events that transpire while constructing the response to an HTTP request. A simple, abstract filter class, ResponseObserverFilter, serves as the base class for (potentially) many filters that observe those events.

An Example: Response Size Monitor Filter

Because the abstract ResponseObserverFilter utilizes the observer pattern, we can use it to define many useful, concrete filters without having to write much code. For example, it is quite easy to create a ResponseSizeMonitorFilter that announces the size of the response generated for an HTTP request.

Applying the ResponseSizeMonitorFilter to the servlets in your web application is a simple matter of including the snippet below in your web.xml file:

<!-- web.xml snippet -->

<filter>
  <filter-name>ResponseSizeMonitorFilter</filter-name>
  <filter-class>net.big_oh.common.web.impl.ResponseSizeMonitorFilter</filter-class>
</filter>

<filter-mapping>
  <filter-name>ResponseSizeMonitorFilter</filter-name>
  <url-pattern>/*</url-pattern>
</filter-mapping>

The ResponseSizeMonitorFilter will now log the size of HTTP responses in the following format:
The response for the requested url (http://127.0.0.1:8080/CommonWeb/ImageServlet) contained about 4.09 kilobytes.

Conky

2010-08-01T20:36:00.023-05:00

Introducing Conky

Conky is a free tool for embedding information into your X desktop. I use it during the work day to keep an eye on my computer's resources and to help remind me how I should be utilizing my own resources.

This tutorial isn't designed to teach you how to use Conky. For that, you'll have to check out the Conky documentation. However, this tutorial will show you how to customize Conky to embed information in your Ubuntu desktop, just like the image to the right.

Configuring Conky

Conky is configurable through the .conkyrc file in your home directory. In order to get Conky to produce the output shown above, I made a few changes to the standard sample .conkyrc file, which you can find at /usr/share/doc/conky/examples/conkyrc.sample.gz.

Conky's colors are highly configurable. I've selected a nice earthy palette of yellow, orange and gray.

# Colors
default_color BDB76B # Values
color0 FF8C00 # Headers
color1 lightgrey # Line Items
color2 BDB76B # Highlighted Values

Next I use my newly defined color palette to draw attention to the processes that are currently consuming the most cpu and memory resources on my computer.

${color1} ${top name 1} ${top pid 1} ${color2}${top cpu 1}${color1} ${top mem 1}
...

${color1} ${top_mem name 1} ${top_mem pid 1} ${top_mem cpu 1} ${color2}${top_mem mem 1}

I've also asked Conky to embed the contents of a text file into my desktop. Specifically, I like to always see my TODO list.

${color0}TODO:${color1}
${execi 30 cat /home/username/Desktop/TODO.txt | fold -w40 }

Integrating all of the tweaks described above, I arrived at the .conkyrc configuration file cataloged below.

################################ Conky Settings ################################

# set to yes if you want Conky to be forked in the background
background no

# X font when Xft is disabled, you can pick one with program xfontsel
font arial

# Use Xft?
use_xft yes

# Xft font when Xft is enabled
xftfont Bitstream Vera Sans Mono:size=11

# Text alpha when using Xft
xftalpha 0.8

# mail spool
mail_spool $MAIL

# Update interval in seconds
update_interval 5.0

# This is the number of times Conky will update before quitting.
# Set to zero to run forever.
total_run_times 0

# Create own window instead of using desktop (required in nautilus)
own_window yes

# If own_window is yes, you may use type normal, desktop or override
own_window_type override

# Use pseudo transparency with own_window?
own_window_transparent yes

# If own_window_transparent is set to no, you can set the background colour here
own_window_colour hotpink

# If own_window is yes, these window manager hints may be used
own_window_hints undecorated,below,sticky

# Use double buffering (reduces flicker, may not work for everyone)
double_buffer yes

# Minimum size of text area
minimum_size 280 5

# Draw shades?
draw_shades no

# Draw outlines?
draw_outline no

# Draw borders around text
draw_borders no

# Draw borders around graphs
draw_graph_borders yes

# Stippled borders?
stippled_borders 8

# border margins
border_margin 4

# border width
border_width 1

# Default border colors
default_shade_color black
default_outline_color black

# Text alignment, other possible values are commented
alignment top_right

# Gap between borders of screen and text
# same thing as passing -x at command line
gap_x 20
gap_y 50

# Subtract file system buffers from used memory?
no_buffers yes

# set to yes if you want all text to be in uppercase
uppercase no

# number of cpu samples to average
# set to 1 to disable averaging
cpu_avg_samples 2

# number of net samples to average
# set to 1 to disable averaging
net_avg_samples 2

# Force UTF8? note that UTF8 support required XFT
override_utf8_locale no

# Add spaces to keep things from moving about? This only affects certain objects.
use_spacer no

# Colors
default_color BDB76B # Values
color0 FF8C00 # Headers
color1 lightgrey # Line Items
color2 BDB76B # Highlighted Values

################################ Screen Text ################################

TEXT
$nodename - $sysname $kernel on $machine
$hr
${color0}Summary:$color
${color1}IP:$color ${addr eth0} ${alignr}${color1}Uptime:$color $uptime_short

${color1}CPU Usage:$color $cpu% ${cpubar}
${color1}RAM Usage:$color $mem/$memmax - $memperc% ${membar}
${color1}Swap Usage:$color $swap/$swapmax - $swapperc% ${swapbar}
$color$hr

${color0}File Systems:$color
/ $color${fs_used /}/${fs_size /} ${fs_bar /}
$color$hr
${color} Name             PID     CPU%   MEM%
${color0}Top CPU:$color
${color1} ${top name 1} ${top pid 1} ${color2}${top cpu 1}${color1} ${top mem 1}

${color1} ${top name 2} ${top pid 2} ${top cpu 2} ${top mem 2}
${color1} ${top name 3} ${top pid 3} ${top cpu 3} ${top mem 3}
${color1} ${top name 4} ${top pid 4} ${top cpu 4} ${top mem 4}
${color0}Top Mem:$color

${color1} ${top_mem name 1} ${top_mem pid 1} ${top_mem cpu 1} ${color2}${top_mem mem 1}
${color1} ${top_mem name 2} ${top_mem pid 2} ${top_mem cpu 2} ${top_mem mem 2}
${color1} ${top_mem name 3} ${top_mem pid 3} ${top_mem cpu 3} ${top_mem mem 3}
${color1} ${top_mem name 4} ${top_mem pid 4} ${top_mem cpu 4} ${top_mem mem 4}

$hr
${color0}Network Connections:$color ${tcp_portmon 1 65535 count}
$color Inbound Ports: ${tcp_portmon 1 32767 count}  Outbound Ports: ${tcp_portmon 32768 61000 count}
${color0}Outbound Connection ${alignr} Remote Service/Port${color1}
${tcp_portmon 32768 61000 rhost 0} ${alignr} ${tcp_portmon 32768 61000 rservice 0}
${tcp_portmon 32768 61000 rhost 1} ${alignr} ${tcp_portmon 32768 61000 rservice 1}
${tcp_portmon 32768 61000 rhost 2} ${alignr} ${tcp_portmon 32768 61000 rservice 2}
${tcp_portmon 32768 61000 rhost 3} ${alignr} ${tcp_portmon 32768 61000 rservice 3}
${tcp_portmon 32768 61000 rhost 4} ${alignr} ${tcp_portmon 32768 61000 rservice 4}

${color0}Inbound Connection ${alignr} Local Service/Port${color1}
${tcp_portmon 1 32767 rhost 0} ${alignr} ${tcp_portmon 1 32767 lservice 0}
${tcp_portmon 1 32767 rhost 1} ${alignr} ${tcp_portmon 1 32767 lservice 1}
${tcp_portmon 1 32767 rhost 2} ${alignr} ${tcp_portmon 1 32767 lservice 2}
${tcp_portmon 1 32767 rhost 3} ${alignr} ${tcp_portmon 1 32767 lservice 3}
${tcp_portmon 1 32767 rhost 4} ${alignr} ${tcp_portmon 1 32767 lservice 4}

$hr
${color0}TODO:${color1}
${execi 30 cat /home/username/Desktop/TODO.txt | fold -w40 }

Running Conky at Login

In order to enjoy the Conky configuration features described in the section above, you may also want to know how to run Conky automatically when you log in. To do so, you need to configure a new startup program for your Ubuntu session, which you can do by clicking System -> Preferences -> Sessions.

Sometimes Conky acts finicky if you start it up before your X session has had time to stabilized, so I have my Conky startup program call this shell script.

#!/bin/sh
sleep 30 && conky

Declarative Container Managed Authentication

2010-08-01T17:33:00.013-05:00

Motivation

For web applications that provide dynamic content tailored to individual users, authentication is an important concern. Authentication confirms that a user is, indeed, who they claim to be. As a result, (web) applications employ authentication to confirm the identities of users and protect privileged resources.

The Java Servlet specification supports declarative authentication, which eases the implementation of a web application's authentication strategy. By using declarative authentication, web developers simply declare that some or all of the application's resources are protected. Web developers are liberated from the burden of writing code that describes how those security constraints are enforced.

This tutorial provides a quick overview for web developers who want to take advantage of the Servlet specification's support of declarative authentication. The tutorial covers both container-agnostic elements of the web.xml file that support declarative authentication, as well as some authentication-related features of the Tomcat servlet container.

Securing Web Resources Declaratively

The web.xml file is the first stop on the way to adding declarative authentication to a web application. In that file, we'll want to declare what type of authentication should be used. By appropriately configuring a <login-config> element, we can tell the servlet container what query method should be used when authenticating users. Several options are available, though form-based authentication is the most common.

<login-config>
  <auth-method>FORM</auth-method>
  <form-login-config>
    <form-login-page>
      /WEB-INF/pages/login.jsp?info=login
    </form-login-page>
    <form-error-page>
      /WEB-INF/pages/login.jsp?info=login_failed
    </form-error-page>
  </form-login-config>
</login-config>

The <login-config> element above tells the servlet container how it should authenticate users for the related web application. Next we need to tell the servlet container which resources in the web application require that the user be authenticated.

<security-constraint>
  <web-resource-collection>
    <web-resource-name>Secured Resources</web-resource-name>
    <description>
      Only logged in users should be able to visit the 
      resources in this collection.
    </description>
    <url-pattern>/command/*</url-pattern>
  </web-resource-collection>
  <auth-constraint>
    <role-name>user</role-name>
  </auth-constraint>
  <user-data-constraint>
    <transport-guarantee>NONE</transport-guarantee>
  </user-data-constraint>
</security-constraint>

<security-role>
    <role-name>user</role-name>
</security-role>

The <security-constraint> element above provides a trivial example in which all URLs that map to the pattern "/command/*" are secured so that they may only be accessed by authenticated users in the "user" role.

Defining a JDBCRealm

All of the authentication-related configuration that we did above in the web.xml file is highly portable since that file will be packaged and deployed with our web application. Notice, however, that the configuration work we did in web.xml isn't sufficient by itself to support declarative authentication. Specifically, we've not yet told the Servlet container where and how to access the web application's list of valid users with related passwords.

This is where we have to delve into some container-specific details. By default, the Tomcat servlet container will attempt to authenticate by reading the user names and passwords defined in its $CATALINA_HOME/conf/tomcat-users.xml file. Obviously, this is not very convenient if we intend to use a relational database to store information about our web application's users.

Thankfully, it's easy to configure Tomcat to read from a relational database instead of the tomcat-users.xml file when authenticating users. To do so, we'll need to configure a new Realm, which is Tomcat's generic term for a collection of information about users.

<Realm 
    className="org.apache.catalina.realm.JDBCRealm"
    driverName="org.postgresql.Driver"
    connectionURL="jdbc:postgresql://localhost:5432/YourDatabaseName"
    connectionName="your_db_username" 
    connectionPassword="your_db_password"
    userTable="user_table_name" 
    userNameCol="user_name_column_name" 
    userCredCol="user_password_column_name"
    userRoleTable="uesr_role_table_name" 
    roleNameCol="role_name_column_name" />

The <Realm> element defined above tells Tomcat how it can use a relational database to authenticate users.

Configuring Web Application Context

In the section above we saw how to define a <Realm> element that instructs Tomcat to employ our relational database when authenticating users. One final consideration remains: where should we place that <Realm> definition? A single Tomcat server can host multiple web applications. Presumably each of those web applications may want to use a different database to authenticate its users. As a result, we should locate our <Realm> element within the <Context> element for our web application so that the Realm applies only to our web application.

A good way to include a <Realm> element within the web application's <Context> is to include a META-INF/context.xml file in our web application. By defining a <Realm> element within such a file, we can ensure that the application will use the appropriate relational database for authentication, regardless of which Tomcat server it is deployed to.

Granting Security Privileges

One final, useful note is that we may need to augment the security constraints for our application server if we want it to use an external relational database for user authentication. For the Tomcat Servlet container, we can add an entry to the $CATALINA_HOME/config/catalina.policy file.

grant {
    permission java.net.SocketPermission "localhost:5432", 
    "connect,resolve";
};

The above statement grants permission for any class in the servlet container to lookup and connect to our database, which runs on the localhost at port 5432.

Beware a slow death by regular expressions!

2010-08-01T14:08:00.036-05:00

Overview & Motivation

The Java programming language provides great support for regular expressions. In general, the performance of regular expressions in Java is very good. The trade-off for that excellent performance is a (somewhat) protracted API. To see what I mean, have a a look at a canonical regular expression example from Sun's javadoc:

Pattern p = Pattern.compile("a*b");
Matcher m = p.matcher("aaaaab");
boolean b = m.matches();

Kind of verbose, considering all we've accomplished is checking a single CharacterSequence for a match against one regular expression! Such complaints about decreased simplicity are likely what motivated Sun to provide some regular expression "convenience" methods inside the API for the String class. Specifically, as of version 6, the String API provides five such convenience methods:

public boolean matches(String regex);
public String replaceFirst(String regex, String replacement);
public String replaceAll(String regex, String replacement);
public String[] split(String regex);
public String[] split(String regex, int limit);

Each of the above convenience methods constructs and delegates the method call to Pattern and Matcher objects. What's not immediately obvious from the documentation for those convenience methods is that they become extremely inefficient as you execute them many thousands of times.

Reg. Exp. API Timing Data

Consider the following bit of code that illuminates the inefficiency of the String.matches(regex) method:

public class RegExpExerciser
{
 public static void main(String[] args)
 {

  int numTimes = 10000000;

  String regexp = "a*b";
  String toMatch = "aaaaab";

  long begin1 = System.currentTimeMillis();
  for (int i = 0; i < numTimes; i++)
  {
   toMatch.matches(regexp);
  }
  System.out.println(
   "Milliseconds using convenience method from String: " 
   + (System.currentTimeMillis() - begin1)
  );

  long begin2 = System.currentTimeMillis();
  Pattern p = Pattern.compile(regexp);
  for (int i = 0; i < numTimes; i++)
  {
   p.matcher(toMatch).matches();
  }
  System.out.println(
   "Milliseconds when re-using compiled reg. exp. pattern: " 
   + (System.currentTimeMillis() - begin2)
  );

 }
}

Executing the above code, my box reveals these times:

Milliseconds using convenience method from String: 5074
Milliseconds when re-using compiled reg. exp. pattern: 1720

RegExpHelper.java to the Rescue!

The code sample above clearly demonstrates that the time to compile a regular expression Pattern dominates the time required to actually check whether a given string matches the pattern. Utilizing that key insight, I offer a helper class in the Big-Oh Software Common library that provides simple APIs for working with regular expressions without sacrificing performance: RegExpHelper.java (javadoc). The key feature to note about that class is that it caches compiled regular expressions, making its methods both simple and efficient.

	Station 1	Station 2	..	Station n
line1	f/l	f/l	f/l	f/l
line2	f/l	f/l	f/l	f/l