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
Text: Data Structures and Algorithm Analysis in Java, Second Edition by Mark Weiss
Prerequisites: COP3330 (OO Programming); COT3100 (Intro to Discrete Structures)
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.
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)
Assignment #1Problems 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
Assignment #2Problem 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 #1Write 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.
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).
Programming Assignment #2
Write a Java program to implement the ADT (class) Partition. Details are at Assignments/Programming Assignment#2.
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.
Week#9: (10/17, 10/19, 10/21 (Midterm)) -- Chapter 10
Week#14: (11/21, 11/23)
Week#15: (11/28, 11/30, 12/2) -- Review; Presentations
Week#15: (12/5, 12/7) -- Review & Final
Final Exam; Wednesday, December 7; 10:00AM-12:50PM in HEC-110