COSC 3320: Algorithms and Data Structures (Spring 2017)

General Informations

- Instructor: Michele Scquizzato, PGH 574, m...@cs.uh.edu.
- Meetings: Tuesdays and Thursdays, 10.00am - 11.25am, SEC 103, January 17 - April 27 (28 classes).
- Office hours: Wednesdays and Fridays, 10.00am - 11.00am.
- TAs:
- Emtiaz Ahmed, mahmed24@uh.edu. Office hours: Mondays, 3.00pm - 4.00pm, PGH 364.
- Avisha Das, adas5@uh.edu. Office hours: Tuesdays, 2.00pm - 3.00pm, PGH 344.
- Nacer Khalil, nkhalil@uh.edu. Office hours: Wednesdays, 11.30am - 12.30pm, T2-221.
- Nguyen Pham, ndpham3@uh.edu. Office hours: Tuesdays, 4.30pm - 5.30pm, PGH 350.

Course Description

COSC 3320 provides an introduction to fundamental principles of algorithm design and analysis.
A (tentative and subject to change) list of topics covered by the course follows.

- Fundamental concepts: computational problem, algorithm, model of computation. Analysis of correctness and complexity of algorithms.
- The divide-and-conquer paradigm, with applications to sorting and algebraic problems.
- Data structures: trees, heaps, hash tables, binary search trees.
- The dynamic programming paradigm, with applications to problems on strings.
- Graphs and graph algorithms: depth- and breadth-first search, minimum spanning trees, shortest paths.
- (if time permits) An introduction to NP-Completeness: complexity classes P, NP, co-NP and NPC, and polynomial-time reductions.

Prerequisites

COSC 2320. If you take this class without this prerequisite, you forfeit your right to complain that the class is at an inappropriate level.

Evaluation

Your performance will be measured in three ways. (The percentage contributions to your grade given below are approximate.)

- Homework: 20%. Assignements are posted on this webpage every other Thursday, starting from the first week
of class, and due the following Thursday, for a total of seven assignments.
All assignments are due at the start of class on the due date, in hard copy. No late homework is accepted.
Homework has to be
**individual**, hence no group submissions are allowed. If a student's homework scores are conspicuously/suspiciously higher than a student's exam grades, the instructor reserves the right to base the course grade on only the exam scores.

Homework 1 Homework 2 Homework 3 Homework 4 Homework 5 Homework 6 Homework 7

- Midterm: 40%. It consists of a few exercises similar to the ones in the homework, and possibly some theoretical questions such as proving some theorem seen in class. This test is closed book, closed notes. Date: March 21, 10.00am - 11.20am, SEC 103.
- Final Exam: 40%. It consists of a few exercises similar to the ones in the homework, and possibly some theoretical questions such as proving some theorem seen in class. This test is closed book, closed notes. Date: May 4, 11.00am - 1.00pm, SEC 103.

Textbook

Not required, but highly recommended:

- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein: Introduction to Algorithms, 3rd edition, The MIT Press, 2009.

- J. Kleinberg and E. Tardos: Algorithm Design, Addison-Wesley, 2005.
- M. T. Goodrich, R. Tamassia, and M. H. Goldwasser: Data Structures and Algorithms in Java (sixth edition), Wiley, 2014.