CISC 3220 (CIS 23)   Analysis of Algorithms

Spring 2010    May still be updated.

Prof. Eva Cogan     cogan_at_sci.brooklyn.cuny.edu     Replace _at_ with @.
http://www.sci.brooklyn.cuny.edu/~cogan/
Office: 3208N (718)951-5000 X2046

Prerequisites

• CISC 2210 (CIS 11) and CISC 3130 (CIS 22) – known well
• Recursion
• Sets
• Basic Probability
• Logarithms
• Linked Lists
• Stacks
• Queues
• Trees (General and Binary)
• Graphs
• Matrices

Text

It is assumed that you will do the reading without being told. Order may vary. Other topics may be covered. Some topics may be omitted.

Appendix A (selected parts)

Appendix B and Appendix C (sections 1,2) ( You are responsible for this material. We may not go over it since it is CIS 11.)

Chapters 1, 2, 3, 4 (Sections 3, 4 and 5), 6, 7, 8, 9 (sections 1, 2 and 3)

10 (You are responsible for the material in this chapter. We may not go over it since it is CIS 22.)

15, 16, 22 (sections 1, 2 and 3), 23, 24.3, 32, approximate string matching (not in text), 34 (sections 1, 2, 3 and 5), 35, 11, 12, 25.2

Other resources

• Algorithm Design, Kleinberg and Tardos, Addison Wesley.
• Algorithm Design, Goodrich and Tamassia, Wiley.
• Computer Algorithms: Introduction to Design and Analysis (3rd Edition), Baase and Van Gelder, Addison Wesley.
• Algorithms, Dasgupta, Papadimitriou, and Vazirani, McGraw Hill.
• Introduction to Algorithms a Creative Approach, Manber, Addison-Wesley.
• The Design and Analysis of Computer Algorithms, Aho, Hopcroft and Ullman
• Many online sites with notes, slides, videos, tutorials, etc.
• Lecture notes from MIT:
  http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/index.htm
• Problems on Algorithms: http://www.eng.unt.edu/ian/books/free/poa.pdf

Performance Objectives

• Demonstrate an understanding of the growth of functions, the use of O, Omega and Theta notation, and worst-case and average-case
  time complexity, and apply the above concepts to analyze the complexity and efficiency of algorithms.
• Demonstrate knowledge of several algorithms for sorting and order statistics and an understanding of the analysis of their complexities.
• Demonstrate an understanding of various design techniques such as divide-and-conquer and greedy methods.
• Demonstrate knowledge of different methods for representing a graph and of basic graph algorithms such as traversals, finding a minimum
  spanning tree and finding the shortest path.
• Demonstrate an understanding of the nature of the classes P, NP and NP-complete, and define several problems that belong to these classes.

Grade

• 16% homework and quizzes, to be adjusted as needed
• 24% Exam1
• 24% Exam2
• 36% Cumulative Final
• No makeup exams
• There will be homework almost every class. Make sure you have the time to do it.
• Some exam questions may be similar to the homework.
• Class participation may change your grade by up to 10%.

Academic Integrity

Any attempt to cheat is grounds for failure.

http://www1.cuny.edu/portal_ur/content/2004/policies/policies.html
The CUNY Policy and the Report of the Committee on Academic Integrity

The faculty and administration of Brooklyn College support an environment free from cheating and plagiarism. Each student is responsible for being aware of what constitutes cheating and plagiarism and for avoiding both. The complete text of the CUNY Academic Integrity Policy and the Brooklyn College procedure for implementing that policy can be found at this site: http://www.brooklyn.cuny.edu/bc/policies. If a faculty member suspects a violation of academic integrity and, upon investigation, confirms that violation, or if the student admits the violation, the faculty member MUST report the violation.

Center for Student Disability Services

In order to receive disability-related academic accommodations students must first be registered with the Center for Student Disability Services. Students who have a documented disability or suspect they may have a disability are invited to set up an appointment with the Director of the Center for Student Disability Services, Ms. Valerie Stewart-Lovell at 718-951-5538. If you have already registered with the Center for Student Disability Services please provide your professor with the course accommodation form and discuss your specific accommodation with him/her.