Class Description
Methods for the systematic construction and mathematical analysis of algorithms. Order notation, the RAM model of computation, lower bounds, and recurrence relations are covered. The algorithm design techniques include divide-and-conquer, branch and bound, and dynamic programming. Applications to combinatorial, graph, string, and geometric algorithms. (Formerly Computer Science 102.)
Class Meeting Times
Lecture
| Monday/Wednesday/Friday | 12:00PM -1:05PM | Performing Arts M110 (Media Theater) |
Discussion Sections
NOTE Discussion Sections do not meet first week of class. They begin Oct 7
Schedule (tentative)
| CSE 102-01A | Day/Time: Monday 2:40PM - 3:45PM | Location: PhysSciences 114 |
| CSE 102-01B | Day/Time: Monday 4:00PM - 5:05PM | Location: Soc Sci 2 179 |
| CSE 102-01C | Day/Time: Tuesday 8:30AM - 9:35AM | Location: PhysSciences 110 |
| CSE 102-01D | Day/Time: Wednesday 8:00AM - 9:05AM | Location: PhysSciences 114 |
| CSE 102-01E | Day/Time: Thursday 7:10PM - 8:15PM | Location: Kresge Acad 3101 |
| CSE 102-01F | Day/Time: Friday 4:00PM - 5:05PM | Location: PhysSciences 110 |
MSI Tutoring Sections
tbd
Instructor
Delbert D. Bailey (ddbailey@ucsc.edu)
Office: E2-249A
Office Hours: Monday/Wednesday 1:30pm to 2:30pm and by appointment.
Teaching Assistants (Tentative)
Shahar Dubiner (sdubiner@ucsc.edu)
- Office: tbd
Office Hours: tbd
Justin Frauenhofer (jtfrauen@ucsc.edu)
- Office: tbd
Office Hours: tbd
Ross Mawhorter (rmawhort@ucsc.edu)
- Office: tbd
Office Hours: tbd
Learning Support Services
Tutor
tbd
Textbook
Introduction to Algorithms, 4th Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, 2022.
Alternatively, you may use the 3rd edition. The differences are not critical to this course.
Syllabus (tentative subject to change)
- Introduction
- Example Design and Analysis
- Asymptotic notation
- Common notations and functions
- Divide and Conquer
- Solving recurrences
- Master Method
- Probabalistic analysis
- Heap Sort
- Quick Sort
- Lower bounds for comparison sorts
- Counting Sort
- Radix Sort
- Bucket Sort
- Medians and order statistics
- Dynamic Programming
- Greedy Algorithms
- Amortized Analysis
- Graph Algorithms
- Minimum Spanning Trees
- Single-Source Shortest Paths
- All-Pairs Shortest Paths
- Maximum Flow
Homework
There will be a minimum of 8 maximum of 10 homework assignments posted via canvas. Submissions must be a legible single pdf file. Scaned handwritten solutions on unruled white paper are permissible. Solutions will be posted and discussed in class and sections shortly after the due dates. Unexcused late submissions will not be accepted for scoring. Partial credit will be given for incomplete submissions so be sure to submit what ever you have by the due date. Your lowest homework score will be dropped so one homework could be missed without impacting your average homework score.
Examination Schedule
| Midterm 1 | Monday, October 21 | 10:40am |
| Midterm 2 | Monday, November 13 | 10:40am |
| Final | Tuesday, December 10 | 8:00am - 11:00am |
The examination schedule is fixed. In particular, requests for changes in the schedule will not be accommodated; if you have conflicts with this schedule, please do not enroll in the class. Also, no time extension will be given for late arrivals.
Evaluation
Homework (P/NP)
Midterm 1 (30%)
Midterm 2 (30%)
Final Exam (40%)
Letter grades A, B, C and D (without pluses or minuses) will be assigned respectively for scores greater than/equal 90, 80, 70 and 60.
Scores within 1% of a cutoff point will be rounded upward.
Academic Integrity
No form of academic dishonesty will be tolerated. Incidents of academic dishonesty will be reported according to UCSC's policy on academic integrity, the full text of which can be found at Academic Misconduct Policy for Undergraduates . Specifically, if you are caught submitting work as your own in this class, that is not solely your own, or assisting others in doing so, a formal written report will be sent to your Department, the School of Engineering, and to your Provost and academic preceptor. Furthermore you will get a failing grade for the course and the incident will be noted in your evaluation. A submitter's inability to explain a submitted solution will be considered prima facie evidence that it was copied.
Student Accommodations Requests
UC Santa Cruz is committed to creating an academic environment that supports its diverse student body. If you are a student with a disability who requires accommodations to achieve equal access in this course, please submit your Accommodation Authorization Letter from the Disability Resource Center (DRC) to me privately during my office hours or by appointment, preferably within the first two weeks of the quarter. At that time, we can also discuss ways we can ensure your full participation in the course. We encourage all students who may benefit from learning more about DRC services to contact DRC by phone at 831-459-2089 or by email at drc@ucsc.edu.
The class design is not optimized for webcasting. However, Lecture Capture Service is available to support DRC students that have an accommodation for class recordings. Note any student can access the recordings via YuJa. However, they are not intended to be used in lieu of class attendence.
Communications
We will use Canvas to make general announements and provide forums to answer clearification questions on homework assignments but not solutions. Questions on how to solve specific homework problems are to be addressed in the Discussion Sections and in office hours. Do not allow other students to read or copy your solutions and do not read or copy solutions of others. Do not use the message facility of canvas to contact the instructor. Use regular email directly to ddbailey@ucsc.edu. Include in the subject line CSE103.
