Skip to content

Latest commit

 

History

History
259 lines (203 loc) · 14.4 KB

index.md

File metadata and controls

259 lines (203 loc) · 14.4 KB
Raw

CSCI H343 Data Structures

Indiana University, Fall 2021

This course studies the fundamental ideas for efficiently analyzing large amounts of data, such as DNA sequence databases and geographic information. These fundamental ideas come in two kinds: algorithms and data structures. Algorithms are instructions for solving problems and data structures are strategies for organizing information on computers. Efficient algorithms require appropriate data structures, and vice versa, so the study of algorithms and data structures is tightly linked. In this course we learn about the algorithms and data structures that form the building blocks for many of Today's large-scale computer systems. We apply these ideas to solve challenging problems in bioinformatics and geographic information systems. Warning: a possible side-effect of taking this course is doing better on job interview questions.

Lecture

Mondays and Wednesdays 1:10pm-2:25pm, Student Building, Room 138.

Lab

Fridays 10:00am-11:55am, Ballantine Hall 118.

Instructors and Office Hours

  • Jeremy Siek (jsiek), office hours: Tue 1-2pm, Wed 11am-noon, in Luddy 3014 (or nearby).
  • Annie Pompa (apompa), office hours: Thu 5-6pm in Luddy 3014, Fri 3-4pm online.
  • Sophia Zhang (zhanso), office hours: Tue 2:30-3:30pm, Fri 2:45-3:45pm, both online.

Textbook

Data Structures and Algorithm Analysis in Java, 3rd Ed. by Mark A. Weiss

Slack (communicating with instructors and other students)

Workspace (signup)

Schedule

Day | Lecture Topic | Reading Due | Assignment Due Aug. 23 | Introduction | | Aug. 25 | Arrays, Rotation, Correctness | Ch. 1 | Aug. 27 | | | Lab: Array Search, submit Aug. 30 | Code Review & Algorithm Analysis | Ch. 2 | Sep. 1 | Algo. Analysis cont'd | | Sep. 3 | | | Project: Flood it!, submit Sep. 6 | Labor Day | | Sep. 8 | Linked Lists & Streams | Ch. 3 sec. 1-5 | Homework 1 Sep. 10 | | | Lab: Streams, submit Sep. 13 | Iterators, Merge Sort, Stack, Queue, Set | Ch. 3 sec. 6-7 | Sep. 15 | Binary Trees | Ch. 4 sec. 1-2 | Assignment: MergeSort, submit Sep. 17 | | | Lab: BinaryTree submit, Quiz Sep. 20 | Binary Search Trees | Ch. 4 sec. 3 and 7 | Sep. 22 | Loop Invariants, Correctness of Recursive Functions | Ch. 4 sec. 4 | Assignment: AVLTree submit Sep. 24 | | | Lab: NextPrevBinaryTree submit Sep. 27 | AVL Trees | Sep. 29 | BST and AVL Remove, Segment Intersection | Oct. 1 | | | Project: Segment Intersection submit Oct. 4 | Hash tables | Ch. 5 sec. 1-3 | Oct. 6 | Debugging and Testing | | Oct. 8 | Fall Break | | Oct. 11 | Review for Midterm Exam | | Oct. 13 | Midterm Exam | | Oct. 15 | | | Lab: HashTable submit Oct. 18 | Heaps and Priority Queues | Ch. 6 sec. 1-4, 9 | Oct. 20 | Binomial Queues | Ch. 6 sec. 8 | Oct. 22 | | | Lab: BinomialHeap submit Oct. 25 | Quicksort | Ch. 7, sec. 1-7 | Oct. 27 | Sorting in Linear Time | Ch. 7 sec. 11 | Oct. 29 | | | Lab: QuickSort submit Nov. 1 | Graphs, Topological Order | Ch. 9, sec. 1-2 | Nov. 3 | Breadth and Depth-first search | Ch. 9, sec. 3 | Nov. 5 | | | Lab: ConnectedComponents submit Nov. 8 | Shortest Paths | Nov. 10 | Union-Find | Ch. 8 Nov. 12 | | | Project: RoutingWires submit Nov. 15 | Minimum Spanning Trees, NO CLASS, video instead | Ch. 9, sec. 5 Nov. 17 | Greedy Algorithms | Ch. 10, sec. 1, Ch. 10, sec. 2 | video Nov. 19 | | | Lab: HuffmanCoding submit Nov. 22-26 | Thanksgiving Break Nov. 29 | Dynamic Programming | Ch. 10, sec. 3 Dec. 1 | DNA Alignment | Dec. 3 | | | Lab: SeamCarving submit Dec. 6 | Backtracking | Dec. 8 | Review for Final Exam | Dec. 10 | | | Project: DNA Alignment submit Dec. 17 | Final Exam | 12:35-2:35 PM in class

Resources

Grade Weighting

  • Assignments (30%)
  • Quizzes (10%)
  • Midterm Exam (25%)
  • Final Exam (35%)

COVID Policies and Precautions

All students signed the Community Responsibility Acknowledgement (CRA). Your agreement to the public health measures in the CRA is a condition of physical presence on the campus this fall. Included in that commitment were the requirements to be vaccinated, for wearing masks in all IU buildings, and maintaining social distancing in all IU buildings. These are classroom requirements.

