Foundations of Computer Science


 


Links: 

LINK

 SUMMARY

INTRODUCTION  
Graphs  

Graph Theory Information

Basic graph theory definitions and links to everything you could ever want to know about graph theory.  This includes: colorings, connectivity, cycle, degree, path, tournament, and trees.
Algorithms  
Data Structures and Algorithms This link covers the complexity and correctness of algorithms, and numerous algorithms.  Such as: searching, plane-sweep, greedy, divide-and-conquer, on-line, real-time, elimination, etc.
The Stony Brook Algorithm Repository This site is intended to serve as a comprehensive collection of algorithm implementations for over seventy of the most fundamental problems in combinatorial algorithms.
Remote Interactive Optimization Testbed Various algorithm applets, including: graph, vehicle routing, and maximum flow.
Graph Algorithm Java Applet Animated solvers for the following problems:  minimum spanning tree problem, shortest path problem, maximum flow problem, and minimum-cost flow problem.
Minimum Spanning Tree Applet Screen shots and directions on how to use applet.
Prim's Algorithm Java Applet Demo Java Applet Demo of Prim's Algorithm.
Kruskal's Algorithm Java Applet Demo Java Applet Demo of Kruskal's Algorithm.
Vehicle Routing Algorithms Applet  Screen shots and directions on how to use applet.
Dijkstra's Algorithm Java Applet Demo Java Applet Demo of Dijkstra's Algorithm.
Algorithmic Visualizations A series of java applets with some visualizations of data structures and algorithms that have been collected from the Web.  These include: Dijkstra's shortest path, AVL Tree, Binomial Heap, Network Flow, Huffman Code, TSP heuristics, sorting, etc.
Algorithm Animations Various java applets: sorting algorithms, searching algorithms, greedy algorithms, graph algorithms, and dynamic algorithms.
The Art Gallery Problem Introduction of the Art Gallery problem, the algorithm and its analysis, demo of the algorithm, related links, and references.
Convex Hull Algorithm Java Applet This applet demonstrates four algorithms (Incremental, Gift Wrap, Divide and Conquer, QuickHull) for computing the convex hull of points in three and two dimensions.
COMPLEXITY THEORY  
Complexity Classes (P, NP, PSPACE)  
NP-completeness (reductions, approximability)  
A compendium of NP optimization problems This is a continuously updated catalog of approximability results for NP optimization problems.
LINEAR PROGRAMMING  
Linear Programming: Foundations and Extensions Information on: the simplex method, duality, efficiency, optimization, interior-point method, matrix notation, convex analysis, and network flows.

Optimization, Problems and Examples  

Simplex Method  

Mathematical Programming

Kenji Ikeda's site that contains various applets used to demonstrate mathematical programming.

Simplex Method Java Applet

A java applet that will present a set of linear programming problems for you to solve.

Simplex Algorithm Java Applet Demo

Java Applet Demo of the Simplex Algorithm.

Linear Programming Applet

A Linear programming Java Applet.

Linear Programming in 2D Applet

A 2D Linear programming Java Applet.
Duality  
Interior Point Methods  
Nonlinear Programming FAQ Nonlinear programming frequently asked questions and their solutions. 
Solvers for linear programming problems Codes for solving linear programming problems.  Such as: Computational Number Theory, Matching, Non-linear Optimization.
Linear Programming FAQ Linear programming frequently asked questions and their solutions. 
INTEGER PROGRAMMING  
APPROXIMATION ALGORITHMS  
Travelling Salesman's Problem, Vertex Cover, etc.   

Traveling Salesman Applet

Screen shots and directions on how to use applet.
Innapproximability and the PCP Theorem  
CODING THEORY  
Linear and Binary Codes, Hamming metrics  
Matrix Techniques  
Data Compression (Huffman codes, Liv-Zempel Algorithms, etc.  
DCP Research Corp. Learn about how to compare compression methods, DCP Research Corp.'s GCA vs. Stac Electronics' LZS, DCP816 Data Sheet, DCP816 evaluation schematics and PAL equations for ISA bus interface, and DCP816 Principles of Operation.
Data Compression Reference Center Guide to basic facts, compression algorithms, hardware implementations, glossary, faq, and related links.

LZW Compression

A link to the background, concept, and algorithm of LZW Compression.  There is also a Java Applet to try.

Huffman Code Help Utility

A java applet that you can step through to demonstrate how the Huffman data compression code works.

Huffman Encoding Java Applet

A java applet that demonstrates how Huffman Encoding works.

CRYPTOGRAPHY

 
Secret and Public-key Cryptosystems (RSA Algorithm)  
Digital Signatures and Watermarks  
COMPUTATIONAL BIOLOGY  

BioComputing Resources

Set of tutorial texts for BioComputing and other related resources.

Links to Computational Biology

Links to courses taught in Computational Biology.  There is also a good set of links to other sites.
Java Biosequence Alignment Applet This applet demonstrates algorithms for pairwise alignment described in the book Durbin et al: Biological Sequence Analysis, Cambridge University Press 1998, chapter 2.
Alignment Applet Practical Sections on Pairwise Alignments: Alignment Applet.  The dynamic programming algorithm for the comparison of two sequences.
Pairwise sequence alignment applet dynAlign is a simple demo pairwise sequence alignment applet that uses the Needleman and Wunsch dynamic programming algorithm.
Sequence Alignments Various programs having to do with sequence alignments.
Alignment Sequence Applet An alignment sequence java applet.
Sequence Similarity and Alignment  
Phylogeny Trees  
APPLIED ALGORITHMS  
Facility location, scheduling, etc.  
Maximum Flow  
Maximum Flow Algorithms Applet Screen shots and directions on how to use applet.
Minimum-Maximum Cut Applet Screen shots and directions on how to use applet.
Max Flow/Min Cut Java Applet Java Applet Demo of Ford-Fulkerson's Algorithm.
Ford-Fulkerson's Algorithm Java Applet Demo Java Applet Demo of Ford-Fulkerson's Algorithm. (Non functional at this time).
On-line algorithms (paging, k-server, etc.)  
FACULTY RESEARCH SUMMARIES  
 


General Links:

LINK

SUMMARY

Algorithms in the real world Guide to basic facts, compression algorithms, hardware implementations, glossary, faq, and related links.
Great Theoretical Ideas in Computer Science Lecture slides and handouts.
The Collection of Computer Science Bibliographies This is a collection of bibliographies of scientific literature in computer science from various sources, covering most aspects of computer science.
   


Utilites:

UTILITY

SUMMARY

Ghostscript, Ghostview, and GSview Download Ghostscript software, an interpreter for the PostScript language and for PDF, and related software and documentation.