605.421.71 Foundations of Algorithms

Fall 2008

John E. Boon, Jr.

Lecturer, Johns Hopkins Engineering for Professionals (EP)

Johns Hopkins University

For all JHU-related matters contact Mr. Boon via email at jboonjr@apl.jhu.edu

NEWS ITEMS ( Wednesday, 07-Jan-2009 18:27:23 EST)

  1. Page updated [January 7, 2009]: Page mothballed. Files on the server have been removed with the exception of the syllabus..

Syllabus:

605.421.71 Foundations of Algorithms [September 22 revision to tentative course schedule page]

Times and Locations:

JHU Weather Related Closings/Emergency Notices: Check Today
  Time Room Building Campus
Class 4:30pm-7:10pm 211 A&R MCC
Office Hours TBD 2nd Floor Lounge A&R MCC

Text Book:

Introduction to Algorithms, Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

  1. McGraw-Hill, 2001 printing (ISBN: 0-07-013151-1)
  2. MIT Press, 2001 printing (ISBN: 0-262-03293-7)
  3. Errata information

6.046J/18.410J Introduction to Algorithms (SMA 5503) MITOPENCOURSEWARE, Fall 2005

Semester Lectures

  1. Lecture 01/02 - What is Algorithm Analysis?
    1. Turing Machines & Petri Nets
    2. The Paranoid Machine: Computing Beyond Turing by Peter Krieg, 10.01.2005, Telepolis.
    3. TestInsertionSort.java
    4. InsertionSort.java
    5. Data Input for TestInsertionSort
    6. RootFinder.java - Method of Golden Sections example
  2. No formal class meeting September 22 which would have been Lecture 03
  3. Lecture 04 - Mathematics for Algorithm Analysis (note -- when you access these notes they will have a file name indicating lecture 02. I did not repost the notes just to rename the file nor change the first page title of the notes)
    1. Summary of Asmyptotic Notations
    2. lgstar.java - example Java program for pages 55-56 lg*n
    3. lgstar.cpp - example C++ program for pages 55-56 lg*n
    4. Calculus Resources On-line
    5. Calculus resources at The Math Forum @ Drexel
    6. Karl's Calculus Tutor
    7. QuickMath automatic math solutions
  4. Lectures 05/06 - Recurrences
    1. Asymptotic Function Check Sheets in Excel
    2. Summary of Master Method
    3. Additional Master Method examples
  5. Lecture 07 - NP-Completeness and Approximation Algorithms
    1. Algorithms and Complexity by Herbert S. Wilf, (online book)
  6. Lecture 08 - Probabilistic Analysis, Randomized Algorithms, and Sorting
    1. LCM_Lattice.xls - analysis of Linear Congruential Method Pseudorandom Number Generators
    2. ARACNE Approximation and Randomized Algorithms in Communication NEtworks
    3. CPS 237 John H. Reif's course at Duke
    4. Marriage Problem
  7. Lecture 09 - Medians and Order Statistics
  8. Lecture 11 - Dynamic Programming and Greedy Algorithms
    1. Catalan Numbers:
      1. Catalan Number mathpage.wolfram.com
      2. Catalan Numbers Robert M. Dickau, on The Math Forum
    2. N-Queens Problem:
      1. N-Queens solution - from C Users Journal Obfuscated C Code competition, Nqueens.c and Nqueens.exe
      2. The International Obfuscated C Code Contest
      3. 8-Queens solution - from Horowitz and Sahni Text , 8queens.cpp and 8queens.exe
    3. Coin Change Problem:
      1. Shing and Kuo implemention of T.C. Hu algorithm, coin.pas, coin.exe, and coin.dat
    4. Job Scheduling Problem:
      1. Set Covering Algorithm, Prof. Donald Gross GWU, Jobsched.cpp, Jobsched.exe
      2. Set Covering Algorithm Data files:
        1. Job.dat
        2. Jobs1.dat
        3. Jobs2.dat
        4. Jobs3.dat

Semester Assignments

  1. PGM01 - Due September 15; String Matcher scans from text chapter 32.
  2. HW01 - Due September 22 (HOLD UNTIL CLASS SEPTEMBER 29)
  3. HW02 - Due October 6 (Revised Oct 1)
  4. HW03 - Due October 13 (Revised Oct 9)
  5. HW04 - Due October 20
  6. HW05 - Due November 17 (Note revised due date)(updated Nov 10)

Semester Support Files and Tools

  1. Research Links:
    1. The Sheridan Libraries of JHU
    2. CiteSeer.IST Scientific Literature Digital Library (reference source)
    3. Copernic Search Tool
    4. ingenta "The most comprehensive collection of academic and professional publications available for online, fax and Ariel delivery."
    5. ACM TechNews
  2. Programming Assignment-Related Items
    1. Java Links - Resources and tools for Java.
    2. C++ Links - Resources and tools for C++.
    3. Object-Oriented Analysis, Design, and Programming Links - Resources and tools for general object-oriented tasks.
    4. Program Support Links - Language-independent tools and resources.
  3. Citing Internet References
    1. Electronic Reference Formats Recommended by the American Psychological Association
    2. MLA Style: Orders for the style manual may be made at this site.
  4. Plagiarism: What It is and How to Recognize and Avoid It
  5. Postscript File Viewer: GSview for Windows.
  6. Note Format this Semester is Acrobat pdf: Get Acrobat Reader Link

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. The Fibonacci Association
    12. On-Line Encyclopedia of Integer Sequences
    13. random.org random number generator by Mads Haahr

Advanced Algorithm Links

  1. The Complexity Zoo
  2. Smoothed Analysis Links
    1. Daniel Spielman's and Shang-Hua Teng's papers on Smoothed Analysis
    2. Smoothed Analysis homepage
  3. Mathematical Programming Links
    1. Mathematical Programming Glossary, hosted INFORMS Computing Society
    2. CMU-IBM Cyberinfrastructure Collaborative site for MINLP, funded by the National Science Foundation, Grant OCI-0750826
  4. 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. Myths and Counterexamples in Mathematical Programming, Harvey Greenberg
    4. NEOS Server for Optimization
    5. Lindo Systems, Inc.
    6. GAMS and Demo version
  5. 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)
  6. 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
  7. 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
  8. Interactive Proof Links
    1. WinKE: A Proof Assistant for Teaching Logic
    2. LEGO Proof Assistant
  9. Deterministic Approaches Links
  10. 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]
  11. Randomized Algorithm Links
    1. ARACNE Approximation and Randomized Algorithms in Communication NEtworks
    2. CPS 237 John H. Reif's Randomized Algorithms course at Duke
  12. 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
  13. 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
    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)

JHU and Whiting School of Engineering Links

Johns Hopkins Portal | JHU IT Services | JHU Engineering for Professionals Course Home Pages | JHU Engineering for Professionals | JHU Whiting School of Engineering | JHUniverse | JHU Montgomery County Campus Home Page

Some Archival Course Information Links

[ Specific Class Information Home Pages | Part-Time Programs In Engineering and Applied Science Home Course Pages ]

John Boon's JHU Home Page

Page last updated Wednesday, 07-Jan-2009 18:27:23 EST.

There have been [TextCounter Fatal Error: Could Not Write to File _Notes_Boon_605421_index_shtml].

Valid HTML 4.01! Valid CSS! Quick Navigation Table

Copyright © 2008 John E. Boon, Jr.