Course web page for Data Structures H343 Fall 2022
View the Project on GitHub IUDataStructuresCourse/course-web-page-fall-2022
Indiana University, Fall 2022
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:15pm-2:30pm, Geological Sciences (GY), Room 4069.
Lab
Fridays 10:20am-12:15pm, Ballantine Hall 118.
Instructors and Office Hours
Textbook
Data Structures and Algorithm Analysis in Java, 3rd Ed. by Mark A. Weiss
Slack (communicating with instructors and other students)
Schedule
| Day | Lecture Topic | Reading Due | Assignment Due |
| Aug. 22 | Introduction | ||
| Aug. 24 | Arrays, Rotation, Correctness | Ch. 1 | |
| Aug. 26 | Lab: Array Search submit | ||
| Aug. 29 | Code Review & Algorithm Analysis | Ch. 2 | |
| Aug. 31 | Algo. Analysis cont’d | ||
| Sep. 2 | Project: Flood It! submit | ||
| Sep. 5 | Labor Day | ||
| Sep. 7 | Linked Lists and Abstract Data Types | Ch. 3 sec. 1-5 | Homework 1 |
| Sep. 9 | Lab: Merge Sort on Linked List submit | ||
| Sep. 12 | More ADTs, Binary Trees | Ch. 3 sec. 6-7, Ch. 4 sec 1-2 | |
| Sep. 14 | Binary Search Trees | Ch. 4 sec. 3 and 7 | |
| Sep. 16 | Lab: NextPrevBinaryTree | ||
| Sep. 19 | Balanced Search Trees (AVL) | Lab NextPrevBinaryTree submission due | |
| Sep. 21 | Code Review, Finish AVL | Ch. 4 sec. 4 | |
| Sep. 23 | Lab: work on Segment Intersection | ||
| Sep. 26 | Testing, Hash tables | ||
| Sep. 28 | Assertions, Pre and Post-conditions, Correctness | ||
| Sep. 30 | Lab: finish Segment Intersection | ||
| Oct. 3 | Heaps and Priority Queues | Ch. 6 sec. 1-4, 9 | Project: Segment Intersection, submit |
| Oct. 5 | Code Review | ||
| Oct. 7 | Lab: HashTable, submit test cases | ||
| Oct. 10 | Review for Midterm Exam | Hashtable, submit | |
| Oct. 12 | Midterm Exam | 2019 Exam, 2021 Exam, 2022 Exam A 2022 Exam B | |
| Oct. 14 | Fall Break | ||
| Oct. 17 | Binomial Queues | Ch. 6 sec. 8 | |
| Oct. 19 | Quicksort | Ch. 7, sec. 1-7 | |
| Oct. 21 | Lab: BinomialHeap, submit test cases | ||
| Oct. 24 | Sorting in Linear Time | Ch. 7 sec. 11 | Due: BinomialHeap, submit |
| Oct. 26 | Graphs, Topological Order | Ch. 9, sec. 1-2 | |
| Oct. 28 | Lab: QuickSort, submit tests | ||
| Oct. 31 | Breadth and Depth-first search | Ch. 9 sec. 3 | Due: QuickSort, submit |
| Nov. 2 | DFS cont’d, Shortest Paths | Ch. 9 sec. 6 | Due: Homework Chapter 5 and 6 Exercises |
| Nov. 4 | Lab: Connected Components, submit tests | ||
| Nov. 7 | Union Find | Ch. 8 | Due: Connected Components, submit |
| Nov. 9 | Minimum Spanning Tree | Ch. 9 sec. 5 | |
| Nov. 14 | Backtracking | Ch. 10 sec. 5 | |
| Nov. 16 | Greedy Algorithms | Ch. 10, sec. 1-2 | |
| Nov. 18 | Due: Routing Wires Project, submit | ||
| Nov. 20 - Nov. 27 | Thanksgiving Break | ||
| Nov. 28 | Dynamic Programming | Ch. 10, sec. 3 | |
| Nov. 30 | DNA Alignment | HuffmanCoding submit test cases | |
| Dec. 2 | Lab: HuffmanCoding | ||
| Dec. 5 | Code Review | Due: HuffmanCoding submit | |
| Dec. 7 | Review for Final Exam | ||
| Dec. 9 | Lab: DNA Alignment submit tests | ||
| Dec. 12 | Final Exam | 5:20-7:20pm in class | Due: DNA Alignment submit |
Resources
Autograder for submitting coding assignments.
Code Editor and Debugger: IntelliJ IDEA (Community Edition)
Grade Weighting
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 biasincident@indiana.edu or incident@indiana.edu;
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.
Counseling and Psychological Services.
CAPS has expanded their services. For information about the variety of services offered to students by CAPS visit: https://healthcenter.indiana.edu/counseling/index.html
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/.
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/.
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.