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