- Description
This course introduces abstract behavior of classic data structures (lists, stacks, queues, priority queues, hash tables, and binary search trees), alternative implementations, informal analysis of time and space 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, Phone: (949)824-1901, e-mail: klefstad@uci.edu,
- Office Hours: MoWe 4:30-5:30pm in ET 616E.
- Lecture
MoWe 3:00pm-4:20 in HH 178. 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 C++, Java, C#, or Python - your choice.

- Objectives
- Understanding of fundamental algorithms and data structures - their interfaces and implementation.
- Ability to analyze the time and space complexity (in big-oh notation) of each of the data structures and algorithms covered in this class.
- Ability to combine complexities for compositions of functions.
- Data Structures include (both array and linked representations)
- Lists (unordered, ordered, sorted)
- Stacks
- Queues
- BinarySearchTrees
- HashTables
- BinaryHeaps
- Character Strings

- Algorithms include
- Sequential search
- Binary search
- Insertion sort
- Quick sort
- Merge sort
- string pattern-matching
- Rabin-Karp
- Knuth-Morris-Pratt
- Boyer-Moore

- Outcomes
- To be able to implement the algorithms and data structures 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 time and space complexity (in big-oh notation) of each of the data structures and 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 8 homeworks (30%), 2 midterm exams (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 your TA. 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 198. Late homework will be docked 30 points per 24 hour period starting from the due time. 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. You should bring a few floppy diskettes to lab.

- Midterms
will be given in lecture as announced by the instructor. The first midterm will cover the homework and lecture material up to the exam, and the second midterm will cover the material from the first midterm until the second midterm.

- Final Exam
will be a comprehensive written test on Wednesday, March 20 from 1:30pm-3:30pm in HH 178.

- Regrades
must be requested from your TA within one week of the posting of that grade. The entire assignment will be regraded by the TA, and the regrade score will replace the original score. Regrade should be requested only if the points were mis-totaled or if there was a mistake in grading a problem. The amount of points taken off for a particular error is not negotiable. Regrade scores are often lower than original grade scores, but if you feel the regrading is unfair, let the instructor know as soon as possible, and I will check for possible grading errors.

- Dropping
this course is not allowed after the last lecture of the 2nd week of the quarter. Until then, anyone may drop with signature of the TA. Some students may be permitted to drop until the last lecture day of 6th week with permission from the ECE chairman's office and signature of the instructor.

- Dealing with TA problems
if you have any problem with your TA or if you notice any inconsistencies in grading, please let the instructor know soon as possible so we can correct the problem. If you have questions about the course material or grading, see your section TA. Feel free to drop by the instructor's office during office hours to chat or get better acquainted. Please do not drop by outside of scheduled office hours. Please direct your questions via email to your TA.