CSE4/529: Algorithms for Modern Computing Systems

Spring 2022

Prof. Russ Miller

338F Davis Hall

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

Syllabus: It is your responsibility to read and understand the contents of this syllabus. If you have any questions, please contact me.

Academic Integrity: Plagairism in any way, shape, or form, will earn you an F in the course. In addition, other sanctions may be sought, including, but not limited to, being dismissed from the university.

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.

Back to Basics: Spring 2022: 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. During 2020-2021, the balance was approximately 50:50 in terms of undergraduate students:graduate students.

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

This semester, CSE4/529 will return to being taught as a graduate-level course. Undergraduate students, as has always been the case, are welcome to take the course and will be graded on a different scale than 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 5:00-6:20 via Zoom (see Blackboard for access)

University Information:

  • Course Dates
  • Course Information

    Required Reading Material

    Projected Order of Material (with chapters from M&B listed):

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

    Piazza: https://piazza.com/buffalo/spring2022/cse4529

    Grading Policy:

    1. CSE429
      • Prerequisite Open Book Participation Activities in zyBook: scaled to 10 points
      • Weekly Open Book Blackboard Preparatory Questions: scaled to 15 points
      • Second Best of 3 Midterms: scaled to 20 points
      • Best of 3 Midterms: scaled to 25 points
      • Final Exam: scaled to 30 points
      • Extra Credit: Minimum of 6 points, presented in no guaranteed distribution, over the exams.
      • Final Letter Grades. These are the final "curved" grades. These numbers are points, not percentages, and include any 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
    2. CSE529
      • Prerequisite Open Book Participation Activities in zyBook: scaled to 7 points
      • Weekly Open Book Blackboard Preparatory Questions: scaled to 8 points
      • Second Best of 3 Midterms: scaled to 22 points
      • Best of 3 Midterms: scaled to 30 points
      • Final Exam: scaled to 33 points
      • Extra Credit: Minimum of 6 points, presented in no guaranteed distribution, over the exams.
      • Final Letter Grades. These are the final "curved" grades. These numbers are points, not percentages, and include any 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
    Sample Exams (Midterms only; No solutions):

    Personnel

    Disclaimer: I reserve the right to change any part of this syllabus at any time.



    Copyright © 2022 by Russ Miller.

    All rights reserved. No part of this document may be used in any form by any electronic or mechanical means without permission in writing by the author.