Algorithms and Data Structures

Dept. Computer Science; room 512E Pray-Harrold
Tel: 734-487-1227; e-mail: evett@emunix.emich.edu;
https://emunix.emich.edu/~evett/DataStructures

Office Hours: TTh 1:00-5:00
You may drop by at times other than office hours, but in that case I cannot guarantee that I'll be able to see you.

Textbook: Weiss, Algorithms, Data Structures and Problem Solving using Java 3nd Edition, Addison-Wesley, 2006.

Course Summary: Students successfully completing this course will understand the beneficial concepts of abstract data types (ADTs) including encapsulation, abstraction, security, polymorphism, inheritance, etc. Students will obtain proficiency in the use and implementation of the most common abstract data types, including trees, linked lists, queues, hash tables, stacks, etc. The course also covers some of the basic techniques for complexity and performance analysis of programs using ADTs.

The course is project oriented, with Java programming assignments spread throughout the semester. Students will learn advanced Java programming techniques including the use of inheritance, generic containers, and the Java Container Library.

Course Calendar:

Course Concepts:

1. Principles of Programming
2. Review of Java concepts
3. Recursion (fundamentals)
4. Data abstraction:  Abstract Data Types and Java classes
5. Linked lists
6.        Pointers and dynamic allocation
7.        Basic operations:  insert and delete, traversal, recursive processing
8.        Variations:  circular, dummy header, doubly-linked
9. Stacks:  Stack ADT, various implementations, applications
10. Queues:  Queue ADT, various implementations, applications
11. Java Class Libraries

• Class relationships and inheritance
• Virtual functions
• Template classes
• Operator overloading

12. Algorithm efficiency:  growth rates and big-O notation
13. Sorting: comparison of various algorithms
14.         Selection, bubble, insertion, merge, and quick sort.
15. Searching: Sequential and Binary Search.
16. Trees:  Binary Tree ADT, binary search tree ADT, implementation and applications
17. Graph ADT, implementation, DFS, BFS.
18. Table ADT
19. Hashing
20. Priority Queue ADT, heaps, heapsort

Grading Policy:

There will be five, unannounced quizzes, evenly distributed across the semester.  The quiz component of a student's overall grade for the course will be the average of that student's four highest quiz grades.

Tardiness Policy: Programming and other homework assignments will be due at the beginning of class. After that, assignments will be accepted through the start of the next scheduled class, but will suffer a full grade penalty. E.g., if a late programming assignment is worthy of an 'A', I will mark it a 'B'. Assignments more than one class late will not be accepted, and will receive a grade of 'F'.

Attendance Policy: We're all grown-ups, when and whether you attend class is up to you. However, missed assignments, and exams shall only be excused by a doctor's written note, verifying that the student was medically indisposed to attend class that day. The first missed quiz (for any reason) will be treated as the "lowest graded quiz", and therefore dropped from the averaging calculation. Any additional missed quizzes must be excused by a doctor's note.

Grading of Programs: Grading of programming assignments will reflect three factors, weighted as shown.

1. (70%) Correctness -- does the program run correctly.
2. (15%) Style -- does the code adhere to class documentation standards? Is the code indented properly? Are the variable names mneumonic? Etc. See the handout on acceptable programming style.
3. (15%) Design -- is the program adequately decomposed (i.e., are the functions and procedures small enough to be comprehensible)? Are the class and structure definitions well chosen? Has the student made good use of existing classes and libraries. Make no mistake: if you hand in a program that works, but that does not adhere to class style standards and is poorly designed, that program can receive a poor grade. Conversely, if you hand in a program that is well documented, well designed, but still has a few bugs, that program can receive a passing grade.

Announcements and the Webcaucus:

Cheating policy: