Computer Science | Grinnell College

NOTE: This Tuesday we will meet in the CS Commons at noon. Please bring your own lunch; we'll try to have some drinks and snacks, too.

This week in CS Table, we will consider some applications of machine learning that show both potential benefit and great risks: The use of ML algorithms in decisions related to bail, sentencing, and parole. We have two readings:

• Simonite, Tom (2017). How to upgrade judges with machine learning. MIT Technology Review.
• Angwin, Julia, Larson, Jeff, Mattu Surya, and Kirchner, Lauren. Machine bias. Pro Publica.

This CS table discussion will cover computer-aided gerrymandering: the ways that legislative district boundaries are drawn to favor specific parties or interests, and how computers have changed this process in recent years. The reading and listening below should give you some useful background information on what gerrymandering is, where it came from, and recent developments in the process.

• This short podcast (21 minutes) gives some useful background information and introduces the Gill v. Whitford case heard by the US Supreme Court this fall.
  • Rameswaram, Sean, narrator. "Who’s Gerry and Why Is He So Bad at Drawing Maps?” Radiolab Presents: More Perfect, season 2, episode 4, WNYC Studios, 2017.
• The following articles look at how computers can be used to place boundaries between legislative districts, both in support of gerrymandering as a potential tool to draw fair legislative districts.
  • Ellenberg, Jordan. “How Computer Turned Gerrymandering Into a Science”, The New York Times: Gray Matter, 6 Oct 2017.
  • Oberhaus, Daniel. “Algorithms Supercharged Gerrymandering. We Should Use Them to Fix it”, Vice: Motherboard, 3 Oct 2017.

