COLLEGE OF SCIENCE AND HEALTH
Computer Science Syllabus and Outline
1. / Course: CS372-01 Design and Analysis of Algorithms, 3 credits
2. / Department secretary: Carol Parken (Coach House 120) can be contacted by telephone at (973)_720-2649 and by e-mail at .
3. / Semester offered: Spring 2003
Time: Monday & Wednesday 2:00 PM- 3:15 PM Location: Coach House T101B
4. / Faculty: Dr. Linda Kaufman, Prof. of Computer Science
Office: Coach House 115, Phone: (973)-720-2952, E-mail: kaufmanlwpunj.edu
Office Hours: Tuesday 2:00PM-3:15PM
Wednesday 12:30-1:30pm
And also by appointment.
5. / Required Texts (2 or 3 depending on combo-arrangement):
Levitin, Anany V., Introduction to the Design and Analysis of Algorithms,
Addison-Wesley, 0-201-74395-7
Suggested Readings: (not required)
Aho, Hopcroft, & Ullman, Design and Analysis of Computer Algorithms,
Addison-Wesley, 1974.
Baase, Sara & Allen van Gelder, Computer Algorithms (3rd edition), Addison-Wesley,
2000.
Bentley, Jon, More Programming Pearls, Addison-Wesley, 1988.
Bentley, Jon, Programming Pearls, Addison-Wesley, 1986.
Brassard, Giles & Bratley, Algorithmics: Theory & Practice, Prentice-Hall, 1988.
Cormen, Thomas, Leiserson, & Rivest, Introduction to Algorithms, MIT Press, 2001. Goodrich, Michael & Roberto Tammassia, Algorithm Design: Foundations, Analysis,
and Internet Examples, Wiley, 2001.
Harel, David Algorithmics: The Spirit of Computing (2nd Edition), Addison-Wesley,
1990.
Horowitz, Ellis, Sartaj Sahni, & Sanguthevar Rajasekaran, Computer Algorithms (C++ version), Computer Science Press, 1996.
.
Manber, Udi, Introduction to Algorithms: A Creative Approach, Addison-Wesley,
1989.
McConnell, Jefferey. Analysis of Algorithms: An Active Learning Approach,
Jones and Bartlett, 2001.
Neapolitan, Richard & Kumarss Naimipour, Foundations of Algorithms (Using C++
Pseudocode), Second Edition, Jones and Bartlett Publishers, 1998.
Papadimitriou, Christos, Computational Complexity, Addison-Wesley, 1994.
Rawlins, Gregory J. E., Compared to What? An Introduction to Algorithm Analysis,
Computer Science Press, 1992.
Sedgewick, Robert Algorithms in C++, Addison Wesley, 1992 (17th printing June 2000).
Sedgewick, Robert Algorithms in Java (Parts 1-4), Third Edition, Addison Wesley, 2003
(First Printing), ISBN 0-201-36120-5.
Sedgewick, Robert Algorithms in C++ (Part 5), Third Edition, Addison Wesley, 2001,
ISBN 0-201-36118-3.
(the two books (above) might be offered at a combo discount at the bookstore)
Sedgewick, Robert and Philippe Flajolet Introduction to the Analysis of Algorithms,
Addison Wesley, 1996.
http://www.comp.nus.edu.sg/~changec/Teaching/Algorithms2004/cs3230.html
http://cs.roosevelt.edu/~dantsin/teaching/280-24.htm#instructorhttp://www.comp.nus.edu.sg/~changec/Teaching/Algorithms2004/cs3230.html
http://cs.roosevelt.edu/~dantsin/teaching/280-24.htm#instructorBottom of Form
http://www.comp.nus.edu.sg/~changec/Teaching/Algorithms2004/cs3230.html
Good Source of notes and Slides:
http://www.personal.kent.edu/~rmuhamma/Algorithms/algorithm.html have to login
http://www.cs.virginia.edu/~luebke/cs332/
http://cs.roosevelt.edu/~dantsin/teaching/280-24.htm#instructor
Expositions on Balanced Binary Trees & Other Algorithmics
Good Sources for Algorithms:
http://www.cise.ufl.edu/~raj/BOOK.html
ftp://ftp.aw.com/cseng/authors/sedgewick/AlgorithmsCC
http://www.cs.fiu.edu/~weiss/dsaa_c++/Code/
Other Important Algorithm Sites:
http://pauillac.inria.fr/algo/AofA/
http://www.cs.sunysb.edu/~algorith/ Great website for problems!
6. / Course Objectives:
An introduction to the concepts, methodologies, and constructive models for formulating algorithms. Use of analytic techniques to determine the relative efficiency of algorithms with respect to several measures such as time and space complexity. Standard algorithm design approaches (such as divide and conquer) will be developed and applied. Later topics introduce alternate models of computation such as probabilistic algorithms, parallel processing, and complexity classes (such as NP). Java and C/C++ will be used as the primary programming language. Important data structures and programming methodologies are assessed. Programming and debugging experience is reinforced by hands-on sessions and programming projects.
7. / Student learning outcomes:
Upon completion of this course, students will:
- Understand complexity theory sufficiently and have enough practice to conduct a Big-O(), -omega, and -theta analysis of a particular program/programming problem. They must demonstrate an appreciation of program design decision-making based upon their combinatorial, asymptotic, and local/pragmatic analyses. Proofs here will involve developing inequalities between functions and using calculus concepts such as limits and derivatives to derive/formulate growth behavior theorems. Students are expected to understand, formulate, and prove those results. This requires extensive problem-solving using all their calculus, probability, discrete structures, and programming background as a foundation. Several handouts of drill problems and proofs will be used in problems solving sessions and homeworks. Students are expected to solve 10-20 of them for each homework. Students are expected to also become adept at solving several categories of recurrence relations.
- Be capable of explaining rudimentary lower-bound theory and the intuitive and formal requirements, methodology, and approaches to a mathematical-proof in this area.
- Effectively and analytically apply several fundamental design methods for algorithms, demonstrating the ability to select methodologies, fully design the algorithms from them, and produce executing programs based on those design methodologies. At least one full program in each design methodology is required as projects.
- Read the literature of the discipline and conduct inquiry-based studies of problems in the area (in the form of a required term paper and other research-based projects). This will be conducted using the library and Internet resources such as on-line books and research papers.
- Appreciate the historical development and current results of the area in terms of classic and recent breakthrough papers in each of the sub-disciplines.
- Through classroom participation in problem-solving sessions and discussions, homework, papers, and other assignments, this course also reinforces the following student learning outcomes in accordance with the university:
· Demonstrate the ability to think critically both in algorithmic synthesis and analysis.
· Locate and use information on the Internet, in monographs and scholarly journals.
· Demonstrate the ability to integrate knowledge and ideas in a coherent and meaningful manner (as cited above).
8. / Weekly Topical outline of the course content (tentative)
Week / Topic and Chapter Numbers
1. / Fundamentals of Algorithmic Problem Solving.
Problem Types
Data Structures-Graphs, Trees /
Levitin
1
2. / Orders of Growth, Assymptotic Notations-big 0, analysis of nonrecursive / Levitin
2.1-2.3
3. / Mathematical Analysis of Recursive Algorithms / Levitin
2.4-2.5
4 / Quiz Fundamentals of Algorithm Analysis
Brute Force Algorithms-selection sort, bubble sort, string matching, sequential search, traveling salesman, knapsack / Levitin 3
5. / Divide and Conquer-mergesort, quicksort, binary search, binary tree traversals / Levitin 4.1-4.3
6. / Decrease and Conquer-insertion sort, depth-first and breadth first search / Levitin 5.1-5.2
7. / Variable size decrease algorithms
Computing medians
Midterm
/ Levitin 5.5-5.68. / Transform and Conquer- Gaussian Elimination, Balanced Search Trees- AVL Trees, 2-3 Trees / Levitin 6.1-6.3
9. / Heaps and Heapsort, Horner’s Rule,
Problem reduction- computing least common , linear programming, graph problems / Levitin 6.4-6.6
10. / Space and Time Tradeoffs- string matching, Hashing, B-trees / Levitin
7
11. / Quiz Dynamic Programming-Floyd’s Algorithm, Optimal Binary Search Trees, knapsack problem / Levitin
8
12. / Greedy Techniques- Minimum Spanning Trees, Prim’s, Kruskal’s, Dijkstra’s Algoirthms, Huffman Trees / Levitin
9
13. / Lower bound arguments. Decision Tree, P, NP, NP complete problems / Levitin10
14. / Backtracking- n queens problem, hamiltonian circuit, branch and bound, approximation algorithms for TSP and Knapsack. / Levitin 11
9. / Teaching methods (e.g., lecture, discussions, presentations, etc.)
a) Classroom lectures, discussions, and problem solving sessions
b) Homework reviews
c) Lab work programming with using compilers, IDE's, &profilers.
10. / Course expectations:
a. Reading Assignments
Item 8 (above) addresses the reading schedule issue.
b. Tentative timeline for submission of written assignments or other work
Projects and class work will be collected as scheduled with a grace period of one week.
c. Attendance
Attendance will be recorded. Departmental guidelines require
that: 3 absences (2 for night) ---> departmental warning letter
7 absences (4 for night) ---> automatic failure in course
Only valid excuses (in writing) allay these consequences.
Attendance and success coincide.
d. Participation in out-of-class activities (e.g. in labs, workshops, performances, etc.)
Not Applicable
e. Examinations (tentative dates, make-up policy, etc.)
All exams will be announced at least one full week in advance.
If you are absent on the day an exam is announced, you are responsible for finding out
about it from a fellow student or the professor. No make-up exams will be given except for
extraordinary circumstances.
Item 8 (above) addresses the examination schedule issue.
Final Exam. Period: Monday 5/12/2003 at 8:00AM - 10:30AM, T101B.
f. Class participation
Bring the specified textbook to each class session.
Before lab sessions and lectures, read relevant text to optimize productivity.
11. / Grading and other methods for assessing student academic performance:
· Periodic examinations, the culminating one being a final examination.
· Programming Projects and homework
· Computation: Final Grade = (40%) * Classwork & Projects +
· (35%) * Average of Quizzesother than final, 25% final
12. / Additional information:
2/21 (Presidents Day), Tuesday 2/22=Monday, SB 3/14-3/13,