Course Prerequisites CS 5343 Data Structures or equivalent Fast track students should have taken CS 4349 CS 6363 001 Design and Analysis of Computer Algorithms Spring 2022 TR 10 00 11 15 am ECSS 2 412 Office Hours For an appointment please email huynh utdallas edu Tues Thurs 1 00 2 00pm via MS Teams Instructor D T Huynh Office ECSS 3 801 Teaching Assistant TBA Contents Description 1 Introduction Algorithms asymptotic notation 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 if time allows Simplex Method Duality 9 NP Completeness Polynomial time 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 3rd edition 2009 Copies of class notes HW assignments and solutions will be uploaded on UTD eLearning Suggested Further Reading Materials Sipser M Introduction to the Theory of Computation Cengage Learning 3rd Edition 2013 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 10 5 Homework assignments Solutions of HW problems will be provided in eLearning HW assignments are due on eLearning on the date given Late HWs will not be accepted HW assignments will be uploaded on eLearning Exam 1 75 minutes 25 Exam 2 75 minutes 30 Exam 3 75 minutes 35 Tues Feb 22 10 00 am Tues March 29 10 00 am Thurs May 5 10 00am Course and Instructor Policies A copy of the lecture notes Chapters 1 9 can be found on UTD eLearning Exam 3 is not comprehensive Each exam will cover approx 1 3 of course content 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 Final grades will be posted by the Records Office Any student wishing to contest a grade on a HW should contact the TA All exams will be graded by the instructor HWs will be graded by the TA No late homework or assignment will be accepted I do not read e Learning e mails Please use my UTD e mail account above for any communications All grade disputes must be reported within 1 week of the grade in question being posted on eLearning There will be no makeup exams under normal circumstances Uncontested grades will be final after 1 week If you have questions concerning your exam grades please contact me Due to FERPA grades cannot be discussed via email Class Materials The instructor may provide class materials that will be made available to all students registered for this class as they are intended to supplement the classroom experience These materials may be downloaded during the course however these materials are for registered students use only Classroom materials may not be reproduced or shared with those not in class or uploaded to other online environments except to implement an approved Office of Student AccessAbility accommodation Failure to comply with these University requirements is a violation of the Student Code of Conduct Classroom Conduct Requirements Related to Public Health Measures UT Dallas will follow the public health and safety guidelines put forth by the Centers for Disease Control and Prevention CDC the Texas Department of State Health Services DSHS and local public health agencies that are in effect at that time during the Fall 2021 semester to the extent allowed by state governance Texas Governor Greg Abbott s Executive Order GA 38 prohibits us from mandating vaccines and face coverings for UT Dallas employees students and members of the public on campus However we strongly encourage all Comets to get vaccinated and wear face coverings as recommended by the CDC Check the Comets United Latest Updates webpage for the latest guidance on the University s public health measures Comets are expected to carry out Student Safety protocols in adherence to the Comet Commitment Unvaccinated Comets will be expected to complete the Required Daily Health Screening Those students who do not comply will be referred to the Office of Community Standards and Conduct for disciplinary action under the Student Code of Conduct UTSP5003 Class Attendance Class Participation Class Recordings Comet Creed The University s attendance policy requirement is that individual faculty set their course attendance requirements Regular and punctual class attendance is expected Students who fail to attend class regularly are inviting scholastic difficulty In some courses instructors may have special attendance requirements these should be made known to students during the first week of classes Regular class participation is expected Students who fail to participate in class regularly are inviting scholastic difficulty A portion of the grade for this course is directly tied to your participation in this class It also includes engaging in group or other activities during class that solicit your feedback on homework assignments readings or materials covered in the lectures and or labs Class participation is documented by faculty Successful participation is defined as consistently adhering to University requirements as presented in this syllabus Failure to comply with these University requirements is a violation of the Student Code of Conduct Students are expected to follow appropriate University policies and maintain the security of passwords used to access recorded