CSE100 Algorithm Design and Analysis (Spring semester 2014)

Instructor

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

Office hours: Tuesdays/Thursdays 4:15-5:15pm (SE284).

TA: Ramin Razi, rraziperchikolaei-[at]-ucmerced.edu. TA hours: Mondays 11am-1pm (AOA142)A.

Lectures: Tuesdays/Thursdays 3-4:15pm (KOL217)

Lab class: Fridays 2-4:50pm (section 02L) and 5-7:50pm (section 03L) (Linux Lab, SE100)

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: CSE31; 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, 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.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.

Homeworks

Homework (to do on your own, graded):

Homework #1 (covering chapters 1-4 from the book): due Feb. 20 at the beginning of the lecture.
Homework #2 (covering chapters 6-12 from the book): due Mar. 13 at the beginning of the lecture.
Homework #3 (covering chapters 15-16 from the book): due Apr. 17 at the beginning of the lecture.
Homework #4 (covering chapters 22-24 from the book): due May 9 during your lab session.

Project

Optional project (to do on your own, for extra credit): experimental run times of hash tables with open addressing. In groups of 3 students. Due May 9 11:59pm PST by email to the TA.

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.
Final exam (30%): as the midterm. It will cover the entire course, but mostly focusing on the part after the midterm.
Lab assignments (20%): these consist of programming selected algorithms in C and C++, and will be graded within the lab session.
Homeworks (20%): exercises and problems similar to those in the textbook to be submitted approximately biweekly.
Optional project for up to 10% extra credit.

While I encourage you to discuss your work with other students, the homeworks, lab assignments, project and exams must be the result of your own work without collaboration. See the Academic Dishonesty Statement and the UC Merced Academic Honesty Policy.

Grade curves: midterm, final.