DOC PREVIEW
Berkeley COMPSCI 61B - Lecture Notes

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Lecture #42: Course SummaryCourse Topic SummaryProgramming-Language TopicsAnalysisMajor Categories of Data StructureSequencesSearchingSortingRandom numbersGraph structuresPragmatic topicsLecture #42: Course SummaryCourse Review: Sunday, 8 December 2001, 4-6PM in 306 Soda. Comeequipped with questions.Tournament: Turn in your tournament version (with instructions) us-ing submit tournament.Readers and lab assistants needed. Consider volunteering to be areader or lab assistant for CS 3, CS 61A, or CS 61B next semester.Reader applications will be available at the beginning of the semester(in fact, before). Readers are paid; lab assistants can get unit credit.Last modified: Fri Dec 6 02:04:18 2002 CS61B: Lecture #42 1Course Topic Summary• Programming language: Java• Program Analysis• Categories of data structure: Java library structure• Sequences• Trees• Searching• Sorting• Pseudo-random numbers• Threads• Graphs• Pragmatic implementation topicsLast modified: Fri Dec 6 02:04:18 2002 CS61B: Lecture #42 2Programming-Language Topics• Object-based programming: organizing around data types• 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 6 02:04:18 2002 CS61B: Lecture #42 3Analysis• Asymptotic analysis• O(·), o(·), Ω(˙), Θ(·) notations• Worst case, average case.• Amortized timeLast modified: Fri Dec 6 02:04:18 2002 CS61B: Lecture #42 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 Java libraryLast modified: Fri Dec 6 02:04:18 2002 CS61B: Lecture #42 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 structures• Basic operations: insertion, deletion• Tree traversals• Representing treesLast modified: Fri Dec 6 02:04:18 2002 CS61B: Lecture #42 6Searching• Search trees, range searching• Multidimensional searches: quad trees.• 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 6 02:04:18 2002 CS61B: Lecture #42 7Sorting• Uses of sorting• Insertion sort• Selection sorting• Merge sort• Heap sort• Quicksort and selection• Distribution sort• Radix sort• Complexity of various algorithms, when to use them?Last modified: Fri Dec 6 02:04:18 2002 CS61B: Lecture #42 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 6 02:04:18 2002 CS61B: Lecture #42 9Graph structures• Definition• Uses: things represented by graphs• Graph traversal: the generic traversal template• Depth-first traversal, breadth-first traversal• Topological sort• Shortest paths• Minimal spanning trees, union-find structuresText Processing• Knuth-Morris-Pratt string searching• Suffix treesLast modified: Fri Dec 6 02:04:18 2002 CS61B: Lecture #42 10Pragmatic topics• See laboratory reader.• Basic ideas behind source-code control systems (our e.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 6 02:04:18 2002 CS61B: Lecture #42


View Full Document

Berkeley COMPSCI 61B - Lecture Notes

Documents in this Course
Lab

Lab

4 pages

Matrix

Matrix

3 pages

Numbers

Numbers

14 pages

Lectures

Lectures

12 pages

Project 1

Project 1

24 pages

Exam

Exam

8 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?