CS 137 | SCS | UW

CS 137 Programming Principles

Objectives

This course introduces software engineering students to elementary data structures, and to the functional programming paradigm.

Intended Audience

Level 1A Software Engineering undergraduates. It is assumed that students have experience developing well-structured, modular programs.

Related Courses

Antirequisites: CS 115, 135, 136, 145, CHE 121, CIVE 121, ECE 150, GENE 121, PHYS 239, SYDE 121

Successor: CS 138.

Hardware and Software

Used in course: An integrated development environment (IDE) for C++ (such as xCode for Mac OS X).

References

C Programming: A Modern Approach 2nd ed. Author: K.N. King

Schedule

Three hours of lecture per week, plus a two-hour lab and a one-hour tutorial. Normally available in Fall only.

Outline

Introduction and review (6 hours)

Review of hardware and software, problem solving and programming, including declarations, selection and looping constructs, I/O.

Subprograms (6 hours)

Functions. Scoping. Parameter passing, by value and by reference. Top-down design. Programming with stubs.

Structured Data (7.5 hours)

Arrays. Structures. Arrays of structures. Multidimensional arrays. Appropriate choice of data structures. String processing and tokenization.

Recursion (3 hours)

Introduction to recursive procedures and functions.

Analysis (1.5 hours)

Introduction to O-notation, space and time efficiency, and complexity.

Sorting Algorithms (4.5 hours)

Algorithm design and efficiency, through discussion of of elementary sorting algorithms (insertion sort, selection sort) and advanced sorting algorithms (mergesort, quicksort, heapsort).

Pointers and Dynamic Structures (6 hours)

Introduction to pointers, memory allocation and deallocation, singly and doubly-linked lists.

History of Computer Science (1.5 hours)

Babbage, Hilbert, Godel, Church, Turing. Early development of electronic computers and programming languages. History of concepts covered in this course.