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