Algorithms and Data Structures

COSC 311

(MW 2:00-3:50, PH 514)

Instructor: Matt Evett ; Dept. Computer Science; Pray-Harold 511
Tel: 734-487-1227
e-mail: mevett@emich.edu
Course web site: http://canvas.emich.edu/

Office Hours: T 10:00 -3:00; Th 10:00-12:00
(These times are subject to change. Please see my web site, http://emunix.emich.edu/~evett for up-to-date hours.) 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.

Prerequisite: COSC 211, 221.

Textbook: Weiss, Data Structures and Algorithm Analysis in Java, 3rd Edition, Pearson, 2012.

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:

Tentative due dates for projects are underlined. Exam dates are in bold. For final calendar, please see the course's Canvas shell.
 
Date Text Projects due
1/7, 1/9

Java review (esp. exception handling, Javadoc and packages), Ch 1

 
1/14, 16 Ch 1 & Java review (esp. interfaces), design patterns, functors, generics  
MLK Day, 1/23 Ch 2 (analysis) HW#1
1/28, 30 Ch 2 (analysis) HW#1.5
2/4, 6 Ch 3 (Lists, Stacks, Queues) HW#2
2/11, 13 Ch 3 & Ch 4 (Binary Trees, traversals) Proj#1
2/18, 20 Ch 4 (AVL, B-Trees) Proj#2
Winter Break    
3/4, 6 Ch 5 (Hashing)  
3/11, 3/13 Ch 6 (Priority Queues) Midterm Exam
3/18, 20 Ch 6 (Binar heaps), Ch 7 (Sorting) Proj#3
3/25, 27 Ch 7 (Quicksort, etc.)  
4/1, 3 Ch 8 (Disjoint Set Class) Proj#4
4/8, 10 Ch 9 (Graph Algs., shortest path) Proj#5
4/15, 17 Ch 9 (Spanning trees, depth-first search)
Monday 4/22 1:30-3:00 Final Exam Final Exam

 

Course Concepts:

    1. Principles of Programming
    2. Review of Java concepts
    3. Recursion (advanced)
    4. Data abstraction:  Abstract Data Types and Java classes
    5. Stacks:  various implementations, applications
    6. Queues:  various implementations, applications
    7. Java class Libraries
      • Class relationships and inheritance
      • Functors
      • Template classes
    8. Algorithm efficiency:  growth rates and big-O notation
    9. Sorting: comparison of various algorithms
    10.         Selection, bubble, insertion, merge, and quick sort.
    11. Searching: Sequential and Binary Search.
    12. Trees:  Binary Tree, binary search tree, implementation and applications
    13. Graph: directed, undirected, implementation, DFS, BFS.
    14. Hashing
    15. Priority Queue, heaps, heapsort

    Grading Policy:

    The final course grade will be a weighted average of the grades received in each of the following categories, as specified: Homeworks 25% of total grade, Quizzes 5%, Programs 25%, Midterm exam 20%, Final exam 25%.

    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. (75%) Correctness -- does the program run correctly?
    2. (10%) 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 Canvas:

    The course's Canvas site is the official means of communicating information about this course, including announcements regarding programming assignments, readings, etc. Please feel free to submit your own questions and remarks to the discussion areas on this site, it is an integral part of the course.

    Cheating policy:

    Students are required to attend to the policy on academic irregularity outlined in the EMU student handbook. In addition, collaboration among students in solving programming and homework assignments is forbidden. If I receive programs or homework assignments that are substantially equivalent, or which are not the original work of the student submitting the material, I will not hesitate to punish all involved parties to the fullest extent, up to and including assignment of a failing grade for the course, and referral to the Office of Judicial Student Services for possible punitive action at the University level, which may include expulsion from the University. In addition, the University and the computer science department maintain policies regarding proper behavior on its computer systems. Failure to adhere to these policies can result in loss of computer privileges, and possible legal action.