CMSC31100-2010Autumn

From CSWiki

Big Ideas in Computer Science

This course introduces many important concepts across the broad scope of computer science. Each week a different speaker presents a self-contained three-lecture sequence on a big idea in her field of specialty. Most speakers are professors in the Department of Computer Science, but several outside speakers introduce the impact of big ideas in CS upon other fields.

Organizer: Michael J. O'Donnell
Venue: MWF 1:30-2:20 in Ryerson 251

Timely notices

Really important: I added some very important comments to the [discussion on Sneha's notes]. I am mostly very laissez faire about the notes. But, on the binary search topic, the whole point is that you have to understand this very small problem and program with essentially perfect precision. The least bit of fuzziness is deadly. Please fix the notes, and understand precisely what is going on. This is for everybody, not just Sneha. --Mike O'D 14:47, 3 December 2010 (CST)
Please actually do what I asked you to do in the notice below. --Mike O'D 18:43, 24 November 2010 (CST)
Please augment the information in the roster so that it is easy for me to find, at least your email address in case I need to contact you, and any other information (such as your regular Web page) that you'd like to share. --Mike O'D 17:27, 15 October 2010 (CDT)

Course work and requirements

Students are required to attend all classes. Let me know by email in advance if you must miss class for something very important, or as soon as possible afterward if you miss due to an unforeseen problem, such as illness. Each week the speaker for that week will assign readings and a short assignment. Grades and course credit are based on attendance, participation, and these assignments. There are no exams. Grading is Pass/Fail.

For each topic, one student will be in charge of taking notes and entering them on the class Wiki. I made random assignments, and listed them in parentheses on the schedule below, but you may trade assignments as much as you like. I only want short summary notes, at most one page per lecture. The student responsible may get help from other students, but please do not ask the speaker for help with notes. Part of the purpose of the notes is to discover any difference between the speaker's intention and the ideas received by the students.

Please use the Wiki discussion feature, accessible through the "discussion" tab at the top of each page, to continue our discussions outside of the meeting times. Please locate your discussion at the most specific page appropriate---usually the page for the notes for the lecture that you are discussing.

Students in the class (please edit your entry)

Schedule of topics and speakers

1A. September 27; October 1

Jesse Shapiro, School of Business (Mark Stoehr), "Ideological Segregation Online and Offline"

Notes by Mark Stoehr

1B. September 29

Mike O'Donnell (Mark Stoehr). Ad hoc opportunistic discussion of Jesse Shapiro's first hour, or whatever other topic we like.

If nothing else comes up, I will probably talk about Turing's article introducing the Turing Machine, and providing the foundation for the idea of computability:

"On computable numbers, with an application to the Entscheidungsproblem" by A.M. Turing Turing's article has some errors, and doesn't present the technical details as clearly as other texts. But, it discusses the point of the definition of the machine very cogently.
The Wikipedia article on Turing Machines complements the Turing paper. It gives a clear description of the TM mechanism, and some examples, but messes up the meaning.

Mark Stoehr's Turing Machine Notes

2. October 4, 6, 8

Borja Sotomayor

Notes (Erik Bodzsar).

Homework: Homework questions can be answered online here. Please complete the questions before class on Friday, October 15.

Paper for homework: Mu'alem, A. W. and Feitelson, D. G. 2001. Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling. IEEE Trans. Parallel Distrib. Syst. 12, 6 (Jun. 2001), 529-543.

Provisioning Distributed Computing Resources (or, what can I do with thousands of CPUs?) (Monday + Wednesday)

The need for computational resources has, over the years, become a fundamental requirement in both science and industry. For example, a scientist could require a large number of computers to run a simulation for just a few hours, but might not need those computers at any specific time (as long as they are made available in a reasonable amount of time). A college instructor may want to make a cluster of computers available to students during the course's lab sessions, at very specific times during the week, and with a specific software configuration. A telecommunications company could posses an existing infrastructure that hosts a number of websites, but may need to supplement that infrastructure with additional resources during periods of unforeseen increased web traffic, meaning those resources have to made available right away with very little advance notice.

A variety of solutions have been developed to meet these requirements, including compute clusters, supercomputers, data centers, grids, and clouds. All of these typically involve large numbers of CPUs, in the order of hundreds or thousands of CPUs. So, how are these resources managed? We will focus on the "big ideas" behind how these resources are managed in a single site (such as a cluster or a supercomputer) and what mechanisms have been developed so "I can run my stuff on these big machines". We will also talk about what happens when these resources are distributed across several sites, as is typical in grid computing.

Anatomy of a Dissertation (Friday)

I have recently completed my dissertation and, like most dissertations, my work deals with a sub-sub-sub-problem of a wider area. In particular, my work lives within the realm of resource provisioning, the topic presented this week. In this presentation, I will briefly describe the work I did for my PhD dissertation, with an emphasis on how dissertation research is structured.

3. October 11, 13, 15

John Reppy "Partial evaluation, staged programming, and meta programming" (Christopher Bun).

Suggested reading: Chapters 4 and 5 of Partial Evaluation and Automatic Program Generation

Sven Auhagen's notes

4. October 18, 20, 22

Anne Rogers (Lamont Samuels). Reduce, Reuse, and Recycle: approaches to boosting memory system performance.

Lamont Samuels's notes

5. October 25, 27, 29

Mike O'Donnell: Busy Beaver and Number Crunching

Nicholas Seltzer's notes

6. November 1, 3, 5

Pedro Felzenswalb (Nicholas Seltzer). "Discrete Optimization Methods in Computer Vision"

Sobhan Naderi's notes

7. November 8, 10, 12

Mike O'Donnell: Real insights from "theoretical" CS.

Basic References:

Wikipedia stub on Acceptable Programming Systems. Wikipedia probably captures the common presentation of this idea pretty well, but I think the common presentation is a poor platform for generating insight.
Wikipedia article on Primitive Recursive Functions. There is a bit more of a start on insight here. Don't sweat the initial Definition. Try to project the section on Computer language definition to a programming language that you know. C makes it rather difficult, since the for loop in C is a generalization of the while loop, and primitive recursion corresponds to a restriction on loops. The old Fortran (it keeps changing, so I don't know about a modern version) had the appropriate sort of for loop, and most of the languages based on Algol are good for this insight, particularly Pascal.
An Introduction to the General Theory of Algorithms. Michael Machtey & Paul Young. North-Holland 1978. My favorite reference for the basic concepts.

