Class Log

----------------------- Thursday, August 29 -----------------------

Introduction

Go over syllabus
Go over academic conduct policy
Go over project late submission policy

----------------------- Tuesday, September 3 -----------------------

Java Review

Java is compiled and interpreted.
Object-oriented features of Java
Comparison of Java with other programming languages
Generic classes in Java

----------------------- Thursday, September 5 -----------------------

Asymptotic Analysis

Euclid's algorithm with proof of correctness and running time analysis
Big-Oh notation

----------------------- Tuesday, September 10 -----------------------

ANT & CVS

Compiling Java programs in the command line: Ant.zip or Ant.tar.
Demoed CVS

Project 0 assigned & discussed.
Project submission process explained.

----------------------- Thursday, September 12 -----------------------

More Asymptotic Analysis

More Big-Oh notation
Ω( f (n) ) and Θ( f (n) )
Summations, estimating summations

Homework 1 assigned.

----------------------- Tuesday, September 17 -----------------------

Expanding arrays

Amortized running times

Linked Lists

Implementation
Dummy headers
Running times

Discussed Project 1

----------------------- Thursday, September 19 -----------------------

Homework 1 collected.

Homework 2 assigned.

More Project 1 discussion

Doubly-Linked Lists

ArrayList vs LinkedList (from Java Collections API)

Running times compared
Iterators and running times

----------------------- Tuesday, September 24 -----------------------

Queues

Circular Buffers

Stacks

Postfix arithmetic expressions
Evaluating postfix expressions
Converting infix expressions to postfix

----------------------- Thursday, September 26 -----------------------

Binary Search Trees

Design goals
In-class OOP design

----------------------- Tuesday, October 1 -----------------------

Exam 1 topics

Binary Search Trees

Review in-class OOP design
Compare in-class OOP design with textbook implementation
Running times

----------------------- Thursday, October 3 -----------------------

Exam 1

----------------------- Tuesday, October 8 -----------------------

Discussed Project 2

Red-Black Trees

Definition
Bounding the height of a red-black tree

----------------------- Thursday, October 10 -----------------------

Discussed Homework 3.

Red-Black Trees, continued

Rotations
Cases for insert
Cases for delete

----------------------- Tuesday, October 15 -----------------------

Red-Black Trees, wrap up

Priority Queues & Heaps

Array implementation of heap

----------------------- Thursday, October 17 -----------------------

Discussed Homework 4.

Homework 3 collected.

Heaps, continued

implementing insert and deletemin
speeding up

----------------------- Tuesday, October 22 -----------------------

Discussed Project 3

Other Types ofTrees

----------------------- Thursday, October 24 -----------------------

Homework 5 assigned.

Homework 4 collected.

B-Trees

----------------------- Tuesday, October 29 -----------------------

Hashing

Separate Chaining
Linear probing, quadratic probing, double hashing

----------------------- Thursday, October 31 -----------------------

Homework 5 collected.

Hashing

Converting a string to a numeric key
Universal hashing
Perfect hashing

----------------------- Tuesday, November 5 -----------------------

Hashing, wrap up

Exam 1 review

----------------------- Thursday, November 7 -----------------------

Exam 2

----------------------- Tuesday, November 12 -----------------------

Threads

Looked over simple threaded programming examples:
Looked over Prof. Banerjee's slides on threads (part1): LectureThreadFall10.pptx

----------------------- Thursday, November 7 -----------------------

Homework 6 assigned.

Threads, continued

Matrix multiplication:
Java VM with time slicing
Does Java VM prioritize threads?

----------------------- Tuesday, November 19 -----------------------

Threads, continued

Interrupts
Reentrant code
Thread safety
Reentrant vs Thread safe

----------------------- Thursday, November 21 -----------------------

Homework 6 collected.

Threads, continued

Looked over Producer-Consumer examples.
Looked over Prof. Banerjee's slides on threads (part2): LectureThreadFall10part2.pptx
Discussed concurrent heaps, briefly

----------------------- Tuesday, November 26 -----------------------

Exam 2 returned.

Disjoint Set Union

Set union is hard
Disjoint sets represented using parent pointers
Union-by-size and Union-by-height
Path compression
log*( n ) is a very slowly growing function.

----------------------- Thursday, November 28 -----------------------

Thanksgiving Break

----------------------- Tuesday, December 3 -----------------------

Discussed Project 5

Kruskal's Algorithm

Defined minimum spanning tree
Example
Implementation using min heap and disjoint set data structure
Running time analysis

----------------------- Thursday, December 5 -----------------------

More Project 5 discussion.

Kruskal's Algorithm (continued)

Greedy algorithms
Proof that Kruskal's algorithm obtains minimum spanning tree.

SCEQ's distributed

----------------------- Tuesday, December 10 -----------------------

Class canceled due to snow. (UMBC closed until 1pm.)

----------------------- Upcoming Topics -----------------------

Final Exam