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.