Home Page

Statement of Ethics

References

Notes and Exercises

Projects

Presentations

Quizzes

Exams

Research Papers

Important Dates

Announcements

1.TA office hour (15:00-16:30

Tuesday and Thursday) NH239

2.September 10th --Quiz 1

3.October 1st --Quiz 2

4.November 3rd --Quiz 4

5.Final Exam

Part I: Nov 24th (Monday) 1:00-2:20pm

           Venue: 110 NH

   Topics: NP-complete problems (Chapter 8)

                 Local search (Chapter 12 complete)

                 Approximations (Including branch and bound)

                 (11.1,11.2,11.4)

                 Randomized algorithms (13.1, 13.5)

Part II: Nov 26th (Wednesday) 1:00-2:20pm

            Venue: 110 NH

   Topics: Sorting

                 Graphs

                 Network Flows

                 Dynamic Programming

                 Greedy Algorithms

                 String matching

                 Computational Geometry

Course Descriptio

Design and Analysis of Algorithms is THE most important basic course in any graduate computer science and engineering curriculum. It is vital for every computer science student to be fluent with algorithms and their analysis. ALGORITHMS ARE FUN; ALGORITHM ANALYSIS is a NECESSARY TOOL; Students are encouraged to solve homework problems and discuss/solve problems in the class. Each student will be given one specific algorithm or problem to carry out an in-depth study. Typically, this course should be taken in the very first semester of your graduate study because algorithms are used in Networks, Operating Systems, Databases, and other (including advanced) courses.

Course Objectives

The objective of this course is to build a solid foundation of the most important fundamental subject in computer science. Creative thinking is essential to algorithm design. Algorithm analysis and verification demands sound mathematical acumen and programming skills.

Course Prerequisites

Data Structures (CSE 2320) and Theoretical Concepts in Computer Science and Engineering (CSE 3315) OR Equivalent.

Mode of Teaching

Mode of Teaching: The class meets twice a week (Mondays and Wednesdays 1:00 to 2:20pm). The Monday class will be of lecture type and the Wednesday class will be of tutorial type. Power point slides and other lecture material will be used on Mondays. At the end of each topic, students must attempt to solve exercise problems. Exercise problems can be found on the course web page and in the text book. All students are expected to work on these problems and participate in the discussions on Wednesdays.

The course on Algorithms is critical to your development as a computer scientist, a researcher, a creative thinker and/or a problem solver. This is a fundamental course - algorithms are extensively used in databases, networks, artificial intelligence, bioinformatics, pervasive and mobile computing, robotics, security, architecture, all engineering and science disciplines, finance, management, music, biology and indeed in everyday life. In this course you will be encouraged to think on your own and to discuss solutions with your peers. The course is not limited to any programming language. Students are strongly encouraged to use the text book and the course material that will be available and updated from time to time on the course page.

Instructor: Mohan Kumar, 333 NH

Class: Mon/Wed   - 1:00 to 2:20 PM

Email: mailto:kumar@cse.uta.edu

Office Hours: Mondays/Wednesdays  2:30 to 4:00 PM   

Phone: (817) 272-3610 or main office: (817) 272-3785;

WWW site: http://crystal.uta.edu/~kumar/cse5311_08FALL

GTA: TBA
Email: TBA

Office Hours: TBA

Location: TBA

Course Syllabus:

·               Review of Asymptotic Analysis and Growth of Functions; Trees, Heaps, and Graphs; and Recurrences.

·             Greedy Algorithms: Minimum spanning tree, Union-Find algorithms, Kruskal's Algorithm, Clustering, Huffman Codes, and Multiphase greedy algorithms.

·             Dynamic Programming: Shortest paths, negative cycles, matrix chain multiplications, sequence alignment, RNA secondary structure, application examples.

·             Network Flow: Maximum flow problem, Ford-Fulkerson algorithm, augmenting paths, Bipartite matching problem, disjoint paths and application problems.

·             NP and Computational tractability: Polynomial time reductions; The Satisfiability  problem; NP-Complete problems; and Extending limits of tractability.

