In Teaching

CS5350 — Advanced Algorithms — Fall 2011

No Comments

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:

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
  • Short projects: Due on October 21, 2011!!!
  • First midterm exam on September 28th (week 6), topics covered in the exam
  • Final exam on Monday November, 16th (week 13)

MATERIAL:

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)
  • 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
  • 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.
  • 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
  • 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: 2.1.3 and 2.1.4, from Introduction to Algorithms
    • Reading assignment: Introduction to Algorithms, Chapter 2, Sections 2.1 and 2.2.
  • 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:

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

Author

Related Posts

Write A Comment

%d bloggers like this: