COMP 401: Foundations of Programming401-3.1COMP 401: Foundations of ProgrammingSpring 2008Course 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 incontinuing in computer science. This course is a prerequisite for COMP 410 (Data Structures).Topics Approximate Number of Weeks (may not be covered in this order)Introduction 2Red tapeWhy Java?Review of JavaSemantics and Rules of Verification: Stating what a program does. 2Propositions, Predicates, Boolean operators, QuantifiersSemantic rules; Loop invariants, Program correctness, Termination.Advanced programming: Good use of the language. 1.5Methods: Functions and ProceduresStatic classes (stateless classes): Toolbox classes and Parameter classes.RecursionObject oriented programming 2Classes and objects; Object state, InheritanceAbstract data types: ADTs of sets, lists, stacks, queues Algorithm Analysis : The Cost of Computing. 1Order notation (The Big-Oh and Big Theta): A Measure of Cost.Recurrence equations and elementary methods of solutionSorting: Putting things in order 1.5Selection, Insertion, Mergesort, QuicksortNon-comparison sortingLinked structures 1.5Linked listsTreesAlgorithm Paradigms401-3.2Brute force (supersets) and Backtracking 1Greedy Algorithms, Divide and conquer, .5Finite state machines .5Exams, review sessions
View Full Document
Unlocking...