CSE100 Algorithm Design and Analysis (Fall semester 2018)

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:15-4:15pm (SE2-217).

TAs:

Yerlan Idelbayev, yidelbayev-[at]-ucmerced.edu. TA hours: Thursdays 10am-12pm (AOA142).
Arman Zharmagambetov, azharmagambetov-[at]-ucmerced.edu. TA hours: Tuesdays 11:30am-1:30pm (AOA142).

Lectures: Tuesdays/Thursdays 4:30-5:45pm (COB116)

Lab class: Mondays 7:30-10:20am (section 02L) and 10:30am-1:20pm (section 03L), Wednesdays 7:30-10:20am (section 04L) and 7:30-10:20pm (section 05L) (Linux Lab, SE1-100)

Course web page: http://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: CSE30, CSE31, MATH24, MATH32; 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, 2nd ed. Springer, 2008. 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. Sorting lower bounds. Heaps. Binary search trees. Hash tables with chaining and open addressing. Dynamic programming and greedy algorithms. Graphs: definition and relevant problems (path search, flow, minimum spanning trees).

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

Textbook reading (table of contents):

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.2-2, 2.2-4, 2.3-1, 2.3-2, 2.3-3, 2.3-5.
Ch. 3 Growth of Functions: 3.1 (skip ο() and ω()).
Exercises: 3.1-1, 3.1-4, 3.1-5, 3.1-6; 3.2-3; problems 3-2, 3-3.
Ch. 4 Divide-and-Conquer: all except 4.3, 4.4, 4.6.
Exercises: 4.1-1, 4.3-1, 4.3-9, 4.4-4, 4.4-6, 4.5-1, 4.5-2, 4.5-3, 4.5-4.
Ch. 6 Heapsort: all.
Exercises: 6.1-1, 6.1-2, 6.1-6, 6.2-1, 6.2-4, 6.3-1, 6.4-1, 6.5-1, 6.5-2, 6.5-7.
Ch. 7 Quicksort: all except 7.4.
Exercises: 7.1-1, 7.2-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-4, 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-1, 10.1-2, 10.1-3, 10.2-1, 10.2-2, 10.2-3, 10.4-1, 10.4-2, 10.4-4; problem 10.1.
Ch. 11 Hash Tables: all except 11.3.3 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 except 12.4.
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. 15 Dynamic Programming: all except p. 382-383 and sec. 15.5.
Exercises: 15.1-1, 15.1-2, 15.1-3, 15.2-1, 15.2-2, 15.2-3, 15.2-4, 15.2-5, 15.3-2, 15.4-1, 15.4-3.
Ch. 16 Greedy Algorithms: all except 16.4 and 16.5 (skim the correctness' proof of Huffman's algorithm).
Exercises: 16.1-1, 16.1-2, 16.1-3, 16.2-1, 16.2-2, 16.3-3, 16.3-4.
Ch. 22 Elementary Graph Algorithms: all (skim proofs).
Exercises: 22.1-1, 22.1-2, 22.1-7, 22.2-1, 22.2-2, 22.2-5, 22.3-2, 22.3-3, 22.3-12, 22.4.1, 22.4.5, 22.5-1, 22.5-2.
Ch. 23 Minimum Spanning Trees: all.
Exercises: 23.1-1, 23.2-4.
Ch. 24 Single-Source Shortest Paths: all except 24.4 and 24.5 (skim proofs).
Exercises: 24.1-1, 24.1-3, 24.2-1, 24.3-1.

If there is time, we will also do one of the following chapters:

Ch. 25 All-Pairs Shortest Paths: all.
Exercises: 25.1-4, 25.1-5, 25.1-6, 25.1-7, 25.1-8, 25.1-9, 25.2-4, 25.2-6, 25.3-3.
Ch. 26 Maximum Flow.
Ch. 27 Multithreaded Algorithms.

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 week of Sep. 24 during your lab session: homework #1 (covering chapters 1-4 from the book).
Due week of Oct. 15 during your lab session: homework #2 (covering chapters 6-12 from the book).
Oct. 23 4:30-5:45pm COB116 (during the lecture slot): midterm exam.
Due week of Nov. 26 during your lab session: homework #3 (covering chapters 15-16 from the book).
Due Dec. 6 at the beginning of the lecture: homework #4 (covering chapters 22-24 from the book).
Dec. 11 8-11am COB116: final exam.

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 seeking 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 (p. 201), 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 (30%): 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 (30%): 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 (20%): 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 (20%): exercises and problems similar to those in the textbook to be submitted approximately biweekly. To do on groups of up to 3 students. You must submit your solutions both as a hardcopy (legibly handwritten or printout) and as a PDF file (scanned or created by a word processor, no larger than 1 MB). We'll give the hardcopy back to you with the grades and any corrections. In the week of the deadline (or before), submit it during your lab section. Each homework counts equally for grading purposes.

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 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. ~~A repeated incident will directly lead to an F.~~ A single incident will directly lead to an F.

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, you can find some online.
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.