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 tests, some written assignments, quizzes (announced and unannounced), a project and a presentation. The project will involve programming some algorithms and carrying out an analysis on their performance. For the presentation, students will individually present an algorithm research paper from a journal or conference, preferably recent.
Grades:
Test 1 20%
Test 2 20%
Presentation 15%
Quizzes and Assignments 15%
Project 20%
Class participation 5%
Announcements:
- Weeks 15 and 16 (finals’ week):
- Projects presentations
- Week 14:
- More work on projects, no class
- Projects reports due by Sunday November, 28th at 7pm via email to your instructor
- Week 13:
- Final exam on Monday November 15th
- Work on projects on Wednesday: no class / instructor available for questions
- Week 12:
- Presentations of articles in class: 5- to 7-minute presentations
- Week 11:
- Long quiz on Monday November, 1 at 1:30 until 2:50pm: objective = to get ready for the exam scheduled on Monday November, 15.
- Week 6:
- First exam on Monday September, 27 at 1:30pm until 2:50pm.
- There will be no office hours since Dr. Ceberio will be out of town attending a conference.
- Week 5: The Monday office hours will exceptionally be moved to Tuesday from 10am to noon.
- Week 3: Since Monday is a day off, office hours from Monday will be moved to Tuesday from 10am to noon.
What to expect — some of this semester’s milestones:
- Semester-long projects:
- Projects will be proposed during week 3: see below for the list of projects / also sent as email to all students enrolled in the class
- Students need to have chosen a project by the end of the last course of Week 4 (i.e., September, 15 at 3pm):
- IMPORTANT! Project assignments were sent out to all students on Wednesday September, 15. You should all be now working on them as all projects require your full attention until the end of week 14.
- Project meetings with instructor: Week 9-10 / week 11-12 / week 14
- The second half of week 13 will be dedicated to working on your projects
- Week 14: no class but you will have to meet with me to report on your project’s progress
- Week 15 and week of the finals: project presentations
- First midterm exam on September 27th
- Article presentations: week 12 (Nov. 8 and 10); articles will be given to students on October 27th.
- Final exam the Monday November, 15th
Material:
- CS5350 Syllabus
- Copy of the daily grading form
- Outline of the semester Lectures and activites
- The list of projects for this semester is now available
- Make sure you give your preferences to Dr. Ceberio by September, 15 at 3pm
- An example of a tree drawn for you by Maria Barraza
- An interesting presentation about testing
- Solution to the Hotel problem by a student
Assignments:
- Week 10:
- Reading assignment: Chapter 8 of Algorithms in a Nutshell and Chapter 26 of Introduction to Algorithms
- Homework:
- Prepare a presentation of the Ford-Fulkerson method. Show how it can be implemented different ways with different performances.
- Prepare a presentation of the example of the FF method as shown on your book, p. 726.
- Week 9:
- Reading assignment: Chapters 16 and 17 of Introduction to Algorithms.
- Extra-credit due by November 3rd on paper
- Homework due by October 27 at the start of the class (randomly picked) + some exercises given in class on showing the greedy choice property
- Week 8:
-
- Reading assignment: Chapters 15 and 16 of Introduction to Algorithms, Chapter 6 of Algorithms in a Nutshell
- Homework assignment:
- Work on the matrix chain multiplication problem, as described in class, for Wednesday October, 13
- More homework to be randomly picked-up next Monday (October 18): description of exercises
- Week 7:
- Reading assignment: Chapters 15 and 16 of Introduction to Algorithms, Chapter 6 of Algorithms in a Nutshell
- Week 5:
- Reading assignment: Chapters 4 and 5 of Introduction to Algorithms
- Homework assignments:
- Exercises 4.1.1, 4.1.2, 4.1.3, 4.1.5
- Problems 3.1 and 3.4
- Extra-exercises to work on:
- 4.3.1, 4.3.2, 4.3.3, 4.3.6, 4.3.9
- 4.4.2, 4.4.4, 4.4.5, 4.4.6, 4.4.7, 4.4.8
- Extra credit: Due via email by Friday Sept. 24 at 7pm: Write an explanation of the proof of the master theorem in your own words (potential for extra points: 10 points towards the sum of the exams’ grades)
- Week 4:
- Reading assignment: Chapter 4 of Introduction to Algorithms, revision of Chapters 1 and 2 + Chapters 3 and 4 of Algorithms in a Nutshell
- Homework assignments:
- Prove all properties of transitivity, reflexivity, etc. from your textbook Introduction to Algorithms that we did not do together in class
- Exercises 3.1.2, 3.1.4, 3.1.5, 3.1.7, 3.1.8
- Week 3: Read Chapter 3 of Introduction to Algorithms and Chapter 2 of Algorithms in a Nutshell. There will be a quiz on Wednesday September, 8th on the whole 3.2 section.
- Homework: Exercises given in class and exercises 3.2.1 and 3.2.2 from Introduction to Algorithms
- Exercises given in class were:
- To show how the recursive Fibonacci number computation is an example of Divide and Conquer algorithm
- To present one algorithm (different from what we saw in class) that is a Divide and Conquer algorithm, and show that it is actually one
- To do the problem on Horner’s rule from the Introduction to Algorithms textbook
- To do the problem on Insertion and Merge sort from the Introduction to Algorithms textbook
- Week 2: Read Chapters 2 and 3 of Introduction to Algorithms
- Week 1: Read Chapters 1 and 2 of both textbooks
Some material:
- August 25: 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.
