CS5350 — Fall 2012

VERY IMPORTANT:

• Students: Please register at http://www.piazza.com/utep/fall2012/cs5350 using your utep.edu email address only.
• 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.

For more information about the course, please download the syllabus here.

SUMMARY OF IMPORTANT DATES:

• Information to be posted soon, as the semester starts

ANNOUNCEMENTS:

• Week 2: No class on Monday: Labor Day / Quiz on Wednesday!
• Week 1: Quiz on Wednesday

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

• An article to summarize
• Semester-long projects: Preliminary list of projects available, teams and topics available here; DEADLINE is November 26th.
• Short projects: some guidelines about the projects, teams and topics available here; DEADLINE is October 25th.
• Midterm exam: Monday October 29th
• Final exam: Wednesday December 12 from 4pm to 6:45pm.

MATERIAL:

• CS5350 Syllabus
• Copy of the daily grading form
• Outline of the semester Lectures and activites from past semester (will be updated as the semester goes)
• An interesting presentation about testing
• Week1 group work material: light intro to correctness, performance, and algorithm design
• Notes on dynamic programming

ASSIGNMENTS:

• Week 16: (december 12)
  • FINAL EXAM on Wednesday December 12 from 4pm to 6:45pm.
• Week 15: (december 3 and 5)
  • Presentations of projects 2
• Week 14: (november 26 and 28)
• Week 13: (november 19 and 21)
• Week 12: (november 12 and 14)
  • Reading assignment: Chapter 26
• Week 11: (november 5 and 7)
  • Reading assignment: Chapters 22, 23, 24, 25
• Week 10: (october 29 and 31)
  • Midterm exam on Monday
  • Greedy algorithms on Wednesday (Read Chapter 16)
• Week 9: (october 22 and 24)
  • Work on dynamic programming problems in teams
  • Review for midterm on Monday October 29
  • Project 1 due on October 25!
• Week 8: (october 15 and 17)
  • Read Chapter 16 of Introduction to Algorithms
• Week 7: (october 8 and 10)
  • Read Chapter 15 of Introduction to Algorithms
• Week 6: (october 1 and 3)
  • Keep reading chapters 4, 5, and 6 from Algorithms in a Nutshell: you need to have it done by the end of Week 6
• Week 5: (september 24 and 26)
  • Read Chapter 4 of Introduction to Algorithms
  • Homework assignment: Problem 4.1, Problem 4.6
  • Keep reading chapters 4, 5, and 6 from Algorithms in a Nutshell: you need to have it done by the end of Week 6
• Week 4:
  • Read Chapters 1 and 2 of Algorithms in a Nutshell
  • Read Chapters 2 and 3 of Introduction to Algorithms
  • Homework assignment: Problem 2.1, Problem 3.1, Problem 3.4, Problem 3.6: homework will be randomly checked on Wednesday September 19th in class: have it ready in a file named: LastName.doc, LastName.docx, or LastName.pdf + your file must be readable without any problem of formatting using open office and word if it is an office document; if your name is called, you will have to send it right after that class.
  • Start reading chapters 4, 5, and 6 from Algorithms in a Nutshell: you need to have it done by the end of Week 6
  • Partial quiz solutions for loop invariants
• Week 3:
  • Problem 2.3 (p.41) due on Thursday September, 13 at 11:59pm via email with email subject: “[CS5350] FirsName LastName: Homework: Problem 2.3”
• Week 2:
  • Chapter 2 with special attention to the loop invariant
  • Problem 2.3 (p.41) due on Thursday September, 13 at 11:59pm via email with email subject: “[CS5350] FirsName LastName: Homework: Problem 2.3”
• Week 1:
  • Triad activities on correctness, performance, and design
  • 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

Additional material:

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