CSCI C211/A591
Introduction to Computer Science

Computer science is the systematic study of computation, hardware systems, software systems, and networks, combined with the design and analysis of algorithms and data structures. It is the foundation upon which all branches of information technology rest. Students of computer science learn to design and implement systems to manage and visualize data, control robots, model human cognition, extract information from vast volumes of data, and build the tools used by other IT professionals.

The goal of this course is to introduce computer science to students interested in pursuing computer science as a major or minor. This course is also suitable for informatics majors who are considering a computer science cognate, or any student who anticipates the need to develop computing skills that are applicable to a variety of disciplines. Students majoring in psychology, business, physics, biology, chemistry, cognitive science, music, fine arts, and mathematics are particularly encouraged to take C211.

Computer programming is a fundamental tool of computer scientists, so a primary focus of this course will be computer programming. We will also be looking at the bigger picture and introducing concepts that will be needed for subsequent computer science courses. We will study various algorithms and abstractions and problem-solving techniques.

The prerequisite for this course is "High school precalculus math." Note that neither MATH M027, M118, nor M211 is required, despite misleading language to this effect in older course descriptions. If you are ready to take a calculus course, then you are ready to take Introduction to Computer Science.

In algebra, you solved problems involving symbols (numbers, variables, and operators like "+") by applying rules (usually in the form of laws or theorems). The trick in algebra was deciding which rule among many was most promising to lead to the solution of the problem. Computer scientists solve problems in much the same way. If you really enjoyed high-school math, you are likely to enjoy this course and to do well in it.

Scheme is the programming language used for the assignments. Scheme is an interesting language in that it is both easy to learn and extremely powerful. Both properties derive from its simple, uniform syntax, its provision of a few general features in place of myriad special-purpose features, and its lack of restrictions. Scheme is often used in industry by expert programmers with really hard problems to solve.

In subsequent courses, you will learn other languages, like C++ and Java, that build in more special-purpose features and, through various restrictions, help the everyday programmer create correct and efficient programs.

Not convinced? Why Scheme rather than Java or C++?

Why Computer Science?

Still not convinced Computer Science is for you? Find out why it might just be the best thing that ever happened to you by reading this excellent resource from Univeristy of Colorado at Boulder.

Course Goals

At the end of C211, you should be able to:

1. Think logically to solve concrete problems.
2. Write a correct and efficient program to implement an algorithm.
3. Productively critique the thinking of self and others.
4. Demonstrate the ability to work in teams, and effectively communicate ideas to others.
5. Acquire a deep and practical understanding of fundamental computer science concepts, especially recursion, abstraction, and data structures.

Learning Outcomes

At the end of C211, you should be able to:

• Explain the behavior of simple programs involving fundamental programming constructs.
• Analyze simple programs by exploring all possible code paths.
• Modify and expand short programs.
• Trace, test, and debug short programs.
• Choose appropriate conditional constructs and relational/logical operators for a given programming task.
• Recognize redundant conditions and unreachable code.
  
  
• Apply functional decomposition to break a program into smaller pieces.
• Describe how actual arguments are passed to formal arguments.
• Devise algorithms for solving simple problems.
• Compose algorithms for solving multi-stage problems.
• Describe strategies that are useful in debugging (such as hand tracing).
• Reason about code (such as identifying invariants and refactoring).
  
  
• Describe the concept of recursion and give examples of its use.
• Identify the base case and the general case of a recursively defined problem.
• Implement, test, trace, and debug simple recursive procedures.
• Differentiate between tail and non-tail recursion.
• Compare and contrast tail and non-tail recursive solutions for elementary problems (such as factorial).
• Recognize the difference between an algorithm and its implementation.
• Write a program to interpret a simple command-style language (such as a controlling a robotic mouse).
  
  
• Describe the purpose of encapsulation.
• Describe the concept of an abstract data type (ADT).
• Write representation independent programs based on a library ADT.
• Implement a basic ADT.
  
  
• Recognize the difference between a single pass and a multi-pass algorithm.
• Perform time trials to compare the efficiency of different algorithms on large inputs.
• Effectively use local variables to aid readability and avoid re-computation.
• Implement common quadratic and O(n log n) sorting algorithms.
• Describe the divide-and-conquer approach and give examples of algorithms that employ the technique.
  
  
• Write programs to traverse a variety of data structures (including lists, strings, trees, vectors, and matrices).
• Compare and contrast the costs and benefits of various data structures.
• Choose the appropriate data structure for modeling a given problem (such as text compression).
  
  
• See programs as data and data as programs.
• Recognize common programming patterns such as map, reduce, and filter.
• Make appropriate use of existing abstractions (such as map) and be able to craft new general-purpose tools.
• Write programs that operate on programs (such as uncomment).

Course Topics

Here's a list of topics that are typically covered in C211:

1. Basic datatypes and recursion
   • Numbers (integers, rationals, reals, etc)
   • Arithmetic operations
   • Computer arithmethic vs. mathematics (exactness)
   • Booleans
   • Relational procedures, predicates
   • Logical operations
   • Conditionals
   • Strings, characters, symbols
   • Type conversions
   • Variables, scope, user-defined procedures
   • Aggregate data structures (lists of numbers)
   • Simple recursion (with only one argument)
   • Understanding the execution model
   • Simple program transformations
   • Nested declarations (inner procedures, local bindings), scope
   • More recursion (multiple arguments, nested loops)
   • Iteration (tail recursion)
   • Error checking
   • Debugging strategies, hand tracing
2. Abstract data types
   • Binary number system
   • Octal and hex number systems
   • Character encoding and strings
   • Abstract data types (ADT), representation independence
   • Binary tree ADT
   • Tree traversals
   • Binary search trees
   • Expression trees
   • Images and matrices
3. Algorithms
   • Sorting (selection sort, insertion sort, merge sort)
   • Quicksort
   • Binary search
   • Time tests, simple run-time analysis
   • Huffman compression
   • Shortest path
4. Advanced programming
   • Programs = Algorithms + Data Structures
   • Procedures as arguments
   • Higher-order procedures, iterators
   • Side-effects of evaluation (I/O, assignments, jumps, etc)
   • Vectors, arrays, mutable data structures
   • Interpreters for simple expressions
   • Dynamic programming (memoization)
5. Programming Style
   • Documentation
   • Layout
   • Using meaningful identifiers
   • Efficiency considerations