CSE100 Algorithm Design and Analysis (Spring semester 2015)

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: 217, Science & Engineering Building 2

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

TAs:

New this year! The Algorithms Clinic: Mondays 4:30-6:20pm (KL202). These are unofficial office hours organized by Brian Bamsch, Robert Wang and Kevin Song from the UC Merced ACM chapter. Get help with exams, job interview questions or anything about algorithms.

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

Lab class: Wednesdays 7:30-10:20am (section 02L), 10:30am-1:20pm (section 03L) and 1:30-4:20pm (section 04L) (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):

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

Other books recommended as additional reading:

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):

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

Homeworks

Homework (to do on your own, graded):

Project

Optional project (to do on your own, for extra credit), in groups of 4 students, due May 8 11:59pm PST by email to the TA. You have a choice among the following two different projects:

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

Grade curves: midterm, final.

Links

Algorithms:

Programming resources:

Plotting resources:

Job interview questions about algorithms:


Miguel A. Carreira-Perpinan
Last modified: Fri Apr 3 00:18:48 PDT 2015

UC Merced | EECS | MACP's Home Page