back to cs203-syllabus

CS203 - Teaching Material - Winter 2006

Lectures

  1. 1/03/06: Recursion. Method call stack. Examples: Fibonacci numbers and factorials. A closed formula for the Fibonacci numbers.

    Textbook: 15.1-15.5



  2. 1/05/06: Length of the binary representation of integers. Analysis of the Fibonacci algorithms for large integers. BigInteger and BigDecimal. Exponentiality of the recursive solution. Memoization.


  3. 1/10/06: Backtracking algorithms: permutations and subsets. Sorting in quadratic time: BubbleSort, InsertionSort, SelectionSort. Sorting in nlog n time: MergeSort. In-place and not in-place methods.


  4. 1/12/06: Adt's: specification and implementation. Use of Java interfaces. The Queue Adt. Array and Linked List implementation. DEQueues.


  5. 1/17/06: Stacks. Binary trees. Inorder, preorder and postorder traversals. Operators trees. Evaluation of operators trees using a stack. Wrappers. Auto-boxing and auto-unboxing.


  6. 1/19/06: Computation of the square root of a number. Newton's method. Evaluation of arithmetic expressions: designing a top-down predictive recursive parser.


  7. 1/24/06: Programming with Generics: generic types and type variables. Reimplementation of LinkedStack and ArrayStack. Using stacks to evaluate operators trees. Building operators trees.


  8. 1/26/06: Programming with Generics: generic methods and wildcards. Algorithms: evaluation of polynomials and the Horner's method.


  9. 1/31/06: An overview on the Java Collections Framework. Interfaces Collection, Set, List, Map and Queue. Classes ArrayList, LinkedList. Hashtables. Classes HashSet, HashMap. Overriding methods equals and hashCode. Binary Search Trees. Classes TreeSet and TreeMap. Use of Comparators. Implementing interface Comparable. Lab: review of pg2.


  10. 2/2/06: Use of HashMap. Developing a scientific calculator.


  11. 2/7/06: Class Class. Collections and Iterators. The for-each loop statement. TreeSet and the Treesort algorithm.


  12. 2/9/06: Class PriorityQueue. Sorting using Priority Queues. More on the for-each loop statement: implementing interface Iterable. The BallotBox Adt.


  13. 2/14/06: Preparation to the test. Computing the GCD using the Euclidean algorithm. Summing recursively the elements of an array.


  14. 2/16/06: Midterm.


  15. 2/21/06: Concurrent programming and multithreading. CPU scheduling: time-sharing and Round-Robin. The Producer-Consumer application. Synchronization. The critical section problem. States of a thread. Threads in Java. Using Lock objects and Condition objects.


  16. 2/23/06: Client-Server applications in Java. Designing a multithreaded Server. The extended BallotBox Project.


  17. 2/28/06: Review of the Midterm Examination.


  18. 3/2/06: Development of the BallotsCollection project using HashMap and TreeSet.


  19. 3/7/06: Development of the Multithreaded Internetworked BallotsCollection project.


  20. 3/9/06: Review of the Multithreaded Internetworked BallotsCollection project and final recap. Topics for the final exam: Data Structures in Java, Binary Search Trees, Backtracking, recursive programming, Multithreading and Synchronization.

Packages

Lab Projects

  1. 1/5/06: cs203-w06-pg1-2 due on Th, January 12, 2006, before lab class.
  2. 1/12/06: cs203-w06-pg2 due on Th, January 19, 2006, before lab class.
  3. 1/19/06: cs203-w06-pg3-2 due Th, February 2, 2006, before lab class.
  4. 1/26/06: cs203-w06-pg4-2 due Th, February 23, 2006, before lab class (updated 2/9/06).
  5. 2/9/06: cs203-w06-pg5 due Th, February 23, 2006, before lab class .
  6. 2/23/06: cs203-w06-pg6 due Th, March 9, 2006, before lab class .

Important Deadlines