Archive for the 'computer science' category

Is computer science baseless?

Mar 31 2010 Published by under computer science, education

From the April Communications of the ACM, the Kode Vicious column is on The Data-Structure Canon.

The reader question is:

In most areas of science there are a few basic underlying laws that inform the rest of the study of a given subject. Physics, chemistry, and electrical engineering all have these basic equations. What are the basic equations in computer science? Or is computer science baseless?

In other words, what's the fundamental intellectual basis of computer science? Well, according to KV, it's data structures!

If there were any set of basics that I wanted to hammer into software engineers and programmers, it would be the basic data structures, their features and pitfalls. ...

The basic data structures are the array, list, tree, and hash table. That seems like a short list, and I'm sure some of the more experienced readers of this column are warming up their mail applications to write me nasty notes about how there are more basic data structures than just these four. To these people I say, "Go for it!"

What I find most interesting about this list is how many programmers take it for granted and how few of them understand the implications of using one data structure versus another. Try as I might, I cannot lay all the blame at the feet of the programmers using these data structures; a good deal of the blame has to go to their teachers and the legions of poorly written "how to program" books that emphasize how to use a data structure rather than the underlying implications of what happens when they are used. Abstraction is a fine thing-it makes understanding large systems easier--but it also can obscure important facts: in particular, the performance implications of certain choices.


Given the different complexities I've just mentioned, I think you'll see that these four data structures, which form the basis of most computer programs, are worth studying time and again. A good place to start is Knuth's The Art of Computer Programming, Volume 1, Chapter 2, which covers all of these subjects more seriously and in depth. When you're done reading all that he has to say, please write me, though I should be retired by then.

Interesting. Although he probably conflates computer science with programming a little too much for my taste, I'm probably mostly in agreement with KV's point of view. But I was wondering what all of you out there in Computer Science Land think?

23 responses so far

Ada Lovelace Day: Jane of See Jane Compute

Wednesday was Ada Lovelace Day!

Ada Lovelace Day is an international day of blogging to celebrate the achievements of women in technology and science.

The first Ada Lovelace Day was held on 24th march 2009 and was a huge success. It attracted nearly 2000 signatories to the pledge and 2000 more people who signed up on Facebook. Over 1200 people added their post URL to the Ada Lovelace Day 2009 mash-up. The day itself was covered by BBC News Channel,, Radio 5 Live, The Guardian, The Telegraph, The Metro, Computer Weekly, and VNUnet, as well as hundreds of blogs worldwide.

In 2010 Ada Lovelace Day will again be held on 24th March and the target is to get 3072 people to sign the pledge and blog about their tech heroine.

Ada Lovelace Day is organised by Suw Charman-Anderson, with design and development support from TechnoPhobia and hosting from UKHost4U.

I encourage you to check out the rather extensive list of posts celebrating women in science and technology. It's truly inspiring.

A couple of days late (as usual) I'd like to add a name to the list of women deserving of a bit of celebration: Jane of the sadly departed blog See Jane Compute (and here for deeper archives).

Way back in 2005 or so, See Jane Compute was the first science blog I started following regularly. Her keen insights into the world of computing was what first drew me in, but it was the warmth and personality of the blog that kept me coming back. I'd done a computing degree myself way back in the 1980s and I saw a lot of what I went through as a student mirrored oddly through her experiences as a prof.

Also, as a callow youth way back then, I don't think I realized the challenges that the women in my program faced just being there, and that's something that Jane's writing really brought home to me, hopefully making me much more aware and sensitive now.

Over time, we also became blog buddies. It was always a thrill to see Jane's name pop up in the comments because I knew that someone who cared about the computing field and the people in it was contributing.

Jane also let us all into her life, let us experience the ups and downs of academia, of being a woman in computing, of everyday life. As all friends are, I was thrilled and happy when Baby Jane came along bringing great joy to the Jane household. I was also dismayed by some of the ups and downs of academic life and the weird tenure process.

