CSE 680 Introduction to Analysis of Algorithms and Data Structures

News

• Here are the solutions to the sample final.
• Here is a sample final. Please complete this by Friday at 10:30 (2 points extra credit). No late turn-ins accepted
• No class or office hours 11/23/2011
• Sample midterm should be worked out by Wednesday.
• Here is the sample midterm.
• Midterm wioll be on Friday, October 28
• No Office hours 10/14/2011
• Final Exam is scheduled for Wednesday, December 7th at 9:30am.
• The 2nd edition of the book is fine.

Note: I have gone green, 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)

Graders

10:30 Section Dachuan Huang Email: huangda -at- cse.ohio-state Office Hours: TR 10:30-11:30 Office Hours Location: BO 118 #18

 

Prof. Crawfis' Office Hours

See Dr. Crawfis' Schedule.

Texts and Other Course Materials

Introduction to Algorithms, 3rd 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 Friday, September 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 Friday, 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-3a, Problem 3-4.
3. Due Monday, October 17 beginning of class:
• From your book do exercises (write the problems down):
  • 3rd edition of book: 4.3-2, 4.4-6, 4.4-8 (will give extra credit for 4.2-2 and 4.2-4).
  • 2nd edition of book: 4.1-1, 4.2-2, 4.2-4
• Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n <= 2.
  Make your bounds as tight as possible, and justify your answers.
  1. T(n) = 2T(n/2) + n^3
  2. T(n) = T(9n/10) + n
  3. T(n) = 16T(n/4) + n^2
  4. T(n) = 7T(n/3) + n^2
  5. T(n) = 7T(n/2) + n^2
  6. T(n) = 2T(n/4) +sqrt(n)
  7. T(n) = T(n - 1) + n
  8. T(n) = T(sqrt(n)) + 1
• Find the missing integer. An array A[1::n] contains all the integers from 0 to n except one. It would be easy to determine the missing integer in O(n) time by using an auxiliary array B[0::n] to record which numbers appear in A. In this problem, however, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A[i]," which takes constant time. Show that if we use only this operation, we can still determine the missing integer in O(n) time.
4. Due Monday, October 24 beginning of class: From your book do exercises: 6.1-3, 6.1-7, 6.2-1, 6.4-3, 6.5-7 (6.5-6 in 2nd edition), 7.1-1, 7.2-5.
5. Due Monday, November 7 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 14 beginning of class: From your book do exercises:
• Problems 12.2-4, 12.2-5, 22.1-1, 22.1-5, (22.2-5 and 22.2-6 (in 2nd Edition)) or (22.2-6 and 22.2-7 (in 3rd Edition)
• Show that using a single bit to store each vertex color suffices by arguing that the BFS procedure would produce the same result if lines 5 and 14 were removed.
• (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, Noveber 21 beginning of class: From your book do exercises:
• (2nd Edition) Problems 22.3-2, 22.3-6, 22.4-5, 22.5-1, 23.2-2, 23.2-7, 24.1-1, 24.3-1, 24.3-4
• (3rd Edition) Problems 22.3-2, 22.3-7, 22.4-5, 22.5-1, 23.2-2, 23.2-7, 24.1-1, 24.3-1, 24.3-6
8. (Extra credit) Due Monday, November 28 beginning of class: From your book do exercises:
• (2nd Edition) Problems 16.1-2, 16.1-3, 16.2-3
• (3rd Edition) Problems 16.1-2, 16.1-4, 16.2-3
• Professor Gekko has always dreamed of inline skating across North Dakota. He plans to cross the state on highway U.S. 2, which runs from Grand Forks, on the eastern border with Minnesota, to Williston, near the western border with Montana. The professor can carry two liters of water, and he can skate m miles before running out of water. (Because North Dakota is relatively flat, the professor does not have to worry about drinking water at a greater rate on uphill sections than on flat or downhill sections) The professor will start in Grand Forks with two full liters of water. His official North Dakota state map shows all the places along U.S. 2 at which he can refill his water and the distances between these locations.
  The professor’s goal is to minimize the number of water stops along his route across the state. Give an efficient method by which he can determine which water stops he should make. Prove that your strategy yields an optimal solution, and give its running time.

Lab Assignments

• Graph Traversal - due Wednesday, November 2.
• Minimum Spanning Trees and Maze generation - due Friday, December 2.

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 30, 2011 10:01 AM