CSE 5311(002): DESIGN AND ANALYSIS ALGORITHMSFall 2007Tu/Th 11:00AM – 12:20PM (WH 308 )Instructor: Gautam Das, Associate ProfessorOffice: 302 Nedderman ([email protected], http://ranger.uta.edu/~gdas)Hours: Tue-Wed 2-3 pm or by appointmentGTA: Will be assigned laterOffice: GS 237Email: arjundasgupta (AT) uta (DOT) eduHours: Thursday 3-5 pm or by appointmentPrerequisites: Algorithms & Data Structures (CSE 2320)Theoretical Computer Science (CSE 3315)Course Description and Goals:This course is designed to teach you, at the graduate level, algorithm design and analysisparadigms, advanced data structures and their use in efficient algorithms, graph algorithms,the theory of NP-completeness, and some specialized topics (to be determined based onstudent input). At the end of the semester you should: - be familiar with the algorithms and algorithmic techniques covered, - be able to argue correctness and analyze the running time of a given algorithm, - be able to design new algorithms for new situations, using as building blocks thealgorithms and techniques learned, - be able to prove a problem is NP-complete using reduction. Textbook:- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001. References:- The Design and Analysis of Algorithms 1974, AV Aho, JE Hopcroft and JD Ullman,Addison-Wesley Publishing Company- Introduction to Algorithms: A Creative Approach, Reprinted 1989, Udi Manber, Addison-Wesley Publishing Company - Introduction to Algorithms, 1982, Sedgewick, Addison Wesley Publishing Company- Graph Algorithms, 1979, Shimon Even, Computer Science Press - Introduction to the Theory of Computation, 1992, Michael Sipser, PWS PublishingCompany - The Art of Computer Programming, Vols. 1 and 3, Knuth, Addison Wesley PublishingCompanyEvaluation: Your grade will be based on the following weights:- Midterm: 30%o There will one midterm exam during the semester (non comprehensive).o There will be no make up exams!- Quizzes: 25%o There will be a few short quizzes during the course which will help to test yourunderstanding of the concepts taught.o Quizzes will generally be allotted 15-20 minutes at the end of the class period.Quizzes will be announced at least a week in advance.- Project: 15%o Students will have a choice of two types of projects: Programming project: - Students will be assigned a programming project in which they canprove that they have understood a specific part of the curriculum.Projects may either be done solo or in teams of two students each.- The programming tasks should be chosen by consultation with theInstructor. Students are encouraged to approach the Instructor withproposals on the programs they envision. - Students will be encouraged to demo their programming projects to theinstructor and the GTA.- Programs have to be turned in to the GTA by the last due day afterwhich late penalty may be applied. Research paper and presentation: - Students will be required to write a research paper (around 10 pages)on a specific topic or problem and present it to the rest of the class in15-20 minute seminars. These projects may either be done solo or inteams of two students each.- The paper’s topic should be chosen by consultation with the Instructor.Students are encouraged to approach the Instructor with proposals onthe topics of their papers.- Papers have to be turned in to the Instructor at least a week before thepresentation. Scheduling presentations will be done during thesemester by consulting with the Instructor.o Students may also decide to undertake ambitious projects that combine substantialresearch efforts along with a programming component. The final exam may bewaived for such students.- Final: 30%o There will one non-comprehensive final exam at the end of the semester.o There will be no make up exams!Make-ups:Make-ups for (non-exam) graded activities may be arranged if your absence is caused byillness or work/personal emergency. A written explanation (including supportingdocumentation) must be submitted to your Instructor. If the explanation is acceptable, analternative to the graded activity will be arranged. Make-up arrangements must be arrangedprior to the scheduled due date.Policies:1. Attendance is not required, but is highly encouraged. Consult me in advance if you mustmiss class for a good reason.2. You are expected to have at least skimmed the new material by the day we start thatmaterial in class. The material will be covered in the order given later.3. Active class participation will prepare you for Quizzes and Exams. I would encourage activeinteraction during lectures.4. CHEATING - YOU ARE EXPECTED TO KNOW UNIVERSITY POLICIES. All cases ofplagiarism will be processed through University channels outside the CSE department.a) Academic Integrity Policy: It is the policy of the University of Texas at Arlington touphold and support standards of personal honesty and integrity for all studentsconsistent with the goals of a community of scholars and students seekingknowledge and truth. Furthermore, it is the policy of the University to enforce thesestandards through fair and objective procedures governing instances of allegeddishonesty, cheating, and other academic/non-academic misconduct.You can assume responsibility in two ways. First, if you choose to take the riskassociated with scholastic dishonesty and any other violation of the Code of StudentConduct and Discipline, you must assume responsibility for your behaviors andaccept the consequences. In an academic community, the standards for integrity arehigh. Second, if you are aware of scholastic dishonesty and any other conductviolations on the part of others, you have the responsibility to report it to the professoror assistant dean of students/director of student judicial affairs. The decision to do sois another moral dilemna to be faced as you define who you are. Students whoviolate University rules on scholastic dishonesty are subject to disciplinary penalties,including the possibility of failure in the course and