Computer science table (CS 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 Tuesdays from 12:00–1:00pm in JRC 224A (inside the Marketplace). Contact the CS faculty 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 (sign in at the JRC front desk).

On Thursday, May 11, students from this semester's “Analysis of Algorithms” will describe and analyze two algorithms with real-world applications.

Two problems will be addressed: “Worst Case Performance Analysis of Machine Learning Robustness” (Anna Blinderman and Reilly Grant), and “Formalizing Mimble-Wimble: Scaling Bitcoin” (three presenters who wish to remain anonymous). Both of these problems pose interesting design questions when considered from a theoretical rather than implementation standpoint. The presenters will describe their work in progress and encourage formative assessment from the audience.

At 4:00 p.m., refreshments will be served in the Computer Science Commons, Noyce 3817. The presentation, “Exploring Algorithms with Design and Analysis Techniques,” will follow at 4:15 p.m. in Noyce 3821. Everyone is welcome to attend!

Algorithms are essential to computer science, and increasingly they are essential to modern decision making on all levels. But are they unbiased? The emerging field of ‘Algorithm Accountability’ is beginning to identify cases in which inherent bias is imbedded in the inference structure of algorithms. The articles for this week’s CS Table run the gamut from popular press to general audience special interest to technical position papers to ACM recommendations for basic principles. The question is no longer ‘are algorithms biased’, but how to determine whether they are, and if so how to prevent them from being so.

Linda Oyolu, Ruth Wu, and Ursula Wolz will be leading our discussion on April 25, 2017. The following readings will give you a good sense of the area; please do your best to read at least some subset of these articles before our CS Table discussion:

• This NY Times overview is a good place to start: Make Algorithms Accountable (01-Aug-2016)
• An MIT Press summary of the emerging field: How to Hold Algorithms Accountable (17-Nov-2016)
• An ACM statement about principles for creating accountable algorithms: (PDF) Statement on Algorithmic Transparency and Accountability (12-Jan-2017)
• One of the seminal articles - a good place to get into the serious study: (PDF) Algorithmic Accountability, Journalistic investigation of computational power structures (07-Nov-2016)

Computer science table (CS 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 Tuesdays from 12:00-1:00pm in JRC 224B. Contact the CS faculty 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 February 28, 2017, we’ll be looking at applications of machine learning to judge people by their faces. Faces have the potential to convey much information about a person’s emotion and intent, but extracting that information from a face alone is a difficult task (and arguably impossible or impractical depending on which side of the research you fall on). Computers equipped with machine learning and computer vision algorithms have the capacity to perform these sorts of analyses on faces. What is possible with this sort of technology? Are there any ethical ramifications to consider?

• Malcom Gladwell. Blink (Excerpt: The Mysteries of Mind Reading).
• Emerging Technology from the arXiv. Machine-Vision Algorithm Learns to Judge People by Their Faces. November 1, 2016.
• Emerging Technology from the arXiv. Neural Network Learns to Identify Criminals by Their Faces. November 22, 2016.

Paper copies of the readings are available outside Prof. Curtsinger's office. Computer science table (CS 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 Tuesdays from 12:00-1:00pm in JRC 224B. Contact the CS faculty 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.

As computation plays a larger role in society, we are beginning to see cases where algorithms encode the biases of the past. While this phenomenon is widespread, there is a particularly interesting case where computer programs make bail recommendations for suspects in criminal cases.

There are two short readings suggested for the discussion on November 15:

• Battling Algorithmic Bias. Keith Kirkbatrick, Communications of the ACM.
• When Algorithms Discriminate. Claire Cain Miller, The New York Times.
• Printed readings are available at Noyce 3827.

Computer science table (CS 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 Tuesdays from 12:00-1:00pm in JRC 224B. Contact the CS faculty 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, February 13, John Stone will describe left-leaning red-black trees, a variant of binary search trees that guarantees that the worst-case running times for search, insertion, and deletion are proportional to the logarithm of the number of elements in the tree, and is easier to understand and simpler to code than more familiar self-balancing tree structures.

Refreshments will be served at 4:15 p.m. in the Computer Science Commons (Noyce 3817). The talk, “Left-leaning red-black trees,” will follow at 4:30 p.m. in Noyce 3821. Everyone is welcome to attend!

• Overview
• Catalog Description
• Syllabus Description
• Class Format and Pedagogy
• Current and Past Offerings
• Student Learning Outcomes

CSC 151, CSC 161, and CSC 207 — the three courses in Grinnell's multi-paradigm, introductory computer science sequence — have been recognized as "exemplar courses" by the ACM/IEEE-CS Task Force on Computing Curricula 2013.

Overview

CSC 207 is the third course in Grinnell's introductory computer science sequence and serves as the core gateway course to the majors. Students develop and analyze core data types (lists, stacks, queues, heaps, trees) and algorithms (primarily sorting and searching). Students also develop facility with object-oriented design. We use the Java programming language.

Starting in Fall 2013, CSC 207 has an experimental theme of Computing for Social Good. Students will work with free and open source projects that relate to the primary content of the course. We will leverage the Android platform for some of this development.

Catalog Description

An introduction to the ideas and practices of computation: message passing, information hiding, classes and interfaces, inheritance, polymorphism, and reflection. The course also includes data structures and the associated algorithms, packages and libraries, exceptions, and the use of an integrated software-development environment. Includes formal laboratory work.

Syllabus Description

Coming Soon

Class Format and Pedagogy

Coming Soon

Current and Past Course Offerings

The department maintains a page of current and past course offerings.

• Full listing of current and past computer science courses
• Listing of current and past offerings of CSC 207

Student Learning Outcomes

Computer Science Curricula 2013 (CS2013), national curricular recommendations from the ACM/IEEE-CS professional societies, identify an extensive list of learning outcomes for undergraduate computer science programs. Upon completing CSC 161, students should achieve the following learning outcomes with the specified level of mastery:

Knowledge Unit	Learning Outcome with [Level of Mastery]
Basic Analysis	Explain what is meant by “best”, “average”, and “worst” case behavior of an algorithm. [Familiarity] In the context of specific algorithms, identify the characteristics of data and/or other conditions or assumptions that lead to different behaviors. [Assessment] Determine informally the time and space complexity of simple algorithms. [Usage] Understand the formal definition of big O. [Familiarity] List and contrast standard complexity classes. [Familiarity] Perform empirical studies to validate hypotheses about runtime stemming from mathematical analysis. Run algorithms on input of various sizes and compare performance. [Assessment] Give examples that illustrate time-space trade-offs of algorithms. [Familiarity] Use big O notation formally to give asymptotic upper bounds on time and space complexity of algorithms. [Usage] Use big O notation formally to give expected case bounds on time complexity of algorithms. [Usage] Explain the use of big omega, big theta, and little o notation to describe the amount of work done by an algorithm. [Familiarity]
Algorithmic Strategies	For each of the above strategies (brute force, greedy, divide and conquer, backtracking, dynamic), identify a practical example to which it would apply. [Familiarity] Have facility mapping pseudocode to implementation, implementing examples of algorithmic strategies from scratch, and applying them to specific problems. [Usage] Use a divide-and-conquer algorithm to solve an appropriate problem. [Usage]
Fundamental Data Structures and Algorithms	Implement simple search algorithms and explain the differences in their time complexities. [Usage, Assessment] Be able to implement common quadratic and O(N log N) sorting algorithms. [Usage] Understand the implementation of hash tables, including collision avoidance and resolution. [Familiarity] Discuss the runtime and memory efficiency of principal algorithms for sorting, searching, and hashing. [Familiarity] Discuss factors other than computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data. [Familiarity] Demonstrate the ability to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in a particular context. [Usage, Assessment] Understand the heap property and the use of heaps as an implementation of priority queues. [Familiarity]
Advanced Data Structures Algorithms and Analysis	Understand the mapping of real-world problems to algorithmic solutions (e.g., as graph problems, linear programs, etc.) [Usage, Assessment] Apply advanced analysis techniques (e.g., amortized, probabilistic, etc.) to algorithms. [Familiarity]
Fundamentals	Explain the concept of modeling and the use of abstraction that allows the use of a machine to solve a problem. [Familiarity] Describe the relationship between modeling and simulation, i.e., thinking of simulation as dynamic modeling.[Familiarity] Create a simple, formal mathematical model of a real-world situation and use that model in a simulation. [Familiarity] Describe several approaches to validating models. [Familiarity]
Processing	Analyze simple problem statements to identify relevant information and select appropriate processing to solve the problem. [Assessment] Identify the issues impacting correctness and efficiency of a computation. [Familiarity]
Graphs and Trees	Demonstrate different traversal methods for trees and graphs, including pre, post, and in-order traversal of trees. [Trees] Model a variety of real-world problems in computer science using appropriate forms of graphs and trees, such as representing a network topology or the organization of a hierarchical file system. [Trees]
Defensive Programming	Explain why you might choose to develop a program in a type-safe language like Java, in contrast to an unsafe programming language like C/C++. [Some Familiarity] Demonstrate the identification and graceful handling of error conditions. [Usage] Use static and dynamic tools to identify programming faults. [Usage]
Data Modeling	Describe the main concepts of the OO model such as object identity, type constructors, encapsulation, inheritance, polymorphism, and versioning. [Familiarity]
Object-Oriented Programming	Compare and contrast (1) the procedural/functional approach—defining a function for each operation with the function body providing a case for each data variant—and (2) the object-oriented approach—defining a class for each data variant with the class definition providing a method for each operation. Understand both as defining a matrix of operations and variants. [Assessment] Use subclassing to design simple class hierarchies that allow code to be reused for distinct subclasses. [Usage] Correctly reason about control flow in a program using dynamic dispatch. [Usage] Use multiple encapsulation mechanisms, such as function closures, object-oriented interfaces, and support for abstract datatypes, in multiple programming languages. [Usage] Define and use iterators and other operations on aggregates using idioms most natural in multiple programming languages, including taking functions as arguments. [Usage] Explain the relationship between object-oriented inheritance (code-sharing and overriding) and subtyping (the idea of a subtype being usable in a context that expects the supertype). [Familiarity]
Functional Programming	Use multiple encapsulation mechanisms, such as function closures, object-oriented interfaces, and support for abstract datatypes, in multiple programming languages. [Usage]
Basic Type Systems	For multiple programming languages, identify program properties checked statically and program properties checked dynamically. Use this knowledge when writing and debugging programs. [Usage] Define and use program pieces (such as functions, classes, methods) that use generic types. [Usage] Explain benefits and limitations of static typing. [Familiarity]
Advanced Programming Constructs	Use various advanced programming constructs and idioms correctly. [Usage] Discuss how various advanced programming constructs aim to improve program structure, software quality, and programmer productivity. [Familiarity] Discuss how various advanced programming constructs interact with the definition and implementation of other language features. [Familiarity]
Algorithms and Design	Determine whether a recursive or iterative solution is most appropriate for a problem. [Assessment] Apply the techniques of decomposition to break a program into smaller pieces. [Usage] Identify the data components and behaviors of multiple abstract data types. [Usage] Implement a coherent abstract data type, with loose coupling between components and behaviors. [Usage] Identify the relative strengths and weaknesses among multiple designs or implementations for a problem. [Assessment]
Fundamental Programming Concepts	Analyze and explain the behavior of simple programs involving the fundamental programming constructs covered by this unit. [Assessment] Identify and describe uses of primitive data types. [Familiarity] Write programs that use primitive data types. [Usage] Modify and expand short programs that use standard conditional and iterative control structures and functions. [Usage] Design, implement, test, and debug a program that uses each of the following fundamental programming constructs: basic computation, simple I/O, standard conditional and iterative structures, the definition of functions, and parameter passing. [Usage] Choose appropriate conditional and iteration constructs for a given programming task. [Assessment] Describe the concept of recursion and give examples of its use. [Familiarity] Identify the base case and the general case of a recursively-defined problem. [Assessment]
Fundamental Data Structures	Discuss the appropriate use of built-in data structures. [Familiarity] Describe common applications for each data structure in the topic list. [Familiarity] Write programs that use each of the following data structures: arrays, strings, linked lists, stacks, queues, sets, and maps. [Usage] Compare alternative implementations of data structures with respect to performance. [Assessment] Compare and contrast the costs and benefits of dynamic and static data structure implementations. [Assessment] Choose the appropriate data structure for modeling a given problem. [Assessment]
Development Methods	Trace the execution of a variety of code segments and write summaries of their computations. [Assessment] Explain why the creation of correct program components is important in the production of high-quality software. [Familiarity] Identify common coding errors that lead to insecure programs (e.g., buffer overflows, memory leaks, malicious code) and apply strategies for avoiding such errors. [Usage] Conduct a personal code review (focused on common coding errors) on a program component using a provided checklist. [Usage] Contribute to a small-team code review focused on component correctness. [Usage] Describe how a contract can be used to specify the behavior of a program component. [Familiarity] Create a unit test plan for a medium-size code segment. [Usage] Refactor a program by identifying opportunities to apply procedural abstraction. [Usage] Apply a variety of strategies to the testing and debugging of simple programs. [Usage] Construct, execute and debug programs using a modern IDE and associated tools such as unit testing tools and visual debuggers. [Usage] Construct and debug programs using the standard libraries available with a chosen programming language. [Usage] Analyze the extent to which another programmer’s code meets documentation and programming style standards. [Assessment] Apply consistent documentation and program style standards that contribute to the readability and maintainability of software. [Usage]
Requirement Engineering	Interpret a given requirements model for a simple software system. [Familiarity] Conduct a review of a set of software requirements to determine the quality of the requirements with respect to the characteristics of good requirements. [Usage]
Software Design	Articulate design principles including separation of concerns, information hiding, coupling and cohesion, and encapsulation. [Familiarity] Use a design paradigm to design a simple software system, and explain how system design principles have been applied in this design. [Usage] Construct models of the design of a simple software system that are appropriate for the paradigm used to design it. [Usasge] Design a contract for a typical small software component for use in a given system. [Usage]
Software Construction	Build robust code using exception handling mechanisms. [Usage]
Software Verification Validation	Describe the role that tools can play in the validation of software. [Familiarity] Discuss the issues involving the testing of object-oriented software. [Usage]
Cross-Layer Communications	Find bugs in a layered program by using tools for program tracing, single stepping, and debugging. [Assessment]
Social Context	Describe positive and negative ways in which computer technology (networks, mobile computing, cloud computing) alters modes of social interaction at the personal level. [Familiarity]
Professional Ethics	Identify ethical issues that arise in software development and determine how to address them technically and ethically. [Familiarity] Recognize the ethical responsibility of ensuring software correctness, reliability and safety. [Familiarity] Describe the strengths and weaknesses of relevant professional codes as expressions of professionalism and guides to decision-making. [??]
Professional Communication	Write clear, concise, and accurate technical documents following well-defined standards for format and for including appropriate tables, figures, and references. [Usage] Evaluate written technical documentation to detect problems of various kinds. [Assessment]

On Thursday, April 4, Aditi Roy 2013 will discuss the evaluation of recommendation algorithms:

While designing a recommendation algorithm for Kindle FreeTime Unlimited (a product which serves a subscription containing books, videos and apps to kids), I realized that there were many varied opinions on what the role of a good recommendation algorithm was. This talk will provide an overview of some of the popular approaches and algorithms used in the industry, the metrics used to evaluate recommendation algorithms, and the challenges involved in serving customers good recommendations.

Refreshments will be served at 4:15 p.m. in the Computer Science Commons (Noyce 3817). The talk, “What is a good recommendations algorithm?” will follow at 4:30 p.m. in Noyce 3821. Everyone is welcome to attend!

On Thursday, April 19, Tolu Alabi 2013, Brad Gordon 2012, and Russel Steinbach 2012 will discuss their work in summer 2011 on parallel algorithms for computing order statistics:

How do you select the 1,678,341st largest number out of a list of 500 million numbers? The answer is surprisingly simple, and will be the subject of our Thursday Extra. We will present two efficient, parallel algorithms for selecting the kth largest element out of very large lists, a problem known as k-selection. We will discuss how graphics processing units (GPUs) enable us to easily and efficiently implement these algorithms on single computers.

Refreshments will be served at 4:15 p.m. in the Computer Science Commons (Noyce 3817). The talk, K-selection on the GPU, will follow at 4:30 p.m. in Noyce 3821. Everyone is welcome to attend!