Theory of Algorithms

CSCI 400, Fall Semester, 2013

Instructor: Dr. Shieu-Hong Lin

Class: Tuesday, Thursday 3:00~4:15pm, BUSN 210

Office Hours: Mon, Wed. 12:00~1:15pm, Math & CS department

Course Website: http://csci.biola.edu/csci400

Course objectives:

· Learn important algorithmic design paradigms such as divide and conquer, dynamic programming, branch-and-bound, and greedy algorithms and how they can reduce the computational time of problem solving in critical real world application domains such as social media, data mining, sequence analysis in bioinformatics, and transportation industry.

· Develop the skills to analyze computational problems, design efficient algorithms for problem solving, prove the correctness of algorithms, analyze the computational complexity of algorithms, and implement the algorithms as functional computer programs.

· Understand the essence of basic complexity classes such as N, NP, NP-Complete, Pspace-Complete, the question of whether P equals NP and its implication, and the use of approximation algorithms and randomized algorithms to cope with time complexity.

Books:

• J. Kleinberg and E. Tardos. Algorithm Design, Addison Wesley, 2005.(Required)
• Jones & Pevzner, An Introduction to Bioinformatics Algorithms, MIT Press, 2004.

Grading

1. Reading 15%

2. Presentation and participation 15%

3. Homework and programming assignments 40%

4. Exams 30%

Presentation and collaboration groups

· You can choose to work alone as a one-person group or choose to team up with another student to form a group of two for collaboration in presentation. (To ensure everyone can find one partner, we may exceptionally allow one group of 3.) For each reading assignment, we will assign one group to present key concepts and/or algorithmic examples in the reading in the class. You don’t need to understand every bit of the reading but you should collaborate within the group in advance to prepare for the presentation and help the class understand the stuff to the class, possibly including questions you have from the reading.

Homework and programming assignments, integrity policy

· The homework and programming assignments require you to apply your understanding of algorithmic design explored in the readings to implement efficient computer programs for solving interesting computational problems. You are encouraged to interact with one another (for example in your presentation group) through brainstorming and discussions in or outside the class. However everything you submit, either your solutions or your program, should be truly yours by the time of submission, which means that you should be able to clearly explain the logic of your solutions from scratch and write your code without the help of other people.

Weekly progress report

· Starting from the second week, by Thursday each week, you should spend around 5~10 minutes to write a brief progress report (see this template) regarding the latest progress made in reading, homework, and programming, and email the report to Dr. Lin.

Tentative Schedule

· Week 1~2 Overview of Algorithmic Paradigms

· Week 3 Asymptotic notation & complexity analysis

· Weeks 4-5 More on divide and conquer

· Weeks 6-7 More on dynamic programming

· Weeks 8-9 More on greedy algorithms

· Weeks 11-12 More on applications

· Week 13 P, NP, and PSPACE

· Week 14 Approximation algorithms

· Week 15 Randomized algorithms

· Final week Final Exam

Students desiring accommodations on the basis of physical, learning, or psychological disability for this class are to contact Disability Services. Disability Services is located in the Learning Center in the Biola Library, upstairs from the main floor, and can be reached by calling 562.906.4542 or extension 4542.

ACADEMIC HONESTY POLICY: We are committed at Biola University to ethical practice in teaching, scholarship, and service. As such, plagiarism and other forms of academic dishonesty will not be tolerated. Please see the undergraduate/graduate student handbook and/or the departmental/program/school policy on academic honesty. It is imperative that you present all written, oral, and/or performed work with a clear indication of the source of that work. If it is completely your own, you are encouraged to present it as such, taking pleasure in ownership of your own created work. However, it is also imperative that you give full credit to any and all others whose work you have included in your presentation via paraphrase, direct quotation, and/or performance, citing the name(s) or the author(s)/creator(s) and the source of the work with appropriate bibliographic information. To do otherwise is to put oneself in jeopardy obeing sanctioned for an act or acts of plagiarism that can carry serious consequences up to and including