COP3503HCS2 Honors Fall 2011 |

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)

**Goals, expectations and rules of the course**- A bit of an insight into what I do
- Some fun with parallelism

- Mathematics review
- Order analysis
- Maximum Subsequence Sum Problem
- First look at Subset Sum
- 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**

- More algorithm analysis
**Discussion of searching****Hashing**- 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).**

- Code generation using tree height associated with an expression tree
- AVL Trees (review)

- B-Trees
**Priority Queues (Heap data structure)**

- Disjoint Sets
- Union/Find

**Programming Assignment #2**

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

**Sorting**

- Oblivious Compare Exchange metatheorem -- Notes pages 69-72
- Metatheories are sometimes elusive but always rewarding: Rice's Theorem at a glance

- Parallel sorting: Shearsort -- Notes pages 73-86
- Weak Heaps

- Parallel sorting: Revsort -- Notes pages 87-93
- QuickSelection
- Bitonic Sort -- Notes pages 94-100
- Project Discussions
- Sample Quiz#1

- Review for Quiz#1

- Graphs
- Search algorithms on graphs (DFS, BFS)
- Topological sort (DFS)
- Sample Quiz#1 Key

- Quiz#1
- Tour of SREAL

- Greedy Algorithms
- Prim's Algorithm (Greedy)

- Kruskal's Algorithm (Greedy)
- Dijkstra's Algorithm (Greedy)
- Hamiltonian Path; Hamiltonian Cycle
- Travelling Salesman Problem (minimum cost tour)

- Decision vs Optimization Problems (achieving a goal vs achieving min cost)

- Polynomial == Easy; Exponential == Hard
- Polynomial reducibility
- Satisfiability of Booolean expressions as a potentially hard decision problem
- P, NP, NP-Hard, NP-Complete
- P =? NP

- Satisfiability as the first NP-Complete problem
- Quiz#1 key

- SAT is polynomial reducible to (<=
_{P}) 3-SAT - SAT3 <=
_{P}SubsetSum - SubsetSum =
_{P}Partition - Network Flow
- Maximum flow (Ford-Fulkerson)

- More DFS applications including data flow analysis
- Recognizing cycles (loops) via DFS

**More greedy Algorithms****Scheduling problems introduced**- 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****
**

- Scheduling problems (fixed number of processors, minimize final finishing time) Notes pages 132-141

- Greedy heuristics

- Scheduling anomalies, level strategy for UET trees, level strategy for UET dags

- Bin packing (fixed capacity, minimize number of bins)
- Notion of NP Completeness
**Huffman codes**- Topics for Midterm

- Review Questions for Midterm
- Midterm

**Note: 10/27 is the Withdraw Deadline**

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

- Dynamic Programming
- Cocke-Kasami-Younger (CKY)
- LCS
- Edit distance
- Floyd-Warshall (actually done earlier)

- Project proposal discussions
- Knapsack (using dynamic programming with changed parameters, n*W versus 2^n)

- Hard problems and heuristic algorithms

- Amortization
- Randomized Algorithms
- Las Vegas and Monte Carlo

- Project Discussions -- lots of them
- Midterm Key

**String Matching**

**Undecidability (fun topic)**

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

**Final Exam Topics****Sample Final (Key)**- Project Presentations

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

- Review Session in HEC-356

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