COSC 3320: Algorithms and Data Structures (Spring 2016)

General Informations

- Instructor: Michele Scquizzato, PGH 574, m...@cs.uh.edu.
- Meetings: Tuesdays and Thursdays, 10.00am - 11.25am, SEC 204, January 19 - April 28 (28 classes).
- Office hours: Wednesdays and Fridays, 10.00am - 11.00am.
- TAs:
- Reza Fathi, rfathi@uh.edu. Office hours: Fridays, 1.00pm - 2.00pm, PGH 350.
- Luis F. De Moraes, ltdemoraes@uh.edu. Office hours: Wednesdays, 2.00pm - 3.00pm, PGH 344.

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%. They are assigned every other Thursday, starting from the first week
of class, and due the following Thursday, for a total of seven assignments.
All homework is due at the start of class on the date due, and no late homework is accepted.
Homework has to be submitted individually, i.e., 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 will consist 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 22, 10.00am - 11.25am, SEC 204.
- Final Exam: 40%. It will consist 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 12, 11.00am - 1.00pm, SEC 204.

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.