CS 6363 002 Design and Analysis of Algorithms Fall 2014 MW 10 00 11 15pm ECSS 2 305 Instructor D T Huynh Office ECSS 3 801 Office Hours Mon Wed 11 15 12 15pm For an appointment please email huynh utdallas edu Teaching Assistant TBA Course Prerequisites CS 5343 Data Structures or equivalent Contents 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 S Course Objectives Asymptotic notations recurrences algorithm analysis Divide and conquer algorithms Greedy algorithms Dynamic programming algorithms Graph algorithms Flow networks NP completeness Required Textbooks and Materials T Cormen C Leiserson R Rivest C Stein Introduction to Algorithms MIT Press 3 rd edition 2009 Copies of class notes HW assignments and solutions will be on UTD eLearning Suggested 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 pm Course 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 After this 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 Policies N A Student 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 Integrity The 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 Use The 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 email address and that faculty and staff consider email from students official only if it originates from a UTD student account This allows the university to maintain a high degree of confidence in the identity of all individual corresponding and the security of the transmitted information UTD furnishes each student with a free email account that is to be used in all communication with university personnel The Department of Information
View Full Document
Unlocking...