CSE 326

Summer 2000

Calendar

Up 

Topic dates are likely to be adjusted as the quarter progresses. The exact reading assignments will also be refined.  Check back here to keep current. Please note that there is a certain amount of skipping around among chapters.

Last updated 08/16/00 10:29 PM

Week # Monday Wednesday Thursday Friday
1.  

June 19

Lecture #1 slides

Welcome to 326!

C++ topics

Textbook: Chapter 1

Lecture #2 slides

C++ (concluded)

Asymptotic analysis (beginning)

2

Welcome

Using UNIX

C++ topics

Lecture #3 slides

Asymptotic analysis (cont.)

2

2.  

June 26

Lecture #4. 

Asymptotic analysis (concluded)

Lists

3.1-3.2

#5 Stacks and queues

3

  #6. Tree concepts

4

3.  

July 3

#7. Dictionary ADT.  Binary search trees

4

#8 Deletion in binary search trees

4

  Priority queues and heaps

6

4.  

July 10

#9. AVL trees

Splay trees

#10. Hash table concepts

Collisions in hash tables

5

  #11. Extendible hashing

The Poisson distribution

5; Handouts

5.  

July 17

Test #1 #13 Hashing wrap-up

Sorting: Insertion Sort and Shell Sort

5, 7

Quicksort and Quickselect #14 Sorting: Heap Sort.  Quicksort

7

6.  

July 24

#15. Sorting : Mergesort

External sorting.

7

External sorting.

Sorting wrap-up.

Graph terminology

9 through 9.1

  Graph concepts

Topological sort

Shortest paths.  Dijkstra's algorithm

9.2-9.4

7.  

July 31

Network flow.

 

9.4

#18. Spanning trees: Prin's and Kruskal's algorithms. Depth-first search   #19. Euler and Hamiltonian paths. Directied graphs.  Biconnectivity  Activity and event graphs
8.  

Aug 7

#20. 

   NP-completeness

9

Job scheduling and Bin Packing.

10.1

#21.

Huffman Codes

10.1

  #22. Divide and conquer analysis.

10.2

Dynamic programming concepts.

10.3

9.  

Aug 14

#23. Optimal binary search tree construction

10

#24. All pairs shortest path.  Disjoint sets; union/find

8

  Test #3 (Final Exam)