Softpanorama |
||||||
Contents | Bulletin | Scripting in shell and Perl | Network troubleshooting | History | Humor |
[Aug 2, 2002] New Links
Journal of Graph Algorithms and Applications Biannual online Journal. Contains many interesting papers.
[Aug 1, 2002] Link updates
[June 7, 2002] Groups & Graphs
is a software package for graphs, digraphs, geometric configurations, combinatorial designs, and their automorphism groups. New in version 3.0 is support for torus maps. A new file structure allows the Mac and Windows versions to read and write the same files. Normalizer and centralizer subgroups can now be computed.
[June 7, 2002] Stas Busygin's NP-Completeness Page
About thirty years ago there was developed a conception designating a hierarchy of complexity classes for problems on finite sets. And so long as we use digital computers with finite memory storing discrete objects to resolve computational problems, it is relevant for any non-trivial algorithm designing. With the current state-of-the-art the most important complexity classes are P (problems solvable in polynomial time) and NP (problems whose solution certificate can be verified in polynomial time). As an example of a P problem we may take a sorting task for a list of numbers. Indeed, successively swapping any disordered pair we can accomplish the task within quadratic time, so the problem is certainly in P. And it is also in NP as when someone gives us another list asserting it is a sorted version of the first one, we can easily look through it to check the order and compare elements to verify are they the same as initial.
Obviously, all P problems are in NP, but is the inverse true... It is one of the most important theoretical problems today and anyone, who shows an ability to resolve it, will be able to get $1M prize from Clay Mathematics Institute.
The most fruitful result of the conception is that complexity classes have so-called complete problems within themselves. A problem of a class is complete if you can solve any other problem of this class in polynomial time having a polynomial time algorithm for the first one. Hence complete problems are hardest in their own classes and as they exist we may choose any of them to advance solving techniques for the entire class. The concept of complete problems for a class is generalized to hard problems for the class by inclusion of all other problems, whose polynomial time algorithm gives polynomial time solvability for the class. So, there are NP-complete and NP-hard problems.
[June 7, 2002] Collection of Lecture Notes, Survey Papers, etc currently maintained by Fedor V. Fomin (fomin@upb.de) . A lot of unique links, especially on graphs, including:
Robin Thomas: Tree-decompositions of Graphs
Jerry Spinrad: A draft of book on graph classes
[May 26, 2002] New and old e-books from FREE Computer and Internet Online Books Download Page
[May 24, 2002] Data Structures and Algorithms authors-titles recent submissions -- Nice archive from Cornell University. Among the papers:
cond-mat/0204181 [abs, pdf] :
Title: Local Search in Unstructured Networks
Authors: Lada A. Adamic, Rajan M. Lukose, Bernardo A. Huberman
Comments: 23 pages, 10 figures, a review of local search strategies in unstructured networks, a contribution to `Handbook of Graphs and Networks: From the Genome to the Internet', eds. S. Bornholdt and H.G. Schuster (Wiley-VCH, Berlin, 2002), to be published
Subj-class: Disordered Systems and Neural Networks; Statistical Mechanics; Networking and Internet Architecturecs.DS/0205050 [abs, ps, pdf, other] :
Title: A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees
Authors: S. Fekete, S. Khuller, M. Klemmstein, B. Raghavachari, Neal E. Young
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: Journal of Algorithms 24(2):310-324 (1997)cs.DS/0205048 [abs, ps, pdf, other] :
Title: Huffman Coding with Unequal Letter Costs
Authors: Mordecai Golin, Claire Kenyon, Neal E. Young
Subj-class: Data Structures and Algorithms
ACM-class: F.2.0; E.4; I.4.2
Journal-ref: ACM Symposium on Theory of Computing (2002)cs.DS/0205045 [abs, ps, pdf, other] :
Title: Balancing Minimum Spanning and Shortest Path Trees
Authors: Samir Khuller, Balaji Raghavachari, Neal E. Young
Comments: conference version: ACM-SIAM Symposium on Discrete Algorithms (1993)
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: Algorithmica 14(4):305-322 (1995)cs.DS/0205043 [abs, ps, pdf, other] :
Title: Low-Degree Spanning Trees of Small Weight
Authors: Samir Khuller, Balaji Raghavachari, Neal E. Young
Comments: conference version in Symposium on Theory of Computing (1994)
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: SIAM J. Computing 25(2):355-368 (1996)cs.DS/0205042 [abs, ps, pdf, other] :
Title: Orienting Graphs to Optimize Reachability
Authors: S. L. Hakimi, E. Schmeichel, Neal E. Young
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: Information Processing Letters 63:229-235 (1997)cs.DS/0205041 [abs, ps, pdf, other] :
Title: Faster Parametric Shortest Path and Minimum Balance Algorithms
Authors: Neal Young, Robert Tarjan, James Orlin
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2; G.1.6
Journal-ref: Networks 21(2):205-221 (1991)cs.DS/0205040 [abs, ps, pdf, other] :
Title: Approximating the Minimum Equivalent Digraph
Authors: Samir Khuller, Balaji Raghavachari, Neal E. Young
Comments: conference version in ACM-SIAM Symposium on Discrete Algorithms (1994)
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: SIAM J. Computing 24(4):859-872 (1995)cs.DS/0205045 [abs, ps, pdf, other] :
Title: Balancing Minimum Spanning and Shortest Path Trees
Authors: Samir Khuller, Balaji Raghavachari, Neal E. Young
Comments: conference version: ACM-SIAM Symposium on Discrete Algorithms (1993)
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: Algorithmica 14(4):305-322 (1995)cs.DS/0205043 [abs, ps, pdf, other] :
Title: Low-Degree Spanning Trees of Small Weight
Authors: Samir Khuller, Balaji Raghavachari, Neal E. Young
Comments: conference version in Symposium on Theory of Computing (1994)
Subj-class: Data Structures and Algorithms; Discrete Mathematics
ACM-class: F.2.2; G.2.2
Journal-ref: SIAM J. Computing 25(2):355-368 (1996)cs.DS/0205033 [abs, ps, pdf, other] :
Title: On-Line File Caching
Authors: Neal E. Young
Comments: ACM-SIAM Symposium on Discrete Algorithms (1998)
Subj-class: Data Structures and Algorithms; Computational Complexity; Networking and Internet Architecture
ACM-class: F.1.2, F.2.0, C.2.0
Journal-ref: Algorithmica 33:371-383 (2002)cs.DS/0205011 [abs, ps, pdf, other] :
Title: On Strongly Connected Digraphs with Bounded Cycle Length
Authors: Samir Khuller, Balaji Raghavachari, Neal Young
Subj-class: Data Structures and Algorithms; Computational Complexity
ACM-class: F.2.0; F.1.3
Journal-ref: Discrete Applied Mathematics 69(3):281-289 (1996)cs.DM/0111061 [abs, ps, pdf, other] :
Title: On a Special Case of the Generalized Neighbourhood Problem
Authors: V. Naidenko, Yu. Orlovich
Comments: 13 pages, 3 figures, in Russian
Subj-class: Discrete Mathematics
ACM-class: G.2.2cs.IR/0108018 [abs, ps, pdf, other] :
Title: Bipartite graph partitioning and data clustering
Authors: H. Zha, X. He, C. Ding, M. Gu, H. Simon
Comments: Proceedings of ACM CIKM 2001, the Tenth International Conference on Information and Knowledge Management, 2001
Subj-class: Information Retrieval; Learning
ACM-class: H.3.3; G.1.3; G.2.2cs.CC/0106048 [abs, pdf] :
Title: On some optimization problems for star-free graphs
Authors: V.G. Naidenko, Yu.L. Orlovich
Comments: 6 pages, in Russian
Subj-class: Computational Complexity; Discrete Mathematics
ACM-class: G.1.2; G.2.2cs.CC/0106045 [abs, ps, pdf, other] :
Title: A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
Authors: Andre Grosse, Joerg Rothe, Gerd Wechsung
Comments: 9 pages, appears in part in an ICTCS 2001 paper by the same authors
Subj-class: Computational Complexity
ACM-class: F.1.3; F.2.2cs.CC/0106041 [abs, ps, pdf, other] :
Title: Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones
Authors: André Grosse, Joerg Rothe, Gerd Wechsung
Comments: 12 pages, appears as part of a ICTCS 2001 paper of the same authors
Subj-class: Computational Complexity
ACM-class: F.1.3; F.2.2
[May 17, 2002] Data Structures in the Web - collection of links
[May 10, 2002] MST Java Project MST 1.0 Calculating a minimum spanning tree from a weighted, undirected graph. by Markus Svensson - Friday, May 10th 2002 06:44 EDT
About: MST is a very simple command line Java application for calculating a minimum spanning tree from a weighted, undirected graph. The graph is read from a standard ASCII text file. One possible minimum spanning tree is then printed to the console.
Download tar.gz archive
Download zip archive
Go To Links
Contact
[Mar 16, 2002] Data Structures and Algorithms Table of Contents a nice e-book by John Morris, 1998
[Mar 16, 2002] Pattern Matching Pointers. link [updated 02/18/2002]
[Feb 18, 2002] R010101 Do Programs Teach Algorithms by Dennis E. Hamilton
What is the relationship between algorithms and their implementations that is important to the mastery of computer programming? Is it foundational merely for computer science or does it inform the development of all successful computing practice? Is there a firm distinction or is it conceptual and qualitative?
Reviewing Sedgewick's approach leads me to explore the separateness of algorithms more closely. I conclude that writing down an algorithm in any form commits one to a framework, like it or not. Formalism is like that.
Even so, I maintain, differentiating statements of algorithms from programs is indispensable. Abstracting algorithms encourages students and practitioners to develop their ability to identify, operate with, and interpret levels of abstractions. It is at the heart of computing.
FAIR USE NOTICE This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available in our efforts to advance understanding of environmental, political, human rights, economic, democracy, scientific, and social justice issues, etc. We believe this constitutes a 'fair use' of any such copyrighted material as provided for in section 107 of the US Copyright Law. In accordance with Title 17 U.S.C. Section 107, the material on this site is distributed without profit exclusivly for research and educational purposes. If you wish to use copyrighted material from this site for purposes of your own that go beyond 'fair use', you must obtain permission from the copyright owner.
ABUSE: IPs or network segments from which we detect a stream of probes might be blocked for no less then 90 days. Multiple types of probes increase this period.
Society
Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers : Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism : The Iron Law of Oligarchy : Libertarian Philosophy
Quotes
War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda : SE quotes : Language Design and Programming Quotes : Random IT-related quotes : Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce : Bernard Shaw : Mark Twain Quotes
Bulletin:
Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 : Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law
History:
Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds : Larry Wall : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS : Programming Languages History : PL/1 : Simula 67 : C : History of GCC development : Scripting Languages : Perl history : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history
Classic books:
The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month : How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite
Most popular humor pages:
Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor
Copyright © 1996-2016 by Dr. Nikolai Bezroukov. www.softpanorama.org was created as a service to the UN Sustainable Development Networking Programme (SDNP) in the author free time. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License.
The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.
Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.
FAIR USE NOTICE This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available to advance understanding of computer science, IT technology, economic, scientific, and social issues. We believe this constitutes a 'fair use' of any such copyrighted material as provided by section 107 of the US Copyright Law according to which such material can be distributed without profit exclusively for research and educational purposes.
This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...
You can use PayPal to make a contribution, supporting development of this site and speed up access. In case softpanorama.org is down you can use the at softpanorama.info |
Disclaimer:
The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the author present and former employers, SDNP or any other organization the author may be associated with. We do not warrant the correctness of the information provided or its fitness for any purpose.
Last updated: July 07, 2013