Section: Friday 11:00-11:50am, Chavez 110
phone: (520) 621-4089
email: jaypatel@cs.arizona.edu
Office Hours: Monday 4:30-5:30pm, Wednesday 4:30-5:30pm
Shirley Palani, GS 710
phone: (520) 621-4089
email: shirley@cs.arizona.edu
Office Hours: Thursday 9:00am-10:00am, Friday 9:00-10:00am
Announcements and updates
Some of the data structures we will study are stacks, queues, trees, tries, and heaps. Algorithms considered will include sorting, searching, and hashing. We will also learn about graphs, graph algorithms, asymptotic notation, and algorithm analysis.
(While $90 at Amazon.com, this textbook is also available used for about $35 at places like ABEBooks.com.)
I Background
- Introduction: Abstract Data Types, asymptotic notation (1)
- Elementary Data Structures: linked lists, stacks, queues (2)
II Trees and Heaps
- Trees and Binary Trees: representations, traversals (2)
- HeapSort, Priority queues: building and maintaining heaps (2)
III Balanced Search Trees
- Search trees and Skip Lists: querying, insertion, deletion (3)
- Variants: AVL, Splay, Red-Black: properties, rotations (3)
IV Sorting
- Simple Sorting and Quicksort: description, performance, analysis (4)
- MergeSort and Radix sort: description, performance, analysis (4)
V Hashing
- Hashing: open and closed hashing (2)
- Bloom Filters: description, performance
VI Advanced Data Structures
- Union-Find: disjoint set operations (4)
- Implementations: Performance and efficiency (4)
VII Graphs
- Representations: adjacency list, adjacency matrix (6)
- Searching: Breadth-first search, depth-first search (6)
VIII Graph Algorithms
- Single Source Shortest Path (7)
- All Pairs Shortest Path (7)
- Midterm Exam: Tuesday October 13, 2:00am-3:15pm.
- Final Exam: Thursday December 17, 2:00-4:00pm.
|
50% Homework Assignments 20% Midterm Exam 30% Final Exam |
| Your final grade will be based on the percentage of all available points that you receive. To give you an idea of how percentages might translate into letter grades, here is a typical example. I do not claim that the grade cutoffs for this class will be the same. These cutoffs are merely to give you an idea of how I have graded in the past. I reserve the right to fail any student who has a failing average for either assignments or exams. |
- A: 91-100
- B: 81-90
- C: 66-80
- D: 50-65
- E: 0-50
Late homework will not be graded for credit. Written homework
is due at the start of class on the designated date and programming
assignments are due at 11:59pm on the designated date. Assignments
turned in after the deadline are not accepted and result in a zero for
that assignment. Yes, this lateness policy is harsh. Why? Because in
the past, those who have fallen behind have had a devil of a time
catching up. So we are trying to prevent you falling behind. In the
past, I have had students complain that they could have handed in
something substandard on time and gotten more points than if they had
handed in something really good a little late. Too bad. It is up to
you to plan your time carefully and get your work in on time! You have
been warned. I will not entertain complaints. If you have extenuating
circumstances, talk to me as early as possible. If you speak with me
well before the due date, requests will be considered reasonably. The
closer to the due date it gets, the less likely I am to give you extra
time.
Writing guidelines for the homework assignments should be observed. Neat and concise solutions are required in order to receive full credit for your solutions. If you cannot solve a particular problem, state this clearly in your write-up, and write down only what you know to be correct; rambling at length about ideas that don't quite work may cause additional points to be deducted.
Programming guidelines should also be observed.
Instructions for the turnin program.
Extra credit:
Most homework assignments will suggest extra credit work. Extra credit
in this course will be tallied separately from regular scores. If you
end up on the borderline between two grades at the end of the course,
extra credit will count in your favor. However, failure to do extra
credit will never be counted against you, as grades are assigned on
the basis of regular scores. You should do extra credit if you find it
interesting and think that it might teach you something. On the other
hand, it is not wise to skimp on the regular assignment in order to do
extra credit.
Any attempt to pass off someone else's work as one's own is considered to be cheating. Using material from a textbook, journal, or other such "external" source without proper acknowledgment, is considered to be cheating. Cheating will not be tolerated: cheating or helping another student cheat will result in a failing grade for this course. If you have any questions about academic integrity and how it relates to CSs 345, please come speak with me.