**VERY IMPORTANT: ALL students SHOULD HAVE THEIR TEXTBOOKS BY DAY 1 of classes!!!**

**Course Description:** The purpose of this course is to present the student with the mathematical techniques used for analyzing the time and space performance of computer algorithms. The focus will be on the practical application of these techniques to designing efficient algorithms. The following topics will be covered: asymptotic notation, recurrences, lower bounds for worst case and average case, dynamic programming, searching algorithms, sorting algorithms, graph algorithms, and if time allows, parallel algorithms, string matching algorithms.

**Textbooks: **

It is very important that ALL students have their books from Day 1.

- “Introduction to Algorithms”, by Cormen, Leiserson, Rivest, and Stein, Third Edition, McGraw Hill
- “Algorithms in a nutshell”, by Heineman, Police, and Selkow, by O’Reilly, 2008.

**Exams:** There will be two examinations, some written assignments, homework assignments, quizzes (announced and unannounced — but roughly one quiz every week), two projects, and a presentation. On of the projects will involve testing an existing library for performance purposes. The other project will involve programming some algorithms and carrying out an analysis on their performance. For the presentation, students will present an algorithm research paper from a journal or conference, preferably recent.

**Grades**:

Test 1 20%

Test 2 20%

Presentation 8%

Quizzes 15%

Homework assignments 10%

Projects 22%

Class participation 5%

**SUMMARY OF IMPORTANT DATES:**

- October 21: deadline for Projects #1
- October 28: deadline for Projects #2 — tutorials
- October 28: deadline for extra credit assignment
- November 4: deadline for article summary; the list of article assignments is now available
*November 7: review*- November 9: long quiz in preparation for the second exam
- November 11: deadline for 2nd extra-credit assignment
*November 14: review*- November 16: examination #2
- November 29 (updated!): deadline for Projects #2

**ANNOUNCEMENTS:**

- Week 14:
- Monday November, 21st: Project #2 Presentation by the team working on Convex Hulls

- Week 12:
- Short quiz on Monday and review for the exam
- Long quiz on Wednesday

- Week 11:
- Group quiz on Monday!
- Grades for project 1 are ready: please stop by my office if you want to know your grade.
- The second extra credit assignment is now available on this page.
- Wednesday:
**office hours are exceptionally changed!**they will be from 10:30 to 11:45 instead of the usual time.

- Week 10:
- Quiz on Monday!

- Week 9:
- Quiz on Monday!

- Week 8:
- Quiz on Monday! and Quiz on Wednesday!

- Week 7:
- Quiz on Monday! (on Chapter 4) and on Wednesday!
- Project #2: make plans to meet with me asap as a group of all the people who picked the same project topic area! Check: http://meetwith.me/mceberio to suggest meeting times (suggest 3 meeting times of half an hour each so that I can pick)

- Week 6:
- The first exam is scheduled on Wednesday September, 28th.

- Week 5:
- Quiz on Monday!

- Week 4:
- Quiz on Monday!
- Remember that you have to send me your projects’ preferences!!!
- Project topics (for project 2) have been assigned: check your mailboxes!

- Week 3: No class on Monday: Labor Day. As a result, the office hours of Monday are moved to Tuesday from 1:30pm to 2:30pm / Quiz on Wednesday!

**WHAT TO EXPECT — some of this semester’s milestones:
**

- An article to summarize: Due by November 4!
- See the guidelines for this assignment
- Make sure that you joined the shared folder to have access to the articles for your assignment
- In case you forgot, you can review your individual article assignment here

