Syllabus

Course Number and Title: COT5405 - 1100X

Course Catalog Description: This course is a graduate level survey of concepts, principles and techniques related to designing and analyzing algorithms. Students will become acquainted with both the strengths and limitations of various techniques like Greedy Approach, Divide and Conquer, Dynamic Programming, Branch and Bound, etc. This course provides 3 credit hours.

Course Pre-requisties: COP 3530 (Data Structures and Algorithms: arrays, linked lists, stacks, queues, priority queue, heap, binary tree and search trees) and COT 3100 (Applied Discrete Structures: set theory, proofs by induction and contradiction, graphs, trees, permutations, combinations, and algebraic systems).

You are also supposed to know the difference between comparison-based sorting and non-comparison-based sorting. Please refer to wikipedia or the CLR book (if you have it) for a nice treatise of the latter.

Mathematical pre-requisites: One must be familiar with the following:

Elementary calculus, especially basic differentiation and integration
Concepts of Limits and asymptotic graphs, L'Hospital's rule
Arithmatic, Geometric & Harmonic Progressions, their summations, summations of progressions involving both Arithmatic and Geometric series, summation using Integration
Rudimentary probability

Course Objectives:

Please refer to the main course page.

Instructor:

Dr. Sanjay Ranka, Professor, Computer and Information Science and Engineering department, University of Florida

Office hours: Tuesday (1-2pm), Thursday (2-3pm) or by appointment
Office: E432 CSE Bldg, University of Florida, Gainesville, FL 32611-6120
E-mail: ranka AT cise.ufl.edu
Phone: (352) 505 1553
Website: http://www.cise.ufl.edu/~ranka

Teaching Assistants:

TBA
Office: CSE E309.

Meeting Time: Tuesday 4th period (10:40 AM - 11:30 AM), Thursday 3rd-4th period (9:35 AM - 11:30 AM) at NEB 100.

Material and Supply Fee: None.

Textbook:

Required: Computer Algorithms by Horowitz, Sahni and Rajasekaran, Computer Science Press (1997) ISBN 0-7167-8315-0 (-8316-9)
Reference: Algorithm Design, Jon Kleinberg and Eva Tardos, Addison Wesley, ISBN 0-321-29535-8.

Topics to be covered:

Foundations (Chapter 1): Review of mathematical induction, asymptotic notations, solving recurrences, models of computation and randomization.
Algorithm Design Paradigms and Advanced Analysis Techniques (Chapters 3-6): divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis, Search and traversal.
Reductions and NP-Completeness (Chapter 11): reductions, complexity classes, and nondeterminism and Cook's theorem.
Additional Topics (if time permits)

Grading:

Homework Assignments 4 : 10% of the letter grade
In-class Exams (2): 60% of the letter grade
Final Exam : 30% of the letter grade
Letter grade will be based on a curve

Grading Scale: The final grades will be curved.

Undergraduate students, in order to graduate, must have an overall GPA and an upper-division GPA of 2.0 or better (C or better). Note: a C- average is equivalent to a GPA of 1.67, and therefore, it does not satisfy this graduation requirement. Graduate students, in order to graduate, must have an overall GPA of 3.0 or better (B or better). Note: a B- average is equivalent to a GPA of 2.67, and therefore, it does not satisfy this graduation requirement. For more information on grades and grading policies, please visit: https://catalog.ufl.edu/ugrad/current/regulations/info/grades.aspx

Makeup Policies: no makeup exams (Exceptions may be made for medical emergencies).

Course Policies:

All regrade requests MUST be initiated within 1 week of returning back the graded homeworks / exams.
If you request for a regrade, not only the problem in doubt, but also all problems on your homework / exam may be regraded at the discretion of the TA or the instructor.
Attending lectures is mandatory - however there will be no attendance taken.
While you may discuss general ideas with others, when you actually write them, you should do so alone. The actual written solutions to the homework assignments should be entirely your own and individual work. Also, you are expected to indicate on your homework the names of those people with whom you discussed the homework.
You will be asked to sign the following statement on all exams in this course: On my honor, I have neither given nor received unauthorized aid on this examination.

Honesty Policies: All students admitted to the University of Florida have signed a statement of academic honesty committing themselves to be honest in all academic work and understanding that failure to comply with this commitment will result in disciplinary action. This statement is a reminder to uphold your obligation as a UF student and to be honest in all work submitted and exams taken in this course and all others.

Read Academic Honesty Guidelines as posted by Dean of Students Office. All academic dishonesty cases will be handled through the University of Florida Honor Court procedures as documented by the Office of Student Services, P202 Peabody Hall. You may contact them at 392-1261 for "Student Judicial Process: Guide for Students" pamphlet.

Accommodation for Students with Disabilities: Students Requesting classroom accommodation must first register with the Dean of Students Office. That office will provide the student with documentation that he/she must provide to the course instructor when requesting accommodation.

UF Counseling Services : Resources are available on-campus for students having personal problems or lacking clear career and academic goals. The resources include:

UF Counseling & Wellness Center, 3190 Radio Rd, 392-1575, psychological and psychiatric services.
Career Resource Center, Reitz Union, 392-1601, career and job search services.

Software Use: All faculty, staff and student of the University are required and expected to obey the laws and legal agreements governing software use. Failure to do so can lead to monetary damages and/or criminal penalties for the individual violator. Because such violations are also against University policies and rules, disciplinary action will be taken as appropriate. We, the members of the University of Florida community, pledge to uphold ourselves and our peers to the highest standards of honesty and integrity.

Miscellaneous: Please make it to the class on time. If you are late, enter the class and settle down quietly, so that you do not disturb the class. Please turn your cell phone to OFF or SILENT mode.