CSC335 – Analysis of Algorithms
Fall 2015

Instructor: Dimitris Papamichail

Office: Forcina Hall 458

Email: papamicd (at tcnj)

(most emails are answered within 24 hours during business days)

URL: www.tcnj.edu/~papamicd

Office Hours: Tuesdays 3:30pm – 5:00pm, Wednesdays 10am – 11:30am, and by appointment.

Class Time: Tuesdays/Fridays 11am – 12:20pm (CSC335-1)

Tuesdays/Fridays 3:30pm – 4:50pm (CSC335-2)

Class Room: Forcina Hall, room 407

Course Description

This course presents the major principles of algorithm design and analysis, and applies those principles to classical problems in computer science. Topics include algorithm complexity, data structures, divide and conquer, searching and sorting, greedy algorithms, graph search and traversal, network flow, bipartite matching, dynamic programming, approximate string matching, partitioning, skip lists, and union-find.

Prerequisites: CSC 230 or 250, and CSC 270, both with a minimum grade of C.

Course Units: 1

Course Materials

Textbook – The required textbook for this course is:

• S. Skiena, The Algorithm Design Manual, 2^nd edition, Springer 2008.

Other useful books in the field are:

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3^rd edition, MIT Press, 2009.
• J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley, 2005.
• S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill, 2006.
• R. Sedgewick, K. Wayne, Algorithms, 4^th edition, Addison-Wesley, 2011.
• U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.
• A. Levitin, Introduction to the Design and Analysis of Algorithms, 3^rd edition, Addison-Wesley, 2011.
• A. V. Aho, J. D. Ullman, J. E. Hopcroft, Data structures and Algorithms, Addison-Wesley, 1983.

Course Requirements

· Readings & Participation

· Homework assignments

· Presentation

· Midterm exam

· Final exam

Course Purpose & Learning Goals

The purpose of this course is to provide students with an introduction to algorithms and data structures. By the end of the course students will be able to:

1. Understand the distinction between constant factor improvements in performance and improvements in asymptotic growth rates.

2. Given an algorithm, empirically or analytically determine its complexity.

3. Given a problem for which efficient algorithmic techniques are known, research and apply those techniques.

4. Given a problem for which no efficient algorithmic techniques are known, apply major principles of algorithm design to seek a suitable algorithmic solution.

Other outcomes addressed by the course:

1. An ability to analyze a problem, and identify and define the computing requirements appropriate to its solution

2. An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices.

In this class, the deep learning outcomes associated with TCNJ’s 4^th hour are accomplished by algorithmic problem assignments involving analytical and creative thinking, which require the students to devote additional research time towards solving them, and the discussions that take place about these assignments in and out of class.

Course Topics and Schedule (subject to change)

Topics and Schedule are listed below. Note that dates are tentative.

Dates	Topic	Assignment
8/25	Introduction
8/28	Reasoning about correctness, problem modeling	Homework Assignment 1 (due on 9/15)
9/1	Machine models, big-Oh notation
9/4	Growth rate and dominance, logarithms and properties
9/11	Elementary data structures
9/15	Dictionary data structures	Homework Assignment 2 (due on 9/29)
9/18	Trees
9/22	Heapsort
9/25	Priority queues
9/29	Quicksort	Homework Assignment 3 (due on 10/16)
10/2	Linear sorting
10/6	Binary search
10/9	Divide and conquer
10/16	Data structures for graphs	Midterm
10/20	Midterm
10/23	Breadth First Search (BFS)	Homework Assignment 4 (due on 11/6)
10/27	Depth First Search (DFS)
10/30	Minimum spanning trees
11/3	Shortest paths
11/6	Network flows	Homework Assignment 5 (due on 11/20)
11/10	Bipartite matching
11/13	Space/Time tradeoff
11/17	Approximate string matching
11/20	Longest increasing subsequence	Presentation (due on 12/4)
11/24	The partition problem
12/1	Skips lists, union-find
12/4	Presentations

Course Policies

· Course material will be posted on canvas. Check often.

· We will utilize the Piazza platform (www.piazza.com) for questions and discussions.

· Homework assignments will be turned in via canvas, and a hard copy will be delivered in class.

· Late homework deliverables are accepted with penalty: 20% per day.

· Grades can be disputed for one week following the return of graded work only.

