605.721.91 Design and Analysis of Algorithms

Spring 2008

John E. Boon, Jr.

Lecturer in the Engineering and Applied Science Programs for Professionals

Johns Hopkins University

NEWS ITEMS ( Saturday, 30-Aug-2008 13:12:47 EDT)

1. Page mothballed [August 20, 2008]: Page skeleton remains from Spring 2008 course offering at Dorsey Center. Syllabus posted is that for Spring 2008 for student reference. All other links to class material either inactive or not maintained until next class offering.

Spring 2008 syllabus:

Times and Locations:

Text Books:

• Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd Edition, Juraj Hromkovic, Springer, 2003 (Corrected 2nd printing 2004) (ISBN: 3-540-44134-4).
  • Text Web Site by Juraj Hromkovic
  • Juraj Hromkovic home page
  • Errata 2nd Edition   .ps   .pdf

Semester Lectures

1. Lectures 01/02 -- Fundamentals of Algorithms
   • Asymptotic Notation (backup materials for reference and class discussion)
   • Summary of Asmyptotic Notations
   • Asymptotic Function Check Sheets in Excel
   • Summary of Master Method
   • NP-Completeness (backup materials for reference and class discussion)
   • "Guarded Commands, Nondeterminacy and Formal Derivation of Programs", Edsger W. Dijkstra, Communications of the ACM, Vol 18, No 8, August 1975, pp 453- 457.
2. Lectures 03/04 -- Deterministic Approaches
   • 8-Queens solution - from Horowitz and Sahni Text , 8queens.cpp and 8queens.exe
   • Coin Change Problem:
     1. Shing and Kuo implemention of T.C. Hu algorithm, coin.pas, coin.exe, and coin.dat
   • Reproduction Curve
   • Lindo Systems, Inc.
   • GAMS and Demo version
   • Simple LP formulation for use in Excel
3. Lectures 05/07 -- Approximation Algorithms
   • Algorithm 4.2.1.3 Greedy Makespan Schedule and Graham's Approx Algorithm GMS.cpp and GMS.exe (compiled for DOS Window on Win32 machine)
   • 4232.cpp CPP code associated with Example 4.2.3.2
   • Ex4233p222.m demo for problem exercise
   • D.B. Shmoys. "Computing near-optimal solutions to combinatorial optimization problems". In: Combinatorial Optimization, (W. Cook, L. Lovasz, and P.D. Seymour, eds.) AMS, 1995, 355-397. (ORIE TR-1120) by David Shmoys, Cornell University.
   • 15-854 Approximation and Online Algorithms, Avrim Blum, CMU
   • Michel X. Goemans, MIT
   • Marco Cesati's Research Page [see unofficial Compendium of Parameterized Problems on this page]
   • Approximation Algs text and info by Vijay V. Vazirani, Georgia Tech
   • Interactive Proofs:
     1. The Logic Machine at Texas A&M University
     2. MetaMath Home Page
        • MetaMath Music Page mathematical proofs set to music
     3. The Logic Toolbox
     4. Logical System links
     5. GATEWAY TO LOGIC (JAVA APPLETS) C. Gottschall, Wien, Austria
     6. Isabelle
     7. Proof General Home Page
4. Lectures 08/10 - Randomized Algorithms
   • ARACNE Approximation and Randomized Algorithms in Communication NEtworks
   • CPS 237 John H. Reif's course at Duke
   • cryptography papers mentioned in class
   • one-way protocol papers
   • QuadResidue.xls
   • Algorithm 5.3.2.4 Quadratic Nonresidue
   • vertex cover example code
   • set cover example code archive
   • Markov Chain solution paper
   • minimal spanning tree algorithm by Yao
   • Mersenne Twister random number generator homepage
5. Lectures 10/12 - Simulated Annealing and Genetic Algoriths
   • See section on GA in General Algorithm Links section below
   • Simulated Annealing papers archive
   • Tabu Search papers archive
6. Lectures 13/14 - Problem Solving Approaches and New Technologies
   • Ant Algorithm paper
   • Quantum Computing papers archive
   • See section on DNA computing in General Algorithm Links section below
   • Marco Dorigo's homepage (ant colony optimization and ant algorithms) and his associated Ant Colony Optimization page
   • Centre for Quantum Computation, Oxford
   • Institute for Quantum Computing, Waterloo

Semester Assignments

1. Research Project
   1. "How to write a great research paper", Simon Peyton Jones, Microsoft Research, Cambridge
   2. "Collected Advice on Research and Writing", Mark Leone
2. HW01 - Due February 19
3. HW02 - Due February 26
4. HW03 - Due March 4
5. HW04 - Due March 18
6. HW05 - Due April 15
7. Exam - Due May 6
   1. Karger's paper

Semester Support Files and Tools

1. MATLAB tutorial/introduction
2. The Paranoid Machine: Computing Beyond Turing by Peter Krieg, 10.01.2005, Telepolis.
3. Calculus Resources On-line
4. Calculus resources at The Math Forum @ Drexel
5. Karl's Calculus Tutor
6. QuickMath automatic math solutions
7. Algorithms and Complexity by Herbert S. Wilf, (online book)
8. The Sheridan Libraries of JHU
9. NEC Research Institute (reference source)
10. Copernic Search Tool
11. ingenta "The most comprehensive collection of academic and professional publications available for online, fax and Ariel delivery."
12. ACM TechNews
13. Citing Internet References
    • Electronic Reference Formats Recommended by the American Psychological Association
    • MLA Style: Orders for the style manual may be made at this site.
14. Plagiarism: What It is and How to Recognize and Avoid It
15. Avoiding Plagiarism
16. Postscript File Viewer: GSview for Windows.
17. Note Format this Semester is Acrobat pdf:

Advanced Algorithm Links