- Semester-long projects: Due by the end of week 14!
- A list of projects (for projects #2) will be proposed
**during week 3** - Students need to have chosen a project (#2) by the end of the last course of Week 4
- Assignment #1 (group assignment): write a tutorial. Due by Friday October, 28

- A list of projects (for projects #2) will be proposed
- Short projects: Due on October 21, 2011!!!
- Guidelines for project #1 are now available.
- Project #1: Final deadline on Friday October, 21 at 11:59pm

- First midterm exam on September
**28th**(week 6), topics covered in the exam - Final exam on
**Monday November, 16th**(week 13)

**MATERIAL: **

- CS5350 Syllabus
- Copy of the daily grading form
- (UPDATED) Outline of the semester Lectures and activites
- An interesting presentation about testing
- Week1 group work material: light intro to correctness, performance, and algorithm design
- Week 8: notes on dynamic programming

**ASSIGNMENTS:**

**Note:**unless otherwise specified, homework will be due via email on Wednesdays at 5pm (from the students whose names are called in class).**Week 12: (Nov. 7 to Nov. 11)**- 2nd extra-credit assignment — Due by Friday November, 11

**Week 11: (Oct. 31 to Nov. 4)**- Article summary assignment — Due by Friday November, 4
- Reading assignment: same as week 10.
- Homework assignment:
- Turn in either of the following proofs: proof that the Huffman’s code algorithm has the greedy choice property; or proof that the greedy approach to the fractional knapsack problem (as discussed in class) has the greedy choice property.
- Turn in a proof that the 0-1 knapsack problem does not have the greedy choice property.

**Week 10: (Oct. 24 to 28)**- Extra-credit assignment: Proof of the master theorem in your own words (more details to come soon) — Due by Friday October, 28
- Project #2: Tutorial due Friday October, 28
- Reading assignment:
- Chapters 15 and 16 from the Cormen textbook
- Chapter 26 of the Cormen textbook and Chapter 8 of Algos. in a Nutshell

- Homework assignment:
- (not to be turned in… yet 🙂 ): Exercises 16.1.* from the Cormen textbook

**Week 9: (Oct. 17 to 21)**- Project #1: Final deadline on Friday October, 21 at 11:59pm (see the project guidelines)
- Homework assignment:
**Deadline extended to Monday October, 24th**- Problem 15.3 from Cormen textbook

- Reading assignment:
- Chapters 15 and 16 from Cormen texbook
- pp. 165-171 of Algorithms in a Nutshell

**Week 8: (Oct. 10 to 14)**

- Homework assignment:
- Exercises 15.1.5 (p. 370 of Cormen textbook), 15.2.1 and 15.2.3 (p. 378) are to be turned in; hints of solutions now available.
- Reminder: besides the exercises to be turned in, you have to practice on as many exercises as possible

- Reading assignment:
- Chapters 15 and 16 from Cormen texbook
- pp. 165-171 of Algorithms in a Nutshell

- Homework assignment:
**Week 7: (Oct. 3 to 7)**- Homework assignment:
- Problem 4.6 of Introduction to Algorithms; solution hints now available

- Reading assignment:
- Chapter 4 of Introduction to Algorithms
- Part II (Chapters 6,7,8) and III (Chapters 10, 11, 12) of Introduction to Algorithms: the purpose of this reading assignment is to refresh everybody’s mind about the material of the course that is a pre- requisite to CS5350.

- Homework assignment:
**Week 6: Week of Exam 1!!!**- Homework assignment: no homework to turn in. However, students are encouraged to practice on the exercises from the book.
- Reading assignment: review of all chapters that were assigned previously
- Project #1 (reminder): intermediate deadline coming up this Friday! (see the project guidelines if you don’t remember what you have to do)

**Week 5:**- Homework assignment: Solution hints
- To be turned in: Problems 2.1, 3.6
- Not to be turned in but likely to appear on a quiz or test: all exercises 3.1.*; Problem 3.4

- Reading assignment: Chapters 3 and 4 of Introduction to Algorithms

- Homework assignment: Solution hints
**Week 4:**- Homework assignment: 2.2.1, 2.2.2, Problem 2.3 (due Wednesday of Week 4 by 5pm / via email); Solution Hints
- Reading assignment: Chapter 2 Section 2 of Introduction to Algorithms, Chapters 2 and 4 of Algorithms in a Nutshell

**Week 3:**- Homework assignment:
- Reading assignment: Introduction to Algorithms, Chapter 2, Sections 2.1 and 2.2.

- Homework assignment:
**Week 2:**- Same reading assignments as for Week 1
- Homework assignment: TBA (due Wednesday September, 5th)

**Week 1:**- Read Chapters 1 and 2 of both textbooks
- For those of you who did not attend Monday’s session:
- Read, print, sign, and turn in the course syllabus
- Check your email: I sent you documents for you to work on on Wednesday, in groups

**Additional material:**

**August 24:**Some information about Fibonacci numbers

**Note:** More information (such as assignments, reminders for due dates, quizzes, exams) will be posted on this page as the semester goes.