· Please be on time and prepared for class, and silence all cell phones before class starts.

Additional Information:

1. Homework Assignments: It is very important to do the homework assignments and solve all problems individually. Although I encourage discussion among students and you will be working in pairs and submit only one deliverable per pair, it is imperative that you make a significant individual effort to devise a complete solution for each problem before you discuss with your partner. Feel free though to divide the writing effort. All homework submissions have to be typed in appropriate typesetting software, such as LaTeX or MS Word, including mathematical formulas. Please use computer generated figures to explain complicated constructions. No handwritten solutions, formulas, or figures will be accepted. Multiple page assignments have to be stapled together. Unstapled copies will receive a 5% penalty. Assignments missing information such as name, course number, assignment number, and date will receive a 5% penalty.

The midterm and final exams may include problems that are similar to ones encountered in the homework assignments. Failing to solve these problems will indicate a lack of individual effort in the homework assignments.

2. Presentation: You will be asked to study in depth an algorithm, data structure, method, or concept, and present it in class.
3. Midterm Exam: The midterm exam will test your understanding of the material and ensure you revise the topics covered so far. The midterm exam will be closed book.
4. Final Exam: The final exam will be comprehensive to encourage you to review all material taught. The final exam will be closed book. You are encouraged to avoid solution memorization, and attempt to comprehend the general methods of algorithm design. Solving your homework assignment problems without aid should help with constructing novel solutions on demand. Exam questions may vary from homework problems in ways that memorizing solutions may confuse you instead of helping you.
5. The course may involve programming.
6. I will be lecturing mostly from slides, but will use the board whenever needed for examples and other illustrations. Feel free to keep notes if you wish, but you do not have to copy the slide material, since it will be made available to you.
7. Course handouts, material, homework assignments, etc. will be available on canvas after being presented in class, along with the latest announcements. Please check them out often. Also, please setup canvas appropriately to receive email notifications when announcements are made.
8. Solutions to algorithm problems should be precise and concise. I may be placing space restrictions for problem solutions, which will save you the ordeal of trying to impress me with volume instead of quality.
9. The best way to learn the material is by solving problems. Unless you learn how to solve problems, I can promise that you will get burned on the exams and thus for your final grade.
10. Because a primary goal of the course is to teach professionalism, any academic dishonesty will be viewed as evidence that this goal has not been achieved, and will be ground for receiving a failing grade. Please review the TCNJ academic integrity policy (link below).
11. This course is under development, so I expect changes/adjustments to the material, homework assignments, and exams. I am open to suggestions to improve and direct the subjects covered, although I have an obligation to cover certain material.
12. The required textbook ‘The Algorithm Design Manual’ will be followed to a great extent, but we may deviate in several subjects, as well as bypass and/or add material. It is recommended that you study the relevant sections from the book, since it is well written and provides great examples and explanations. Any additional slides will be made available on canvas.

Grading

Grades will be assigned as follows:

o Class participation: 10%

o Homework: 40%

o Presentation: 10%

o Midterm exam: 15%

o Final: 25%

Letter grades are assigned in relation to final score. Traditionally scores above 90% receive ‘A’, scores from 75% – 90% receive ‘B’, scores from 60% to 75% receive ‘C’, scores from 50% to 60% receive ‘D’, and scores below 50% receive ‘F’, although ranges may vary.

Selected TCNJ Policies

TCNJ’s final examination policy is available on the web: http://policies.tcnj.edu/policies/digest.php?docId=9136

Attendance

Students are expected to be present, on time, and prepared to participate in each scheduled class session as detailed in TCNJ’s attendance policy, available on the web at: http://policies.tcnj.edu/policies/digest.php?docId=9134

Academic Integrity Policy

The Academic Integrity Policy of TCNJ, available on the web at: http://policies.tcnj.edu/policies/digest.php?docId=7642

Americans with Disabilities Act (ADA) Policy

Any student who has a documented disability and is in need of academic accommodations should notify the professor of this course and contact the Office of Differing Abilities Services (609-771-2571). Accommodations are individualized and in accordance with Section 504 of the Rehabilitation Act of 1973 and the Americans with Disabilities Act of 1992.

TCNJ’s Americans with Disabilities Act (ADA) policy is available on the web:

http://policies.tcnj.edu/policies/digest.php?docId=8082