Spring 1998 CS111, Lecture Notes (Sects 1-6)

Note: these lecture notes were prepared by Professors Barbara Ryder (ryder@cs.rutgers.edu) and Donald Smith (dsmith@cs.rutgers.edu) for a course at Rutgers University during 1997-98. Permission from the authors is needed to use these materials.

1. 1/22/98 CS111 information and procedures, CS111 environment

2. 1/26/98 Problem solving in NIM, Java Fundamentals: classes, objects
   methods, variables, Backus Naur Form - defining syntax. last updated 1/28/98

3. 1/29/98 More Fundamentals: BNF, derivations, parse trees,
   method invocation, constants, expressions, Strings in output,
   output statements, NIM program, last updated 2/1/98

   See example NIM program in NimState-10.java

4. 2/2/98 Writing a Java program, example of UStime class -- converting
   EST times to different US time zones, if statements, toString() function,
   main method, procedural abstraction, more on methods and parameters.
   last updated 2/5/98

   See examples UStime.java and UStime-procs.java

5. 2/5/98 Boolean values and operators, simplification rules, truth tables.
   last updated 2/5/98

6. 2/9/98a Boolean simplification rules, truth tables.
   2/9/98b More on primitive types, debugging with jdb, how to use javadocs
   last updated (slide#7) on 2/9/97

   See examples UStime-procs-err.java with UStime-procs-err.output
   which contains a trace of the jdb session.

7. 2/12/98 Comparing objects for equality, simple For loops, more on
   if statements; last updated (slides 4,9,19) on 2/14/98

   See examples NimState-loop.java, UStime-loop.java, UStime-nestloop.java,
   and sum.java

8. 2/16/98 Declarations and scope, design of a class, PriceTickets program,
   inheritance, method placement and lookup

   See example ticketMaster.java

9. 2/19/98 Discussion of Assignment 3, class variables and class methods
   conversion between classes, enumerations, extending classes;
   last updated 2/26/98, slide 22

   2/23/98 Lecture cancelled because of Hourly 1 on Feb 24th, 6:10-7:30pm.
   Note: Prof Ryder's 4-6pm office hours will be held.

10. 2/26/98 Example of enumerations, loop constructs: do-while, while, for

    See examples sumwhile.java, sumwbreak.java, sumdoublewbreak.java,
    sumbreakcontinue.java

11. 3/2/98 Algorithm design by GCD example.
    last updated 3/11/98 slides #5,#10.

    Prof Ryder's 4-6pm office hours are cancelled on 3/2/98.

12. 3/5/98 Practice with Hourly 1 question (in class); Input.

    See examples sumkey.java, summark.java, sumeof.java

13. 3/9/98 Reading from and writing to a file, Buffering,
    Exceptions, try, catch, finally clauses; exception handling -
    local, external; Last updated 3/11/98 slides #13, #22.

    See examples sumfile.java, sumfileio.java, sumexcept.java,
    DoubleLoopInput.java

14. 3/12/98 Arrays, Strings, standard interfaces to both classes.

    See examples hist.java, hist.output

15. 3/23/98 Arrays, revisited; jdb breakpoints; Linear search; Binary Search
    Last updated 3/26/98 slide #29.

    See examples newbinsearch.java, newbinsearch.output,
    newbinsearchRec.java, and myTest2.java.

16. 3/26/98 Complexity of search, Asymptotic complexity, big O notation,
    average cost analysis

17. 3/30/98 Review for Hourly 2

18. 4/2/98a Envelope classes and input.
    4/2/98b Assignment 5 inheritance hierarchy, abstract classes, use of super,
    abstract data types. (Note: part b of this lecture now has new slides
    (see 4/6/98 lecture below) which should be consulted instead
    for information about the homework; it will be presented
    on 4/6/98.)

19. 4/6/98 Assignment 5 and issues of inheritance; Expr objects, inheriting
    instance variables and methods, method lookup reviewed, abstract classes,
    Last updated 4/7/98 at 1:00pm; sides #2,4,6,8,9,10,21 changed

20. 4/9/98 Explanation of structural equality, equals() function - an example
    of a recursive method; use of super, examples.

21. 4/13/98 Lists, Stacks - abstract data types; how to design a class interface,
    push(), pop(), peek(), empty()

    See /usr/local/class/cs111/packages/src/cs111/util/(Stack.java,
    List.java, StackException.java)

22. 4/16/98 Object visibility, Queue class, interface, representation
    using lists, methods enter(), remove()
    Recursion a la Dr. Seuss.
    Last updated 4/19/98 changed slide #2.

    See/usr/local/class/cs111/packages/src/cs111/util/(Queue.java,
    QueueException.java)

23. 4/20/98 Assignment 6: postfix form of expressions, evaluating postfix expressions;
    Queues with a different representation type by same inteface,
    example of an ADT, Abstract Data Type

    See my example directory to find /newstacks/(Queue.java, QueueException.java)
    Note: to run this form of the Queue class you will need to copy all
    the *.java files in directory /newstacks.

    The next two lectures contain important material; attendance
    in lecture is strongly suggested.

24. 4/23/98 Introduction to Sorting as problem decomposition,
    class SortProblem, Selection Sort and its complexity, Quicksort
    Last updated 4/23/98, slides #5,9,17,20.

    See /usr/local/class/cs111/packages/src/cs111/util/(SortProblem.java,Sortable.java)

25. 4/27/98 Quicksort and its complexity
    Merge sort and its complexity, empirical experiments counting
    operations in sorts, asymptotic complexity
    Last updated 4/23/98, slide #6.

    See /usr/local/class/cs111/packages/src/cs111/util/(SortProblem.java,Sortable.java)

26. 4/30/98 Experiments with sorting methods,
    method resolution - examples, inheriting methods, overriding methods,
    interfaces - cloning

    See /studempl/*.java, /clone/*.java, /overrid/*.java.

27. 5/4/98 Review for final exam.