CSCI 700: Algorithms I - Design and Analysis of Algorithms

Fall 2010

Tuesday Thursday 6:30pm - 7:45pm

NSB C205

Instructor: Andrew Rosenberg (andrew_at_cs.qc.cuny.edu)

Office Hours: Thursday 5-6pm NSB A330

Fall 2010

Tuesday Thursday 6:30pm - 7:45pm

NSB C205

Instructor: Andrew Rosenberg (andrew_at_cs.qc.cuny.edu)

Office Hours: Thursday 5-6pm NSB A330

Overview

This class will cover the fundamentals of the design and analysis of algorithms. A focus on implementation in out-of-class assignments will accompany the theoretical discussions of the material in class. Solid grasp of the design and analysis of algorithms is foundational to being a successful computer programmer and computer scientist.

Class Policy

Come to Class. It will be difficult to do well in the class without regular attendance. There is no additional penalty for missing class.

Cell phones must be on silent, and are not to be checked or used during class - if you are expecting an urgent call, tell the instructor at the start of class.

Laptops are fine for taking notes. No internet, no chat, no games.

Cell phone and Laptop policy: One warning, after that 5 points off the next homework or exam for each issue. Same policy for the instructor. One warning, after that, everyone gets 5 points on the next homework or exam.

Grading Policy

Assignments: 55% (11 x 5%)

Midterm: 15%

Final: 25%

Timeliness Bonus: 5%

The Final Letter Grade will be based on a scaled adjustment of the Final Numeric Grade. When the scale has been determined, the class will be informed either in class or over email, and it will be posted to the course webpage (here).

Assignment Policy

**Do not cheat.** You may discuss assignments with your classmates, but write or program your assignment alone. Do not ask for or offer to share code, or written assignments. If you discuss an assignment with a classmate, or on an online forum, include the name of the classmate or URL of the forum on your assignment or in the documentation of your code. The first instance of cheating results in an automatic zero for the assignment (or midterm or final). A second instance of cheating results in a zero (F) for the course. The Computer Science Department will be notified in writing of all instances of cheating. On a second instance a report will be submitted to the Office of Academic Integrity.

Assignments will be posted to the website (here) after class on Tuesdays.

All assignments will be scored out of 100 points.

There are 11 assignments. 7 are written assignments, 4 are coding assigments.

Assignments will be due just after the start of class, 6:35pm, on the following Tuesday. Written assignments should be emailed or hard-copies should be delivered in class.

Deliver assignments at the start of class or email with a timestamp before 6:35pm to avoid a late penalty. If an extension is needed let me know as soon as possible. I will do my best to be reasonable to you and fair to the rest of class. Delivering an assignment while being more than 5 minutes late for class will be make the assignment considered Late. There is a 5 point Late Penalty for each 12 hours late the assignment is delivered. Tuesday 6:35pm - Wednesday 6:35am: -5 points. Wednesday 6:36am - Wednesday 6:35pm: -10 pts. Wednesday 6:35pm - Thursday 6:35am: -15pts. Thursday 6:35am - Thursday 6:30pm: -20pts.

Grades will be posted at 6:30pm on Thursdays, just before class. After 6:30, 2 days after an assignment was due, no assignments will be accepted. Assignments that were delivered on time will be returned during Thursday classes.

After each assignment and the midterm is graded, anonymous mean, median, maximum and minimum scores will be posted to this page.

If every assignment is handed in on time, a 5 point bonus will be awarded.

Coding Assignments

Assignments will be written in C++, and must compile using g++ on venus.cs.qc.cuny.edu with no external libraries.

In general, grading will be 15% Compilation, 15% Execution, 35% Correctness (15% passing tests, 20% implementational details), 35% Documentation and Style. This may be adjusted for some assignments. Always read the assignment for the grading breakdown.

Testing will be performed automatically. Sample tests will be delivered with each assignment. If code does not operate using the published and distributed testing format, the assignment will be considered Incorrect and zero "Correctness" points will be awarded.

Detailed requirements will accompany each assignment. The instructions and requirements on a particular assignment always take precedence over the general guidelines on the course website.

Submission of coding assignments should be performed over email. Don't forget to attach your files. Submitting multiple times is fine. The latest assignment submitted on time will be graded. If you submit an assignment late, after submitting an assignment on time, you must let me know, via email, that you would like the late submission graded for the assignment.

Written Assignments

Written Assignments can be delivered electronically by email, or hard copies can be delivered by hand either in class, or dropped at my office NSB A330.

