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