Data Structures and Introduction to Algorithms

Instructor: Don Sheehy
Email: donald@engr.uconn.edu
Class Meets: MWF 1:25-2:15 in Biology/Physics Building 131 (map)
Office Hours: MW 9-10am
Office: ITEB 361
TA: Abdullah Baihan, Nguyen Nhan, and Antonia Lewis (See Piazza for contact info and office hours)

Course description

This course discusses fundamental concepts of data structures and the algorithms that proceed from them. Topics to be covered include the implementation and use of linked lists, stacks, queues, trees, priority queues, heaps and graphs, with an emphasis on recursion, abstract data types, object-oriented design, and associated algorithms and complexity issues.

Resources

Book: Data Structures and Algorithms in Java (6th Edition)

Discussion: We will use Piazza for discussion.

Submission: We will use Mimir for assignment submission.

Official Announcements and Grades: We will use the HuskyCT system available at lms.uconn.edu.

Policies

See the Course Policies.

Lecture Schedule

Note: reading sections are listed in parentheses referring to 6th edition of the book.
  1. 31-Aug Java Primer (1, 2)
  2. 2-Sep Arrays, Lists, and Doubly-Linked Lists (3)
  3. 4-Sep List exercises: equivalence and cloning (3.5, 3.6)
  4. 7-Sep NO CLASS
  5. 9-Sep Recursion (5)
  6. 11-Sep Recursion and Design patterns exercises
  7. 14-Sep Stacks, Queue's and Deques (6)
  8. 16-Sep Abstract Lists (7)
  9. 18-Sep Stacks, Queue's and Deques Exercises (7.7)
  10. 21-Sep Trees 1 (8.1, 8.2)
  11. 23-Sep Trees 2 (8.3, 8.4)
  12. 25-Sep Trees 3 with exercises
  13. 28-Sep Priority Queues (9)
  14. 30-Sep More on Heaps and Priority Queues (9.5, 9.6)
  15. 2-Oct Midterm 1 Review
  16. 5-Oct Midterm 1
  17. 7-Oct Maps (10.1)
  18. 9-Oct Hash Tables (10.2)
  19. 12-Oct Sorted Maps (and Sets)
  20. 14-Oct Binary Search trees (11.1, 11.2)
  21. 16-Oct Balanced Binary Search trees (11.1, 11.2)
  22. 19-Oct AVL Trees
  23. 21-Oct Splay Trees (11.4)
  24. 23-Oct Online Assignment in lieu of class: Hash Tables, Balanced Binary Search Trees, and Object-Oriented Programming
  25. 26-Oct Sorting: Divide and Conquer, MergeSort (12.1)
  26. 28-Oct Sorting: QuickSort (12.2)
  27. 30-Oct Sorting Lower Bounds and Radix Sort (12.3)
  28. 2-Nov Comparing Sorting Algorithms (12.4)
  29. 4-Nov Selection (12.5)
  30. 6-Nov Midterm 2 review
  31. 9-Nov Midterm 2
  32. 11-Nov Text Processing, pattern Matching (13.1, 13.2)
  33. 13-Nov Tries (13.3)
  34. 16-Nov Suffix Trees (13.3)
  35. 18-Nov Dynamic Programming (13.5)
  36. 20-Nov More Dynamic Programming (13.5)
  37. 23-Nov NO CLASS
  38. 25-Nov NO CLASS
  39. 27-Nov NO CLASS
  40. 30-Nov Graphs and Definitions (14.1)
  41. 2-Dec The Graph ADT (14.2)
  42. 4-Dec Graphs Traversal DFS and BFS (14.3)
  43. 7-Dec Single Source Shortest Paths (14.6)
  44. 9-Dec Minimum Spanning Trees (14.7)
  45. 11-Dec Course Review