CS 6363.002 Design and Analysis of Algorithms – Fall 2014MW 10:00-11:15pm, ECSS 2.305Instructor: D.T. HuynhOffice: ECSS 3.801Office Hours: Mon/Wed. 11:15 – 12:15pm (For an appointment please email [email protected])Teaching Assistant: TBACourse Prerequisites: CS 5343 (Data Structures) or equivalentContents Description:1. Introduction (Algorithms, asymptotic notations, recurrence relations…)2. Sorting and Order Statistics(Heapsort, Quicksort, Median & Order Statistics…)3. Algorithm Design Techniques (Divide-and-Conquer, Dynamic Programming, Greedy technique…)4. Algorithms Involving Sets and Sequences (Binary Search Trees, Pattern Matching, Union-Find…)5. Graph Algorithms (Graph Search, Minimum-Cost Spanning Trees, Shortest Paths, Network Flows…)6. Geometric Algorithms (Basic geometric algorithms incl. Convex Hull, Closest Pairs …)7. Algebraic Algorithms (Polynomials, Matrix Multiplication, Fast Fourier Transform…)8. Linear Programming (Optional) (Simplex Method, Duality…)9. NP-Completeness (Reducibilities, NP-completeness, Cook’s Theorem, NP-complete problems)Course Description: The study of efficient algorithms for various computational problems. Algorithm design techniques. Sorting, manipulation of data structures, graphs, matrix multiplication, and pattern matching. Complexity of algorithms, lower bounds, NP completeness. Prerequisite: CS 5343 (3-0) SCourse Objectives: Asymptotic notations, recurrences, algorithm analysis. Divide and conquer algorithms. Greedy algorithms. Dynamicprogramming algorithms. Graph algorithms. Flow networks. NP-completeness.Required Textbooks and Materials:T. Cormen, C. Leiserson, R. Rivest & C. Stein.: “Introduction to Algorithms”, MIT Press, (3rd edition) 2009. Copies of class notes, HW assignments and solutions will be on UTD eLearningSuggested Further Reading Materials:Sipser, M.: “Introduction to the Theory of Computation”, Thomas Course Technology, 2nd Edition, 2006.Arora, S & Barak, B.: “Computational Complexity: A Modern Approach”, Cambridge University Press, 2009.Vazirani, V.: “Approximation Algorithms”, Springer 2003.Assignments and Academic Calendar/Grade Scale:- Homework assignments 10%(Solutions of HW problems will be provided.)(HW assignments are due in class on the date given. Late submissions will not be accepted. If you are not able to attend a class, you’re responsible for any announcements/handouts. HW assignments can be found on eLearning.)- Exam #1 (85 minutes) 25% Wednesday, Oct. 1, 10:00 am- Exam #2 (85 minutes) 30% Monday, Nov. 10, 10:00 am- Exam #3 (120 minutes) 35% Monday, Dec. 15, 11:00 am – 1:00 pmCourse and Instructor Policies:- No comprehensive final exam will be given. Students are required to have two photo IDs during the exams.- Students are encouraged to discuss HW problems. However, your submission must be your own work. Anyone caught cheating on HWs will receive zero credit. - If you decide to stop attending class, be sure to drop the course since you will not be dropped automatically.- Any student wishing to contest a grade on a HW should contact the TA.- Exams #1 and #2 will be returned to students after the grades are announced. Students have a window of 2 weeks to review their exams. Your request to re-grade your exam paper must be submitted in writing. Afterthis 2-week period, no request for regarding will be considered.- Exam #3 will be kept by the instructor for one semester. Anyone wishing to look at his/her exam #3 can make an appointment with the instructor or see him during his OHs. - All exams will be graded by the instructor. HWs will be graded by the TA.Field Trip PoliciesN/AStudent Conduct & Discipline The University of Texas System and The University of Texas at Dallas have rules and regulations for the orderly and efficient conduct of their business. It is the responsibility of each student and each student organization to be knowledgeable about the rules and regulations which govern student conduct and activities. General information on student conduct and discipline is contained in the UTD publication, A to Z Guide, which is provided to all registered students each academic year. The University of Texas at Dallas administers student discipline within the procedures of recognized and established due process. Procedures are defined and described in the Rules and Regulations, Board of Regents, The University of Texas System, Part 1, Chapter VI, Section 3, and in Title V, Rules on Student Services and Activities of the university’s Handbook of Operating Procedures. Copies of these rules and regulations are available to students in the Office of the Dean of Students, where staff members are available to assist students in interpreting the rules and regulations (SU 1.602, 972/883-6391).Academic IntegrityThe faculty expects from its student a high level of responsibility and academic honesty. Because the value of an academic degree depends upon the absolute integrity of the work done by the student for that degree, it is imperative that a student demonstrate a high standard of individual honor in his or her scholastic work.Scholastic dishonesty includes, but is not limited to, statements, acts, or omissions related to applications for enrollment or the award of a degree, and /or the submission as one’s own work or material that is not one’s own. As a general rule, scholastic dishonesty involves one of the following acts: cheating, plagiarism, collusion and /or falsifying academic records. Students suspected of academic dishonesty are subject to disciplinary proceedings.Plagiarism, especially form the web from portions of papers for other classes, and from any other source is unacceptable and will be dealt with under the university’s policy on plagiarism (see general catalog for details). This course will use the resources of turnitin.com, which searches the web for possible plagiarism and is over 90% effective. Email UseThe University of Texas at Dallas recognizes the value and efficiency of communication between faculty/staff and students through electronic mail. At the same time, email raises some issues concerning security and the identity of each individual in an email exchange. The university encourages all official student email correspondence be sent only to a student’s U.T. Dallas
View Full Document
Unlocking...