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