CS Table

CS Table (Friday, February 21, 2014): Skip lists

This Friday at CS Table, we will consider skip lists, an interesting data structure that, like lists, makes it easy to add and remove elements, and like arrays, lets you do something like binary search to quickly find elements.

Pugh, W. “Skip lists: A probabilistic alternative to balanced trees.” Communications of the ACM 33 (1990), no. 6, p. 668.

Computer Science Table is an open weekly meeting of Grinnell College community members (students, faculty, staff, etc.) interested in discussing topics related to computing and computer science.

CS Table (Friday, February 7, 2014): "P vs. NP"

This Friday at CS Table, we will consider the classic “P vs. NP” problem.

Fortnow, Lance. “The status of the P versus NP problem.” Communications of the ACM 52 (2009), no. 9, pp. 78–86.

In this article I look at how people have tried to solve the P versus NP problem as well as how this question has shaped so much of the research in computer science and beyond. I will look at how to handle NP-complete problems and the theory that has developed from those approaches. I show how a new type of “interactive proof systems” led to limitations of approximation algorithms and consider whether quantum computing can solve NP-complete problems (short answer: not likely). And I close by describing a new long-term project that will try to separate P from NP using algebraic-geometric techniques.

This article does not try to be totally accurate or complete either technically or historically, but rather informally describes the P versus NP problem and the major directions in computer science inspired by this question over the past several decades.

Computer Science Table is an open weekly meeting of Grinnell College community members (students, faculty, staff, etc.) interested in discussing topics related to computing and computer science.

CS Table (January 31, 2014): The ACM Code of Ethics

This Friday at CS Table, we will discuss the ACM Code of Ethics. Along the way, we will consider the purpose and roles of professional codes of ethics and what it means to think of yourself as a “professional.”

Computer Science Table is an open weekly meeting of Grinnell College community members (students, faculty, staff, etc.) interested in discussing topics related to computing and computer science.

CS Table (Friday, 24 January 2014): 3D printing

For the first CS table of 2014, we are going to consider 3D printing. We will start with a short reading:

Young, Susan. “Cyborg parts.” MIT technology review 116 (2013), no. 5, pp. 104–106.

However, you should feel free to bring additional articles and knowledge.

Computer Science Table is an open weekly meeting of Grinnell College community members (students, faculty, staff, etc.) interested in discussing topics related to computing and computer science.

Computer Science Table: "The Reactive Manifesto"

At this week's Computer Science Table (at noon on Friday, December 13, in Rosenfield 224A), we will discuss a recent statement from a group of programmers about desired features of modern applications. The reading is:

From the statement:

A new architecture has evolved to let developers conceptualize and build applications that satisfy today's demands. We call these Reactive Applications. This architecture allows developers to build systems that are event-driven, scalable, resilient and responsive: delivering highly responsive user experiences with a real-time feel, backed by a scalable and resilient application stack, ready to be deployed on multicore and cloud computing architectures. The Reactive Manifesto describes these critical traits which are needed for going reactive.

Computer Science Table: "Beyond efficiency"

At this week's Computer Science Table (at noon on Friday, December 6, in Rosenfield 224A), we will discuss issues, other than efficiency, that programmers should take into account when implementing algorithms. The reading is:

Computer Science Table is an open weekly meeting of Grinnell College community members (students, faculty, staff, etc.) interested in discussing topics related to computing and computer science.

CS Table: the Network Time Protocol

At this week's Computer Science Table (at noon on Friday, November 8, in Rosenfield 224A), we will discuss the Network Time Protocol. The reading is:

  • Mills, D. L. Internet time synchronization: the network time protocol. IEEE Transactions on Communications 39, no. 10, pp. 1482–1493.

The Network Time Protocol (NTP) uses a symmetric architecture in which a distributed subnet of time servers, operating in a self-organizing, hierarchical configuration, synchronizes local clocks within the subnet and to national time standards via wire, radio, or calibrated atomic clock. The servers can also redistribute time information within a network via local routing algorithms and time daemons. Performance data show that the NTP synchronization system ensures timekeeping accuracy throughout most portions of the Internet to within a few milliseconds, even in cases of failure or disruption of clocks, time servers, or networks.

Computer Science Table: "Are we free to code the law?"

At this week's Computer Science Table (at noon on Friday, October 4, in Rosenfield 224A), we will consider attempts to write code that reflects the law (e.g., providing legal advice).

Lauritsen, Marc. “Are we free to code the law? ” Communications of the ACM 56 (2013), issue 8, 60–66.

The emergence of interactive online services for legal self-helpers has triggered suppression efforts by the legal profession, as well as by state government officials in the U.S. While couched in terms of consumer protection, and at least partly motivated by such concerns, these efforts are also seen by some as blatant turf management by a profession anxious to avoid further erosion of its monopoly over legal advice and representation.

Often neglected in these discussions is whether restricting the distribution of software is within the legitimate scope of government action. No one would contend that attempts to suppress books, pamphlets, and speeches on how the legal system works and what forms one needs to interact with it would pass constitutional muster. Is providing software that helps people meet their legal needs an activity the state can prohibit under the U.S. Constitution?

Here, I explore ways software-based legal-assistance systems can be understood for purposes of public policy and constitutional analysis. The focus is on circumstances in the U.S., but many other countries face the same issues.

Computer Science Table: "The story of Mel"

For this week's Computer Science Table (at noon on Friday, September 27, in Rosenfield 224A), the reading is a classic short story about a “real programmer,” providing some historical perspective on the practice of programming:

Nather, Ed. “The story of Mel.” Usenet, 1983.

Computer Science Table: "Pair programming"

For this week's Computer Science Table (at noon on Friday, September 20, in Rosenfield 224A), the reading is a recent work on pair programming:

Wray, Stuart. “How pair programming really works.” IEEE computer 27 (2010), 50–55.

Come and learn more about why we teach our classes the way we do (and how to do better when working in a pair)!

Syndicate content