CSE100 Algorithm Design and Analysis (Fall semester 2026)

Instructor

Miguel Á. Carreira-Perpiñán Professor Electrical Engineering and Computer Science School of Engineering University of California, Merced mcarreira-perpinan-[at]-ucmerced.edu; 209-2284545 Office: 217, Science & Engineering Building 2

Office hours: Mondays/Wednesdays 3:30-4:25pm (SE2-217).

TAs:

Rasul Kairgeldin, rkairgeldin-[at]-ucmerced.edu. TA hours: Fridays 2-5pm (SE2 lobby).
Kuat Gazizov, kgazizov-[at]-ucmerced.edu. TA hours: Tuesdays 3-5pm (SE2 lobby).

Lectures: Tuesdays/Thursdays 9-10:15pm (COB105)

Lab class: Mondays 10:30am-1:20pm COB281 (section 02L), Wednesdays 7:30pm-10:20pm COB281 (section 03L), Wednesdays 10:30am-1:20pm SE1-100 (section 04L), Wednesdays 1:30pm-4:20pm SE1-138 (section 05L), Mondays 10:30am-1:20pm KOL208 (section 07L)

Course web page: https://faculty.ucmerced.edu/mcarreira-perpinan/teaching/CSE100

Course description

The course introduces the basics of computational complexity analysis and various algorithm design paradigms. It covers the major algorithms and data structures for searching, sorting, parsing, and memory management. Other topics include theoretical models of computation, concepts of algorithm complexity, computability, and NP-completeness.

Prerequisites: CSE015/024/030, MATH023/032 and concurrent prerequisites CSE031, MATH024; proficient level of programming skills in C/C++/Java and elementary data structures; basic math and probability knowledge.

Textbook

Required textbook (get the errata):

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein: Introduction to Algorithms, 3rd ed. MIT Press, 2009.

The companion site for the book has additional materials (partial solutions, slides, etc.).

Other books recommended as additional reading:

J. Kleinberg and É. Tardos: Algorithm Design, Addison-Wesley, 2005. Companion site for the book.
S. S. Skiena: The Algorithm Design Manual, 3rd ed. Springer, 2020. This book is accessible online from within UC Merced.
S. Dasgupta, C. H. Papadimitriou and U. V. Vazirani: Algorithms, McGraw-Hill, 2006.
Donald Knuth: The Art of Computer Programming.
A. V. Aho, J. E. Hopcroft and J. D. Ullman: Data Structures and Algorithms, Prentice-Hall, 1983.

Syllabus and required textbook reading

Syllabus

Topics: Asymptotic notation. Divide-and-conquer. Recurrent equations and the master theorem. Space and time complexity. Loop invariants. Linear and binary search. Sorting algorithms: insertion sort, selection sort, mergesort, quicksort, heapsort (and heaps); sorting lower bounds. Binary search trees. Hash tables with chaining and open addressing. Dynamic programming and greedy algorithms. Graphs: definition and relevant problems (minimum spanning trees, shortest paths).

The course will follow parts I, II, III, IV and VI of the textbook (skipping occasional topics).

Textbook reading:

