Instructor: Dr. Daniel S. Roche, Michelson 356, x36814, .

Course Website: http://www.usna.edu/cs/roche/312/

All assignments, class notes, and important announcements will be posted from the course website. Students are expected to check it frequently.

1 Course Description

This course examines abstract data types (ADTs), data structures, data representation and information management including storage structures, allocation and collection. ADTs and data structures presented include lists, stacks, queues, trees, heaps, priority queues, maps, dictionaries and graphs. Sorting and searching techniques, hashing and graph algorithm analysis are also covered.

2 Textbooks

None required.

3 Graded Work

3.1 Quizzes

Quizzes are a low-stakes chance for students to assess their progress. They will be given occasionally at the start of class. No collaboration is allowed on quizzes.

3.2 Homeworks

Routine out-of-class homework assignments will be assigned frequently and are usually due at the next class meeting, or within one week. Some homeworks will involve programming.

Collaboration is allowed on homeworks (according to definitions below), but copying is never allowed. All sources must be properly, clearly, and specifically cited.

Students must complete all homework assignments in order to earn a passing grade in the class.

3.3 Projects

There will be 3 significant projects in this class.

Except when directed to work in small groups, projects must be on an individual effort. Students may informally discuss projects but may not collaborate in any way (see definitions below). Any discussion or resources used must be properly, clearly, and specifically cited.

Students must complete all projects in order to earn a passing grade in the class. "Completion" is at the discretion of the instructor, but entails (at least) submitting code that substantially works as specified in the project requirements.

3.4 Exams

Two midterms (not cumulative) and a final exam (cumulative) will be given. Dates will be announced well in advance, and any student with a scheduling conflict for any exam date must notify the instructor at least one week in advance so that alternative arrangements can be made.

3.5 Final grade

• 2%: Quizzes
• 20%: Homeworks
• 30%: Projects (3)
• 22%: Midterm exams (2)
• 26%: Final exam

4 Late Work

Homeworks and projects submitted after the deadline will not receive credit, in order to facilitate immediate posting of solutions. Exceptions for bona fide emergencies or other exceptional circumstances will be considered by the instructor.

All homeworks, projects, and exams must be completed in order to earn a passing grade in the class. Homeworks and projects may be submitted (or resubmitted), after the deadline, for no credit, in order to satisfy this requirement.

5 Absences

Students missing class for valid reasons are excused from in-class quizzes.

Otherwise, each student is responsible to make up the work they miss due to planned absences such as movement orders for sports and extra-curricular activities as well as medical procedures. There will be no blanket exception to the late policy to account for absences. Generally, students should plan ahead and make arrangements with classmates or the instructor to ensure their work is submitted prior to the deadline.

6 Academic Integrity

For the purposes of this class, we make a distinction between:

• Discussion means talking between classmates about how to tackle a particular (written or programming) problem. Anything that is written down in a discussion (including code) must be erased or destroyed, and cannot be submitted. Students must wait at least one hour after any discussion before they sit down to write up their own solutions.
• Collaboration means actually sitting down and working together on a problem. This is beyond discussion because the written materials are not destroyed. However, each student must still write up their own solution in their own words. Furthermore, copying is not collaboration, and each student is responsible to have a complete understanding of anything they submit.

Discussion is allowed on projects and homeworks, but collaboration is only allowed for homeworks. Copying is never allowed. A simple rule of thumb is that, for anything submitted as a course project, you should be the only human being that has ever seen it, other than your instructor. The only exception to this rule is that the MGSP leader for IC 312 may look at your project to provide help, but this must be clearly documented.

Citations must be given for all help received from any source, including MGSP leaders, other faculty members, other students, any other person, or any online source. Examples of good citations are:

• Discussed problem 3(b) with MIDN Carter
• Received help from MGSP leader in debigging NullPointerException in the Widget class
• http://en.wikipedia.org/Big_O_notation referenced for problem 2

You do not need to cite the instructor or the course website.

Further details can be found at the CS department's honor website http://www.usna.edu/CS/Resources/honor.php. In case of any ambiguity, it is the responsibility of the Midshipman to ask the instructor for clarification on the policy. This document does not cover every possible scenario, and Midshipmen are expected to ask when in any doubt on these issues.

7 Extra Instruction

The instructor has an "open door" policy for EI, and his schedule is posted online for convenient appointment scheduling.

8 MGSP

MIDN 1/C Josh King is the MGSP leader for IC 312 this semester. He will hold a regular meeting each week, as well as participate in review sessions and the class discussion forum.

9 Learning Objectives

1. Understand the fundamentals of algorithm analysis. (supports outcome c)
2. Possess an understanding of the concept of abstraction and be able to describe the idea of separation of implementation and interface. (supports outcome b)
3. Recognize and apply the canonical ADTs (Lists, Queues, Stacks, Trees, Priority Queues, Dictionaries, and Graphs) appropriate for solving a problem. (supports outcome b)
4. Demonstrate the ability to implement the canonical ADTs with: arrays, linked lists, binary trees, hash tables, balanced trees, and other similar structures (supports outcome c)
5. Be proficient in defining and coding recursive algorithms, including recognizing when recursive solutions are appropriate (supports outcome c)

10 Supported Student Outcomes

• (b) An ability to analyze a problem, and identify and define the computing requirements appropriate to its solution.
• (c) An ability to design, implement, and evaluate a computer-based system, process, component, or program to meet desired needs.

11 Section Leader

The section leader is responsible for:

• Calling the class to attention and recording attendance for the instructor.
• Contacting the department main office (x36800, MI 346) if the instructor is 10 minutes late, and making sure students do productive work in the instructor's absence.

12 Classroom Decorum

No food or beverages (except in closable containers) are permitted in the classroom.