---

email: ceh@cs.ucf.edu

---

A schedule of lecture topics, exam dates, quiz dates and assignment due dates are provided on this web page. Check it frequently for updates and additional information.

Cheating will not be tolerated in this courses since students are expected to do their own work. However, discussing (not copying) assignments with your classmates is fine and is encouraged within the rules provided in the separate agreement that all you must read, sign and turn in to me by the end of the fourth class meeting (August 31).

Week	Topic	Chapters
1 (1 day)	Overview of course -- read chapters 1, 2 and 3 of W as a review  Java/C++ overviews Assignment #1: Problems 1.8a,b,c, 1.12.  Be complete and neat.  This is individual work.  If you have problems, see me. Turn in on Thursday, August 26.	W 1
2	More Java/C++ overviews     classes and objects (constructors)     is-a versus has-a; class versus parts hierarchy     protocols (services); levels of protection     encapsulation, polymorphism, dynamic binding, inheritance; abstract vs concrete classes     explicit pointers versus object handles     single vs multiple inheritance     genericity through interfaces and templates     argument passing     destructors and garbage collection (automatic versus user-directed) Maximum Sublist Problem (book calls it subsequence -- it's not) Order Analysis (Big-O, Omega, Theta, little-o)     (notion of witnesses c and n0)     Example: Suppose f(n) is O(g(n)), show that max(f(n),g(n)) is O(g(n)). Recursion and recurrence equations     four solutions and their analyses Assignment # 2: Problems 2.15, 2.17. Prove the correctness of Algorithm 4, Figure 2.8. This is individual work.  If you have problems, see me. Turn in on Thursday, September 2.  Assignment # 3:Diagnostic Test (completness check only). Turn in on Thursday, September 2. Programming Assignment #1: Turn in on Thursday, September 9. Write a Java or C++ program that implements all four of the maximum contiguous subsequence (sublist) algorithms shown in the text. Add instrumenting code that allows you to count the actual number of iterations and method calls performed. Analyze the results you get for values of N = 8, 32, 128 and 512, using randomly generated test values in the range [-15, 16]. Develop a table like that seen in Figure 2.13, providing a brief justification of the results you get.  Of course your compares are to based on the appropriate theoretical bounds and comparison counts, not times. Note: Most of your code is in the text and available in Java or C++.  Turn in: Source listing, analysis, floppy disk with source and executable (.cpp, .h, .exe in C++) (.java, .class and .jpr in Java.) Your name must appear in the header of each file. This is individual work.  If you have problems, see me. Help: to get random numbers //C++   #include <stdlib.h>   int r = rand() % N; // generates an integer number in range [0 and N-1] //Java   import java.util.Random;   Random random = new Random();   int r = random.nextInt(32); // generates an integer number in range [0 and N-1]	W 1,2 App. A,B
3	Proofs of correctness (usually induction or contradiction) Order Analysis (Big-O, Omega, Theta, little-o) Order analysis for parallel algorithms; time, work/cost, work/cost efficiency   parallel sort (even/odd transposition) Algorithm classifications     greedy, divide and conquer, dynamic programming    amortization ADTs:      sequences, stacks, queues, priority queues, sets, bags  Abstract representations:      lists, trees, binary trees, binary search trees, priority ordered trees, graphs  Text merges ADTs and abstract representations Data structures:      linked lists, arrays, heaps  Graph data model and competing data structures Dynamic Programming and the LCS problem Programming Assignment #2: Turn in on Thursday, September 30. Write a program in Java or C++ to solve the longest increasing subsequence problem.  This is actually posed in the text as problem 10.53.  Your program reads a sequence of n integers, and produces all longest increasing subsequences. Be sure to do this using an O(n2) algorithm (dynamic programming).  Turn in: Source listing, floppy disk with source and executable (.cpp, .exe in C++) (.java, .class and .jpr in Java.) Your name must appear in the header of each file. This is individual work. If you have problems, see me. See details on assignment#2.	W 2,3
4	List Data Model     stacks, queues, deques Discussion of problem 2.17 b -- find the minimal positive sublist (consecutive subsequence) sum     n lg n based on sort of cumulative sums (a[0] ... a[k]), k<n Discussion of programming assignment#2     applicability of Principle of Optimality to longest increasing subsequence problem Tree Data model. Binary Trees.      representations, traversals	W 3,4
5	Hurricane Floyd  More on longest increasing subsequence problem     an evil recursive solution Expression trees. Code generation. Tree data model use for abstract implementations of dictionaries.      BST; Tries Key to Diagnostic Test Sample Quiz	W 4
6	Key to Sample Quiz Balanced Search Trees (AVL Trees).     associativity and rotations     We will defer Splay Trees and B-Trees.Set model; Hashing     hash function     chaining     open addressing          sequential, linear, random, quadratic, double, virtual, extendible     use for finding a pair of equals in a sequence of random numbers Priority queue ADT, priority ordered tree (POT) abstract implementation      balanced POT (BPOT) abstract implementation Heap data structure     use for balanced trees (it's more general than just for BPOTs)     use for BPOT Heap Sort      analysis of Heapify (O(N))     use for k largest (k O(ln N) + O(N) = O(N))     we will defer variants of simple min and max heaps Java Applet related to sequence assignments     Netscape version     IE version Review for Quiz # 1 Topics and Promises	W 5, 6
7	Quiz # 1 on Tuesday, September 28 Discussion of Quiz#1 (key) Sorting	W 7
8	More on Sorting; Some additional hints for Exam#1  Exam # 1 on Thursday, October 7	W 7
9	Discussion of Exam#1 (key) Withdraw Deadline on Friday, October 15 Quick Sort and Quick Selection Set model; relations Equivalence Classes and Union/Find Problem Assignment # 4: Programming Assignment#2 could be attacked with an O(N2) algorithm to get the LIS lengths, but we discussed no bounds on how hard it was to extract all the actual subsequences of this length. Show mathematically a lower bound on this (Omega(?(N))), based on a worst case count of the number of such subsequences may occur in a sequence of length N. Now, present and analyze an algorithm to extract such subsequences, given an LIS length vector. You may either analyze the algorithm you developed for your program, come up with a new algorithm, or find one in the literature. You may use any resource you want, including up to two other class mates. Be sure to include a list of all your sources. Turn in by 4:00 PM on Tuesday, October 26. Programming Assignment #3: Turn in on Monday, November 1. Write a program in Java or C++ to compare the use of a hash table versus a "balanced" tree for finding duplicates in a text file.  The details of this assignment are found at PgmAssign3.html This is due on Monday, November 1, by 4:00 PM. (Okay, you win, I'll accept up to Monday, November 8 by 8:30 AM without lateness. But then no acceptances after that.) This is individual work. If you have problems, see me. Extra Credit Programming Assignment: This can be used to replace your grade in programming assignment#1 or programming assignment#2, or as an extra measure in calculating your midterm result. In the latter case, this will count for up to 18 percent of your Q+E grade, reducing the weight of the lower of your quiz or midterm by the same percentage. In effect, this makes it possible to have a bad test count for only 20% of the combined quiz/midterm grade. The task is to take the "Better Quick Sort" that I presented in the notes (pages 176-178) and the Quick Sort from the text, and create an even better Quick Sort that combines ideas from both. As a first step implement (in effect copy) these solutions. Develop a main program that exercises these with large randomized and specialized data, comparing their performances. Now, add into the mix your version, hopefully based upon what you learned in the previous experiments. Rerun your experiments and draw appropriate conclusions. Write all this up with comments about the relative strengths and weaknesses of all three approaches. Turn in a disk with all your code (source and executable), analysis documents, and any instructions we need to replicate your experiments. Turn in by 4:00 PM on Monday, November 8.	W 7,8
10	Relational data model     complexity analysis; algebraic simplifications	W 8, Notes
11	Graph Model: various data structures Connected components and partitions Spanning trees (Kruskal's versus Prim's algorithm) Proofs of correctness of	W 9
12	Parallelization of Prim's Algorithm Topological sort Shortest path problems   All pairs shortest path Proof of correctness for Floyd's algorithm	W 9,10.3.4
13 (1 day)	Depth first search Scheduling Problems Holiday on Thursday, November 11 Programming Assignment #4: Turn in on Friday, December 3 at 4:00PM. Write a program in Java or C++ to read in a graph and do all sorts of wonderous stuff to and with it.  The details of this assignment are found at PgmAssign4.html This is individual work. If you have problems, see me.	W 9.6.1, 9.6.4, 9.7,10.1.1 Notes
14	More Scheduling Sample Quiz#2 Review for Quiz#2 Quiz#2 on Thursday, November 18
15 (1 day)	Revisit Quick Sort analysis More depth first search Thanksgiving on November 25	W 9.4,9.6
16	Cocke-Kasami-Younger (CKY) Parser   O(N3) recognizer for arbitrary Chomsky Normal Form Grammar Distributed computing Networked programming; remote method invocation; JavaSpace ; Jini Discussion of Quiz#2 (key) Review for Final Exam	PPT Notes
Final	December 7, 7:00AM-9:50AM