Java Programming

Java program – Shortest-paths client

April 29, 2011

public class PathFinder { // prev[v] = previous vertex on shortest path from s to v // dist[v] = length of shortest path from s to v private ST<String, String> prev = new ST<String, String>(); private ST<String, Integer> dist = new ST<String, Integer>(); // run BFS in graph G from given source vertex s public [...]

Read the full article →

Java program – Using a graph to invert an index

April 29, 2011

public class IndexGraph { public static void main(String[] args) { // read in the graph from a file In in = new In(args[0]); String delimiter = args[1]; Graph G = new Graph(in, delimiter); // read a vertex and print its neighbors while (!StdIn.isEmpty()) { String v = StdIn.readLine(); for (String w : G.adjacentTo(v)) { StdOut.println(” [...]

Read the full article →

Java program – Graph data type

April 29, 2011

/** * The <tt>Graph</tt> class represents an undirected graph of vertices * named 0 through V-1. * It supports the following operations: add an edge to the graph, * iterate over all of the neighbors adjacent to a vertex. * Parallel edges and self-loops are permitted. * <p> * For additional documentation, see <a href=”http://algs4.cs.princeton.edu/51undirected”>Section [...]

Read the full article →

Java program – Dedup filter

April 29, 2011

public class DeDup { public static void main(String[] args) { SET<String> distinct = new SET<String>(); while (!StdIn.isEmpty()) { String key = StdIn.readString(); if (!distinct.contains(key)) { distinct.add(key); StdOut.println(key); } } } } /************************************************************************* * Execution: java DeDup < words.txt * Dependencies: SET.java StdIn.java * * Read in a list of words from standard input and print [...]

Read the full article →

Java program – BST symbol table

April 29, 2011

public class BST<Key extends Comparable<Key>, Value> { private Node root; // root of BST private class Node { private Key key; // sorted by key private Value val; // associated data private Node left, right; // left and right subtrees private int N; // number of nodes in subtree public Node(Key key, Value val, int [...]

Read the full article →

Java program – Load balancing simulation

April 29, 2011

public class LoadBalance { public static void main(String[] args) { int M = Integer.parseInt(args[0]); int N = Integer.parseInt(args[1]); int S = Integer.parseInt(args[2]); // Create server queues. RandomQueue<Queue<Integer>> servers = new RandomQueue<Queue<Integer>>(); for (int i = 0; i < M; i++) { servers.enqueue(new Queue<Integer>()); } // Assign an item to a server for (int j = [...]

Read the full article →

Java program – M/D/1 queue simulation

April 29, 2011

public class MD1Queue { public static void main(String[] args) { double lambda = Double.parseDouble(args[0]); // arrival rate double mu = Double.parseDouble(args[1]); // service rate Histogram hist = new Histogram(60 + 1); Queue<Double> queue = new Queue<Double>(); StdDraw.setCanvasSize(700, 500); double nextArrival = StdRandom.exp(lambda); // time of next arrival double nextService = nextArrival + 1/mu; // time [...]

Read the full article →

Java program – Generic FIFO queue (linked list)

April 29, 2011

import java.util.Iterator; import java.util.NoSuchElementException; /** * The <tt>Queue</tt> class represents a first-in-first-out (FIFO) * queue of generic items. * It supports the usual <em>enqueue</em> and <em>dequeue</em> * operations, along with methods for peeking at the top item, * testing if the queue is empty, and iterating through * the items in FIFO order. * <p> [...]

Read the full article →

Java program – Expression evaluation

April 29, 2011

public class Evaluate { public static void main(String[] args) { Stack<String> ops = new Stack<String>(); Stack<Double> vals = new Stack<Double>(); while (!StdIn.isEmpty()) { String s = StdIn.readString(); if (s.equals(“(“)) ; else if (s.equals(“+”)) ops.push(s); else if (s.equals(“-”)) ops.push(s); else if (s.equals(“*”)) ops.push(s); else if (s.equals(“/”)) ops.push(s); else if (s.equals(“sqrt”)) ops.push(s); else if (s.equals(“)”)) { String [...]

Read the full article →

Java program – Generic stack

April 29, 2011

import java.util.Iterator; import java.util.NoSuchElementException; /** * The <tt>Stack</tt> class represents a last-in-first-out (LIFO) stack of generic items. * It supports the usual <em>push</em> and <em>pop</em> operations, along with methods * for peeking at the top item, testing if the stack is empty, and iterating through * the items in LIFO order. * <p> * All [...]

Read the full article →

Java program – Stack of strings (array doubling)

April 29, 2011

public class DoublingStackOfStrings { private String[] a; private int N; public DoublingStackOfStrings() { a = new String[2]; N = 0; } // is the stack empty? public boolean isEmpty() { return (N == 0); } // resize the underlying array holding the elements private void resize(int capacity) { String[] temp = new String[capacity]; for (int [...]

Read the full article →

Java program – Stack of strings (linked list)

April 29, 2011

public class LinkedStackOfStrings { private int N; // size of the stack private Node first; // top of stack // helper Node class private class Node { private String item; private Node next; } // is the stack empty? public boolean isEmpty() { return first == null; } // number of elements on the stack [...]

Read the full article →

Java program – Stack of strings (array)

April 29, 2011

import java.util.Iterator; public class ArrayStackOfStrings implements Iterable<String> { private String[] a; // holds the items private int N; // number of items in stack public ArrayStackOfStrings(int max) { a = new String[max]; } public boolean isEmpty() { return (N == 0); } public void push(String item) { a[N++] = item; } public String pop() { [...]

Read the full article →

Java program – Longest repeated substring

April 29, 2011

import java.util.Arrays; public class LRS { // return the longest common prefix of s and t public static String lcp(String s, String t) { int n = Math.min(s.length(), t.length()); for (int i = 0; i < n; i++) { if (s.charAt(i) != t.charAt(i)) return s.substring(0, i); } return s.substring(0, n); } // return the longest [...]

Read the full article →

Java program – Frequency counts

April 29, 2011

public class FrequencyCount { public static void main(String[] args) { // read in the words as an array String s = StdIn.readAll(); // s = s.toLowerCase(); // s = s.replaceAll(“[\",!.:;?()']“, “”); String[] words = s.split(“\\s+”); // sort the words Merge.sort(words); // tabulate frequencies of each word Counter[] zipf = new Counter[words.length]; int M = 0; [...]

Read the full article →

Java program – Mergesort

April 29, 2011

public class Merge { public static void sort(Comparable[] a) { sort(a, 0, a.length); } // Sort a[lo, hi). public static void sort(Comparable[] a, int lo, int hi) { int N = hi – lo; // number of elements to sort // 0- or 1-element file, so we’re done if (N <= 1) return; // recursively [...]

Related Posts Plugin for WordPress, Blogger...
Read the full article →

← Previous Entries