CSC 222: Computer Programming II
Spring 2005

Course Overview

Course Goals * To know and use basic programming tools for object-oriented problem solving (e.g., classes, polymorphism, inheritance, interfaces) * To appreciate the role of algorithms and data structures in problem solving and software design (e.g., objected-oriented design, searching and sorting, recursion, stacks, queues, and linked lists) * To be able to design and implement a program to model a real-world system, and subsequently analyze its behavior. * To develop programming skills that can serve as a foundation for further study in computer science Object-oriented Programming Java basics review of fundamental programming constructs from CSC221 Scanner class, user input inner classes design: highly cohesive, loosely coupled interfaces & polymorphism Comparable interface, Collections.sort defining an interface, implementing an interface class hierarchies: e.g., Comparable --> String, Integer inheritance derived class, parent class inheriting methods/fields, overriding methods IS-A relationship, polymorphism class hierarchies: e.g., BankAccount --> SavingsAccount, CheckingAccount event handling events, event sources, event listeners ActionListener interface, actionPerformed method Swing classes: JFrame, JButton, JLabel, JPanel, JTextField, JTextArea, JScrollPane, setLayout, BorderLayout, GridLayout Data Structures arrays and ArrayLists advantages of ArrayLists over arrays methods: add, remove, set, get, size, ... parallel arrays/ArrayLists list/dictionary ADT: add, contains, size, display implementation built on top of ArrayList, generic unsorted vs. sorted vs. "lazy" sorted versions List interface stack ADT: push, pop, peek, empty, size ArrayList implementation, java.util.Stack class stack applications: delimiter matching, reverse Polish, run-time stack queue ADT: enqueue (offer), dequeue (remove), peek, isEmpty, size Queue interface, LinkedList class queue applications: simulating customer lines, print queues, ... LinkedList class implements both Queue and List interfaces linked list implementation ListNode, references/pointers, null singly-linked vs. doubly linked methods: addFirst, addLast, removeFirst, removeLast, get, set, size, ... LinkedList vs. ArrayList Algorithms algorithm analysis big-Oh notation, rate-of-growth worst case vs. average case vs. best case performance searching sequential search O(N) vs. binary search O(N log N) Collections.binarySearch, List & Comparable interfaces sorting insertion sort O(N^2) vs. selection sort O(N^2) vs. merge sort O(N log N) implementing an O(N) merge mixing selection & merge sorts Collections.sort, Collections.shuffle recursion base case(s), recursive case(s) recursive methods (e.g., fibonacci, GCD) recursive classes (e.g., Triangle, PermutationGenerator) avoiding infinite recursion, Cat in the Hat analogy recursion vs. iteration efficiency tradeoffs, redundancy simulations and modeling