Revised December 11, 2013
CS 116: Introduction to Computer Science 2
General description
- CS116 continues the development started in CS115, transitions to imperative programming, and introduces important issues in Computer Science.
Logistics
Audience
- 1B students in the Faculty of Mathematics
- Students interested in pursuing a Computer Science minor
- Students interested in learning more about Computer Science
Normally available
- Fall, Winter, and Spring
Related courses
- Predecessors: CS 115, CS 135
- Successors: CS 136, CS 230, CS 234, CS 330
- Co-requisites: None
- Conflicts: CS 137, CS 138
For official details, see the UW calendar.
Software/hardware used
- Python programming language
- WingIDE programming environment or alternate
Typical reference(s)
- A. Downey, Think Python: An Introduction to Software Design, O'Reilly Media
Required preparation
At the start of the course, students should be able to
- Given a clear and concise statment of a problem or task, write a program from scratch of up to fifty lines of properly-formatted, tested, and documented Racket code to solve the problem or carry out the task
- Use elementary data structures, such as lists and trees, in programs
- Use abstract list functions in programs
Learning objectives
At the end of the course, students should be able to
- Given a clear and concise statement of a problem or task, write a program from scratch of up to a hundred lines of properly-formatted, tested, and documented Python code to solve the problem or carry out the task
- Use higher-order functions to improve the readability and efficiency of programs
- Use various forms of recursion (structural, accumulative, generative) in programs
- Use various forms of iteration (for, while) in programs
- Describe the basic memory model for mutation of basic types, lists, and objects in Python
- Distinguish between constant, linear, quadratic and exponential running times of algorithms
- Explain the relative advantages and disadvantages of lists and dictionaries
- Write useful Python programs using console and file input and output for practical tasks
Typical syllabus
Introduction to imperative programming (15 hours)
- Common features of imperative languages
- Basics of Python: assignment and introduction to mutation, basic console output and keyboard input, basic program structure, defining and using functions
- Relating concepts from Racket to Python: lists of basic types, if statements, including nested conditionals; basic structural recursion; abstract list functions and lambda
- Basic Python memory model, including lists
More advanced concepts from imperative programming (15 hours)
- Additional forms of recursion: accumulative and generative
- Iteration: bounded (for loop), guarded (while loop); simple and nested iteration; applications, including linear and binary search algorithms
- Investigating several sorting algorithms
- Dictionaries
- Basic use of classes (in comparison to Racket structures), introduction to object-oriented principles in Python, and mutation of objects
- Functions as parameters: extending the design recipe to include polymorphism
- File input and output: basic and structured file processing, basic exception handling (try-except block)
- Additional topics, possibly including programming with real world data, web pages, etc.
Issues in Computer Science (6 hours)
- Basic introduction to run-time analysis and simple run-time classes (constant, logarithmic, linear, linearithmic, quadratic, exponential) through studied algorithms
- Discussion of design issues related to data structures (for example, choosing between lists and dictionaries) and effects on complexity and memory requirements