Syllabus

Course Number and Title: COT5405 - 1100X

Class Hours: Tuesday 2nd period (8:30 AM - 9:20 AM), Thursday 2nd-3rd period (8:30 AM - 10:25 AM) at CSE 118.

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.

Instructor:

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

• Office hours: Monday, Thursday 1:00-2:00pm or by appointment
• Office: E432 CSE Bldg, University of Florida, Gainesville, FL 32611-6120
• E-mail: ranka AT cise.ufl.edu
• Phone: (352) 392 - 6838

Teaching Assistants:

Course Objectives:

Please refer to the main course page.

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

Please check the first announcement in the announcement page, which gives a sample quiz that tests your mathematical abilities .

Announcements: It is your responsibility to check announcements at least once every week.

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)

Evaluation:

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

Course Policies:

• There will be no makeup exams (Exceptions may be made for medical emergencies).
• 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 not mandatory. However, you are responsible for all announcements and course material discussed in the class.
• 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. If you are in doubt about this policy, simply avoid any discussion at all, and work entirely on your own.
• Do not use any published solutions or solutions from prior semesters unless we explicitly post them for your use. If you obtain solutions from another student from a prior semester, and use them, it will be considered cheating (and it is easy for us to catch you).
• 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.

Academic Dishonesty: 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.

Counselling and Mental Health: Please refer to the University Counselling Services (phone number (352) 392-1575 ) and Student Mental Health Services (phone number (352) 392-1171) here.

Students with Disabilities: Students requesting classroom accommodation must first register with the Dean of Students Office. The Dean of Students Office will provide documentation to the student who must then provide this documentation to the Instructor when requesting accommodation.

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.