Supplementary Readings:

Uncomputability of halting function given by a Python program

Related optional meeting on November 23

I will speak at the Formal Philosophy workshop on campus Tuesday November 23 4:30-6:20 PM in Cobb 119. I will discuss Formal Systems from the point of view that they are made of exactly the same stuff as computational systems, but we usually ask different questions about the computations/derivations. You can find a description of the topic, and some readings, in the archive for 2009 May 26.

I decided to snub Descarte and Hilbert a bit, and use Lewis Carroll's "What the Tortoise Said to Achilles" as my springboard. That will at least be sorta fun.

John Oberlin's Notes

8. November 15, 17, 19

Coup d'état: Mark Stoehr--"How might computers learn to perceive speech?" Acoustics, HMMs, Phonetics, Phonology, Grammars, and Coarse-to-fine search strategies.

I'll be discussing modern speech recognition architectures, some basic linguistics, and a different approach to the speech recognition problem.

Notes by Tatiana Orlova at Google Docs Local copy of Tatiana's notes

Old Description of November 15, 17, 19

9A. November 22

Mike O'Donnell (Chris Bun). "A tale of two sillies." In the Internet business, two silly buzz phrases have arisen. Well, way more than two, but I'm going to mention these two:

Best effort. What does that mean? Yet, somehow, the agreement that every gateway in the Internet will make its "best effort" to forward packets effectively toward their goals really works.
Quality of Service. Aka "QoS." What does that mean? Every service has lots of qualities. It pretty much seems to mean providing different levels of service to different uses of the Internet. A bit of probabilistic reasoning shows under what conditions this might be a good idea.

Chris Bun's Notes

9B. November 24

Ridgway Scott (Sobhan Naderi Parizi). biological computing

Thanksgiving Break November 25-26

10A. November 29

Mike O'Donnell, "Do you understand binary search? No, you don't!" (Sneha Popley).

If you can, take 15 minutes to 2 hours (your choice), and try to write a totally correct binary search program off the top of your head (before you read the good solution from Bentley or elsewhere).
Really read Jon Bentley's column number 4 of "Programming Pearls." It first appeared as a column in Communications of the ACM, which should be available online through our library subscription. But, I couldn't find it. It is now collected into a book, Programming Pearls, which you should buy. I provided a paper copy in class on Wednesday.
Check out Joshua Block's Google research blog entry on a further bug in Bentley's binary search. Well, we might call this a bug in the programming language compiler, but one way or another, we gotta get it right, right? (I attached a page of the text to the end of the Bentley column.)
I started working on a presentation of binary search for a Programmer's Toolkit. My collaborator finked out, so the project is up for grabs if anybody wants to do it (or some variation using the material):

Sneha's Notes

10B. December 1, 3

Ketan Mulmuley, "Gödel's incompleteness theorem" (Sneha Popley).