Ch. 1 The Role of Algorithms in Computing: all.
Ch. 2 Getting Started: all.
Exercises: 2.1-1, 2.1-2, 2.1-3, 2.1-4, 2.2-2, 2.2-4, 2.3-1, 2.3-4, 2.3-6.
Ch. 3 Characterizing Running Times: 3.1, 3.2 (skip ο() and ω()).
Exercises: 3.1-1, 3.1-2, 3.1-3, 3.1-4, 3.1-5; problems 3-2, 3-3.
Ch. 4 Divide-and-Conquer: all except 4.3, 4.4, 4.6, 4.7.
Exercises: 4.5-1, 4.5-2, 4.5-3.
Ch. 6 Heapsort: all.
Exercises: 6.1-1, 6.1-2, 6.1-7, 6.2-1, 6.2-5, 6.3-1, 6.4-1, 6.5-1, 6.5-2, 6.5-9.
Ch. 7 Quicksort: all except 7.4.
Exercises: 7.1-1, 7.2-2, 7.2-5, 7.3-2.
Ch. 8 Sorting in Linear Time: all.
Exercises: 8.2-1, 8.2-3, 8.2-6, 8.3-1, 8.3-2, 8.3-3, 8.4-1.
Ch. 9 Medians and Order Statistics (not required): skim 9.1-9.2.
Exercises: problem 9.1.
Ch. 10 Elementary Data Structures: all except 10.3. This chapter is review material.
Exercises: 10.1-2, 10.1-3, 10.1-4, 10.2-1, 10.2-2, 10.2-3, 10.3-1, 10.3-2, 10.3-4; problem 10.1.
Ch. 11 Hash Tables: all except 11.3.2-11.3.5 and 11.5.
Exercises: 11.2-2, 11.2-5, 11.3-1, 11.3-4, 11.4-1, 11.4-2, 11.4-3.
Ch. 12 Binary Search Trees: all.
Exercises: 12.1-1, 12.1-2, 12.1-4, 12.1-5, 12.2-1, 12.2-3, 12.3-1, 12.3-3.
Ch. 14 Dynamic Programming: all except p. 385-386 and sec. 15.5.
Exercises: 14.1-1, 14.1-2, 14.1-3, 14.2-1, 14.2-2, 14.2-3, 14.2-5, 14.3-2, 14.4-1, 14.4-3.
Ch. 15 Greedy Algorithms: all except 15.4 (skim the correctness' proof of Huffman's algorithm).
Exercises: 15.1-1, 15.1-2, 15.1-3, 15.2-1, 15.2-2, 15.3-3, 15.3-4.
Ch. 20 Elementary Graph Algorithms: all (skim proofs).
Exercises: 20.1-1, 20.1-2, 20.1-7, 20.2-1, 20.2-2, 20.2-5, 20.3-2, 20.3-3, 20.3-12, 20.4.1, 20.4.5, 20.5-1, 20.5-2.
Ch. 21 Minimum Spanning Trees: all.
Exercises: 21.1-1, 21.2-4.
Ch. 22 Single-Source Shortest Paths: all except 22.4 and 22.5 (skim proofs).
Exercises: 22.1-1, 22.1-3, 22.2-1, 22.3-1.
Ch. 23 All-Pairs Shortest Paths: all.
Exercises: 23.1-4, 23.1-5, 23.1-7, 23.1-8, 23.1-9, 23.2-4, 23.2-6, 23.3-3.

The third edition of the textbook has a very similar coverage of the material.

Deadlines

Late submissions (homework or lab assignments) get a grade of zero. No excuses. There is plenty of time to work on them.

About weekly: lab assignments (see separate document in CatCourses).
Due Sep. 28 at 5pm: homework #1 (covering chapters 1-4 from the book).
Due Oct. 15 at 5pm : homework #2 (covering chapters 6-8, 10-12 from the book).
Oct. 20 in the usual lecture time/classroom: midterm exam (covering chapters 1-4, 6-8, 10-12 from the book).
Due Nov. 17 at 5pm: homework #3 (covering chapters 14-15 from the book).
Due Dec. 8 at 5pm: homework #4 (covering chapters 20-23 from the book).
Dec. 18 at 11:30am-2:30pm: final exam (covering all chapters above).

Homeworks

You must submit your solutions through CatCourses as a PDF file (scanned from a legibly handwritten hardcopy or created by a word processor, no larger than 3 MB). If the group has several members, submit a single PDF file listing the group members in the first page. We'll give you back the PDF file annotated with the grades and any corrections. Each homework counts equally for grading purposes. Late homeworks will receive a grade of zero. Don't leave it for the last minute!

Good computer scientists do no waste resources. Tips to create small but legible PDF files:

If it is a photo or scanned image, set the resolution low enough and apply lossy compression (JPEG). One handwritten page should be perfectly legible in about 100 kilobytes or less. You can convert a set of JPEG files to a single PDF file using ImageMagick's convert: convert *.jpg output.pdf.

In Linux, you can compress existing PDF files with:

xournal: open the file and export it to PDF
Ghostscript: you can use this wrapper: shrinkpdf
ImageMagick's convert (check its options)

Note: Apple iPads, etc. can produce hugely bloated PDF files.

Lab assignments

