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.
-
It is your responsibility to read and observe the departmental policy and university policy on plagiarism and academic integrity.
- Lectures will be recorded and made available to the students in this class for the sole purpose of reviewing material for this class. Such recordings may not be distributed in any way, shape, or form, as discussed below. A violation of this policy will have significant consequences, as outlined below.
- Students may not record lectures or any presentations associated with this course. This includes, but is not limited to, video and audio recording.
- All materials utilized in this course are for the educational benefits of the students in this course, period. As such, students may not take pictures or take screen shots, record, reproduce, transmit, distribute, upload, or provide such course material to any person, site, organization, or system without my permission. Violations of this policy will result in academic and legal penalties, including those available through University policy, New York State laws, and Federal (United States) laws.
- Such course materials include, but are not limited to, the textbook,
PowerPoint slides, exams, quizzes, drawings/annotations on "whiteboards," slides, or any other material provided for this class, as well as, lectures, lecture notes, review (Q&A) sessions, and so forth, all regardless of format (e.g., PPT, Word, PDF, CSV, and on and on).
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.
- We meet on-line via UB's Zoom system.
- Our success as an online class will depend on the same commitment
that we bring to a face-to-face class.
- We will adopt the same norms as a face-to-face class: take notes;
participate by asking and answering questions; wear classroom-ready clothing;
show respect for your fellow students, the professor, the department,
and the university.
- For everyone’s benefit, join the course in a quiet place whenever possible.
- Turn on your video whenever possible.
- Mute your microphone unless you are speaking.
- If you want to contribute, please unmute your mic and speak clearly. Alternatively, use the Chat area, but note that chat is difficult to follow while
lecturing.
- Close browser tabs not required for participating in class. `
- You are not permitted to make audio or video recordings of lectures.
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
- Blackboard Open Book Weekly Preparatory Questionsdue Tuesdays at 4:00p EST. Available Sundays at Noon.
- Midterm I: Thursday, February 24, Norton 112
- No Classes: March 22 and March 24, Spring Break
- Midterm II: Thursday March 31, Knox 20
- Midterm III: Thursday, April 21, Norton 112
- Last Day of Classes: Friday, May 13, 2022
- Final Exam: Tuesday, May 17, 7:15p - 10:15p, Knox 109
Course Information
- CSE4/529 will be taught as a graduate-level course in algorithms for modern computing systems, though undergraduate students and graduate students will
be graded on a different scale, as given below.
- There will be no programming projects in this class.
- There will be no makeup exams. If you have a medical issue,
documentation is required.
- If you have a conflict with the final exam, you must handle the situation in terms of making arrangements in your other class(es).
- This will be a paper and pencil course. There will be
no programming assignments.
- Introduction to Asymptotic Notation
- Learning Outcome (Middle States Accreditation): Ability to understand the fundamental principles of the field of
Analysis of Algorithms.
Required Reading Material
- Algorithm Design and Applications, Goodrich and Tamassia, 2022, zyBooks, A Wiley Company.
- This is an interactive text, which is an enhanced version of
the Wiley text from 2014.
- This book is used to provide a resource for pre-requiste material for which
you are responsible.
- Instructions for gaining free access to the book are given in Blackboard.
- Homework assignments from this book are given in Blackboard.
- Algorithms Sequential & Parallel (Third Edition), R. Miller and L. Boxer, Cengage Learning, 2013.
- A digital copy of this book (i.e., a pdf) will be provided to the students in the class for use only in this class. This book will be available for viewing only (i.e., not for downloading or printing).
- The book is copyrighted and may not be distributed in any way, shape, or form, period. You may not give a copy to a friend, post to a website, or distribute it in any way. It is for your own academic use during the class. Please refer to the material on academic integrity presented at the beginning of this syllabus.
- Note that this is the 3rd Edition of the book.
If you decide to obtain a copy of this book through another source, please
note that, regardless of the edition, it is illegal to obtain a copy of this book
without purchasing it through proper channels.
- Hard copies of the book are available through a variety of sources, including Amazon.
- Be advised that there are significant conesquences to obtaining an illegal copy of the book and/or distributing a digital copy of the book.
- Additional material and citations to relevant material will be made available via this Web site/LMS.
Projected Order of Material (with chapters from M&B listed):
- NB: Students responsible for Chapts 1-3
- Asymptotic Analysis Review (Chapt 1)
- Divide-and-Conquer (Chapt 9)
- Intro to Parallel Algorithms and Architectures (Chapt 4)
- Combinational Circuits and Sorting Networks (Chapt 5)
- Algorithms based on Parallel Prefix (Chapt 7)
- Computational Geometry (Chapt 10)
- Image Processing (Chapt 11)
Succeeding in this course (student view):
Students consistently state that the following is key to success in this class.
- Work on the course an hour or so per day, seven days/week. Don't let this course slide!.
- Read the material thoroughly prior to lecture.
- Attend lecture, pay attention, take notes by hand, participate.
- Transcribe notes daily. Do/create practice problems.
- Spend time with the TAs at least once a week. Be prepared. Work through problems and/or discuss areas of confusion.
Piazza: https://piazza.com/buffalo/spring2022/cse4529
Grading Policy:
- 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
- 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
- Dr. Russ Miller
- T.A.: Alessandro Baccarini e-mail
- Office Hours (and by appointment):
- Tuesdays 3:30p - 4:30p EST via Zoom (see piazza)
- Thursdays 3:30p - 4:30p EST via Zoom (see piazza)
- T.A.: Fei Xu e-mail
- Office Hours (and by appointment):
- Mondays 10:30a - 12:00p EST via Zoom (see piazza)
- Wednesdays 1:00a - 2:00p EST via Zoom (see piazza)
- Fridays 10:30a - 12:00p EST via Zoom (see piazza)
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.