Unfortunately, Jane's voice is mostly silent now -- I'm happy to report that she does still show up in the comments occasionally (here, for example). I'll also have a small little regret -- See Jane Compute closed down on Science Blogs on May 5, 2009 while I joined only a couple of weeks later, on May 18. Longtime blog friends, we missed being blog siblings by only a whisker.

So, slightly late Happy Ada Lovelace Day! And take a minute to go read some terrific insights by one of the great women technology bloggers here and here. And check out the interview I did with her on my old blog.

One response so far

Are Computing journals too slow?

Continuing the ongoing discussion about the publication habits of computing researchers that I've recently blogged about:

This time around, we have Moshe Vardi Revisiting the Publication Culture in Computing Research in the latest Communications of the ACM.

The May 2009 editorial and the August 2009 column attracted a lot of attention in the blogosphere. The reaction has been mostly sympathetic to the point of view reflected in both pieces. For example, Jeanette Wing asked in her blog: "How can we break the cycle of deadline-driven research?", and Filippo Menczer, in a Letter to the Editor published in the November 2009 issue, said: "I propose the abolition of conference proceedings altogether."

Not everyone, however, agreed with this point of view. For example, in another Letter to the Editor from the November 2009 issue, Jano van Hemert said: "For CS to grow up, CS journals must grow up first." Mr. van Hemert's issue with computing-research journals is that they are known to have "slow turnaround, with most taking at least a year to make a publish/reject decision and some taking much longer before publishing." Such end-to-end times, he argued, "are unheard of in other fields where journal editors make decisions in weeks, sometimes days."


What is the reason for the unacceptably slow turnaround time in computing-research journals? When considering this question, one must factor the problem into two separate issues: time from submission to editorial decision, and time from positive editorial decision to publication.


Let us now consider the editorial process in computing-research journals. Why is it soooo slow? Consider who is in charge of that process. It is not the publishers; it is the editors and referees. In other words, it is us. The process is slow because that is the way we run it. If we want it changed, it is up to us to change it! I suspect that we cannot separate our conference-focused publication culture from our sluggish journal editorial process. Conferences have sharp deadlines, journals do not. We simply do not take our roles as editors and referees as seriously as we do as program committee members because we do not take journals as seriously as other fields. If we, as a community, decide that we need to shift from conference-based publication to journal-based publication, we definitely must address the slow editorial process, but we should not complain about "them journals." We have found the enemy, and it is us! (emphasis added -JD)

Now, I'm not going to comment on whether or not reviewers or editors take to long to do their job, or whether or not computing should be a journal-based or a conference-based field. I'm not even going to comment on whether or not those two things are related.

On the contrary, I'd like to see the "problem" of "slow journals" as an opportunity to talk about disruptive change in scholarly publishing. Here we are in the most disruptive age imaginable for scholarly communications, here we are talking about computing -- and yet it all comes down to time lines for peer review.

What's the real opportunity?

Perhaps the opportunity isn't to ask, "Are Computing journals too slow?" but to ask, "What do Computing scholars really need?"

What really interests me is the potential for the transformation of a disciplinary scholarly communications culture, the opportunity to start from scratch and build something that makes sense for all the stakeholders, not just entrenched interests, commercial forces and historical entitlements.

Realistically speaking, the incredible weight of history and cultural inertia probably make total transformation impossible in any kind of short or medium term. Societies aren't going away, journals aren't going away, scholarly conferences aren't going away. Even monographs aren't going away.

A couple of things do strike me, though.

