CSE 680 Introduction to Analysis of Algorithms and Data Structures

News

• Here is the C# source and VS project for the Binary Tree code shown Monday, Nov. 16.
• No class Wednesday, Nov. 11 (Veterans Day).
• No class or office hours Wednesday, Nov. 25.
• Final Exam for 10:30 section is Wednesday, December 9 from 9:30-11:30
• Final Exam for 12:30 section is Monday, Decemeber 7 from 11:30-1:30
• Sample midterm solution is here.
• Sample Midterm is posted here.
• Programming assignment extended until Monday night at midnight.
• After talking to a few students, I have removed the edge iterators. You should access an edge via its two node indices to get its label. You  can also access a nodes neighbors through an iterator that will return the indices of the adjacent nodes. This change implies that you do not need a separate type for an edge. There is an algorithm or two that deal primarily with edges, but we will see whether we can support this a different way later in the quarter.
• Midterm will be Monday, November 2, 2009.
• Programming Assignment #1 Part I has been assigned and is due on Monday, October 19 in class (see link below). We will discuss this on Friday and Part II on Monday.
• No class Wednesday, October 14 (career fair)

Note: I am going green this quarter, so visit this site often for class updates. I encourage you to go green as well and follow the notes on-line. Note, that the material will change as the course progresses this quarter, so please do not print and refer to the old printed version in the future.

Description

Performance analysis considerations in design of algorithms and data structures; asymptotic analysis, recurrence relations, probabilistic analysis, divide and conquer; searching, sorting, and graph processing algorithms.

Level, Credits, Class Time Distribution, Prerequisites

Intended Learning Outcomes

• Master analyzing running time of "for" and "while" loops.
• Master analyzing running time of simple iterative algorithms.
• Master analyzing running time of simple recursive algorithms.
• Master solving simple recurrence relations.
• Master using asymptotic notation.
• Be familiar with designing divide-and-conquer algorithms.
• Be familiar with designing graph algorithms.
• Be familiar with designing backtracking algorithms (optional).
• Be familiar with designing branch-and-bound algorithms (optional).
• Be exposed to analyzing probabilistic algorithms.
• Be exposed to NP-completeness (time permitting).
• Be exposed to lower bound arguments (optional).

Topics (not in order)

Grader

Yang Zhang Email: zhangya -at- cse.ohio-state.edu Office Hours: W 9:30-11:00 M 3:30-5:00 Office Hours Location: Boltz 118, #18

 

Prof. Crawfis' Office Hours

See Dr. Crawfis' Schedule.

Texts and Other Course Materials

Introduction to Algorithms, 2nd Edition Cormen, Leiserson, Rivest and Stein Amazon Required

Course Notes

Powerpoint slides

Reading Assignments

Below are the reading assignments for the course. Unless otherwise noted, all readings are from the required textbook.

• Week1:
  • Chapters 1, 2 and Appendix A.
• Week 2:
• Chapters 3, 4
• Week 3:
• Chapters 5 and 6
• Week 4
• Chapters 7, 8 and Section 10.4
• Week 5
• Chapters 11, and 12
• Week 6
• Chapter 15
• Week 7
• Chapters 16 and 22
• Week 8
• Chapters 23 and 24
• Week 9
• Chapter 25
• Week 10
• Chapter 34

Homeworks (due weekly in class)

1. Due Wednesday, Septmeber 30 beginning of class: From your book do exercises: 1.2-3, Problem 1-1, 2.1-1, 2.1-3, 2.2-2
2. Due Wednesday, October 7 beginning of class: From your book do exercises: 2.3-1, 2.3-3 (make very formal), 2.3-4, 2.3-7, Problem 2-2, 3.1-1, 3.1-4, 3.2-2, Problem 3-3, Problem 3-4.
3. Due Friday, October 16 beginning of class: From your book do exercises: 4.1-1, 4.1-6, 4.2-2, 4.2-4, Problems 4-1 (4 points) and 4-2 (2 points).
4. Due Wednesday, October 28 beginning of class: From your book do exercises: 6.1-3, 6.1-7, 6.2-1, 6.4-3, 6.5-6, 7.1-1, 7.2-5.
5. Due Monday, November 9 beginning of class: From your book do exercises: 11.2-1, 11.2-2, 11.3-3, 11.4-1, Problem 11-3, 12.1-1, 12.1-4, 12.2-1, Appendix B.4-4 and 22.1-6
6. Due Monday, November 16 beginning of class: From your book do exercises:
• Problems 12.2-4, 12.2-5, 22.1-1, 22.1-2, 22.1-5, 22.2-3, 22.2-6
• (2x points) Rework the Binary Search Tree-Delete pseudo code to be object oriented, use better variable names, include comments and in general be easier to maintain. Note, you are to provide a higher-level pseudo code for this, not C++ or Java code. Primary emphasis will be on readability and correctness.
7. Due Monday, November 30 beginning of class: From your book do exercises:
• Problems 22.3-2, 22.3-6, 22.4-5, 22.3-10, 22.3-11, 22.5-1, 23.2-2, 24.1-1, 24.3-1, 24.3-4
8. Due Wednesday, December 2 beginning of class: From your book do exercises:
• Problems 16.1-2, 16.1-3, 16.1-4, 16.2-3, 16.2-4, TBD

Lab Assignments

• Graph Interfaces and Data Structures
  • Lab1 Review
• Graph Queries
  • Java Framework
  • C++ Framework

Other Web Goodies and Tools

• Book web site for students
• Chris Brown's Math Prelim and exercises
• Steve Sieden's Math Cheat sheet for Computer Scientists
• Sorting algorithm animations - Smith College
• Collection of source code for different Sorting algorithms
• Wikipedia List of Graph Theory pages.
• Wikipedia Tree Theory page.
• Wikipedia Graph Theory Glossary.

Grades

Schedule (Tentative - based on last quarter taught)

Lecture # / topic(s)

1. Course overview, Algorithm Design
2. Data Structures Review, Graph Data Structures
3. Data Structures continued, Insertion Sort
4. Insertion Sort Correctness, Bubble Sort, Selection Sort.
5. Mathematical review and Asymptotic analysis.
6. Merge sort
7. Recurrences and the Master Method
8. The Master Method and Heaps
9. Heapsort and Quicksort
10. Quicksort and Minimum Comparison sorting complexity
11. Counting sort, Radix sort, Bucket sort
12. Hash Tables
13. Hashing
14. Binary Search Trees, Augmented Data Structures
15. Binary Search Trees
16. Midterm Review
17. Midterm
18. Greedy Algorithms
19. Graph Traversal, Depth-first, Breadth-first
20. Topological Sorting, cycle detection
21. Minimum Spanning Trees
22. Shortest Path, Dijkstra's Algorithm
23. Final Review

Relationship to BS-CSE Program Outcomes/EC 2000 Criterion 3 Outcomes

Last modified: November 23, 2009 11:52 AM