Mercurial > Algorithms__Sedgewick
changeset 0:17ee997bf124
Initial commit
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Sat, 16 May 2015 12:02:55 -0500 |
parents | |
children | 5cc971338a2b |
files | .hgignore algs4-c++/1.1.14/lg.cpp algs4-c++/1.1.9/int_to_binary.cpp algs4-c++/BinarySearch/BinarySearch.cpp algs4/1.1.19/Fibonacci.java algs4/1.1.19/Fibonacci_Memoized.java algs4/1.1.20/LnFact.java algs4/BinarySearch/BinarySearch.java algs4/algs4-data.zip algs4/algs4.jar algs4/bin/drjava algs4/bin/java-algs4 algs4/bin/javac-algs4 algs4/drjava.jar algs4/hello/HelloWorld.java algs4/stdlib.jar |
diffstat | 16 files changed, 229 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/.hgignore Sat May 16 12:02:55 2015 -0500 1.3 @@ -0,0 +1,4 @@ 1.4 +algs4/algs4-data/.* 1.5 +algs4/algs4-code/.* 1.6 +.*~$ 1.7 +.*\.class$
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/algs4-c++/1.1.14/lg.cpp Sat May 16 12:02:55 2015 -0500 2.3 @@ -0,0 +1,21 @@ 2.4 +// Write a static method lg() that takes an int value N as argument and returns the largest int not larger than the base-2 logarithm of N. Do not use Math. 2.5 + 2.6 +// g++ lg.cpp -o lg 2.7 + 2.8 +#include <cmath> 2.9 +#include <climits> 2.10 +#include <iostream> 2.11 + 2.12 +int main( int argc, char **argv ) { 2.13 + 2.14 + while ( ! std::cin.eof() ) { 2.15 + int i; 2.16 + std::cin >> i; 2.17 + int lg = 0; 2.18 + while ( (1 << lg) <= i ) { 2.19 + lg++; 2.20 + } 2.21 + lg--; 2.22 + std::cout << "lg(" << i << ") >= " << lg << " actual value is " << log2(i) << std::endl; 2.23 + } 2.24 + }
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 3.2 +++ b/algs4-c++/1.1.9/int_to_binary.cpp Sat May 16 12:02:55 2015 -0500 3.3 @@ -0,0 +1,16 @@ 3.4 +// g++ int_to_binary.cpp int_to_binary 3.5 + 3.6 +#include <climits> 3.7 +#include <iostream> 3.8 + 3.9 +int main( int argc, char **argv ) { 3.10 + int num; 3.11 + while ( ! std::cin.eof() ) { 3.12 + std::cin >> num; 3.13 + 3.14 + for ( int i = (INT_MAX - INT_MAX/2); i > 0; i /= 2 ) { 3.15 + std::cout << ( ( num & i ) ? 1 : 0 ); 3.16 + } 3.17 + std::cout << std::endl; 3.18 + } 3.19 + }
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 4.2 +++ b/algs4-c++/BinarySearch/BinarySearch.cpp Sat May 16 12:02:55 2015 -0500 4.3 @@ -0,0 +1,58 @@ 4.4 +// g++ -D COMPILE_MAIN BinarySearch.cpp -o BinarySearch 4.5 + 4.6 +#include <algorithm> 4.7 +#include <fstream> 4.8 +#include <iostream> 4.9 +#include <vector> 4.10 + 4.11 +namespace BinarySearch { 4.12 + template <typename T> 4.13 + long rank( T key, std::vector<T> a ) { 4.14 + long lo = 0; 4.15 + long hi = a.size() - 1; 4.16 + while ( lo <= hi ) { 4.17 + long mid = lo + ( hi - lo ) /2 ; 4.18 + if ( a[mid] < key ) 4.19 + lo = mid + 1; 4.20 + else if ( a[mid] > key ) 4.21 + hi = mid - 1; 4.22 + else 4.23 + return mid; 4.24 + } 4.25 + return -1; 4.26 + } 4.27 + }; 4.28 + 4.29 +//////////////////////////////////////////////////////////////////////////////// 4.30 + 4.31 +#ifdef COMPILE_MAIN 4.32 + 4.33 +int main( int argc, char **argv ) { 4.34 + std::vector<int> whitelist; 4.35 + 4.36 + std::fstream whitelist_file( argv[1] ); 4.37 + while ( whitelist_file.good() ) { 4.38 + int i; 4.39 + whitelist_file >> i; 4.40 + whitelist.push_back(i); 4.41 + } 4.42 + whitelist_file.close(); 4.43 + 4.44 + std::sort( whitelist.begin(), whitelist.end() ); 4.45 + 4.46 + std::cout << "Sorted whitelist" << std::endl; 4.47 + for ( std::vector<int>::iterator it = whitelist.begin(); it < whitelist.end(); ++it ) { 4.48 + std::cout << *it << std::endl; 4.49 + } 4.50 + 4.51 + while ( ! std::cin.eof() ) { 4.52 + int key; 4.53 + std::cin >> key; 4.54 + if ( BinarySearch::rank( key, whitelist ) > -1 ) { 4.55 + std::cout << key << " is in the whitelist" << std::endl; 4.56 + } 4.57 + } 4.58 + 4.59 + } 4.60 + 4.61 +#endif
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 5.2 +++ b/algs4/1.1.19/Fibonacci.java Sat May 16 12:02:55 2015 -0500 5.3 @@ -0,0 +1,12 @@ 5.4 +public class Fibonacci { 5.5 + public static long F( int N ) { 5.6 + if ( N == 0 ) return 0; 5.7 + if ( N == 1 ) return 1; 5.8 + return F( N-1 ) + F( N-2 ); 5.9 + } 5.10 + 5.11 + public static void main( String[] args ) { 5.12 + for ( int N = 0; N < 100; N++ ) 5.13 + StdOut.println( N + " " + F(N) ); 5.14 + } 5.15 + } 5.16 \ No newline at end of file
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 6.2 +++ b/algs4/1.1.19/Fibonacci_Memoized.java Sat May 16 12:02:55 2015 -0500 6.3 @@ -0,0 +1,16 @@ 6.4 +public class Fibonacci_Memoized { 6.5 + static long[] fibs = new long[100]; 6.6 + 6.7 + public static long F( int N ) { 6.8 + if ( N == 0 ) return 0; 6.9 + if ( N == 1 ) return 1; 6.10 + if ( fibs[N] == 0 ) 6.11 + fibs[N] = F( N-1 ) + F( N-2 ); 6.12 + return fibs[N]; 6.13 + } 6.14 + 6.15 + public static void main( String[] args ) { 6.16 + for ( int N = 0; N < 100; N++ ) 6.17 + StdOut.println( N + " " + F(N) ); 6.18 + } 6.19 + } 6.20 \ No newline at end of file
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 7.2 +++ b/algs4/1.1.20/LnFact.java Sat May 16 12:02:55 2015 -0500 7.3 @@ -0,0 +1,25 @@ 7.4 +public class LnFact { 7.5 + public static double ln_fact ( int n ) { 7.6 + if ( n < 1 ) 7.7 + return -1; 7.8 + if ( n == 1 ) 7.9 + return 0; 7.10 + return Math.log( n ) + ln_fact( n - 1 ); 7.11 + } 7.12 + 7.13 + // public static double fact ( int n ) { 7.14 + // if ( n < 1 ) 7.15 + // return 0; 7.16 + // if ( n == 1 ) 7.17 + // return 1; 7.18 + // return n * fact( n - 1 ); 7.19 + // } 7.20 + 7.21 + public static void main( String[] args ) { 7.22 + while ( ! StdIn.isEmpty() ) { 7.23 + int n = StdIn.readInt(); 7.24 + StdOut.println( ln_fact( n ) ); 7.25 +// StdOut.println( Math.log( fact( n ) ) ); 7.26 + } 7.27 + } 7.28 + } 7.29 \ No newline at end of file
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 8.2 +++ b/algs4/BinarySearch/BinarySearch.java Sat May 16 12:02:55 2015 -0500 8.3 @@ -0,0 +1,31 @@ 8.4 +import java.util.Arrays; 8.5 + 8.6 +public class BinarySearch { 8.7 + public static int rank( int key, int[] a ) { 8.8 + int lo = 0; 8.9 + int hi = a.length - 1; 8.10 + while ( lo <= hi) { 8.11 + int mid = lo + ( hi - lo ) / 2; 8.12 + if ( key < a[mid] ) 8.13 + hi = mid - 1; 8.14 + else if ( key > a[mid] ) 8.15 + lo = mid + 1; 8.16 + else 8.17 + return mid; 8.18 + } 8.19 + return -1; 8.20 + } 8.21 + 8.22 + public static void main( String[] args ) { 8.23 + int[] whitelist = In.readInts( args[0] ); 8.24 + 8.25 + Arrays.sort( whitelist ); 8.26 + 8.27 + while ( ! StdIn.isEmpty() ) { 8.28 + int key = StdIn.readInt(); 8.29 + if ( rank( key, whitelist ) >= 0 ) 8.30 + StdOut.println( key ); 8.31 + } 8.32 + } 8.33 + 8.34 + } 8.35 \ No newline at end of file
9.1 Binary file algs4/algs4-data.zip has changed
10.1 Binary file algs4/algs4.jar has changed
11.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 11.2 +++ b/algs4/bin/drjava Sat May 16 12:02:55 2015 -0500 11.3 @@ -0,0 +1,9 @@ 11.4 +#!/bin/bash 11.5 + 11.6 +# ************************************************* 11.7 +# Wrapper for using DrJava 11.8 +# Last edited: September 18, 2011 11.9 +# ************************************************* 11.10 + 11.11 +jar=~/algs4/drjava.jar 11.12 +java -jar ${jar}
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 12.2 +++ b/algs4/bin/java-algs4 Sat May 16 12:02:55 2015 -0500 12.3 @@ -0,0 +1,16 @@ 12.4 +#!/bin/bash 12.5 + 12.6 +# ************************************************* 12.7 +# java-algs4 12.8 +# Hayk Martirosyan 12.9 +# ------------------- 12.10 +# Wrapper for java that includes algs4 libraries. 12.11 +# ************************************************* 12.12 + 12.13 +# This must match the install directory 12.14 +INSTALL=~/algs4 12.15 + 12.16 +# Sets the path to the classpath libraries 12.17 +jars=(.:${INSTALL}/stdlib.jar:${INSTALL}/algs4.jar) 12.18 + 12.19 +java -cp "$jars" "$@"
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 13.2 +++ b/algs4/bin/javac-algs4 Sat May 16 12:02:55 2015 -0500 13.3 @@ -0,0 +1,16 @@ 13.4 +#!/bin/bash 13.5 + 13.6 +# ************************************************* 13.7 +# javac-algs4 13.8 +# Hayk Martirosyan 13.9 +# ------------------- 13.10 +# Wrapper for javac that includes algs4 libraries. 13.11 +# ************************************************* 13.12 + 13.13 +# This must match the install directory 13.14 +INSTALL=~/algs4 13.15 + 13.16 +# Sets the path to the classpath libraries 13.17 +jars=(.:${INSTALL}/stdlib.jar:${INSTALL}/algs4.jar) 13.18 + 13.19 +javac -cp "$jars" -g -encoding UTF-8 "$@"
14.1 Binary file algs4/drjava.jar has changed
15.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 15.2 +++ b/algs4/hello/HelloWorld.java Sat May 16 12:02:55 2015 -0500 15.3 @@ -0,0 +1,5 @@ 15.4 +public class HelloWorld { 15.5 + public static void main(String[] args) { 15.6 + System.out.println("Hello, World"); 15.7 + } 15.8 + }
16.1 Binary file algs4/stdlib.jar has changed