Some questions:

  • If I was a computing person and I was going to start over with the whole scholarly communications apparatus, would I even bother with journals or conference proceedings at all?
  • Oh sure, I would still have conferences but mostly in resort cities with good bars and interesting museums and other tourist attractions. In other words, places that will stimulate interaction, investigation and collaboration, not more PowerPoint.
  • But seriously, in terms of actually communicating scientific or technical ideas in a structured, systematic and repeatable format, I probably need something like the arxiv.
  • The objects that would get deposited could include experimental narratives (ie. papers & reports, potentially with accompanying audio or video), code, data, presentations (slides and/or A/V), monograph-length material
  • I would also allow stuff that isn't research-based like informal presentations, course materials including syllabi, problem sets and other stuff.
  • Since we value peer review, I would probably do a few things.
    • Organize something like what PLoS ONE does for research-based materials, to make sure everything represents legitimate research output.
    • I would consider making all the reviewers' comments openly available, possibly even signed
    • Bolt on something like Friendfeed to aggregate commentary and discussion around the objects
    • I would also bolt on the kind of object-level metrics that PLoS is using.
  • Who pays? Again, I would use the PLoS model with author fees picking up production costs and organizing reviewing. The kinds of models that arxiv and SCOAP3 are exploring are also potentially viable.
  • None of this precludes the continued existence of a non-scholarly, general interest venue like the Communications of the ACM.

What am I missing? Is this too Utopian? How do you reboot a whole scholarly culture?

Perhaps even more interesting a question for us -- what's the library's role in the post-stuff collections age? Preservation, co-ordination, training, facilitating collaboration?

(Re: My Job in 10 Years book project: This is potentially an extract from the chapter on scholarly communications.)

One response so far

IT Professional on strategic planning

The latest issue of IT Professional (v11i6) has some interesting articles on strategic planning for IT organizations.

2 responses so far

Computing: the fourth great domain of science

Oct 27 2009 Published by under computer science, culture of science, engineering

The September Communications of the ACM has a provocative article by Peter J. Denning and Paul S. Rosenbloom, Computing: the fourth great domain of science (OA version). It's well written and persuasive, certainly worth reading the whole thing.

Science has a long-standing tradition of grouping fields into three categories: the physical, life, and social sciences. The physical sciences focus on physical phenomena, especially materials, energy, electromagnetism, gravity, motion, and quantum effects. The life sciences focus on living things, especially species, metabolism, reproduction, and evolution. The social sciences focus on human behavior, mind, economic, and social interactions. We use the term "great domains of science" for these categories.


The core phenomena of the computing sciences domain--computation, communication, coordination, recollection, automation, evaluation, and design--apply universally, whether in the artificial information processes generated by computers or in the natural information processes found in the other domains. Thus, information processes in quantum physics, materials science, chemistry, biology, genetics, business, organizations, economics, psychology, and mind are all subject to the same space and time limitations predicted by universal Turing machines. That fact underpins many of the interactions between computing and the other fields and underlies the recent claim that computing is a science of both the natural and the artificial.


Computing is pervasive because it is a fundamental way of approaching the world that helps understand its own crucial questions while also assisting other domains advance their understandings of the world. Understanding computing as a great domain of science will help to achieve better explanations of computing, increase the attraction of the field to newcomers, and demonstrate parity with other fields of science.

To say that computing is a domain of science does not conflict with computing's status as a field of engineering or even mathematics. Computing has large slices that qualify as science, engineering, and mathematics. No one of those slices tells the whole story of the field.

The exercise of examining computing as a domain of science reveals that the extent of computing's reach and influence cannot be seen without a map that explicitly displays the modes of implementation and interaction. It also reveals that we need to revisit deep questions in computing because our standard answers, developed for computer scientists, do not apply to other fields of science. Finally, it confirms that computing principles are distinct from the principles of the other domains.

So, what do you think? Is computing the fourth great domain of science?

5 responses so far

IT Professional on Ontologies, OWL, and the Semantic Web

The IEEE Computer Society's magazine IT Professional has a special issue on Ontologies, OWL, and the Semantic Web (v11i5). There's lots of very cool-looking stuff, mostly pretty basic.

A couple of other non-semantic web articles that look worth checking out:

No responses yet

Time for computer science to grow up?

That's the question asked by Lance Fortnow in a recent Communications of the ACM Viewpoint article (free fulltext).

