Fall 2014

COURSE TIMES:

• Section 1: Tue and Thu 12:30 - 1:45 PM in ECS-141.

PREREQUISITES: COP-3530 Data Structures You must drop the course if you haven't gotten a C or better in Data Structures.

INSTRUCTOR: Prof. Mark Allen Weiss

OFFICE HOURS: You are free to stop by my office ECS-353 any time you can find me. My office hours represent a time when I am (more or less) guaranteed to be available. This semester this is Tuesday and Thursday 11:00 AM - 12:15 PM. My office phone is FIU-2036.

On other days, and after hours, you are better off trying email: . You will generally get an answer within 10 minutes of my reading the message.

I have three standing rules:

1. I will not debug programs. Debugging is part of the assignment. If you are very confused about some compiler error messages, you can ask, but read the error message carefully and ask as a last resort, not a first. Also, check the announcements page, since I occasionally post answers to common problems reported to me.
2. If you miss class, get the class notes from a classmate or check the lectures page. Do not ask me what you missed.
3. I am very unsympathetic toward questions that are asked on the assignment due date. You should be done by then.

LANGUAGES AND PLATFORMS: Programming assignments should be done in Java 8.

TEXT: The course text is the same as in COP-3530: Data Structures and Algorithm Analysis in Java (M. Weiss) There are no other texts required or recommended.

COURSE GRADING: Grades will be based on six assignments (generally assignments), quizzes based on the assignments, one midterm exam (graded prior to the drop date), and a final examination. The midterm is worth 2 assignments, the final is worth 2 assignments, and each quiz is worth the same as an assignment. I will drop both the lowest and highest assignment and the lowest and highest quiz. So the final average will be based on 4 assignments, 4 quizzes, and 2 exams, and assignments, quizzes, and exams are each worth one-third of your grade. If you miss an assignment or quiz, that will be the one that is dropped. The scale is as follows: A is 90% or higher, B is 80% or higher, and C is 70% or higher. + or - is done at 3.33% intervals, so A- is 86.67% or higher, B+ is 83.33%, etc. C- is 66.67% or higher. I reserve the right to change the method of assigning grades, including changing the number of assignments or exams, but in no case will a curve be applied.

ASSIGNMENTS: Assignments are due at the start of class and must be submitted via moodle. Your submission must be a ZIP file (please use zip, not rar format), named as y_xxxxxxx.zip (where y is the assignment # (ranging from 1-6) and xxxxxxx is your seven digit panther IDi); the file should include source code and sample output. I will generally specify what the data is. Your work must be your own, and you must attest to this in a comment that begins each assignment. See also FIU's Code of Academic Integrity. You can assume that assignments will be run through software that detects inappropriate collaborations.

The assignments and if appropriate, input data, will be placed here.

COURSE OUTCOMES

• Be familiar with standard algorithm techniques including dynamic programming, greedy algorithms, divide and conquer, backtracking, and randomized algorithms
• Be familiar with some graph algorithms, computational geometry algorithms, numerical algorithms, combinatorial optimization algorithms, and string algorithms
• Be able to synthesize the knowledge of algorithmic strategies to analyze and design solutions to new and challenging problems

COURSE OUTLINE (OPTIMISTIC):

• Graph Algorithms
  • graph theory
  • topological sorts
  • shortest paths
  • network flows and bipartite matching
  • minimum spanning trees and disjoint sets
  • depth first and breadth first search
• Greedy Algorithms
  • Huffman Codes
  • Approximate Bin Packing
  • Simple Job Scheduling
• Divide-And-Conquer Algorithms
  • Master Theorem
  • Multiplication
  • Linear-time Selection
  • Closest Points
• Dynamic Programming
  • edit distance
  • string pattern matching
  • reconstructing paths
  • optimization application
• Randomized Algorithms
  • Introduction to random numbers
  • Randomization and hashing
  • Skip Lists and Treaps
  • Number Theory
  • prime numbers
  • divisibility
  • modular arithmetic applications
  • congruences
  • number theoretic libraries
• Backtracking
  • constructing subsets
  • constructing permutations
  • pruning search
  • puzzle solving
• String Algorithms
  • Knuth-Morris Pratt, Rabin-Karp, Boyer-Moore
  • Suffix trees
  • Regular expressions
  • String and pattern matching libraries
• Combinatorial Optimization
  • gaussian elimination
  • linear programming