CSE4/529: Algorithms for Modern Computing Systems

Fall 2021

Prof. Russ Miller

338F Davis Hall

Read this before sending e-mail to miller@buffalo.edu

Overview: This course is concerned with the design, analysis, and implementation of algorithms for sequential and parallel models of computation. Traditional algorithmic techniques, including divide-and-conquer, will be discussed. Models of computation include the traditional RAM, as well as standard parallel models, including the shared-memory PRAM, as well as networked models configured as arrays, rings, meshes, hypercubes, and pyramids. We also consider innovative parallel models that involve dynamic reconfiguration. In addition, we discuss algorithmic strategies for Network of Workstations, clusters, grids, and clouds. Problem domains include computational geometry, graph theory, image analysis, sorting, and searching. Time, space, and processor complexity of solutions to problems are a critical component to the course.

Changes for Fall 2021: I have been teaching this course for 35+ years. It was originally labeled CS4/531 and then CSE4/531. In 2013, it was relabled as CSE4/529 to distinguish it from a traditional course in algorithms, which retained the label of CSE4/531, and to allow students to take both a course in algorithms for modern compute systems and a course in traditional sequential algorithms. Last year, the balance was approximately 50:50 in terms of undergraduate students:graduate students.

Unfortunately, the objectives, pace, and level of detail of CSE429 and CSE529 are quite different. Since the Department of Computer Science and Engineering will not teach distinct CSE429 and CSE529 courses, it is important to note that in Fall of 2021, CSE4/529 will be taught as an undergraduate course for the first time. Graduate students are welcome to enroll in the CSE529 component of the course. Further, while graduate students will take the same course, they will be graded on a different scale. Note that in the past, this course was taught as a graduate course that undergraduates were able to take (and were graded on a different scale from the graduate students).

ON-LINE LECTURES: This course will be presented with synchronous on-line lectures via Zoom. However, all 3 exams will be administered in person and on campus. No exceptions. Please do not register for this course if taking such a course is problematic.

Prerequisites: Calculus I, Calculus II, Discrete Structures, and a course in Advanced Data Structures. Students are responsible for the material in chapters 1-13 of Introduction to Algorithms, by Cormen, Leiserson, and Rivest. This includes asymptotic notation, recurrence equations, and quicksort. In addition, students are also responsible for pointers, lists, stacks, queues, binary trees, and balanced trees (e.g., AVL, Red/Black, B-trees).

Lecture: TTh 2:20-3:35 via Zoom (see Blackboard for access)

Important University Information:

  • Important Dates
  • Important Information

    Optional Reading Material:

    Projected Order of Material:

    Succeeding in this course (student view): Students consistently state that the following is key to success in this class.

    Piazza: TBD

    Grading Policy:

    1. Graded Materials
      • CSE429
        • A maximum of 1.25 points per week (10 points maximum) for attending a TAs office hour and having a significant discussion with the TA on CSE429 material: 10 points
        • Midterm I: 25 points
        • Midterm II: 30 points
        • Final Exam: 35 points
        • Extra Credit: Minimum of 6 points, presented in no guaranteed distribution, over the exams.
      • CSE529
        • Midterm I: 30 points
        • Midterm II: 30 points
        • Final Exam: 40 points
        • Extra Credit: Minimum of 6 points, presented in no guaranteed distribution, over the exams.
    2. Course Grades
      • CSE 429 Final Letter Grades. These are the final "curved" grades. These numbers include the additional bonus points (i.e., there will be more than 100 points available in the course). There will be "+"s and "-"s that will be determined after the numeric grading for the semester is complete.
        • A: 75+
        • B: 60+
        • C: 50+
        • D: 35+
        • F: <35
      • CSE 529 Final Letter Grades. These are the final "curved" grades. These numbers include the additional bonus points (i.e., there will be more than 100 points available in the course). There will be "+"s and "-"s that will be determined after the numeric grading for the semester is complete.
        • A: 85+
        • B: 75+
        • C: 60+
        • D: 50+
        • F: <50
    3. Sample Exams (Midterms only)