University of Minnesota
Computer Science & Engineering
http://www.cs.umn.edu/

CSCI 1901: THE Structure of Computer Programming I

Overall Description

1901 is a required undergraduate course that we expect students to take in their freshman year. It is one of the courses required for admission to the CSci major, and is the first class in the sequence for all computer science and computer engineering majors. 1901 offers an introduction to the fundamental principles of programming and to different programming paradigms, with emphasis on the design of abstract data types and recursive algorithms.

The course does not assume any programming knowledge, but students with a rudimentary knowledge of Unix will be able to move into the material faster. Upon successfully completing this class, students should be able to design algorithms and abstract data types, design programs of significant complexity, and be comfortable in using recursion.

Catalog Description

Recursion as algorithm development technique. Use of abstractions to hide program details. Use of modularity to manage complexity. Objects, data structures. Programming language Scheme as implementation vehicle. Introduction to Python as transition to other programming languages.

Course Outline

Week Sections in
Textbook		 Topics
1 1.1 Introduction to Scheme.
2 1.2 Recursion and Iteration
3 1.3 Lambda Expressions
4 2.1 Data Abstraction
5 2.2 Hierarchical Data
6 2.3 Symbolic Data
7 2.4 Multiple Representations of Data
8 2.5 Generic Operators
9 3.1 The Assignment Operation
10 3.2 Environment Model of Evaluation
11 3.3 Mutable Data (Queues and Tables), Discrete Event Simulation
12 3.4 Propagation of Constraints, Concurrency
13   Introduction to Python
14   Python
15   Python, Review, Special Topics

Alternative Material

Streams (Section 3.5), the scheme interpreter (Section 4.1), or logic programming (Section 4.4) may be substituted for some of the later material.

Why This Class is Important and its Role in the Curriculum

Computer science and engineering students need to acquire the reasoning and abstraction skills needed for designing algorithms and programs. This course teaches how to think as a computer scientist, by teaching the process of building abstractions to hide implementation details, of decomposing problems into simpler problems, and of controlling the intellectual complexity of designing large software systems.

Most students will take 1901 in their first year. It is one of the courses required for admittance to the CSci major.

Prerequisites and Rationale

Students should have taken, or be taking, Calculus I. 1901 requires mathematical maturity, and students need to do be able to do abstract reasoning. Although students may not use, in 1901, much of the material covered in calculus, they will need solid reasoning skills and the willingness to use mathematics as a tool for analyzing and solving problems.

Classes Having 1901 as a Prerequisite and Rationale

1902, the second course for majors, requires 1901 as a prerequisite. Even though students will use a different programming language (currently Java) in 1902, 1901 will give them the reasoning and abstraction skills they need to become computer scientists as opposed to programmers. The simplicity of the Scheme language they use in 1901 will allow them to learn and experiment early with abstract data types, learn to use recursion as a fundamental problem solving method, understand some programming language design issues, and learn how to design solutions to complex problems such as discrete event simulation, propagation of constraints, or games.

Class Format

4 credits, 3 hour long lectures + 1 two-hour lab per week. Recitation will be used for hands-on learning using the computer, problem solving or review, or more in-depth discussion of topics and examples given in the large class. Since this is the first course for majors, the recitation will help students acquire familiarity with the Unix operating system, and with problem solving and program design.

Textbook

Abelson and Sussman, Structure and Interpretation of Computer Programs, McGraw-Hill, 2nd edition, 1996.

Outcomes

Upon successful completion of the course students should have the following skills and proficiencies. Students should be able to:

  1. understand the notion of computational process and be able to express computational processes using procedures in Scheme
  2. understand the notion of abstract data type, how to create new abstract data types, and how to express them in Scheme
  3. be able to use recursion as a problem solving method
  4. be able to explain how the process of evaluation is performed from the perspective of the computer and how procedural objects are created and manipulated
  5. understand the basic principles of program design, using abstractions to hide implementation details, and problem decomposition to control the intellectual complexity of the problem
  6. understand how to use different programming styles (functional, object-oriented, data-driven)
  7. be able to write elementary programs in the Python programming language.

Given a problem, students should be able to:

  1. design appropriate data structures and algorithms, using recursion whenever appropriate,
  2. design, implement, and test a Scheme program solving the problem, and have some basic understanding of the computational complexity of the programs they write.
Contact CS&E | CS&E Employment | Site Map
Contact: 4-192 Keller Hall, 200 Union St, Minneapolis, MN 55455     Phone: (612) 625-4002