CSE 2331

Foundations II: Data Structures and Algorithms

Diego S. Zaccai

Course Topics

Design/analysis of algorithms and data structures; divide-and-conquer; sorting and selection, search trees, hashing, graph algorithms, string matching; probabilistic analysis; randomized algorithms; NP-completeness.

Course Information

Instructor: Diego Zaccai.
Office Hours: available here.

Grader:
Text(required): "Introduction to Algorithms," Third Edition, by Corman, Leiserson, Rivest and Stein.

Syllabus: Can be downloaded here.

Prerequisite: CSE 2231 and CSE 2321 and (Stat 3460 or STAT 3470).
Corequisite: MATH 3345.

More information about the course will be posted on Carmen.

Exams

Midterm 1: Wednesday, February 12, 8:00 - 9:45 p.m. in Mendenhall Lab (ML) 100
Midterm 2: Wednesday, March 25, 8:00 - 9:45 p.m. in Mendenhall Lab (ML) 100
Final: Wednesday, April 22, 8:00 - 9:45 a.m. in Jennings Hall (JE) 155

Sequence of Topics

  1. Asymptotic notation review (CLRS, Chapter 3).
  2. Analyzing algorithms review (CLRS, Chapters 1, 2).
  3. Recurrence relations (CLRS, Sections 4.1, 4.2).
  4. Probabilistic analysis (CLRS, Chapter 5).
  5. Quicksort (CLRS, Chapter 7).
  6. Median find (CLRS, Chapter 9).
  7. Hashing (CLRS, Chapter 11).
  8. Table doubling (CLRS, Sections 17.4).
  9. Heaps (CLRS, Sections 6.1-6.4).
  10. Binary Search Trees (CLRS, Chapter 12).
  11. Red Black Trees (CLRS, Chapter 13).
  12. Minimum spanning trees (CLRS, Chapter 23).
  13. Union-find data structures (CLRS, Chapter 21).
  14. Shortest paths (CLRS, Section 24.3).
  15. Maximum Flow (CLRS, Sections 26.1-26.3).
  16. NP-completeness (CLRS, Chapter 34).

Grading Scheme

Participation4%
Homework12%
Programming Assignments 4%
Midterm 120%
Midterm 220%
Final40%

General Information

Homework is due at the beginning of class. Late homework will not receive credit.

Programming assignments are due at 11:59 p.m. and will incur a 20\% penalty per 24 hour lateness up to 48 hours.

Information regarding the course will be posted on Carmen. CSE 2331 is not an online course. You are expected to attend class regularly. I will try my best to make class worth your time and I expect you to help me by participating. Even so, no one is perfect and I might fall short of this goal some times, I expect you to let me know when I fail to make class worth your time.

In the event that you must miss a class, you are responsible for finding out what assignments were made, what due dates were announced, and what material was covered. Students are also expected to sign the attendance sheet, failure to do so will result on the student being recorded as absent in the class.

Piazza, www.piazza.com, will be used to post announcements and as a student discussion platform for the course. Some examples of acceptable topics to discuss include: general information, concepts as related to assignments, interpretation of assignments, problems with coding such as syntax and execution errors, etc. Please do not post answers or partial answers to homework problems. Do not post any code from programming assignments. Piazza will be monitored by the course grader and/or instructor. Students are responsible for any announcements and information provided on Piazza.

Academic Misconduct

Students are required to follow the Ohio State Code of Student Conduct which can be found at studentaffairs.osu.edu/pdfs/csc_12-31-07.pdf. Among the other restrictions, pay specific attention to the section on Academic Misconduct. Among the restrictions, students are prohibited from:

Note: Faculty is required by the University to report any suspected violation of these conditions to the Council on Academic Misconduct. Misconduct cases are resolved via the CoAMs hearing processes. More about this process can be found at: http://oaa.osu.edu/coam.html.

Grades

You have one week (7 calendar days) to ask about any grade concerns you have on an assignment or exam, from the day the papers were handed back in class whether or not you were there to get your copy. If you are not in class on the day that an assignment or exam is handed back, it is your responsibility to contact me and get your graded work. If the graded work is on Carmen, then you have one week (7 calendar days) from the time grades are released on Carmen.

If you have any concerns or questions related to a grade, you must contact the grader or instructor within that one week time frame. The one week clock starts ticking at the end of the class period during which the papers are handed back whether you are present to receive your individual copy or not. In order to document that you have contacted the teaching staff within the time allowed, you should email the grader for homework or lab assignments, or the instructor for exams, and keep a copy of the message. After that week deadline, although you may still ask questions (at any time), a grade change will not be made even if one would normally be available. The idea is to be concerned about your grade, and to communicate any concerns you have to the grader and/or lecturer, in a timely manner.