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:

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

The companion site for the book has additional materials (partial solutions, slides, 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:

Deadlines

Late submissions (homework or lab assignments) get a grade of zero. No excuses. There is plenty of time to work on them.

Lab assignments

Course grading

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:

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:

  1. I used the textbook, notes taken during the lectures, companion material from the textbook.
  2. I helped student X or received help from X (describe how specifically).
  3. I consulted an online resource: website / book / video / etc. Give its URL and explain how you used it.
  4. I consulted book X.
  5. etc.

Some general advice about the course

Links

Algorithms:

Programming resources:

Plotting resources:

Job interview questions about algorithms:

Other:


Miguel A. Carreira-Perpinan
Last modified: Sun Nov 25 23:34:34 PST 2018

UC Merced | EECS | MACP's Home Page