CSE4/529: Algorithms for Modern Computing Systems
Syllabus: Spring 2023
Prof. Russ Miller
338F Davis Hall
Read this before sending e-mail to miller@buffalo.edu
Syllabus:
- Students enrolled in this class are responsible for
reading and comprehending the contents of this syllabus.
- Students enrolled in this class accept responsibility for
the material presented in this syllabus.
- Consider the material presented in this syllabus as a contract between you and me, as the instructor in the class.
- If you have any questions concerning this syllabus or how it applies to you, please ask me.
- This semester, based on student feedback from the previous two semesters, this course will be taught as a straight paper-and-pencil theory course. There will be no programming component. If this is not to your liking, please enroll in another course.
Teaching Environment:
- All lectures will be presented remotely, via Zoom.
- All exams will be held on campus, in person. No exceptions.
- If this format is of concern, please consider taking another course.
- Feel free to contact me or an appropriate academic advisor for options about potential alternative courses.
Overview:
This course is concerned with the design and analysis
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.
History of CSE4/529: 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.
Recently, the number of undergradute students enrolled in the course has
been approximately the same as the number of graduate students enrolled
in the course.
That said, the objectives, pace, and level of detail of
CSE429 and CSE529 are quite different.
Please note that since the course is presented as a cross-listed senior-level course and a first-year graduate course, that
in Spring 2023, CSE4/529 will continue to be taught as a graduate-level course, where undergraduates are welcome and encouraged to take the course, and will be graded on a different scale than the graduate students.
Prerequisites: Calculus I, Calculus II, Discrete Structures,
and a junior- or senior-level course in Data Structures and their Algorithms.
Students are responsible for
the material in chapters 1-13 of Introduction to Algorithms,
by Cormen, Leiserson, Rivest, and Stein. This includes, for example, 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). Note that many students struggle in this course because they are unprepared in terms of such material.
There will not be any review of this material in class. It is your responsibility to have an excellent command of this prerequisite material, including the mathematics, data structures, algorithms, and methodologies discussed, as well
as have an excellent command over programming skills in high-level languages.
Lecture: TTh 2:00-3:20 via Zoom
Academic Integrity:Plagairism in any way, shape, or form, will earn you an F in the course. In addition, other sanctions will likely be sought,
including, but not limited to, being dismissed from the university.
- Any work that is handed in for a grade must be done completely and exlusively by you. No exceptions. No second chances.
-
It is your responsibility to read and observe the departmental policy and university policy on plagiarism and academic integrity.
- Lectures will be presented remotely. The Zoom links will be provided in your Learning Management System (LMS), which is Blackboard via UBLearns. Zoom lectures will be recorded, and you will have access to those recordings via the LMS. These recordings are 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 class in any way, shape, or form. This includes, but is not limited to, video and audio recordings, still images via screen shots, and the like.
- 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.
At a minimum, it is likely that you will receive an F in the course with a notation on your transcript that it was due to lack of Academic Integrity.
- 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).
University Information:
Course Dates
- Blackboard (UBLearns) Open Book Weekly Preparatory Questions will be made available at approximately Noon on Sundays and will be due 30 minutes prior to class on Tuesdays.
- See Grading Policy below for utilization of exams towards your final letter grade.
- Midterm I: Thursday, March 9, 7:00p-8:20p, Knox 20
- Midterm II: Thursday, April 13, 7:00p-8:20p, Knox 20
- Last Day of Classes: Friday, May 12
- Final Exam: Tuesday, May 16, 7:15p-10:15p, NSC225
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 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).
- 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
- 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)
- Introduction 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 lectures, pay attention, take notes by hand, and 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: TBA
Grading Policy:
- We had been using an on-line (zyBook) for review, where students were awarded 10% of their grade for reading several chapters of the book and 10% of their grade for some basic programming assignments. However, students from last semester recommended against using this book and against having 20% of the course grade be based on reading problems and programming assignments of prerequisite material in this book. Therefore, we will not be using any required text to help you review prerequisite material.
- Weekly Open Book Blackboard Preparatory Questions: scaled to 10 points
- Exam I: scaled to 20 points
- Exam II: scaled to 30 points
- Final Exam: scaled to 40 points
- Extra Credit: Minimum of 6 points, presented randomly during class.
Final Letter Grades:
These are the final "curved" grades.
(That is, there is no need to ask me during the semester if I will curve the final 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.
- CSE429
- A: 75+
- B: 60+
- C: 50+
- D: 35+
- F: <35
- CSE529
- A: 85+
- B: 75+
- C: 60+
- D: 50+
- F: <50
Sample Exams (Midterms only; No solutions):
Personnel
- Dr. Russ Miller
- Zoom-only Office Hours: TBA
- T.A.: Fei Xu (e-mail)
- Zoom-only Office Hours (and by appointment):
- Wednesdays: 2:00p - 3:00p
- Fridays: 2:00p - 3:00p
- T.A.: Davoud Moradi (e-mail)
- Zoom-only Office Hours (and by appointment):
- Mondays: 5:00p - 7:00p
- Tuesdays: 11:15a - 12:15p
- Thursdays: 10:30a - 11:30a
Disclaimer: I reserve the right to change any part of this
syllabus at any time.
Copyright © 2023 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.