COP3503H
CS2 Honors

Fall 2011

U.C.F.

Charles E. Hughes
Electrical Engineering and Computer Science
University of Central Florida


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)


Week#1: (8/22, 8/24, 8/26) -- Chapter 1.2; 2.1-2.4.3; Syllabus; Parallel Sort and Max
  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


Week#2: (8/29, 8/31, 9/2) -- Chapter 2.4.4-2.4.6; Chapter 4.4, 4.7; You should review Chapter 3 and  4.1-4.3
  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).


Week#3: (9/7, 9/9) -- Chapters 5, 6, 8
  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.
Due: September 21 at 11:59PM.


Week#4: (9/12, 9/14, 9/16) -- Chapter 7
  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


Week#5: (9/19, 9/21, 9/23) --   Chapter 7
  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

Week#6: (9/26, 9/28 (Quiz#1), 9/30) --  Chapter 9
  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


Week#7: (10/3, 10/5, 10/7) -- Chapter 9
  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


Week#8: (10/10, 10/12, 10/14) -- Chapter 9
  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

Week#10: (10/24, 10/26, 10/28) -- Chapter 10; WITHDRAW DATE IS THURSDAY, OCT. 27
  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


Week#11: (10/31, 11/2, 11/4) -- Chapter 10 
  1. Dynamic Programming
  2. Cocke-Kasami-Younger (CKY)
  3. LCS
  4. Edit distance
  5. Floyd-Warshall (actually done earlier)



Week#12: (11/7, 11/9) -- Chapter 9 and lots of notes
  1. Project proposal discussions
  2. Knapsack (using dynamic programming with changed parameters, n*W versus 2^n)
  3. Hard problems and heuristic algorithms



Week#13:  (11/14, 11/16, 11/18) --  Chapter 11
  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




UCF (Charles E. Hughes)  -- Last Modified December 5, 2011