Working through Sedgwick's Algorithms for Rubyists in Emacs

1. How to learn as little Java as Possible.
- 1.1. Motivation
2. Setup
3. Week 1
- 3.1. Union Find
  - 3.1.1. Dynamic Connectivity
  - 3.1.2. Modeling the Objects
- 3.2. Programing Assignments
4. How this was published
- 4.1. TODO Incorporate ./publish.el into this document

1 How to learn as little Java as Possible.

1.1 Motivation

Robert Sedgwick's textbook introduced a generation of students to the study of Algorithms. There are few better introductions. Unfortunately, he uses Java to teach his classes, but hopefully not so much Java that a Ruby programmer should be able to succeed in the class with a little advanced preparation.

2 Setup

First Problem: create and execute a java program with emacs.

2.1 Java from the course site

2.1.1 move algs4.jar to ~/usr/src/java

2.1.2 modify ~/bin/java[c]-algs4 to point to algs4.jar

2.2 Emacs

2.2.1 Eclim

After trying to get everything working with jdee-mode for a couple days, I found this great tutorial, and so I gave it up and tried eclim. Surprisingly, it wasn't so bad.

2.2.1.1 Install algs4 jar

Have to use Eclipse. The only way I found to do that is to leave a copy of algs4.jar in projectroot/lib, fire up Eclipse, the add by going to Properties > Java Build Path > Libraries

2.2.2 TODO XML

2.2.2.1 Install trang

Download
make small script in ~/usr/bin

2.2.3 Checkstyle

jdee expects the jar file in a very specific place. (.emacs.d/elisp/wherever_the_packages_installed/java/ et .c) I put it there until I can find a better location.

2.3 Maven

Originally, the motivation for using Maven 3 was because Jdee was so
tightly integrated with it, that it seemed easier to figure out Maven
than to figure out how to use Jdee without it.  However, at about the
same time as I figured out Maven, I also figured out that ecvim-mode
was the way to go. However, Maven seemed so useful as a
meta-framework, that I continued using it for this project.

Originaly, I tried setting up this project wiht Maven 3 because that seemed to be tightly integraged into

:CUSTOM_ID: setup-maven

2.3.1 Install: just copy to /opt and make some symlinks

2.3.2 Set up project

Using this book

2.3.2.1 mvn archetype:generate -DgroupID=org.momus.algorithms

2.3.2.2 mvn install –dowload deps, build project, run tests

2.3.2.3 Customize Project information.

2.3.2.4 Install the Algs4 libraries:

After inability to get Maven to include a simple algs4.jar file without wanting POMs and god-knows what, I found this method in Maven Central:

<dependency>
    <groupId>com.googlecode.princeton-java-algorithms</groupId>
    <artifactId>algorithms</artifactId>
    <version>4.0.1</version>
</dependency>

and now the statement `

2.3.2.5 Run your class with agruments:

mvn -X -e exec:java -Dexec.mainClass=org.momus.algorithms.EuclidsGCD -Dexec.args="340 1200"
-X adds logs of dubugging information.

2.3.2.6 mvn eclipse:eclipse

will make it into an Eclipse project for use with eclim

2.3.3 Running Projece code

:dir ~/repos/learnin/algorithms/ :exports both

mvn exec:java -Dexec.mainClass="org.momus.algorithms.HelloWorld" \
| grep -v INFO

mvn exec:java -Dexec.mainClass="org.momus.algorithms.EuclidsGCD" \
-Dexec.args="24 58" | grep -v INFO

2.4 Projectile

2.5 Checkstyle

2.5.1 using maven:

2.5.2 install jalopy plugin.

3 Week 1

3.1 Union Find

3.1.1 Dynamic Connectivity

Given a set of N objects:

Union Command: connets the two objects
Find/Connect Query: finds if path between objects exists

3.1.2 Modeling the Objects

"is connected to" is an equivalence relation¹:

reflexive: if p is connected to p
symmetric: if p is connected to q, then q is connected to p

3.2 Programing Assignments

mvn exec:java -Dexec.mainClass="org.momus.algorithms.HelloWorld" | grep -v INFO
mvn exec:java -Dexec.mainClass="org.momus.algorithms.EuclidsGCD"  -Dexec.args="24 58" | grep -v INFO

4 How this was published

4.1 TODO Incorporate ./publish.el into this document

Footnotes:

equivalence relation :: a binary relation that is at the same time a reflexive relation, a symmetric relation, and a transative relation.