Wednesday, May 12, 2010

java 300s

Lectures

http://www.tacoma.washington.edu/tech/courses/tcss342/06sp/lectures.html

notes:

files:

    2006-06-01:

    Today we reviewed for the final exam. The practice problems are in the Handouts section. We also did course evaluations.

    2006-05-30:

    Today we went over Marty's solution to Homework 7 (HashMap). Then we talked a bit about Homework 8 (Kevin Bacon). Lastly we learned about priority queues and how to implement a priority queue using a heap.

    2006-05-25:

    Today we talked further about graphs. We learned how to implement a graph using an edge list, adjacency list, and adjacency matrix. We also learned about Dijkstra's algorithm for finding the minimum weight path between two vertices in a weighted graph. Homework 8 (Kevin Bacon) was assigned.

    2006-05-23:

    Today we talked about a solution to HW6 Boggle. Then we saw a different board-driven solution to Boggle using prefix trees ("tries"). Lastly we started to learn about graph path searching using breadth-first and depth-first search algorithms.

    2006-05-18:

    Today we went over the solution to Homework 5 (Darth Vader brain). Then we talked about Homework 6 (Boggle), including briefly looking at a data structure called a prefix tree that is very fast for board-driven searches. I showed some examples of prefix trees in action, including Google Suggest and Dasher. Next Homework 7 (HashMap) was assigned. Lastly we talked more about graphs, stopping just before the graph searching slides.

    2006-05-16:

    Today we began by talking about recursive backtracking algorithms using the example of eight queens. Next we worked on our implementation of a hash table set. We then implemented a map using a binary search tree. Lastly we began to talk about the graph ADT.

    2006-05-11:

    Today we talked about more complex usages of Map and Set data structures, such as Maps of Sets (CountWords.java). Homework 6 (Boggle) was assigned. We then talked in detail about how to implement a Set data structure using a hash table (HashTableSet.java). This includes adding, searching, resizing (rehashing), and removing (using 'lazy removal').

    2006-05-09:

    Today we went over the midterm, then we talked about sets and maps. We discussed in mild detail how a hash table implements a set and map. We solved a few problems using sets and maps (CountWords.java).

    2006-05-04:

    Today was our midterm exam.

      2006-05-02:

      Today we finished talking about AVL trees. We wrote the code to add to the AVL tree, including the rotation commands. We also prepared for the midterm exam by doing several practice problems.

      2006-04-25:

      Today we did several practice problems in groups, related to binary trees. We practiced adding and removing nodes from a tree, and counting the size, height, and other attributes of the tree. We also wrote some practice code problems with trees such as numLeft and nodesAtDepth. Homework 5 (Sith Sense) will be assigned tonight.

      2006-04-20:

      Today we started talking about binary trees. In particular we wrote code for a binary search tree, which can add and search for elements in O(log n) average expected time. We wrote most of our binary search tree code recursively, because this is the easier way to represent the tree algorithms.

      2006-04-18:

      Today we talked more about sorting. We focused on the "good" sorting algorithms (ones faster than O(n^2)): merge sort, shell sort, and quick sort. Homework 4 (Sort Detective) was assigned.

      2006-04-13:

      Today we talked about searching and sorting. We saw sequential and binary search. We talked about bogo sort, bubble sort, selection sort, and insertion sort. Next time we'll discuss faster algorithms such as merge sort and quick sort. We also saw a sorting animation applet page.

      2006-04-11:

      Today we continued implementing our LinkedList; we renamed it to UnfinishedLinkedList and extended it with LinkedList. We converted the linked list into a doubly-linked one with prev and next pointers. We talked about how to effectively design an iterator for a linked list, which will be your task for Homework 3. We also began talking about recursion, doing some short recursive algorithms such as GCD and printing a folder on our hard disk.

      2006-04-06:

      Today we implemented our own ArrayList. We wrote an iterator (CrappyListIterator) for that ArrayList. We also continued implementing our LinkedList. We saw the useful trick of using a dummy header to avoid any special cases in the code.

      2006-04-04:

      Today we talked about usage of linked lists. We modified our List methods so that they run on a Java LinkedList object. Usually this means creating an iterator to retain our position as we move through the linked list. We also implemented a little bit of our own LinkedList class (just the add, get, and size operations). Homework 2 (List Methods) was assigned.

      2006-03-30:

      Today we did an algorithm analysis of the MaxSubsequenceSum2 algorithm, discovering that its runtime is roughly n^2 + n. We talked in detail about the usage of ArrayList, including analyzing the runtime of several operations on the list. We noticed that inserting or removing from the beginning/middle of the list is slow (O(n)). We wrote some ArrayList algorithms in the ListMethods.java file and empirically analyzed them in ListMethods.java.

      2006-03-28:
    Posted by at

    No comments:

    Post a Comment

    Subscribe to: Post Comments (Atom)