back to cs203-syllabus

CS203 - Teaching Material - Winter 2007

Lectures

  1. 1/2/07: Recursion. Method call stack. Examples: Fibonacci numbers. Exponentiality of the recursive solution. Memoization. A closed formula for the Fibonacci numbers.

  2. 1/4/07: Binary representation of integers: conversions and 2-complement. Length of the representation of an integer number. Robustness: estimation of the length of the binary representation of the nth Fibonacci Number. Analysis of the complexity of the recursive solution to the Fibanacci problem. The class BigInteger. Timing Java applications. Experimental analysis.

  3. 1/9/07: Backtracking Algorithms: generating permutations and binary sequences.

  4. 1/11/07: Data Structures. Specification and Implementation. Java interfaces and Java classes. The Stack Adt. Array implementation and Linked List implementation. Parameter estimation: the Least Squares Method (LS).

  5. 1/16/07: The Adt Queue. Circular Buffers. Linked Lists and Doubly Linked Lists. Analysis of Fibo2 and Fibo3.

  6. 1/18/07: Sorting in quadratic time: SelectionSort, InsertionSort and BubbleSort. Sorting in nlogn time: MergeSort.

  7. 1/23/07: PriorityQueues. Heap implementation and its analysis. Generating random permutations.

  8. 1/25/07: PriorityQueues. HeapSort. Randomized QuickSort.

  9. 1/30/07: More on the LS method. Construction of package LeastSquaresEstimator. Wrapper classes. Autoboxing and autounboxing. Binary Trees and Binary Search Trees.

  10. 2/1/07: Generic types and generic methods.

  11. 2/6/07: More on generic methods. Binary Search Trees (BSTs). Insertion, deletion and traversals (preorder, postorder and inorder). TreeSort. Height of a Binary Tree.

  12. 2/8/07: Red-Black trees. Analysis of the depth. Insertion.

  13. 2/13/07: The Java Collections Framework. Interfaces Queue, List, Set and Map. Classes HashSet, HashMap, TreeSet, TreeMap, PriorityQueue, LinkedList, ArrayList. Overriding consistently methods equals and hashCode. Interface Iterable and iterators.

  14. 2/15/07: Hashtables. Use of HashSet and HashMap: how to override hasCode. Use of TreeSet and TreeMap: implementing interface Comparable. Designing iterators.

  15. 2/20/07: Exercises.

  16. 2/22/07: MT.

  17. 2/27/07: Review of MT. More on PJ4.

  18. 3/1/07: Introduction to multithreading. States of a thread.

  19. 3/6/07: Thread Executors. Need for synchronization. Deadlock and Starvation. Locks and Condition Variables. The producer-consumer problem.

  20. 3/8/07: Classes ServerSocket and Socket. Designing multithreaded client-server applications.

Announcements

  1. 02/22/07: Midterm Examination. Topics: Recursion, Data Structures, Collections, Generics.

Packages


Projects

  1. cs203-w07-pj1. Due Thursday, January 11, 2007, at the beginning of lab class.
  2. cs203-w07-pj1-2. Due Thursday, January 18, 2007, at the end of lab class.
  3. cs203-w07-pj2. Due Tuesday, Feb 6, 2007, at the end of lab class. (Extended to Thu, Feb 8).
  4. cs203-w07-pj3. Due Thursday, Feb 15, 2007, at the end of lab class.
  5. cs203-w07-pj4. Due Thursday, Mar 1, 2007, at the end of lab class. Extended to March 6, 2007.

CSNS - Computer Science Network Services

Assignments and exams should be uploaded by the due date through the CSNS - Computer Science Network Services website. If you have never used this system before then follow the instructions for students.