-
Notifications
You must be signed in to change notification settings - Fork 1
/
index.md~
185 lines (142 loc) · 10.1 KB
/
index.md~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
## CSCI H343 Data Structures
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**
* Jeremy Siek (jsiek), office hours: Wednesdays 2:30pm-3:30pm, Thursdays 4:30pm-5:30pm, in Luddy 3014.
* Brooke Augustine (bsaugust), office hours: Mondays 4-5pm, Wednesdays 12-1pm, in Luddy 3014.
**Textbook**
*Data Structures and Algorithm Analysis in Java*, 3rd Ed. by Mark A. Weiss
**Slack (communicating with instructors and other students)**
[Workspace](https://h343datastruc-h256084.slack.com)
([signup](https://join.slack.com/t/h343datastruc-h256084/shared_invite/zt-1e7jf70gm-~sf6Fcc~0waqxHsdF1qSCg))
**Schedule**
Day | Lecture Topic | Reading Due | Assignment Due
Aug. 22 | [Introduction](./lectures/Aug-22.md) | |
Aug. 24 | [Arrays, Rotation, Correctness](./lectures/Aug-24.md) | Ch. 1 |
Aug. 26 | | | Lab: Array [Search](./Search/README.md) [submit](https://autograder.luddy.indiana.edu/web/project/461)
Aug. 29 | [Code Review & Algorithm Analysis](./lectures/Aug-29.md) | Ch. 2 |
Aug. 31 | [Algo. Analysis cont'd](./lectures/Aug-31.md) | |
Sep. 2 | | | Project: [Flood It!](./FloodIt/README.md) [submit](https://autograder.luddy.indiana.edu/web/project/456)
Sep. 5 | Labor Day | |
Sep. 7 | [Linked Lists and Abstract Data Types](./lectures/Sep-7.md) | Ch. 3 sec. 1-5 | [Homework 1](./HW1.md)
Sep. 9 | | | Lab: [Merge Sort](./MergeSortList/README.md) on Linked List [submit](https://autograder.luddy.indiana.edu/web/project/509)
Sep. 12 | [More ADTs, Binary Trees](./lectures/Sep-12.md) | Ch. 3 sec. 6-7, Ch. 4 sec 1-2 |
Sep. 14 | [Binary Search Trees](./lectures/Sep-14.md) | Ch. 4 sec. 3 and 7 |
Sep. 16 | | | Lab: [NextPrevBinaryTree](./NextPrevBinaryTree/README.md)
Sep. 19 | [Balanced Search Trees (AVL)](./lectures/Sep-19.md) | | Lab NextPrevBinaryTree [submission](https://autograder.luddy.indiana.edu/web/project/458) due
Sep. 21 | [Code Review, Finish AVL](./lectures/Sep-21.md) | Ch. 4 sec. 4 |
Sep. 23 | | | Lab: work on Segment Intersection
Sep. 26 | [Testing, Hash tables](./lectures/Sep-26.md) | |
Sep. 28 | [Assertions, Pre and Post-conditions, Correctness](./lectures/Sep-28.md) |
Sep. 30 | | | Lab: finish Segment Intersection
Oct. 3 | [Heaps and Priority Queues](./lectures/Oct-3.md) | Ch. 6 sec. 1-4, 9 | [Project: Segment Intersection](./SegmentIntersection/README.md), [submit](https://autograder.luddy.indiana.edu/web/project/465)
Oct. 5 | [Code Review](./lectures/Oct-5.md) |
Oct. 7 | | Lab: [HashTable](./HashTable/README.md), [submit test cases](https://autograder.luddy.indiana.edu/web/project/519)
Oct. 10 | [Review for Midterm Exam](./lectures/Oct-10.md) | [Hashtable](./HashTable/README.md), [submit](https://autograder.luddy.indiana.edu/web/project/443)
Oct. 12 | **Midterm Exam** | [2019 Exam](./midterm-2019.pdf), [2021 Exam](./midterm-2021.pdf), [2022 Exam A](./midterm-2022-a.pdf) [2022 Exam B](./midterm-2022-b.pdf)
Oct. 14 | **Fall Break** |
Oct. 17 | [Binomial Queues](./lectures/Oct-17.md) | Ch. 6 sec. 8 |
Oct. 19 | [Quicksort](./lectures/Oct-19.md) | Ch. 7, sec. 1-7 |
Oct. 21 | | | Lab: BinomialHeap, [submit test cases](https://autograder.luddy.indiana.edu/web/project/526)
Oct. 24 | [Sorting in Linear Time](./lectures/Oct-24.md) | Ch. 7 sec. 11 | Due: [BinomialHeap](./BinomialHeap/README.md), [submit](https://autograder.luddy.indiana.edu/web/project/466)
Oct. 26 | [Graphs, Topological Order](./lectures/Oct-26.md) | Ch. 9, sec. 1-2 |
Oct. 28 | | | Lab: [QuickSort](./QuickSort/README.md), [submit tests](https://autograder.luddy.indiana.edu/web/project/527)
Oct. 31 | [Breadth and Depth-first search](./lectures/Oct-31.md) | Ch. 9 sec. 3 | Due: [QuickSort](./QuickSort/README.md), [submit](https://autograder.luddy.indiana.edu/web/project/464)
Nov. 2 | [DFS cont'd, Shortest Paths](./lectures/Nov-2.md) | Ch. 9 sec. 6 | Due: [Homework Chapter 5 and 6 Exercises](./HW-Ch5-6.md)
Nov. 4 | | | Lab: [Connected Components](./ConnectedComponents/README.md), [submit tests](https://autograder.luddy.indiana.edu/web/project/532)
Nov. 7 | [Union Find](./lectures/Nov-7.md) | Ch. 8 | Due: [Connected Components](./ConnectedComponents/README.md), [submit](https://autograder.luddy.indiana.edu/web/project/467)
Nov. 9 | [Minimum Spanning Tree](./lectures/Nov-9.md) | Ch. 9 sec. 5 |
Nov. 14 | [Backtracking](./lectures/Nov-14.md) | Ch. 10 sec. 5 |
Nov. 16 | [Greedy Algorithms](./lectures/Nov-16.md) | Ch. 10, sec. 1-2 |
Nov. 18 | | | Due: [Routing Wires Project](./RoutingWires/README.md), [submit](https://autograder.luddy.indiana.edu/web/project/469)
Nov. 20 - Nov. 27 | **Thanksgiving Break** | |
Nov. 28 | [Dynamic Programming](./lectures/Nov-28.md) | Ch. 10, sec. 3 |
Nov. 30 | [DNA Alignment](./lectures/Nov-30.md) | | [HuffmanCoding](https://iu.instructure.com/courses/2081904/assignments/14231139) [submit test cases](https://autograder.luddy.indiana.edu/web/project/536)
Dec. 2 | | | Lab: HuffmanCoding
Dec. 5 | Code Review | Due: [HuffmanCoding](https://iu.instructure.com/courses/2081904/assignments/14231139) [submit](https://autograder.luddy.indiana.edu/web/project/468)
Dec. 7 | [Review for Final Exam](./lectures/Dec-7.md) |
Dec. 9 | | | Lab: DNA Alignment [submit tests](https://autograder.luddy.indiana.edu/web/project/538)
Dec. 12 | **Final Exam** | 5:20-7:20pm in class | Due: [DNA Alignment](./DNA_Alignment/README.md) [submit](https://autograder.luddy.indiana.edu/web/project/460)
**Resources**
* Final Exam with solutions from [2017](./final-2017.pdf) and [2021](./final-2021.pdf).
* [Autograder](https://autograder.luddy.indiana.edu/web/course/39) for
submitting coding assignments.
* Code Editor and Debugger:
[IntelliJ IDEA](https://www.jetbrains.com/idea/download) (Community Edition)
**Grade Weighting**
* Assignments (30%)
* Quizzes (10%)
* Midterm Exam (25%)
* Final Exam (35%)
**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.
**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.