CS 116 Introduction to Computer Science 2
Objectives
This course continues the development started in CS 115, providing further exposure to functional programming, an introduction to imperative programming, and basic coverage of important issues in computer science.
Intended Audience
CS 115 is intended for non-CS majors, but it can be taken by CS majors who completed CS 135 but with an insufficiently high grade to enter CS 136.
Related Courses
Prerequisites: CS 115 or CS 135
Antirequisites: CS 134, 136, 137, 138, 145 taken fall 2010 or earlier, 146
Successor: CS 234, CS 136.
Hardware and Software
Used in course: Programs are written in subsets of the language Scheme, and in Python. Student labs are equipped with the DrScheme integrated development environment running on networked personal computers. Versions for Windows, Mac OS, Unix/X and Linux are freely downloadable for use on computers owned by students. The Python resources to be used are still to be determined.
References
Think Python: An Introduction to Software Design, Allen Downey, Publisher: Green Tea Press (Optional)
How To Design Programs by Felleisen, Findler, Flatt, and Krishnamurthi, MIT Press, 2001. This book is available in its entirety on the Web, though students are encouraged to purchase a physical copy.
Course notes are also required.
Schedule
Three hours of lecture per week, plus a lab and a tutorial.
Outline
Introduction and review (1.5 hours)
Review of the basic ideas from CS 115: function definition and application, types of data, conditional expressions, structures, lists and recursion, recursion on integers, local definitions, abstract list functions.
More on functional abstraction (3 hours)
Writing abstract functions for lists. Using lambda to create simple functions.
Beyond structural recursion (4.5 hours)
Generative (general) recursion. Examples such as GCD and quicksort. Accumulative (iterative) recursion. Patterns for accumulative recursion: structural or generative recursion on one parameter while using others as accumulators. Benefits in time and space efficiency.
Mutation and imperative Languages (6 hours)
The need for mutation: remembering information from much earlier. set! and begin. Mutation of structures and lists. Common features of imperative languages. Assignment in Python: simple straight-line programs. Basic console output. Tracing programs.
Old ideas expressed in new ways (6 hours)
Lists, tuples, and dictionaries in Python. If statements. Defining and using functions. Abstract list functions in Python.
Iteration (6 hours)
Bounded iteration: for loops. Guarded iteration: while loops. Simple file input. Efficiency considerations.
Input and output (6 hours)
Keyboard input. General file input. Structured output to the console and to files.
Issues in Computer Science (3 hours)
A brief overview of computer organization. Reasons for different paradigms of computation, different languages, different systems. Dealing with complexity. Scalability, maintainability, empowerment.