Write a Java program that displays a tree structure. It should be possible to select individual nodes; when a node is selected, its name is displayed in a label. Make use of
Explain the key differences between Proxima and Eclipse in about 20 lines of text.
November 29 (extended to December 6)
Discuss the concept of dynamic programming, with special reference to whitespace distribution.
We discuss a sequence of instances of nfib.
Verify for yourself why the following function is extremely expensive.
nfib 1 = 1
nfib 2 = 1
nfib n = nfib (n-1) + nfib (n-2)
The Haskell libraries contain a function
memo :: (a -> b) -> a -> b
which suggests that it can be used to overcome the problem of rescusrive calls with the same argument.
Unfortunately, as the documentation explains, the function however does not work for integers, but essentially depends on pointer equality.
Using an array we can build our own memo function. We make now explicitly use of the fact that we know beforehand with which arguments the function will be called!
fib n = let index = (1,n)
fibs = index -> [(i,if i < 3 then 1 else fibs!(n-1) + (fibs!(n-2) )| i <- index]
in fibs ! n
Scheduling the computation
A little bit of reflection reveals that once we have constructed the value ot fib!i, we may forget the value at fib!j, where j < i-1, assuming of course that we are ultimately only interested in fib n. So we convert the demand driven algorithm (which is typical for such recurrent relations) into a data driven algorithm, in which we carefully organise the storage needed for memoising what we still need, and schedule the computation accordingly:
fib n = if n < 3 then 1
else loop (n-2) 1 1
where loop 0 prev last = last
loop n prev last = loop (n-1) last (prev+last)
Typical dynamic programming algorithms:
- are based on some recurrent relation
- which can be analysed for its recurring patterns
- leading to an explicit scheduling of the computation and use of memory
The recurrence relation in quite a few occasions occurs in some some optimisation problem, in which we memoize "best" solutions for subproblems.
Optimal Line Breaking
In TeX the algorithm that is used to split a paragraph into lines, is based on dynamic programming
, in which we memoise optimal solution for subproblems
of the original problem..
When looking for the paper describing the paragraph formatting problem, I stumbled upon:
For the assignment, in which you explain in your own words how this process takes place, you may want to provide an implementation of the formatting algorithm in Haskell (probably documenting it with lhs2TeX).
Use the PDE to create a simple plugin for Eclipse. Package it into a zip file ready for installation in the plugins directory.
In the paper "Notes on the Eclipse Plug-in Architecture" the file
- In Eclipse 3.1.*, the corresponding file is in a different directory. Where is it now?
- How does the file differ from the one in the paper? List the differences and explain their purpose.
- Explain how to open this file with Eclipse's Extension Point Schema Editor.
Modify the presentation sheet (
) of the Helium editor in such a way that the background color of an expression represents the nesting depth of that expression. Use color (255,255,255) for a depth of 0, color (223,223,223) for a depth of 1, color (191,191,191) for depth 2, etc. Here's an example:
haakjes = 1^(((2+3))*4)
To make the assignment a bit easier, I've put a slightly modified version of the presentation sheet in SVN, so make sure you do an update on
- The file
HeliumEditor/DocumentType.hs contains the document type definition for the Helium editor.
- You need to declare an attribute that represents the nesting depth. In order to handle the attribution over the generated parts of lists of expressions and list of alternatives (
[Alt]), add the following declarations:
ATTR List_Exp [ depth : Int | | ]
ATTR ConsList_Exp [ depth : Int | | ]
ATTR List_Alt [ depth : Int | | ]
ATTR ConsList_Alt [ depth : Int | | ]
SEM rules need to be specified for the depth attributes on these list data structures since the attribution is entirely handled by copy rules. You can have a look at
PresentationAG_Generated to see the exact AG datastructures that are generated for
Write an Eclipse plugin containing a variation on the
that, given a string, displays its suffix tree
Write an Eclipse plugin that provides an editor for *.wiki files. Syntax coloring should make the delimiters '|' red, boldface items (surrounded by '*') green, italic items (surrounded by '_') orange, monospaced items (surrounded by '=') purple, and hyperlinks (surrounded by double brackets) blue.
Autocompletion should function when a line is started with '---' and should offer the possibility to add one through six '+' signs. It should also function when a line is started with three spaces, and should then offer the possibility to add a '*' or '1' or 'A' or 'i' or '$'.