ECE 215 Design and Analysis of Algorithms Fall 2008 Course Information

• Description: This course covers a presents a variety of algorithms and techniques for designing good algorithms and for evaluating their efficiency. Also introduced are classic algorithms (sorting, searching, string pattern matching) and efficient algorithm design techniques (recursion, divide-and-conquer, branch-and-bound, dynamic programming). Weekly lab assignments will require programming in an object-oriented programming language.

---

• Instructor: Dr. Klefstad, e-mail: klefstad@uci.edu,
• Office Hours: TuTh 6:20pm-? outside ELH 110
• Lecture TuTh 5:00pm-6:20 in ELH 110. I will present concepts and examples to help you master the material. I will also answer concept-related questions of general interest.
• Programming language may be either Java, C++, or C# - your choice.
• Objectives
  • Understanding of fundamental algorithms and data structures - their implementation and complexity analysis.
  • Ability to analyze the running time complexity (in big-oh notation) of each of the algorithms covered in this class.
  • Ability to combine complexities for compositions of functions.
• Algorithms include
  • Sequential search
  • Binary search
  • Insertion sort
  • Quick sort
  • Merge sort
  • string pattern-matching
    • Rabin-Karp
    • Knuth-Morris-Pratt
    • Boyer-Moore
  • and more...

Outcomes

• To be able to implement the algorithms outlined above in a modern high-level object-oriented programming language both in homework assignments and on in-class exams.
• To be able to analyze the running time complexity (in big-oh notation) of each of the algorithms covered in this class and for compositions of functions with known comlexities.

Text

Required Textbook

• Introduction to Algorithms 2nd Edition by Cormen, Leiserson, Rivest, Stein. ISBN: 0-262-03293-7 Positive: this is a comprehensive text that is used by many universities so it has good resale value, algorithms are presented in a pseudocode that is very similar to Python. Negative: very terse and the math can overwhelm all but the most interested student, very weak in describing typical applications of data structures and algorithms.

Recommended Textbooks

• Algorithm Design: Foundations, Analysis, and Internet Examples by Goodrich, Tamassia. ISBN: 0-471-38365-1. Positive: uses psuedo code and Java, describes internet applications of the data structures and algorithms, lots of pictures. Negative: seems more like a first draft than a text, both the code and the prose could benefit from some editing/rewrite.
• Data Structures & Algorithm Analysis in C++ by Mark Allen Weiss ISBN: 0-201-36122-1. It is OK for a C++ specific text.
• Data Structures and Algorithms by Aho, Hopcroft, Ullman ISBN: 0-201-00023-7. I haven't seen it, but it has been used in several universities. Check out algorithms and data structures on-line at algorithms and data structures

Assigned Reading should be read before the appropriate lecture to help you understand the material as it is presented in lecture. I will implement the algorithms and data structures in lecture. See the table on the course main page for assigned reading.

Course grade will be assigned according to a curve of combined scores from 6 homeworks (30%), 4 quizzes (40%), and a final exam (30%). No make-ups for exams. All questions about homework, course material, and grading should be directed to your TA. Use the lab/discussion section or email to your TA for clarification of homework and lecture material.

Homework will be graded in your lab section each week. You must submit your homework directly to me in lecture. Start early on homework assignments to allow yourself adequate time for unforeseen delays and last minute crunches. Label your homework with your name, student ID, and ECE 215. Late homework will not be accepted. Discussing concepts with others is ok, but copying another's solution is cheating and all students involved will be punished severely. Fabricating output for a program that does not work correctly is also cheating and will result in a zero score for that assignment. Homework is your chance to teach yourself the material for that week.

Quizzes will be passed out in lecture on Thursday. They will be take home exams. Your typed solution is due by start of lecture the following Tuesday. You may use any book reference, but no human help.

Final Exam will be a comprehensive take-home exam. You must complete the exam yourself with no help from other humans. You may use any book reference you like. I will give you one full week to complete the exam.