These requirements are necessary for us to protect each other.

Therefore, if a student is present in a class without a mask, the student will be asked to put on a mask and I will report the student to the Division of Student Affairs: Office of Student Conduct.

  • If a student refuses to put a mask on after being instructed to do so, the instructor may end the class immediately, and contact the Office of Student Conduct. Violation of the mask rule is a threat to public safety within the meaning of the Summary Suspension Policy.
  • If a student comes to class without a mask twice, the student’s final grade will be reduced by one letter (e.g., from an A to a B, for instance).
  • If the student comes to class without a mask three times, the student will be withdrawn from the class without refund of tuition and reported to the Office of Student Conduct.
  • If Student Conduct receives three cumulative reports from any combination of instructors or staff members that a student is not complying with the requirements of masking and physical distancing, the student will be summarily suspended from the university for the semester.

If you have a positive COVID-19 test, have COVID-like symptoms, or have been instructed to quarantine you should not attend class. Please work with the instructor to determine a path to continue your progress in the class during these absences.

Bias-Based Incident Reporting.

Bias-based incident reports can be made by students, faculty and staff. Any act of discrimination or harassment based on race, ethnicity, religious affiliation, gender, gender identity, sexual orientation or disability can be reported through any of the options:

  1. email [email protected] or [email protected];

  2. call the Dean of Students Office at (812) 855-8188 or

  3. use the IU mobile App (m.iu.edu). Reports can be made anonymously.

Dean on Call.

The Dean of Students office provides support for students dealing with serious or emergency situations after 5 p.m. in which an immediate response is needed and which cannot wait until the next business day. Faculty or staff who are concerned about a student’s welfare should feel free to call the Dean on Call at (812) 856-7774. This number is not to be given to students or families but is for internal campus use only. If someone is in immediate danger or experiencing an emergency, call 911.

Boost.

Indiana University has developed an award-winning smartphone app to help students stay on top of their schoolwork in Canvas. The app is called “Boost,” it is available for free to all IU students, and it integrates with Canvas to provide reminders about deadlines and other helpful notifications. For more information, see https://kb.iu.edu/d/atud.

Counseling and Psychological Services.

CAPS has expanded their services. For information about the variety of services offered to students by CAPS visit: http://healthcenter.indiana.edu/counseling/index.shtml.

Disability Services for Students (DSS).

The process to establish accommodations for a student with a disability is a responsibility shared by the student and the DSS Office. Only DSS approved accommodations should be utilized in the classroom. After the student has met with DSS, it is the student’s responsibility to share their accommodations with the faculty member. For information about support services or accommodations available to students with disabilities and for the procedures to be followed by students and instructors, please visit: https://studentaffairs.indiana.edu/disability-services-students/.

Reporting Conduct and Student Wellness Concerns.

All members of the IU community including faculty and staff may report student conduct and wellness concerns to the Division of Student Affairs using an online form located at https://studentaffairs.indiana.edu/dean-students/student-concern/index.shtml.

Students needing additional financial or other assistance.

The Student Advocates Office (SAO) can help students work through personal and academic problems as well as financial difficulties and concerns. SAO also assists students working through grade appeals and withdrawals from all classes. SAO also has emergency funds for IU students experiencing emergency financial crisis https://studentaffairs.indiana.edu/student- advocates/.

Disruptive Students.

If instructors are confronted by threatening behaviors from students their first obligation is to insure the immediate safety of the classroom. When in doubt, call IU Police at 9-911 from any campus phone or call (812) 855-4111 from off-campus for immediate or emergency situations. You may also contact the Dean of Students Office at (812) 855-8188. For additional guidance in dealing with difficult student situations: https://ufc.iu.edu/doc/policies/disruptive-students.pdf.

Academic Misconduct.

If you suspect that a student has cheated, plagiarized or otherwise committed academic misconduct, refer to the Code of Student Rights, Responsibilities and Conduct: http://studentcode.iu.edu/.

Sexual Misconduct.

As your instructor, one of my responsibilities is to create a positive learning environment for all students. Title IX and IU’s Sexual Misconduct Policy prohibit sexual misconduct in any form, including sexual harassment, sexual assault, stalking, and dating and domestic violence. If you have experienced sexual misconduct, or know someone who has, the University can help.

If you are seeking help and would like to speak to someone confidentially, you can make an appointment with:

  • The Sexual Assault Crisis Services (SACS) at (812) 855-8900 (counseling services)

  • Confidential Victim Advocates (CVA) at (812) 856-2469 (advocacy and advice services)

  • IU Health Center at (812) 855-4011 (health and medical services)

It is also important that you know that Title IX and University policy require me to share any information brought to my attention about potential sexual misconduct, with the campus Deputy Title IX Coordinator or IU’s Title IX Coordinator. In that event, those individuals will work to ensure that appropriate measures are taken and resources are made available. Protecting student privacy is of utmost concern, and information will only be shared with those that need to know to ensure the University can respond and assist. I encourage you to visit stopsexualviolence.iu.edu to learn more.