File labs.tar.gz in CatCourses contains all the assignments and deadlines (in file labs.pdf), the test files for each assignment, and any other necessary files.
Each lab assignment consists of programming a selected algorithm in C++ (or C). The goal is for you to program, test and debug several of the algorithms you learn in the lectures.
The lab sessions are intended for you to work on the lab assignments and ask questions to the TAs if you need to. The TAs will explain the lab assignments and discuss any issues (however, they cannot help you to debug your code, this is a crucial skill each student should master). To make the discussion fruitful, read the assignments and the book before asking for help. Attendance is not required (you can work on the assignments on your own), but is highly recommended.
There are several lab assignments that you have to submit and will be graded. The TAs will explain the mechanics of how this works in the first lab session. Essentially, you submit one .cpp file with your source code (to CatCourses by the due deadline). This is then graded automatically based on a set of test cases. The grade of each lab is the percentage of test cases passed (0 if the source doesn't compile correctly). Of the test cases we grade on, we give some to you for free and the rest are secret; you can test your code on the former using the automatic grader (you can also create your own tests, of course, don't just rely on the ones we provide).
Later assignments may depend on code produced in earlier assignments, so make sure to finish all assignments as you go.
For the first labs, both C or C++ are ok. For some assignments later in the course, you'll use only C++ and the Standard Template Library (STL), to be able to use linked lists and other data structures easily (see links below). You can still use C if you really want, but you'll spend too much time implementing lists, stacks, queues, etc.
Note: your code should follow closely the pseudocode in the book (also explained in class). For example, for bucketsort, it's ok to use STL functions to sort an individual list or to concatenate the lists, as noted in the pseudocode. For binary search trees, it's NOT ok to use a tree data structure or tree functions from the STL; you must implement the pointer handling yourself.

Course grading

Midterm exam (25%): in-class, closed-book, consisting of problems and conceptual questions. It will cover ch. 1-12 (parts I-III) inclusive. To do on your own (individually).
Final exam (50%): as with the midterm. It will cover the entire course, but mostly focusing on the part after the midterm. To do on your own (individually).
Lab assignments (10%): these consist of programming selected algorithms in C and C++. To do on your own (individually). Each lab assignment counts equally for grading purposes.
Homeworks (15%): exercises and problems similar to those in the textbook to be submitted approximately every four weeks. To do on groups of up to 3 students. Each homework counts equally for grading purposes. We'll give you back a marked-up PDF file with the grades and any corrections.

Grade histogram.

Academic dishonesty

While I encourage you to discuss your work with other students, the homeworks, lab assignments and exams must be the result of your own work (or your group's work, for homeworks) without collaboration. Cheating causes two problems: you learn less well, and it is unfair to students who put honest effort into their work. See the Academic Dishonesty Statement in the syllabus and the UC Merced Academic Honesty Policy. Importantly: should copying (or other infraction) occur, both the student who copied work from another student and the student who gave material to be copied will both automatically receive a zero for the assignment. Further, if the School of Engineering determines that the student had committed an infraction in any other course, the penalty will be elevated to an F in the entire course.

Specifically regarding the lab assignments:

We use a plagiarism checker. Don't risk failing the course. The lab assignments are simple and instructive and you'll learn a lot if you work through them.
About using the web to get information: do not try to find a solution in the web for the algorithm we ask you to implement and then try to adapt it to the assignment given; that's cheating. But do use the web to check the syntax of C/C++/STL, Unix commands, etc.

For both lab assignments and homeworks: you must disclose whatever sources you used to complete your work or to help others complete theirs. For homeworks, write it at the beginning of your submission. For programming assignments, write it as a comment at the beginning of your .cpp file. Examples of possible sources:

I used the textbook, notes taken during the lectures, companion material from the textbook.
I helped student X or received help from X (describe how specifically).
I consulted an online resource: website / book / video / etc. Give its URL and explain how you used it.
I consulted book X.
etc.

Some general advice about the course

I teach this course without slides, by developing the algorithms in the whiteboard step by step. I find this forces students to think and they learn better (if they pay attention). If you want slides covering similar material, you can find some online: MIT OpenCourseWare, Stanford University.
The best way to prepare and learn is to read the book chapter (as indicated in the course web page) before attending the lecture that covers it, as we move along the course. Then you'll be better prepared to ask questions about things you didn't understand. Not only is this pretty obvious, but there is a lot of research backing this learning strategy. Also, I don't cover everything in the book in the lectures, but you are expected to study it.
Likewise, do the exercises suggested as we go along. Some of them have public solutions in the textbook companion site. Of the exercises I suggest you to do, I won't solve all in class and I'll generally do only partial solutions for the rest. Come to my or the TA office hours or lab sessions if you have questions.
Distractions (such as checking your mobile phone) mean you don't learn well. If you come to class, pay attention, you'll end up saving more time than trying to do things in parallel. Again, there is a lot of research showing that people don't do multiple cognitive tasks well at once. All of this applies to remote learning.