Queen's School of Computing

CISC 121/3.0 Introduction to Computing Science I

Original Author: Bob Tennent
Last Revised: November 6, 2013

Calendar Description
Introduction to design and analysis of algorithms. Control structures: recursion, backtracking, exits. Data structures: structures, sequences, linked lists and references, binary search trees. Elementary searching and sorting. Introduction to assertions and loop invariants. Introduction to order-of-magnitude complexity. Introduction to numerical computation. Documentation, testing and debugging.
Learning Hours: 120 (36L;84P)

Recommendation: Some programming experience (such as high-school level programming or CISC 101/3.0 or CISC 110/3.0) will be expected; see Introductory Courses in Departmental Notes.

Pre or Corequisite: CISC-102/3.0 or any first-year course in Mathematics.

This course is a direct prerequisite to

  • CISC-124/3.0 (Introduction to Computing II)
  • CISC-220/3.0 (System-Level Programming)
  • CISC-221/3.0 (Computer Architecture)
  • CISC-271/3.0 (Scientific Computing)

and a co-requisite to CISC-203/3.0 (Discrete Mathematics for Computing Science).

This course is required in all Computing programs.

Topics
  • Review of imperative/procedural programming

  • Basics of hardware representation of data and control

  • Recursion, backtracking, exits from control structures/procedures/programs

  • Linear structures: lists, stacks, queues, sequential files;

  • Hierarchical structures: lists of lists, binary trees;

  • Linked data structures: nodes, references/pointers, box diagrams;

  • Searching: linear search, binary search, binary search trees;

  • Sorting: selection, insertion, quicksort (simple form)

  • Introduction to assertions and loop invariants

  • Introduction to order-of-magnitude analysis

  • Documentation, testing and debugging

  • Introduction to numerical computation, round-off and truncation errors, random number generation

Starting in Fall 2008, the programming language used in this course is Python.