401 3 1 COMP 401 Foundations of Programming Spring 2008 Course Objective 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 COMP 110 14 Experience programming in a language such as C Java or Pascal is essential No previous 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 Topics order Approximate Number of Weeks may not be covered in this Introduction Red tape Why Java Review of Java 2 Semantics and Rules of Verification Stating what a program does Propositions Predicates Boolean operators Quantifiers Semantic rules Loop invariants Program correctness Termination 2 Advanced programming Good use of the language Methods Functions and Procedures Static classes stateless classes Toolbox classes and Parameter classes Recursion 1 5 Object oriented programming Classes and objects Object state Inheritance Abstract data types ADTs of sets lists stacks queues 2 Algorithm Analysis The Cost of Computing Order notation The Big Oh and Big Theta A Measure of Cost Recurrence equations and elementary methods of solution 1 Sorting Putting things in order Selection Insertion Mergesort Quicksort Non comparison sorting 1 5 Linked structures Linked lists Trees 1 5 Algorithm Paradigms 401 3 2 Brute force supersets and Backtracking Greedy Algorithms Divide and conquer Finite state machines Exams review sessions 1 5 5 1 5
View Full Document
Unlocking...