·             Approximation Algorithms, Local Search and Randomized Algorithms

·            Applications of Algorithms, sample examples

Text book

           Algorithm Design
           by Jon Kleinberg and Eva Tardos

           Pearson Addison-Wesley

           ISBN 0-321-29535-8

References

Class Notes, Power point slides, and Exercise Problems

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, Second Edition, 2001

T Cormen, C E Leiserson, R L Rivest and C Stein McGraw Hill and MIT Press

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

Assessment

Quizzes and class participation: 40%

The structure of the quizzes will be discussed in class, at least one week prior to the quiz.

Quiz 1 (10%): September 10, 2008

Quiz 2 (10%): September 24, 2008

Quiz 3 (10%): October 08, 2008

Quiz 4 (10%): October 29, 2008

Final Exam (25 %): December 03, 2008.

Quizzes 1 thru 4 are of duration 30 minutes and the Final Exam is of duration 2 hours.

Group Project: 35%

Students will have the option of doing a group study or group project.

Project problems will be handed out by September 15, 2008 and the expected date of Completion is 9 AM December 3, 2008. The students will be required to write programs and run experiments. Presentation and demonstration of the projects will be during the first week of December 2008.

Homework Assignments: No Grades awarded directly!

Missed Exams, Quizzes, and Makeup Work

If you miss an exam or quiz due to unavoidable circumstances (e.g., health), email the instructor for an appointment or meet with him during office hours. Do NOT ask for make up exams or other components if you missed an exam or a project due to travel (except when you are required to travel to represent the university or the department).

Attendance and Drop Policy

Attendance though not mandatory, is HIGHLY encouraged. Class participation is important to your grade in the 'Quizzes and Class Participation' component

Final Review Week

A period of five class days prior to the first day of final examinations in the long sessions shall be designated as Final Review Week. The purpose of this week is to allow students sufficient time to prepare for final examinations. During this week, there shall be no scheduled activities such as required field trips or performances; and no instructor shall assign any themes, research problems or exercises of similar scope that have a completion date during or following this week unless specified in the class syllabi. . During Final Review Week, an instructor shall not give any examinations constituting 10% or more of the final grade, except makeup tests and laboratory examinations. In addition, no instructor shall give any portion of the final examination during Final Review Week.

Americans With Disabilities Act

The University of Texas at Arlington is on record as being committed to both the spirit and letter of federal equal opportunity legislation; reference Public Law 93112 -- The Rehabilitation Act of 1973 as amended. With the passage of new federal legislation entitled Americans With Disabilities Act - (ADA), pursuant to section 504 of The Rehabilitation Act, there is renewed focus on providing this population with the same opportunities enjoyed by all citizens.

As a faculty member, I am required by law to provide "reasonable accommodation" to students with disabilities, so as not to discriminate on the basis of that disability. Student responsibility primarily rests with informing faculty at the beginning of the semester and in providing authorized documentation through designated administrative channels.

Academic Dishonesty

It is the philosophy of The University of Texas at Arlington that academic dishonesty is a completely unacceptable mode of conduct and will not be tolerated in any form. All persons involved in academic dishonesty will be disciplined in accordance with University regulations and procedures. Discipline may include suspension or expulsion from the University.

"Scholastic dishonesty includes but is not limited to cheating, plagiarism, collusion, the submission for credit of any work or materials that are attributable in whole or in part to another person, taking an examination for another person, any act designed to give unfair advantage to a student or the attempt to commit such acts." (Regents’ Rules and Regulations, Part One, Chapter VI, Section 3, Subsection 3.2, Subdivision 3.22)

Student Support Services Available

The University of Texas at Arlington supports a variety of student success programs to help you connect with the University and achieve academic success. These programs include learning assistance, developmental education, advising and mentoring, admission and transition, and federally funded programs. Students requiring assistance academically, personally, or socially should contact the Office of Student Success Programs at 817-272-6107 for more information and appropriate referrals.