algorithms

Thursday Extra: "Exploring Algorithms with Design and Analysis Techniques"

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!

CS Table 4/25: Algorithmic Accountability

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:

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.

CS Table 2/28: What's in a face?

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? 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.

CS Table 11/15: Algorithmic Bias

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:

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.

Thursday Extra: "Left-leaning red-black trees"

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!

CSC 207 - Object-Oriented Problem Solving and Algorithms

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.

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 UnitLearning 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 organizaiton 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]

Thursday Extra: "What is a good recommendations algorithm?"

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!

Thursday Extra: "K-selection on the GPU"

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!

Friday Extra: "Video analytics"

At noon on Friday, October 9, Dr. Harold Trease of the Pacific Northwest National Laboratory will speak on Video analytics for indexing, summarization and searching streaming video and video archives:

Given streaming video or video archives, how does one effectively summarize, classify, and search the information contained within such a large amount of image data? In this presentation, we address these issues by describing a process for the automated generation of a table of contents and of keyword, topic-based index tables that can be used to catalogue, summarize, and search large amounts of video data. Having the ability to index and search the information contained within the videos, beyond just metadata tags, provides a mechanism to extract and identify useful content. During this presentation, we describe some of the mathematics, computer science and engineering, and applications of being able to use image and video keywords as the primary search criteria, much as Web browsers (such as Google) allow us to search text today.

Dr. Trease is a graduate of the University of Nebraska at Kearney and received his doctorate from the University of Illinois at Urbana-Champaign, in nuclear engineering. He has more than thirty years of research experience in the design, implementation, and application of high-throughput, high-performance computer software. He currently leads the P3D Code Development Project. P3D is a large-scale framework for modeling, simulation, and prediction in computational physics.

Pizza and soda will be served before the talk. Everyone is welcome to attend!

This lecture serves as this week's CS Table.

Thursday Extra: "Interfaces for video analytics"

On Thursday, October 8, Alex Exarhos 2010 will present the results of his summer research on analyzing videos:

I worked with a set of video indexing and searching algorithms through a Department of Homeland Security internship. These algorithms are capable of quickly providing a summary of a video by breaking it up into sections based on the content, and this method of indexing makes it possible to instantly locate other images, frames, or video segments within the indexed library. I will also talk about the web services I created for these algorithms, and the work I did implementing a mobile interface for a Google Android phone.

Refreshments will be served at 4:15 p.m. in the Computer Science Commons (Noyce 3817). The talk, Interfaces for video analytics, will follow at 4:30 p.m. in Noyce 3821.

Syndicate content