1 Instructors

• Prof. Daniel S. Roche, 438 Hopper Hall, x36814, (Coordinator).

• Maj Eric Wikman, 447 Hopper Hall, x36826, .

• Dr. Mark Woodcock, 443 Hopper Hall, x36803

2 MGSP Leader

• 1/C Carey Hutchens. 22^nd company,

3 Grading

The work of the class consists of:

• Quizzes and class participation (instructor discretion)
• Homeworks (roughly weekly)
• Projects (3 total)
• Midterm exams (6-week and 12-week)
• Final exam

Any student that completes every homework assignment to a satisfactory level will have their lowest homework grade dropped at the end of the semester. The definition of “satisfactory level” is based on effort and is at the sole discretion of the instructor. Work submitted late may count for this requirement, even if it is late and gets zero credit.

Plus/minus grades will be assigned based on the following numerical cutoffs:

	-		+
A	90–92	93–100
B	80–82	83–86	87–89
C	70–72	73–76	77–79
D		60–66	67–69
F		0–59

Here is a breakdown of percentages by grading period.

	6 weeks	12 weeks	16 weeks	Final
Quizzes	10%	10%	10%	5%
Homeworks	20%	20%	20%	15%
Projects	40%	40%	40%	30%
Midterms	30%	30%	30%	20%
Final				30%

4 Collaboration

The guidance in the Honor Concept of the Brigade of Midshipmen and the Computer Science Department Honor Policy must be followed at all times. See https://www.usna.edu/CS/resources/honor.php. Specific instructions for this course:

• Collaboration or assistance from any human other than the instructors, MGSP leaders, and those enrolled in IC312 this semester is not permitted. This includes any written or electronic materials from previous semesters.

• Homework: Students may collaborate on homework with others in the same class, but must cite this collaboration clearly. Every student must actually complete their own assignment and understand anything they turn in.

• Projects: No discussion or collaboration is permitted except with the instructors and MGSP leaders. Any online resources used must be clearly and specifically cited how they are used.

• Exams: No collaboration is allowed. Any group study guides should be shared with the instructor.

All collaboration and outside sources should always be cited. The same rules apply for giving and receiving assistance. If you are unsure whether a certain kind of assistance or collaboration is permitted, you should assume it is not, work individually, and seek clarification from your instructor.

5 Absences

Students are responsible for all class material. Notes will be posted for each lecture, along with recommended readings. However, this material is not exhaustive and students missing class should arrange to copy notes from a classmate.

6 Late Policy

Homework solutions will generally be discussed immediately, and so no late submissions of homeworks will be accepted for credit. The same deadline applies even in the case of excused absences.

Project submissions will follow an exponential partial credit for late days, as \(5^{k-1}\) where k is the number of calendar days late. This can be seen in the following table:

Submission before…	Maximum grade
23:59 on due date	100%
23:59 +1 calendar day	99%
23:59 +2 calendar days	95%
23:59 +3 calendar days	75%
4 or more days late	0

7 Classroom Conduct

Everyone in the classroom will show appropriate respect to each other at all times.

This class relies on active engagement and frequent interaction. Use of electronic devices during class time outside of note-taking apps is not permitted.

The section leader is responsible for recording attendance, bringing the class to attention, notifying the CS department office if the instructor is more than 5 minutes late, and directing the class in useful work in the instructor’s absence.

Drinks are permitted, but they must be in closable containers. Food, alcohol, and tobacco (of all kinds) are prohibited. Electronic devices must be silent during class and should never serve as a distraction to other students.

8 Optional Textbook

• Robert Sedgewick. Algorithms in Java, Part 1-4, Addison Wesley, 3rd ed., 2002.

9 Course Website

https://www.usna.edu/Users/CS/roche/courses/f22ic312

10 Extra Instruction

Extra instruction (EI) is strongly encouraged and should be scheduled by email. (For Dr. Roche, first go here to check available times.) EI is not a substitute lecture; students should come prepared with specific questions or problems.

11 Course Description

This course examines abstract data types (ADT), 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. [fall]

12 Credits

3-0-3

13 Requisites

IC211 (prerequisite) and (SM242 or SI242) (corequisite)

14 Learning Objectives

1. Understand the fundamentals of algorithm analysis. (supports outcome 2)
2. Possess an understanding of the concept of abstraction and be able to describe the idea of separation of implementation and interface. (supports outcome 1)
3. Recognize and apply the canonical ADTs (Lists, Queues, Stacks, Trees, Priority Queues, Sets, Maps, and Graphs) appropriate for solving a problem. (supports outcome 1)
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 2)
5. Be proficient in defining and coding recursive algorithms, including recognizing when recursive solutions are appropriate (supports outcome 2)

15 Student Outcomes

Graduates of the program will have an ability to:

1. Analysis.

Analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions.

2. Implementation.

Design, implement, and evaluate a computing-based solution to meet a given set of computing requirements in the context of the program’s discipline.

3. Communication.

Communicate effectively in a variety of professional contexts.

4. Ethics.

Recognize professional responsibilities and make informed judgments in computing practice based on legal and ethical principles.

5. Teamwork.

Function effectively as a member or leader of a team engaged in activities appropriate to the program’s discipline.

CS-6. Theory.

Apply computer science theory and software development fundamentals to produce computing-based solutions.

IT-6. Requirements.

Identify and analyze user needs and to take them into account in the selection, creation, integration, evaluation, and administration of computing based systems.

16 Syllabus

• Unit 1: Big-O (Classes 1–4)
  Introduction, Analysis, Examples with loops
• Unit 2: Recursion (Classes 5–7)
  Writing and using recursion, Recursive Big-O analysis
• Unit 3: ADTs and 1-D data structures (Classes 8–10)
  Data Types, Lists, Stacks, Queues
• Unit 4: Trees (Classes 11–14)
  Structure, Traversal, Binary search trees
• Unit 5: Ordered Maps (Classes 15–19)
  Map ADT, AVL trees, 2-3-4 trees
• Unit 6: Priority queues (Classes 20–22)
  Priority queue ADT, Heaps, HeapSort
• Unit 7: Hash tables (Classes 23–25)
  Hash functions, Separate chaining, Open addressing
• Unit 8: Sets (Classes 26–27)
  Set ADT, Data structure options, Union and intersection
• Unit 9: Graphs (Classes 28–31)
  Graph ADT, Adjacency list, Adjacency matrix, BFS, DFS
• Unit 10: Shortest paths (Classes 32–35)
  Dijkstra, Floyd-Warshall
• Unit 11: Project presentations (Classes 36–38)
  
• Unit 12: Strings (Classes 39–41)
  Pattern matching, Suffix trees, Compression

17 Updates to the course policy

In case this course policy needs to be changed during the semester, students will be notified by email and verbally during class. The current version will always be posted on the course website.