CSE logo University of Washington Computer Science & Engineering
 CSE326 Summer 2007
  CSE Home    326 Home   About Us    Search    Contact Info 

Projects
 Project 1
 Project 2 A
 Project 2 B
 Project 2 C
 Project 3
Homework
 Homework 1
 Homework 2
 Homework 3
 Homework 4
 Homework 5
 Homework 6
 Homework 7
 Homework 8
Administrative
 Home
 Annoucement ArchiveCSE only
 Anonymous Feedback
Lectures
 Calendar & Slides
Policies
 General Guidelines
 Grading Policies
 Programming Guidelines
 Written HW Guidelines
Computing
 Unix Basics
   

Announcements

  • Final Exam, Friday, August 17, 2007

    • Exam policies
      • Closed book, closed notes. No cheating.
      • The exam begins promptly at 9:40 and ends at 10:40.
    • Pre-midterm topics covered
      • Stacks and Queues, array and list implementations.
      • Recursion. Designing algorithms recursively.
      • Asymptotic analysis, Big-O. Worst case, upper bound, lower bound, analyzing loops, recurrences, amortized complexity.
      • Trees – definitions
      • Binary Heaps, D-heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
      • Binomial Queues - Findmin, Deletemin, Insert. Additional operations of merge, increase, decrease.
      • Dictionary ADT
      • Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
      • AVL trees - Single and double rotations, insert, find.
      • Splay trees - Splaying, insert, find.
      • B trees - Motivation, choice of M and L.
      • Disjoint Union/Find - Up-trees. Weighted union (union by size) and path compression.
    • Post-midterm topics covered
      • Hashing. Properties of good hash functions. Selecting hash table size.  Separate chaining and open addressing. Linear Probing, Quadratic Probing, & Double Hashing to resolve collisions.  Rehashing.
      • Sorting. Insertion sort, Selection sort, Heap sort, Merge sort, quicksort.
      • Bucket sort, Radix sort. Lower bound on comparison sorting. In-place sorting. Stable sorting.
      • Graphs. Directed and undirected. Adjacency list and adjacency matrix representations.
      • Topological sorting.
      • Graph searching. Depth-first, breadth-first search
      • Shortest paths. Dijkstra's algorithm for SSSP. (Greedy Algorithms) Floyd-Warshall for APSP (Dynamic programming)
      • Minimum spanning tree: Prim’s and Kruskal’s algorithms
      • Network flows.  Ford-Fulkerson method, augmenting flows, uses of network flow
      • NP-completeness.  Definition of P, NP, NP-hard, NP-complete.  Euler and Hamiltonian circuits; clique and vertex-cover.  Reduction proofs
      • Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
      • In general: Algorithmic analysis (best case, worst case, average case, amortized). Order notation (Big Oh, big Omega). Recursion.
    • Study guides:
      • Do concrete problems from the book and re-work problems from lecture, section, and homeworks. Suggestions of more problems from the book: Chapter 2: 2.6, 2.10. Chapter 3: 3.21, 3.22, 3.23 (a). Chapter 4: 4.1, 4.8, 4.22, 4.27, 4.28. Chapter 6: 6.2, 6.3, 6.30.
      • Selected solutions to practice problems. Please note that some of the figures end up on the last page.
      • More problems: Chapter 5: 5.1, 5.8, 5.9, 5.10, 5.11. Chapter 7: 7.1, 7.15, 7.19, 7.39. Chapter 9: 9.20, 9.34, 9.53. Ruth Anderson's homework 3.
      • Practice all the sorting and hashing algorithms. Practice topological sort, graph search, and shortest path. Practice analysis of algorithms.
      • All material from lecture up through NP Completeness is fair game. This material corresponds to: Chapters: 1, 2, 3, 4, 5, 6 (not including 6.6 and 6.7), 7, 8 (not including 8.6), and 9 (not including 9.4).
  • Midterm

    The midterm will be held during lecture on Monday, July 16. A list of topics has been posted.

Class E-Mail Lists

  • All students must sign up for the cse326-announce mailing list. You are responsible for any information posted to this list. Only the instructor and TAs are allowed to post to this list, so it should be fairly low-volume.

Office Hours

Who

When

Where

Ben Lerner

Tuesday 1045-11:45.

CSE212

Ioannis Giotis

Monday 11:00-12:00

CSE430

Gyanit Singh

Monday 11:00-12:00

CSE430

Lectures

Section

Instructor

When

Where

A

Ben Lerner

MWF   09:40-10:40   

EEB  026 

Sections

Section

When

Where

AA

Th   09:40-10:40

EEB 025

Textbook: Data Structures and Algorithm Analysis in Java 2nd Ed., Mark Allen Weiss, Addison Wesley: 2007, ISBN: 0-321-37013-9 Errata is here


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to blerner]