---

email: charles.e.hughes@knights.ucf.edu  Use Subject COP3503H

---

Lectures: MW 11:30AM to 12:20PM), HEC-110; 42 class periods, each 50 minutes long.
Labs: None, but our Friday lectures will often be very different than the MW classes.
Go To Week 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Instructor: Charles Hughes; Harris Engineering Center HEC-247C; 823-2762 (use e-mail; I spend most of my time in my lab)
Office Hours: MW 9:45AM-10:45AM; M 5:30-6:30; and by appointment
GTA: None

Text: Data Structures and Algorithm Analysis in Java, Second Edition by Mark Weiss
ISBN-10: 0321370139

Prerequisites: COP3330 (OO Programming); COT3100 (Intro to Discrete Structures)

Web Pages:
Base URL: http://www.eecs.ucf.edu/courses/cop3503h.fall2011
Base for Code from Text: http://www.eecs.ucf.edu/courses/cop3503h.fall2011/CodeWin
Course Wiki: Soon to come

Assignments: 5 to 8, one of which is the major project. Each assignment will have a due date and 10% will be subtracted for each day late (up to 2 days late, 20% off; more than two days late results in no credit)

Exams: Two quizzes; a midterm and a final

Material: I will draw heavily from text by Weiss. You are responsible for material discussed in notes and in in-class discussions. Not all of this is addressed in text. I highly recommend attending class, interacting with me and listening very carefully when I say a topic is important to me; hint, hint about exam questions ;-)

Important Dates: Labor Day -- September 5; Quiz -- September 28; Midterm Exam -- October 21 (Tentative); Withdraw Deadline -- October 27; Final -- December 7, 10:00AM-12:50PM
Quiz will precede midterm and be warm-up with feedback.

Evaluation (Tentative):
Quizzes -- 10% each
Mid Term -- 15%
Final Exam -- 25%
Programming and Other Assignments -- 20%
Final Programming Project -- 25%
Wild Card -- 5% (used to increase weight of what you did well on)
Grading will be  A >= 90%, B+ >= 87%, B >= 80%, C+ >= 77%, C >= 70%, D >= 60%, F < 60%. (minuses may be used in some cases)

1. Goals, expectations and rules of the course
2. A bit of an insight into what I do
3. Some fun with parallelism
   
4. Mathematics review
5. Order analysis
6. Maximum Subsequence Sum Problem
7. First look at Subset Sum
8. Amortization, e.g., sorting for subset sum or searching
   

   Assignment #1

   Problems 1.8a,b,c, 1.12.  Be complete and neat.  This is individual work.  If you have problems, see me.
   

   Due: Class time on Friday. August 26

1. More algorithm analysis
2. Discussion of searching
3. Hashing
4. Trees (review)
   

   Assignment #2

   Problem 2.15.  Prove the correctness of Algorithm 4, Figure 2.8. Be complete and neat.  This is individual work.  If you have problems, see me.
   

   Due: Class time on Friday. September 2
   

   Programming Assignment #1

   Write a Java program that implements all four of the maximum contiguous subsequence 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. You must turn in the source and your analysis document.
   Note: Most of your code is in the text  This is individual work.  If you have problems, see me.
   //  Random numbers can be gotten as follows.
     import java.util.Random; 
     Random random = new Random(); 
     int r = random.nextInt(32); // generates an integer number in range [0 and 31]
   

   Due: September 12 at 11:59PM (I will set things up for on-line submission).
   

1. Code generation using tree height associated with an expression tree
2. AVL Trees (review)
   
3. B-Trees
4. Priority Queues (Heap data structure)
   
5. Disjoint Sets
6. Union/Find

Programming Assignment #2

Write a Java program to implement the ADT (class) Partition. Details are at Assignments/Programming Assignment#2.

1. Sorting
   
2. Oblivious Compare Exchange metatheorem -- Notes pages 69-72
3. Metatheories are sometimes elusive but always rewarding: Rice's Theorem at a glance
   
