Code Self Study Forum

Algorithms 1 (Coursera)

This thread is for anyone working through Algorithms 1 on Coursera. (textbook)

I set up Java last night and restarted the videos from the beginning. Here are some tips for anyone else who might be new to Java.

Java Quickstart

Here’s how I got Java running on my computer. (I’ve never really used it.)

I downloaded JDK for Java 13. Edit: it looks like the book recommends Java 8?
https://jdk.java.net/

Also the community edition of Intellij IDE. Edit: see below: I’m using a regular text editor now (vim).

I went through the “hello world” example below. It shows how to point Intellij at the JDK (above).

https://www.jetbrains.com/help/idea/creating-and-running-your-first-java-application.html#

The helper libraries for the course can be found here. When starting a new project in Intellij, go to File -> Project Structure in the menu. Then click “libraries” (shown below), the plus sign, and then navigate to where you downloaded the algs4 library. After that, the code from the course will work.

Intellij algs4 library

Week 1 Topics

  • Union-Find
  • Analysis of algorithms
  • Exercise: percolation
  • Interview questions based on the material
  • Lecture slides
  • He suggests reading chapters 1.4 and 1.5 in the textbook
1 Like

I’m writing my notes in markdown in a git repo. To add diagrams, I’m using Graphviz.

I put graphviz code like this into a filename.dot file:

digraph UnionFind1 {
    0;
    1;
    9 -> 2  [arrowhead=none];
    9 -> 4 -> 3  [arrowhead=none];
    6 -> 5 [arrowhead=none];
    7;
    8;
}

and then render it with:

$ dot -Tpng filename.dot -o filename.png

Here’s the rendered output from my notes:

graphviz

Graphviz also also works directly in the forum – you can wrap the code in [graphviz][/graphviz] tags and then copy the rendered image out of the forum editor into your notes. This is the same code above rendered in the forum’s post editor:

I’ve also started a section of the new site for a wiki, so that anyone can publish collaborative notes on data structures and algorithms. We can use graphviz (or similar) there as well.

3 Likes

Doing Union-Find thing.

1 Like

Here are some more tips for anyone who might have encountered these problems.

Edit: I just found that most of the information in this post is actually at the bottom of this page. I should have scrolled down below the list of programs.

Finding the Supplemental Files

I’m reading 1.4 and 1.5 in the textbook. I had trouble finding the 1Mints.txt file on the booksite. It isn’t on this page:
https://algs4.cs.princeton.edu/14analysis/

But it’s buried in that directory here:
https://algs4.cs.princeton.edu/14analysis/1Mints.txt

I found it by using an inurl:1Mints.txt query on Google. Then add the word “princeton” to the query to filter to the book site. (filter=0 stops Google from hiding some results, and num=100 shows 100 results per page.)

It looks like someone also posted a lot of the files here:

If anyone is interested in that problem, it’s on page 173 of the textbook. The goal is to write a program that reads through the list of 1 million integers and find triples that sum to 0. I’ll post his example of an inefficient solution below.

Running Java Code without an IDE

Intellij was too much for me to deal with. I finally figured out how to edit the Java code with vim. These instructions should work for any code editor, include vscode.

Create a text file, ThreeSum.java with the following contents (see p. 173 of the textbook). All I’ve added are the two import statements on the top. I’ll explain those after the code snippet.

// From the sample code, `In` and `StdOut` were not built-in, so I
// imported them from the book's library.
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

public class ThreeSum {
    public static int count(int[] a) {
        // count triples that sum to 0
        int n = a.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (a[i] + a[j] + a[k] == 0) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        int[] a = in.readAllInts();
        StdOut.println(count(a));
    }
}

I downloaded the course’s required algs4.jar file from this page and put it in a directory at ~/algs4/. Then I followed the idea from this post to add it to my CLASSPATH in my ~/.zshenv file. (It might be ~/.bashrc or ~/.bash_profile depending on your shell and OS. Leave a comment below if you don’t know which file to use.)

It looks like this in my .zshenv file:

export CLASSPATH=$HOME/algs4/algs4.jar:$CLASSPATH

Close the terminals and reopen them for the changes to take effect (or run source on the file to reload it: source ~/.zshenv).

Then the program should compile:

$ javac ThreeSum.java

A file named ThreeSum.class will be produced.

The program should then be runnable on the input file:

$ java ThreeSum ../data/1Mints.txt

I put the data directory above the directory that holds my Java code because I have other directories for solving the algorithm exercises in other languages. That command is being run from the java directory, and the data files are above that in data:

.
├── c_cpp
├── data
├── elixir
│   ├── lib
│   │   └── algorithms
│   └── test
├── images
│   └── union_find
├── java
├── javascript
│   ├── test
│   └── union_find
└── python

(I’m also using the Python book and the C/C++ Udemy course as resources.)

I’m not familiar with Java imports, and there might be a better way to do it, but this method works for now.

If anyone knows of better ways to do these things, leave a comment below. :slight_smile:

One of my biggest complaints against Java is the tooling’s complete dependence on IDEs. In any case, I’ll be building the projects with tried and tested make. I’d be happy to share the build files with anyone once I make them, probably tomorrow at the meetup.

1 Like

I got it working without an IDE. I can show you my setup tomorrow if you want. I’d be interested in seeing how you use make.

I’ve watched all the videos for week 1, and done part of the reading, but I haven’t done the coding exercises yet.

I’m also working on some other things like the new Code Self Study website and some C/C++ videos.

WRT the Algorithms class, I’m more or less where you are. Except setting up Java of course. Yeah, comparing build strategies could be interesting. My hope would be a “one and done” make good for all exercises w/o too much, if any, modifications.

1 Like