Computer Science | Grinnell College

This week in CS Table, we will consider a widely used technique for using Internet services anonymously: onion routing. The leading free implementation of onion routing is Tor. The Tor Project provides a variety of software packages incorporating or building on this technique, of which the best known is the Tor browser, a Firefox derivative that uses onion routing for interactions with Web servers.

The readings are:

• Tor Project. 2015. Tor: overview. https://www.torproject.org/about/overview.html.en
• Reed, M. G., and Syverson, P. F. 1999. Onion routing [abstract only]. Prepared for the 1999 Symposium on Advanced Information Processing and Analysis. http://www.onion-router.net/Publications/AIPA-1999.pdf
• Dingledine, R., Mathewson, N., and Syverson, P. 2004. Tor: the second-generation onion router. Proceedings of the 13th USENIX Security Symposium. http://www.onion-router.net/Publications/tor-design.pdf

Packets containing copies of these readings are available on the bench near Noyce 3821.

There is also one optional reading (on-line only):

• Anderson, M. 2014. 81% of Tor users can be de-anonymized by analyzing router information, research indicates. http://thestack.com/chakravarty-tor-traffic-analysis-141114

Computer Science Table is a weekly meeting of Grinnell College community members (students, faculty, staff, etc.) interested in discussing topics related to computing and computer science. CS Table meets Fridays from 12:10 to 12:50 in the Day PDR (JRC 224A). Contact Sam Rebelsky, rebelsky@grinnell.edu, for the weekly reading. Students on meal plans, faculty, and staff are expected to cover the cost of their meals. Visitors to the College and students not on meal plans can charge their meals to the department.

This week in CS table, we will read the first major paper on RAID (not the bug spray, but the disk technology - Redundant Arrays of Inexpensive Disks). This classic paper not only led computer scientists to think differently about storage, but also saw wide adoption in the real world. Copies are available outside Professor Rebelsky's office.

Patterson, D. A., Gibson, G., and Katz, R. H. 1988. A case for redundant arrays of inexpensive disks (RAID). In Proceedings of the 1988 ACM SIGMOD international Conference on Management of Data (Chicago, Illinois, United States, June 01 - 03, 1988). H. Boral and P. Larson, Eds. SIGMOD '88. ACM, New York, NY, 109-116. DOI=https://dl.acm.org/citation.cfm?doid=50202.50214.

Increasing performance of CPUs and memories will be squandered if not matched by a similar performance increase in I/O. While the capacity of Single Large Expensive Disks (SLED) has grown rapidly, the performance improvement of SLED has been modest. Redundant Arrays of Inexpensive Disks (RAID), based on the magnetic disk technology developed for personal computers, offers an attractive alternative to SLED, promising improvements of an order of magnitude in performance, reliability, power consumption, and scalability. This paper introduces five levels of RAIDs, giving their relative cost/performance, and compares RAID to an IBM 3380 and a Fujitsu Super Eagle.

Computer science table is a weekly meeting of Grinnell College community members (students, faculty, staff, etc.) interested in discussing topics related to computing and computer science. CS Table meets Fridays from 12:10-12:50 in the Day PDR (JRC 224A). Contact Sam Rebelsky, rebelsky@grinnell.edu, for the weekly reading. Students on meal plans, faculty, and staff are expected to cover the cost of their meals. Visitors to the College and students not on meal plans can charge their meals to the department.

This week in Computer Science Table, we're exploring a different side of things. In particular, we are considering some under the hood issues in common programming areas, such as strings, memory allocation, and databases. Our reading is

Spolsky, Joel (2001, December 11). Back to Basics. Joel on Software. Web page at http://www.joelonsoftware.com/articles/fog0000000319.html.

Some questions to think about for this meeting: How are strings represented internally in your favorite programming languages? If you had a choice of how to represent strings internally, what would you do? Are all versions of malloc created equal? What flaws do you see in Spolsky's comments?

Computer science table is a weekly meeting of Grinnell College community members (students, faculty, staff, etc.) interested in discussing topics related to computing and computer science. CS Table meets Fridays from 12:10-12:50 in the Day PDR (JRC 224A). Contact Sam Rebelsky rebelsky@grinnell.edu> for the weekly reading. Students on meal plans, faculty, and staff are expected to cover the cost of their meals. Visitors to the College and students not on meal plans can charge their meals to the department.

On Thursday, December 4, in Noyce 3821, Professor Samuel A. Rebelsky and the other faculty of the Department of Computer Science will present the department's annual discussion of summer opportunities in CS:

It may be hard to believe given the forthcoming sub-freezing temperatures, but it's about time to starting thinking about what you're going to do this coming summer (and maybe even in subsequent summers). If you enjoy computer science (or at least computer programming), summer is an opportunity to explore new approaches, to develop new skills, and perhaps even to make some money. But what kinds of things can you do? While students tend to focus on a few options (e.g., research with faculty), a wide variety of opportunities are available. In this session, we will discuss goals you might set for the summer and some opportunities that can help you achieve those goals.

