CSE5311 Design and Analysis of Algorithms

Dr. Mohan Kumar

SPRING 2013

Course Syllabus and Details

Course Description

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. Typically, this course should be taken in the very first semester of graduate study because algorithms are used in Networks, Operating Systems, Databases, and other (including advanced) courses.

Course Objectives

The principal objective of this course is to build a solid foundation in algorithms and their applications. Students completing this course are expected to appreciate the importance of algorithms in other areas including routing in networks, query processing in databases, collaboration in distributed computing, efficient caching in operating systems etc.

Course Prerequisites

Data Structures (CSE 2320) and Theoretical Concepts in Computer Science and Engineering (CSE 3315) OR Equivalent. Creative thinking, sound mathematical insight and programming skills.

Mode of Teaching

The class meets twice a week (Tuesdays and Thursdays 5:00 am to 6:20pm). Power point slides and other lecture material will be available on Blackboard. Whiteboard will be used in all classes. At the end of each topic, students must attempt to solve exercise problems. Solutions to exercise and homework problems will be discussed in class. Solutions may not be provided in electronic form. The instructor will provide comprehensive notes and references to relevant material. Exercise problems can be found on the course web page, in the text book and in reference books. Solutions to problems will be discussed in class or in meetings with the instructor/GTA. All students are expected to work on these problems and participate in the class discussions. The Midterm and final exams will be open-notes; all notes MUST be handwritten by the individual student. Exceptions will be made for persons with special abilities and requirements (please contact the instructor for more details).

 

Algorithms are 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 reference books and course material provided by the professor.

 

Professor: Mohan Kumar; 559 ERB;Email: mkumar@uta.edu;Phone: (817) 272-3610

Class: TBA; Tue/Thu - 5:00 PM - 6:20 PM;Office Hours: Thursdays 2:00 to 4:30 PM;

Course site: http://ranger.uta.edu/~kumar/CSE5311_SP13

GTA: TBA

 

Course Syllabus:

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

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

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

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

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

o     Approximation Algorithms, Local Search and Randomized Algorithms

o     Applications of Algorithms, sample examples

Text book

o     Algorithm Design

o    Jon Kleinberg and Eva Tardos, Pearson Addison-Wesley, 2004 or Later Edition

References

Assessment

Midterm exams: 30%

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

o    Midterm Exam 1 (15%): February 21, 2013

o    Midterm Exam 2 (15%): April 11, 2013

Final Exam : (30%): May 02, 2013.

 

Midterm exams are 80 minutes and the Final Exam is of 2 hours duration.

 

Homework and Quizzes : 10 %

 

Lab Assignment: 30%

Assignment problems will be handed out by February 05, 2013 and the expected date of completion is 9 am May06, 2013. The students will be required to write programs and run experiments.

 

Homework Assignments:

Class participation: ACTIVE Participation will prepare you well for the Exams. Students are expected to interact actively during lectures.

All students are expected to solve homework problems and discuss solutions in the class.

Missed Exams and Makeup Work

Talk to the instructor if you miss an exam or quiz due to unavoidable circumstances (e.g., health).

Attendance and Drop Policy

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

Please visit course page for details on Americans with Disabilities Act, Academic Dishonesty and Student Support Services.