AdministrativeCourse Review: Sunday, 16 December 2001, 4-6PM in100 Lewis. Come equipped with questions.Tournament next week: Turn in your tournament ver-sion (with instructions) using submit tournament.Readers and lab assistants needed. Consider volun-teering to be a reader or lab assistant for CS 3, CS 61A,or CS 61B next semester. Reader applications will beavailable at the beginning of the semester (in fact, be-fore). Readers are paid; lab assistants can get unitcredit.Last modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32 1Course Topic Summary• Programming language: Java• Program Analysis• Categories of data structure: Java library structure• Sequences• Trees• Searching• Sorting• Pseudo-random numbers• Threads• Graphs• Programming language: C• Pragmatic implementation topicsLast modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32 2Programming-Language Topics• Object-based programming: organizing around datatypes• Object-oriented programming:– Dynamic vs. static type– Inheritance– Idea of interface vs. implementation• Memory model: containers, pointers• Numeric types• Arrays• Java syntax and semantics• Scope and extent• Standard idioms, patterns:– Objects used as functions (e.g., Comparator)– Partial implementations (e.g., AbstractList)– Iterators– Views (e.g., sublists)Last modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32 3Analysis• Asymptotic analysis• O(·), ø(·), Ω(˙), Θ(·) notations• Worst case, average case.• Amortized timeLast modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32 4Major Categories of Data Structure• Collection interface and its subtypes• Map interface and its subtypes• Generic implementations of collections, lists, maps• Complete concrete collection and map classes in JavalibraryLast modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32 5Sequences• Linking:– Single and double link manipulations– Sentinels• Linking vs. arrays• Stacks, queues, deques• Circular buffering• Trade-offs: costs of basic operationsTrees• Uses of trees: search, representing hierarchical struc-tures• Basic operations: insertion, deletion• Tree traversals• Representing treesLast modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32 6Searching• Search trees, range searching• Hashing• Priority queues and heaps• Balanced trees– Rebalancing by rotation– Balance by construction (B-trees)– Probabilistic balance (skip lists)– Tries• Search times, trade-offsLast modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32 7Sorting• Uses of sorting• Insertion sort• Selection sorting• Merge sort• Heap sort• Quicksort and selection• Distribution sort• Radix sort• Complexity of various algorithmsLast modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32 8Random numbers• Possible uses• Idea of a pseudo-random sequence• Linear congruential and additive generators• Changing distributions:– Changing the range– Non-uniform distributions• Shuffling, random selectionThreading• Creating multiple threads of control in Java• Need and mechanisms for mutual exclusion in Java• Use of mailboxes for communication• Idea of a coroutine (HW 9).Last modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32 9Graph structures• Definition• Uses: things represented by graphs• Graph traversal: the generic traversal template• Depth-first traversal, breadth-first traversal• Topological sort• Shortest pathsLast modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32 10Lower-Level Programming• Basics of C (The C Programming Language)• The C memory model: comparisons with Java• C-specific constructs: unions, void*s, enumeratedtypes.• Looking under the hood at Java:– Implementation of dynamic types and method se-lection.– Implementation of memory allocation and deallo-cation.Last modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32 11Pragmatic topics• See laboratory reader.• Basic ideas behind source-code control systems (oure.g.: PRCS).• Use of debugging– What debuggers can do– How to use to pin down bugs• Compilation control (our e.g.: gmake)Last modified: Fri Dec 7 10:25:25 2001 CS61B: Lecture #32
View Full Document
Unlocking...