CSE 5311(002): DESIGN AND ANALYSIS ALGORITHMS Fall 2007 Tu/Th 11:00AM – 12:20PM (WH 308 ) Instructor: Gautam Das, Associate Professor Office: 302 Nedderman ([email protected], http://ranger.uta.edu/~gdas) Hours: Tue-Wed 2-3 pm or by appointment GTA: Will be assigned later Office: GS 237 Email: arjundasgupta (AT) uta (DOT) edu Hours: Thursday 3-5 pm or by appointment Prerequisites: 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 analysis paradigms, advanced data structures and their use in efficient algorithms, graph algorithms, the theory of NP-completeness, and some specialized topics (to be determined based on student 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 the algorithms 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 Publishing Company • The Art of Computer Programming, Vols. 1 and 3, Knuth, Addison Wesley Publishing Company Evaluation: 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 your understanding 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 can prove 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 the Instructor. Students are encouraged to approach the Instructor with proposals on the programs they envision. • Students will be encouraged to demo their programming projects to the instructor and the GTA. • Programs have to be turned in to the GTA by the last due day after which 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 in 15-20 minute seminars. These projects may either be done solo or in teams 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 on the topics of their papers. • Papers have to be turned in to the Instructor at least a week before the presentation. Scheduling presentations will be done during the semester by consulting with the Instructor. o Students may also decide to undertake ambitious projects that combine substantial research efforts along with a programming component. The final exam may be waived 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 by illness or work/personal emergency. A written explanation (including supporting documentation) must be submitted to your Instructor. If the explanation is acceptable, an alternative to the graded activity will be arranged. Make-up arrangements must be arranged prior to the scheduled due date. Policies: 1. Attendance is not required, but is highly encouraged. Consult me in advance if you must miss class for a good reason.2. You are expected to have at least skimmed the new material by the day we start that material 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 active interaction during lectures. 4. CHEATING - YOU ARE EXPECTED TO KNOW UNIVERSITY POLICIES. All cases of plagiarism 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 to uphold and support standards of personal honesty and integrity for all students consistent with the goals of a community of scholars and students seeking knowledge and truth. Furthermore, it is the policy of the University to enforce these standards through fair and objective procedures governing instances of alleged dishonesty, cheating, and other academic/non-academic misconduct. You can assume responsibility in two ways. First, if you choose to take the risk associated with scholastic dishonesty and any other violation of the Code of Student Conduct and Discipline, you must assume responsibility for your behaviors and accept the consequences. In an academic community, the standards for integrity are high. Second, if you are aware of scholastic dishonesty and any other conduct violations on the part of others, you have the responsibility to report it to the professor or assistant dean of students/director of student judicial affairs. The decision to do so is another moral dilemna to be faced as you define who you are. Students who violate University rules on scholastic dishonesty are subject