CISC 121/3.0 Introduction to Computing Science I
Original Author: Bob Tennent
Last Revised: November 6, 2013
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 or CISC 151/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.
Starting in Fall 2008, the programming language used in this course is Python.
- 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
linear search, binary search, binary search trees;
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