ON THIS PAGE:

Course Objectives

Prerequisites

Course Outline

Course Objectives
Introduction to the basic principles of computer programming in the small: algorithms, data structures, basic principles of object oriented programming, and survey material. Principles will be illustrated through programming exercises and written assignments. Students will develop skills and techniques for good programming 'in the small.' The course will emphasize a mathematical approach to the subject matter. Characterizing how a program works (via documentation and assertions) will be considered as important as producing a program that apparently produces the correct answers.

Prerequisites
A first formal course in programming is required. Experience programming in a language such as C++, Java, or Pascal may suffice. No previous Macintosh or PC experience or college mathematics is required, but the course is aimed at those interested in continuing in computer science. This course is a prerequisite for COMP 410 (Data Structures).

Course Outline

Introduction: 2

• Red tape
• Why Java?
• Review of Java

Semantics and Rules of Verification: Stating what a program does (2)


Propositions, Predicates, Boolean operators, Quantifiers Semantic rules; Loop invariants, Program correctness, Termination.

Advanced programming: Good use of the language (1.5)


• Methods: Functions and Procedures
• Static classes (stateless classes): Toolbox classes and Parameter classes.
• Recursion

Object oriented programming (2)


• Classes and objects; Object state, Inheritance
• Abstract data types: ADTs of sets, lists, stacks, queues

Algorithm Analysis : The Cost of Computing (1)


• Order notation (The Big-Oh and Big Theta): A Measure of Cost.
• Recurrence equations and elementary methods of solution

Sorting: Putting things in order (1.5)


• Selection, Insertion, Mergesort, Quicksort
• Non-comparison sorting

Linked structures (1.5)


• Linked lists
• Trees

Algorithm Paradigms

• Brute force (supersets) and Backtracking (1)
  
• Greedy Algorithms, Divide and conquer, (.5)
• Finite state machines (.5)

Exams, review sessions (1.5)