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