4. Parallel sorting: Shearsort -- Notes pages 73-86
5. Weak Heaps
   

1. Parallel sorting: Revsort -- Notes pages 87-93
2. QuickSelection
3. Bitonic Sort -- Notes pages 94-100
4. Project Discussions
5. Sample Quiz#1
   
6. Review for Quiz#1
   

1. Graphs
2. Search algorithms on graphs (DFS, BFS)
3. Topological sort (DFS)
4. Sample Quiz#1 Key
   
5. Quiz#1
6. Tour of SREAL
   

1. Greedy Algorithms
2. Prim's Algorithm (Greedy)
   
3. Kruskal's Algorithm (Greedy)
4. Dijkstra's Algorithm (Greedy)
5. Hamiltonian Path; Hamiltonian Cycle
6. Travelling Salesman Problem (minimum cost tour)
   
7. Decision vs Optimization Problems (achieving a goal vs achieving min cost)
   
8. Polynomial == Easy; Exponential == Hard
9. Polynomial reducibility
10. Satisfiability of Booolean expressions as a potentially hard decision problem
11. P, NP, NP-Hard, NP-Complete
12. P =? NP
    
13. Satisfiability as the first NP-Complete problem
14. Quiz#1 key

1. SAT is polynomial reducible to (<=_P) 3-SAT
2. SAT3 <=_P SubsetSum
3. SubsetSum =_P Partition
4. Network Flow
5. Maximum flow (Ford-Fulkerson)
   
6. More DFS applications including data flow analysis
7. Recognizing cycles (loops) via DFS
   
8. More greedy Algorithms
9. Scheduling problems introduced 
10. Partition and scheduling problems

    Programming Assignment #3

    Write a Java program to implement Dijkstra's shortest path algorithm.  You must  use a min heap and the cost up updating  a node in the heap must be  constant time.  Moreover, you must provide unit testing using either JUnit or TestNG. A nice starting point is the algorithm and discussion in  http://renaud.waldura.com/doc/java/dijkstra/. The issue here is that he has a linear time update as he looks through the priority queue to be sure an updated node is not already present. That is not acceptable in your implementation. The Notes discuss a data structure to circumvent this.

    Due: October 24 at 11:59PM.
    

Week#9: (10/17, 10/19, 10/21 (Midterm)) -- Chapter 10

1. Scheduling problems (fixed number of processors, minimize final finishing time) Notes pages 132-141
   
2. Greedy heuristics
   
3. Scheduling anomalies, level strategy for UET trees, level strategy for UET dags
   
4. Bin packing (fixed capacity, minimize number of bins)
5. Notion of NP Completeness
6. Huffman codes
7. Topics for Midterm
   
8. Review Questions for Midterm
9. Midterm
   
10. Note: 10/27 is the Withdraw Deadline

1. Database operations Notes, pages 142-156
2. Divide and Conquer
3. Integer multiplication
4. Tromino tiling
5. Closest points
6. Subset sum (recursively)
7. Doubly Logarithmic Max (d&c + amortization) Notes, pages 157-161
   

1. Dynamic Programming
2. Cocke-Kasami-Younger (CKY)
3. LCS
4. Edit distance
5. Floyd-Warshall (actually done earlier)
   

1. Project proposal discussions
2. Knapsack (using dynamic programming with changed parameters, n*W versus 2^n)
   
3. Hard problems and heuristic algorithms

1. Amortization
2. Randomized Algorithms
3. Las Vegas and Monte Carlo
   
4. Project Discussions -- lots of them
5. Midterm Key
   

Week#14: (11/21, 11/23)

1. String Matching
   
2. Undecidability (fun topic)
   

Week#15: (11/28, 11/30, 12/2) -- Review; Presentations

1. Final Exam Topics
2. Sample Final (Key)
3. Project Presentations

Week#15: (12/5, 12/7) -- Review & Final

1. Review Session in HEC-356
   

Final Exam; Wednesday, December 7; 10:00AM-12:50PM in HEC-110