`
Miguel Á. Carreira-Perpiñán
Assistant 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 12pm-1pm (SE284).

TA: Chao Qin, cqin-[at]-ucmerced.edu. TA hours: Mondays/Wednesdays 4pm-5pm (AOB143).

Lectures: Tuesdays/Thursdays 10:30am-11:45am (KOL217)

Lab class: Fridays 2-4:50pm (Linux Lab, SE100)

Course web page: `http://faculty.ucmerced.edu/mcarreira-perpinan/CSE100`

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.

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.

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:

- Ch. 1: all.
- Ch. 2: 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: 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: 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: 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: all except 7.4.

Exercises: 7.1-1, 7.2-1, 7.2-2, 7.2-5, 7.3-2. - Ch. 8: 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 (not required): skim 9.1-9.2.

Exercises: problem 9.1. - Ch. 10: all except 10.3. This chapter is review material.

Exercises: none. - Ch. 11: 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: 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: 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: all except 16.4 and 16.5.

Exercises: 16.1-2, 16.1-3, 16.2-1, 16.3-3. - Ch. 22: 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: all.

Exercises: 23.1-1, 23.2-4. - Ch. 24: all except 24.4 and 24.5 (skim proofs).

Exercises: 24.1-1, 24.1-3, 24.2-1, 24.3-1.

Homework (to do on your own, graded):

- Homework #1 (covering chapters 1-4 from the book):
**due September 22 at the end of class**. - Homework #2 (covering chapters 6-12 from the book):
**due October 15 at the beginning of class**. - Homework #3 (covering chapters 15-16 from the book):
**due November 17 at the beginning of class**. - Homework #4 (covering chapters 22-24 from the book):
**due December 9 in the TA hours**.

Optional project (to do on your own, for extra credit): experimental run times of sorting algorithms. **Due December 7** by email to the TA.

- Midterm exam (30%): in-class, closed-book, consisting of problems and conceptual questions.
- Final exam (30%): as the midterm.
- Lab assignments (20%): these consist of programming selected algorithms in 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 20% 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.

Algorithms:

- Sorting Algorithm Animations
- Sort Algorithm Animator
- Algorithm Animations/Visualizations (in Java)
- Huffman codes: see Morse code and ETAION_SHRDLU.

Programming resources:

Plotting resources:

- Semi-log and log-log graphs.

Miguel A. Carreira-Perpinan Last modified: Tue Dec 22 01:09:31 PST 2009