Electronic copies must be in one of the following formats: .pdf, Microsoft Word .doc, Google Docs.

Hand written copies are acceptable, but be very careful that the work is clear. If I can't read that an answer is correct, it is wrong.

Points for each question will be described in each assignment.

Exam Policy

The Midterm will be held during class on October 21nd. If you will not be able to make this date, let me know as early as possible, and I will do my best to schedule another time for you to take the Midterm.

During both the Midterm and Final exam, you will be allowed to bring a single (8.5in x 11in) sheet of paper with notes. No other material will be allowed during the exams.

The Final Exam will be cumulative, with a focus on material covered in the second half of the semester.

When the Final Exam is scheduled, time and location information will be posted here.

Text Book

Introduction to Algorithms 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. MIT Press. 2001. ISBN: 978-0262033848

This should be available through the bookstore, but may be found through other outlets at a discount.

Schedule

Date | Material | Assignments |
---|---|---|

Thursday, August 26 |
Introduction. Class Overview. Review of Basic Data Structures and Math. Sequential v. Binary Search Slides | HW1 (Personal Information) Assigned |

Tuesday, August 31 |
No Class. | |

Thursday, September 2 |
Asymptotic Notation. Recursion. Review of Inductive Proofs. Slides | HW1 Due, HW2 Assigned (Written: Asymptotics and Run Time of Algorithms) |

Tuesday, September 7 |
Runtime of Recursive Algorithms Part I (Merge Sort, Quick Sort) Slides | |

Thursday, Sepember 9 |
No Class | |

Tuesday, September 14 |
No Class, Friday Schedule. | |

Thursday, September 16 |
Runtime of Recursive Algorithms Part II Slides | Read Chapter 8. HW 2 Due, HW 3 Assigned (Code: Sorting) [HW-3] [Sample input] [Sample output] [Sample input (DOS)] [Sample output (DOS)] |

Tuesday, September 21 |
Linear-time Sorting - Counting Sort, Radix Sort, Bucket Sort. Slides Proof of Horner's Rule | |

Thursday, September 23 |
Binary Search Trees Slides | HW 3 Due, HW-4 Assigned (Written: Sorting) |

Tuesday, September 28 |
No class | |

Thursday, September 30 |
No class | |

Tuesday, October 5 |
Heaps. Slides | |

Thursday, October 7 |
Balanced Binary Search Trees Part I Slides | HW 4 Due, HW-5 Assigned (Code: Heaps and Heapsort) |

Tuesday, October 12 |
Balanced Binary Search Trees Part II Slides | |

Thursday, October 14 |
Operations on Streams of Data Slides | HW 5 Due, HW-6 Assigned |

Tuesday, October 19 |
Midterm Review | |

Thursday, October 21 |
Midterm Exam | |

Tuesday, October 26 |
Dynamic Programming Slides | HW 6 Due |

Thursday, October 28 |
Greedy Algorithms Slides | HW-7 Assigned (Code: Dynamic Programming) |

Tuesday, November 2 |
Huffman Coding Slides | |

Thursday, November 4 |
Optimization Slack and Review. Slides | HW 7 Due, HW-8 Assigned (Written: Optimization) |

Tuesday, November 9 |
Introduction to Graphs. Slides | |

Thursday, November 11 |
Graph Algorithms: Breadth-first-search. Depth-first-search.Slides | HW 8 Due, HW-9 Assigned (Written: Graph DFS, BFS, Dijkstra's Algorithm) |

Tuesday, November 16 |
Dijkstra's Algorithm. Strongly Connected Components. Minimum Spanning Trees. Prim's Algorithm. Slides | |

Thursday, November 18 |
Kruskal's Algorithm. Bellman-Ford Slides Slides part 2 | HW 9 Due, HW-10 Assigned (Written: Graph Distances) |

Tuesday, November 23 |
NP-Completeness Slides | |

Thursday, November 25 |
No Class - Thanksgiving | |

Tuesday, November 30 |
Hashing Slides | HW 10 Due, HW-11 Assigned (Code: Graph Distances) |

Thursday, December 2 |
More Hashing Slides | |

Tuesday, December 7 |
Multi-core Algorithms Slides | |

Thursday, December 9 |
Final Review SlidesNote: the final covers any material covered in class and homework unless explicitly noted otherwise. This includes material not explicitly covered in these review slides. |
HW 11 Due |

Tuesday, December 14 |
Final Exam 6:15pm - 8:15pm |