CSC335 – Analysis of Algorithms
Spring 2017

 

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 and Fridays 5pm – 6:30pm,  

                                         and by appointment.

Class Time:                    Tuesdays/Fridays 2pm – 3:20pm

Class Room:                  Forcina Hall, room 409 (or 406)

 

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

TextbookThe required textbook for this course is:

Other useful books in the field are:

 

Course Requirements

á       Readings & Participation

á       Homework assignments

á       Programming 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 4th 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 and deviations will be made as needed.

Dates

Topic

Assignment

1/24

Introduction

 

1/27

Reasoning about correctness, problem modeling

 

1/31

Machine models, big-Oh notation

Homework Assignment 1

(due on 2/7)

2/3

Growth rate and dominance, logarithms and properties

2/7

Elementary data structures

Homework Assignment 2

(due on 2/14)

2/10

Dictionary data structures

2/14

Trees

Programming Assignment 1 (due 2/24)

2/17

Heapsort

2/21

Priority queues

2/24

Quicksort

 

2/28

Linear sorting

Homework Assignment 3

(due on 3/7)

3/3

Binary search

3/7

Divide and conquer

Midterm preparation

3/10

Midterm

 

3/14

No class – Spring break

Homework Assignment 4

(due on 3/24)

3/17

3/21

Data structures for graphs

3/24

Programming Assignment 2 (due on 4/4)

3/28

Breadth First Search (BFS)

3/31

4/4

Depth First Search (DFS)

Homework Assignment 5

(due on 4/11)

4/7

4/11

Minimum spanning trees

Programming Assignment 3 (due 4/21)

4/14

Shortest paths

4/18

Bipartite matching

4/21

Space/Time tradeoff

Presentations (due on 4/28)

4/25

Approximate string matching

4/28

Longest increasing subsequence

Homework Assignment 6

(due on 5/5)

5/2

The partition problem

5/5

Review

 

 

Course Policies

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

á       We will utilize the Piazza platform (www.piazza.com) for questions and discussions. Piazza is also accessible through canvas. Please make sure you register at the beginning of the semester.

á       Homework assignments will be turned in via canvas, and a hard copy will be delivered in class. Failure to deliver a printed copy at the beginning of class will result in a 10% grade penalty.

á       Multiple page assignments have to be stapled together. Unstapled copies will receive a 5% penalty.

á       Assignments missing crucial information such as names, course number, assignment number, and date will receive a 5% penalty.

á       Late work 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 attempt to 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.

  1. Programming Assignments: You will be asked to implement data structures and/or algorithms. Your code will be tested for correctness and possibly for efficiency.
  2. Presentation: You will be asked to study in depth an algorithm, data structure, method, or concept, and create a video presentation.
  3. Midterm Exam: The midterm exam will test your understanding of the material and ensure you review 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. Extra credit for just you is discrimination. Don't ask for it; you won't get it. If any extra credit opportunities arise in class, they will be available to all students.
  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 for posterity, 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 and other changes 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 continuous development, so I expect changes/adjustments to the material, homework assignments, programming assignments, and exams. I am open to suggestions to improve and direct the subjects covered, keeping in mind that I have an obligation to cover certain material.
  12. The required textbook 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 or information will be made available on canvas.
  13. Students are expected to be on time to class, and prepared for the lecture. You should be revising material covered in class before every lecture, as well as reading ahead in the textbook. You are expected to ask insightful questions about the material, pay attention and answer critical understanding questions during class, and contribute to discussions about design and implementation of algorithms and data structures covered in earlier classes.

 

Grading

Grades will be assigned as follows:

o   Class participation: 10%

o   Homework: 30%

o   Programming Assignments: 15%

o   Presentation: 5%

o   Midterm exam: 15%

o   Final exam: 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