Instructor: Sungjin Im

- Email: im3-[at]-ucmerced.edu; Phone: 209-228-2358 (Email is the best way to reach the instructor)
- Office: 214, Science and Engineering Building 2
- Office hours: 6-7pm, Tuesday (SE2-214)

TAs:

Mahshid Montazer Qaem

- Email: mmontazerqaem-[at]-ucmerced.edu.
- (Old) office hours (-2/17) : 10:30-11:30am, Thursday (AOA-142)
- (New) office hours (2/27-) : 6:20-7:20pm, Mon (AOA-142)

Bhrigu Adlakha

- Email: badlakha-[at]-ucmerced.edu.
- (Old) office hours (-2/17): 10:00-10:30am and 04:30-05:00pm, Wed (AOA-142)
- (New) office hours (2/20-): 9pm, Thursday. Online (CatCourses Chat)

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

Lab class: Monday 1:30-4:20pm (section 02L), 7:30-10:20pm (section 03L), and Wed 10:30am-1:20pm (section 04L), 1:30pm-4:30pm (section 05L). Linux Lab, SE100

Introduction to the design and analysis of computer algorithms. Topics include analysis and implementation of algorithms, concepts of algorithm complexity, and various algorithmic design patterns. Course will also cover major algorithms and data structures for searching and sorting, graphs, and some optimization techniques.

Prerequisites: CSE 15 and CSE31; proficient level of programming skills in C or C++ 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 E. 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 (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*: all. (skim 9.3).

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*.

- 1/17: Lecture. ch01. Course introduction. Administrivia
- 1/19: Lecture. ch02.
- 1/23, 1/25: Lab01 (deadline 2/1). Discussion01.
- 1/24: Lecture. ch02 merge sort revisitd. ch03.
- 1/26: Lecture. ch03. ch04.
- 1/30, 2/1: Lab02 (deadline 2/8). Discussion02.
- 1/31: Lecture. ch04.
- 2/2: Lecture. ch04.
- 2/6, 2/8: Lab03. Discussion03
- 2/7: Lecture. ch04.
- 2/9: Lecture. ch06.
- 2/13, 2/15: Lab04-1. Lab04-2. Discussion04
- 2/14: Lecture. ch07.
- 2/16: Lecture. ch08.
- 2/20, 2/22: No Lab (2/20 is Presidential Holiday)
- 2/21: Lecture.
- 2/23: Lecture.
- 2/27, 3/1: Lab.
- 2/28: Lecture.
- 3/2: Lecture.
- 3/6, 3/8: Lab.
- 3/7: Lecture.
- 3/9: Lecture.
- 3/13, 3/15: Lab.
- 3/14: ***Midterm***
- 3/16: Lecture.
- 3/20, 3/22: Lab.
- 3/21: Lecture.
- 3/23: Lecture.
- 3/27, 3/29: Spring break.
- 3/28: Spring break.
- 3/30: Spring break.
- 4/3, 4/5: Lab.
- 4/4: Lecture.
- 4/6: Lecture.
- 4/10, 4/12: Lab.
- 4/11: Lecture.
- 4/13: Lecture.
- 4/17, 4/19: Lab.
- 4/18: Lecture.
- 4/20: Lecture.
- 4/24, 4/26: Lab.
- 4/25: Lecture.
- 4/27: Lecture.
- 5/1, 5/3: Lab.
- 5/2: Lecture.
- 5/4: Lecture.
- 5/9: Final.

- Midterm exam (25%): In-class. Closed-book. 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 or 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.
- Attendance (5%): You are allowed to miss up to 6 lectures/discussion sessions. The first lab hour is devoted to discussion and requires attendance. No need to attend the second part of lab if you can complete the lab assignment by yourself.
- Participation: Active participation will be factored in final grading.

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. If you cheat once, you will get zero points for the hw/lab/exam you cheated on. If you do twice, you will get an F.

Algorithms:

- List of algorithms
- Sorting algorithm animations
- Sorting algorithms with dances
- Algorithm animations/visualizations (in Java)
- Huffman codes: see Morse code and ETAION_SHRDLU.

Programming resources:

- man pages
- The GNU C Library
- The GNU Scientific Library
- C++ Reference
- Standard Template Library (STL) Programmer's Guide

Plotting resources:

- Semi-log and log-log graphs.

Job interview questions about algorithms:

- S. S. Skiena:
*The Algorithm Design Manual*(interview problems in each chapter). This book is accessible online from within UC Merced. - J. Mongan, N. Suojanen and E. Giguï¿½re:
*Programming Interviews Exposed*. - G. Laakmann: Cracking the Coding Interview.
- S. S. Skiena and M. A. Revilla: Programming Challenges. This book is accessible online from within UC Merced.
- Real interview questions: www.careercup.com, www.glassdoor.com.

* Acknowledgements: The instructor thanks Prof. Carreira-Perpiñán for allowing me to borrow the course format including this webpage itself.