Refreshments will be served at 4:15 p.m. in the Computer Science Commons (Noyce 3817). Professor Rebelsky's talk, Summer opportunities in computer science, will begin at 4:30. Everyone is welcome to attend!

At 11:00 on Wednesday, December 3, 2014, students in section 1 of CSC 207 will present their work on developing software that creates competition schedules for college athletic teams. Presentations will be in Science 3813.

At first glance, scheduling seems easy. In the standard form, each team must play every other team twice, once home and once away. But real scheduling is much more complicated. For example, some schools may be on a quarter system while others are on a semester system, so not every team can play on the same set of dates. Many teams also have severe restrictions on how far they can travel during weekdays. And when teams play multiple games on a weekend, they typically do all of those games at home or all of those games away. With enough of these kinds of restrictions, forming a schedule that meets all of the restrictions is impossible.

In a sequence of lightning presentations, student project teams will discuss their creative approaches to solving a concrete version of this problem and in generalizing those approaches.

Refreshments will be provided.

On Thursday, November 20, Toby Baratta 2017, Bo Wang 2016, and Kitt Nika 2016 will present their summer research on the automatic detection of place names on historical maps:

This past summer we did research on toponym detection and recognition on historical maps. Overall, our research goal was making historical maps more search-friendly and making information in the maps more accessible. Kitt Nika and Shen Zhang worked on detecting text strings on map images with maximally stable extremal regions (MSER). With this, they implemented a binarization method for future research in text detection. Kitt will discuss MSERs and the methods involving them in regards to text detection. Toby Baratta and Bo Wang worked on linking geographic datasets and recognizing toponyms from the detected text strings. With the alignment between historical maps and real-life geography, we used a Bayesian model to calculate probabilities of possible toponyms. Toby and Bo will discuss their work on increasing the range of our recognition system by adding area features such as lakes.

At 4:15 p.m., refreshments will be served in the Computer Science Commons. The talk, “Historical map processing: text detectors, database linking, and region models,” will begin at 4:30 p.m. in Noyce 3821. Everyone is welcome to attend!

This Friday at CS Table, we discuss a recent security failure in Unix, GNU/Linux, and Mac OS X operating systems: the Shellshock bug. Our reading is:

• Wheeler, David A. “Shellshock.” October 20, 2014. http://www.dwheeler.com/essays/shellshock.html

Computer Science Table is a weekly meeting of Grinnell College community members (students, faculty, staff, etc.) interested in discussing topics related to computing and computer science. We meet on Fridays from 12:10 to 12:50 in Rosenfield 224A (the Day PDR). Students on meal plans, faculty, and staff are expected to cover the cost of their meals. Students not on meal plans can charge their meals to the department.

Contact John Stone for a copy of this week's reading.

On Thursday, November 13, Professor Gianfranco Ciardo, Professor and Chair of the Department of Computer Science at Iowa State University, will speak on extensions of binary decision diagrams:

Binary decision diagrams (BDDs) have had enormous success since Bryant showed how to use them for the efficient verification of boolean hardware designs and Clarke and McMillan employed for symbolic model checking. In this talk, we take BDDs as a starting point and explore various extension of decision diagrams, we apply them to problems beyond temporal logic verification, and we discuss several challenging research problems related to decision diagrams.

Before the talk, Professor Ciardo will meet informally with students considering the possibility of graduate study at Iowa State. This meeting will be in the Computer Science Commons (Noyce 3817), beginning at 3:45 p.m.

At 4:15 p.m., refreshments will be served in the Computer Science Commons. Professor Ciardo's talk, “Beyond BDDs: advanced decision diagrams and their applications,” will begin at 4:30 p.m. in Noyce 3821. Everyone is welcome to attend!

On Thursday, November 6, Professor Janet Davis and Richard Bright, Director of Off-Campus Study, will lead a discussion of options for combining off-campus study with study of computer science. CS majors who have studied abroad are welcome to come share their experiences.

Refreshments will be served at 4:15 p.m. in the Computer Science Commons (Noyce 3817). The presentation, “Off-campus study and computer science,” will begin at 4:30 p.m. in Noyce 3821. Everyone is welcome to attend!

On Thursday, October 30, Professor Sriram Pemmarju of the Department of Computer Science at the University of Iowa will discuss the uses of randomness in algorithm design:

Randomness has proven itself to be an amazingly useful resource in the design of simple and efficient algorithms. Randomized algorithms are now widespread in all areas of computer science; examples can be found in cryptography, data compression, distributed systems, machine learning, network protocols, online and streaming algorithms, etc. This talk will present a few “gems” of randomization—algorithms that highlight the elegance and power of randomized techniques, while identifying underlying principles that guide the design of randomized algorithms. Time permitting, the talk will also consider the theoretical question of whether randomness provably adds to the power of efficient algorithms.

Refreshments will be served at 4:15 p.m. in the Computer Science Commons (Noyce 3817). Professor Pemmarju's talk, “Toss a coin, throw a ball,and solve a problem,” will begin at 4:30 p.m. in Noyce 3821. Everyone is welcome to attend!