1. Smoothed Analysis Links
   1. Daniel Spielman's and Shang-Hua Teng's papers on Smoothed Analysis
   2. Smoothed Analysis homepage
2. Linear Programming Links
   1. IOE 310 Introduction To Optimization Methods, Professor Katta G. Murty
   2. Linear Programming Frequently Asked Questions , Optimization Technology Center of Northwestern University and Argonne National Laboratory
   3. NEOS Server for Optimization
   4. Lindo Systems, Inc.
   5. GAMS and Demo version
3. NP Links
   1. A compendium of NP optimization problems, Editors: Pierluigi Crescenzi, piluc@dsi.unifi.it and Viggo Kann, viggo@nada.kth.se. Subeditors: Magnús Halldórsson (Graph Theory -- Covering and Partitioning, Subgraphs and Supergraphs, Sets and Partitions) Marek Karpinski (Graph Theory -- Vertex Ordering, Network Design -- Cuts and Connectivity) Gerhard Woeginger (Sequencing and Scheduling)
   2. The P vs NP Problem, A Millennium Prize Problem, Clay Mathematics Institute (Solution award $1 Million Dollars)
4. DNA Computing Links
   1. Laboratory for Molecular Science at USC
   2. Adleman's Homepage
   3. Molecular Computation of Solutions to Combinatorial Problems, Leonard M. Adleman, Science, vol. 266, November 11, 1994, page 1021.
   4. Computing with DNA, Leonard Adelman, Scientific American, August 1998.
   5. DNA Computing, Talk by James A. Foster
   6. Dan Boneh papers on DNA computing
5. Turing Machine Links
   1. The Church-Turing Thesis, Stanford Encyclopedia of Philosophy
   2. IV. Turing's Proof of the Unsolvability of the Halting Problem, from The Unknowable, G.J. Chaitin, IBM Research Division, T.J. Watson Research Center, Hawthorne, NY
6. Interactive Proof Links
   1. WinKE: A Proof Assistant for Teaching Logic
   2. LEGO Proof Assistant
7. Deterministic Approaches Links
8. Approximation Algorithm Links
   1. D.B. Shmoys. "Computing near-optimal solutions to combinatorial optimization problems". In: Combinatorial Optimization, (W. Cook, L. Lovasz, and P.D. Seymour, eds.) AMS, 1995, 355-397. (ORIE TR-1120) by David Shmoys, Cornell University.
   2. 15-854 Approximation and Online Algorithms, Avrim Blum, CMU
   3. Michel X. Goemans, MIT
   4. Marco Cesati's Research Page [see unofficial Compendium of Parameterized Problems on this page]
9. Randomized Algorithm Links
   1. ARACNE Approximation and Randomized Algorithms in Communication NEtworks
   2. CPS 237 John H. Reif's Randomized Algorithms course at Duke
10. Simulated Annealing Links
    1. Simulated Annealing, part of A Survey of Global Optimization Methods at Sandia National Laboratories
    2. Simulated Annealing & other Combinatorial Approximation Algorithms, USU Real-time, Embedded, and Concurrent Computing
    3. Parallel Simulated Annealing Library
11. Genetic Algorithms Links
    1. AAAI info on genetic algorithms
    2. Test FunctionsGenetic Algorithms (Evolutionary Algorithms): Repository of Test Functions
    3. The Genetic Programming Notebook
    4. Evolutionary Computation Repository maintained by the Jozef Stefan Institute
    5. IlliGAL Illinois Genetic Algorithms Laboratory
    6. GALib C++ Library of Genetic Algorithm Components
    7. Genetic Algorithms in Perl:
       1. Cultured Perl: Genetic algorithms applied with Perl
       2. OPEAL (Obvious Pearl Evolutionary Algorithm Library)

General Algorithm Links

1. General Algorithm Links
   1. Dictionary of Algorithms and Data Structures, NIST
   2. Abramowitz and Stegun: Handbook of Mathematical Functions on-line book
   3. The Stony Brook Algorithm Repository, Steven S. Skiena, Department of Computer Science, State University of New York
   4. Numerical Recipes Books on-line
   5. Perfectly Scientific, Inc.
   6. Maths Thesaurus, University of Cambridge
   7. Algorithms Courses on the WWW, maintained by Kirk Pruhs, Pitt
2. Algorithm Animation Links
   1. Zeus and Algorithm Animation DEC SRC-075 report
   2. Algorithm Animation GVU center at Georgia Tech
   3. JWAA Java and Web based Algorithm Animation
3. General Mathematics Links
   1. USC Lab For Molecular Science Links Institute of Standards and Technology (NIST)
   2. Digital Library of Mathematical Functions, National Institute of Standards and Technology (NIST)
   3. ResearchIndex, The NECI Scientific Literature Digital Library
   4. Very Large Data Base Endowment Inc., "(VLDB Endowment) is non-profit organisation incorporated in the United States for the sole purpose of promoting and exchanging scholarly work in databases and related fields throughout the world".
   5. arXiv.org e-Print archive, Cornell University Library Host
   6. Project Euclid, Cornell University Library Host
   7. The Math Forum, Internet Mathematics Library
   8. MATHEMATICSweb by Elseviermathematics
   9. MathTools.net hosted by The MathWorks
   10. Mathematical Constants by Steven Finch
   11. Mathsoft Mathematical Constants
   12. MathSoft Unsolved Problems
   13. The Fibonacci Association
   14. On-Line Encyclopedia of Integer Sequences
   15. random.org random number generator by Mads Haahr

JHU and Whiting School of Engineering Links

Page last updated Saturday, 30-Aug-2008 13:12:47 EDT.

There have been 00087 hits since August 30, 2008.

Quick Navigation Table

Copyright © 2008 John E. Boon, Jr.