Fortnow's article continues a discussion about scholarly communication patterns in computer science that's been going on for a while in the "pages" of the CACM. I've blogged about it a couple of times here and here.

Fortnow's main idea is that CS needs to get past the youthful stage of using conferences as the main vehicle for disseminating new ideas and move to a journal-based model, like most of the rest of scientific disciplines. In the end, it's all about peer review:

Unlike every other academic field, computer science uses conferences rather than journals as the main publication venue. While this made sense for a young discipline, our field has matured and the conference model has fractured the discipline and skewered it toward short-term, deadline-driven research. Computer science should refocus the conference system on its primary purpose of bringing researchers together. We should use archive sites as the main method of quick paper dissemination and the journal system as the vehicle for advancing researchers' reputations.


But even worse, the focus on using conferences to rate papers has led to a great growth in the number of meetings. Most researchers don't have the time and/or money to travel to conferences where they do not have a paper. This greatly affects the other roles, as conferences no longer bring the community together and thus we are only disseminating, networking, and discussing with a tiny subset of the community. Other academic fields leave rating papers and researchers to academic journals, where one can have a more lengthy and detailed reviews of submissions. This leaves conferences to act as a broad forum and bring their communities together.


Our conference system forces researchers to focus too heavily on quick, technical, and safe papers instead of considering broader and newer ideas. Meanwhile, we have devoted much of our time and money to conferences where we can present our research that we can rarely attend conferences and workshops to work and socialize with our colleagues.

Computer science has grown to become a mature field where no major university can survive without a strong CS department. It is time for computer science to grow up and publish in a way that represents the major discipline it has become.

Check out the comments on the original post as well as at Fortnow's blog. He's also collected various blog reactions here.

I find it interesting that the CS community, surely among the most "online" of all the scholarly disciplines, is reaffirming the value of strong peer review. More interesting, perhaps, is the way Fortnow distinguishes between speedy initial publications in archives combined with slower, more deliberate peer review before something later appears in a journal. Which is sort of like what's happening in various physics communities with arxiv and later journal publication.

However, I'm not convinced that you need a "journal" to have peer review, that it can't be embedded as another layer in whatever kind of fast-track publication system ends up being used.

If the CS community decides to go in this direction, it would be an amazing opportunity to rebuild their corner scholarly publishing from the ground up, to decide on what they truly value. Some ideas:

  • fast and efficient to dissemination of findings
  • combining data, code, narrative and other pieces into one scholarly object
  • a layering of traditional peer review and open commenting and discussion over the collection of scholarly objects
  • versioning of those objects
  • working with the various stakeholders to figure out how it's all going to be funded and built: departments, societies, libraries, publishers, conference organizers, journal editorial boards.

They could, in essence, lead the way into the post-journal scholarly communications landscape.

13 responses so far

Engineering and Society: Working Towards Social Justice

I've always thought the born-digital, high-quality review articles (called "lectures") that Morgan & Claypool publish as part of their Synthesis product are one of the best products out there. They really get publishing scholarly and professional materials in the digital age.

One of their most interesting lecture series is the Synthesis Lectures on Engineers, Technology and Society.

Three new lectures in that series look to be perfect texts for a broad range of Engineering & Society-type course. In fact, I think a pretty good course along those lines could use nothing but the Synthesis articles.

A few examples of previously published lectures in that series:

These are subscription products, so if you're institution doesn't have them you should contact your local engineering librarian.

It's worth noting that I think Synthesis is a great example of the kinds of things academic libraries should be supporting and promoting. It's hard to imagine a free business model that would work for this kind of fairly unique, high-quality content. It's up to us to decide to spend our money on things that are truly worth it.

No responses yet

IEEE-USA History Project

Just yesterday I posted on preserving the the history of the computing field, musing at the end that digitization projects could save a lot of documents.

Well, what comes along today in the latest What's New @ IEEE for Students is a note about the IEEE-USA History Project:

