ECE 198
Algorithms and Data Structures
Spring 2002
Course Information
• 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.```

• Office Hours: MoWe 4:30-5:30pm in ET 616E.
• Lecture
```MoWe 3:00pm-4:20 in HH 178. I will present concepts
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
```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.
```
```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
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
on homework assignments to allow yourself adequate
time for unforeseen delays and last minute crunches.
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.
```
```must be requested from your TA within one week of the
posting of that grade. The entire assignment will be
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