Digital Archives, Organization's Four Decades of Service Unveiled
IEEE-USA is building a digital archive featuring documents and photos of its 36-year history of promoting the careers and public policy interests of U.S. IEEE members. Part of the IEEE-USA History Project, the archive features:

  • An overview of the first four decades of IEEE-USA from 1973-2009
  • A listing of IEEE-USA's leaders from 1973 to date, including photos of boards of directors from 1998
  • A detailed description of IEEE-USA's formation and its first 10 years (1973-1983), including an IEEE Spectrum special report on the constitutional referendum that added professional activities to the IEEE constitution
  • A look at IEEE-USA growth and maturity from 1984-1999, with annual reports covering the 15-year period
  • A glimpse of IEEE-USA in the 21st Century from 2000-present, including annual reports from 2002-2008, years in review from 2005-2008 and program handbooks for 2007-2008
  • Program histories, including IEEE-USA's Student Professional Awareness Conferences (S-PACs)

John Meredith, IEEE-USA's 2007 president, is leading the IEEE-USA History Project. Meredith chaired the 2009 IEEE Conference on the History of Technical Societies, in Philadelphia from 5-7 August, and made a presentation on IEEE-USA history.

Bravo, IEEE!

No responses yet

Preserving Records of the Past, Today

An interesting article from the most recent IEEE Annals of the History of Computing, Preserving Records of the Past, Today by James W. Cortada. In concerns the difficulty that scholars of the history of computing have in finding primary materials to work with, mostly in the form of documents.

Scholars examining the history of information technology run into many practical, nuts-and-bolts problems more frequently than historians in other fields that
have existed for considerable periods of time, such as diplomatic and political national history. Problems with the history of information technology center on the paucity of the tools historians rely on to do their work. This paucity includes insufficient finding aids
to archival collections and too few reference guides, bibliographies, and library collections adequately stocked with books and other publications. Of course,
the 800-pound guerrillas we all want in our intellectual spaces are large collections of archival materials needed to underpin our work. When compared to so many
other fields of history, we are long on demand and short on supply, mainly because our field is new. In time, all will be well in our part of history.

The author is kind enough to make a few suggestions to his fellow scholars about how they could improve conditions for themselves and coming generations of scholars.

Of course, the suggestions have a lot of applicability for librarians too, especially those (like me) who support historians of technology.

Let's take a look his suggestions. If you have access, it's well worth reading the whole article:

  • First, donate archival materials in whatever shape, form, or copy you acquire them to institutions of your choice so that future historians may consult them.
  • Second, collect and preserve all ephemera on your subject that you come across with the intention of donating it to a library or archive.
  • Third, write and publish bibliographic and historiographical articles describing materials and your research strategies.
  • Fourth, prepare annotated bibliographies and other research aids.

The first two, of course, seem the most directly applicable to libraries. There's a lot of pressure on space these days at libraries. On the one hand, we see ourselves as builders and promoters of excellent student spaces for study, relaxing and collaboration. On the other hand, economic pressures are forcing the closure of many dedicated subject libraries. Also, with technology books, magazines and other materials, the easy answer is that since the materials become technically obsolete fairly quickly, older versions can just be discarded. As well, with so much current material being online (both on the free web and in subscription ebook & periodical databases), there's also the impulse to just get rid of the stuff.

But, just as librarians in other disciplines are concerned with the histories of their fields, we must be careful about jettisoning the history of the disciplines that we support, we must be aware that our collections often serve more than what we think of as our core audience, but also historians, sociologists and anthropologists.

I would hope that Google and other book digitization programs will get around to a lot of that old material, but a lot of those old books, magazines and other ephemera will likely never be digitized by the commercial projects. I think there's lots of latitude here for special collections work, especially those that have off-site storage facililties or that can fund their own digitization projects for this type of material.

We live in interesting times, surrounded by rocks and hard places.

4 responses so far

« Newer posts Older posts »