back to classes

CS312 Data Structures and Algorithms

Syllabus

Fall 2005

cs312 website: http://www.calstatela.edu/faculty/vcrespi/CS/CS312/cs312.html
Lectures:

TR 1:30-3:10pm, ET A210

Final Exam:

Thursday, Dec 8, 1:30-4:00pm, ET A210

Instructor:

Valentino Crespi
vcrespi@calstatela.edu
(323) 343-4596.
ET-A318

Office Hours:

MW 3:00-4:00pm, TR 6:00-7:00pm.

Course Description: Abstract data types and their use in constructing algorithms for manipulating lists, trees, and graphs; analysis of algorithms for searching, sorting, and data structure manipulation.
Course Goals: At the end of the course, students are able to
  1. Analyze the correctness and the computational complexity of computer algorithms.
  2. Design (specify and implement) efficient advanced Data Structures.
  3. Know advanced design techniques and their nontrivial application to classic problems of searching, sorting, graph optimization and combinatorial optimization.
Prerequisites: MATH208, MATH248, CS203
Textbook: Richard Johnsonbaugh, Marcus Schaefer. Algorithms. Prentice Hall, 2004.
References:
  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms(2nd edition). MIT Press and McGraw Hill, 2001.
  2. Michael T. Goodrich, Roberto Tamassia. Data Structures and Algorithms in Java (4th edition). John Wiley & Sons, Inc, 2006.
Topics: This is a general overview. However you can access the archive to see full logs of previous instances of this same course.
  • Mathematical Foundations: summation Formulas, Logarithms, Induction, Lower and Upper bounds, Asymptotic Notation, Recurrence Relations, Master Theorem, Loop Invariants. (cp 1-2)
  • Analysis of the Correctness and of the Computational Complexity of Computer Algorithms. (cp 1-2)
  • Advanced Data Structures: Binary Search Trees, Balanced Trees, Heaps, Indirect Heaps, Priority Queues, Dictionaries, Hash-Tables, Union-Find structures. (cp 3)
  • Graph Algorithms and Searching and Sorting Algorithms. (cp 4)
  • Design Techniques: Divide and Conquer, Greedy and Dynamic Programming. (cp 5-8)
Grading Policy: Two Midterm Exams (25%+25%), Final Exam (40%), Homework Assignments (10%)
Score (%) Letter Grade
90-100 A
80-89 B
60-79 C
50-59 D
0-49 F
Academic Integrity: Students are allowed and encouraged to discuss reading materials with each other. However, homework assignments must be solved and written individually. If you obtain a solution with help then you should acknowledge your source in the paper and then write independently your own solution.

Cheating will not be tolerated. Cheating on any assignment or exam will be taken seriously. All parties involved will receive a grade of F for the course and be reported to the Academic Senate.
General Policies:
  • Makeup Exams: No.
  • Homework Assignments:
    Homework assignments should be written neatly on standard sized paper (8.5 x 11 inch), possibly in black or blue ink (please do not use red) and submitted at the due date (no electronic submissions accepted unless stated otherwise in class). Each page should be numbered. Late submissions will not be accepted.
  • Use of Cell Phones: forbidden.
  • Late arrivals:
    Students arriving 30min after the beginning of class will not be admitted.
  • Office:
    Students are warmly invited to visit the instructor (during the announced office hours) for questions and clarifications.
  • E-mail:
    E-mails addressed to vcrespi@calstatela.edu must have, in the subject, the keyword CS312 (e.g. Subject: CS312 ...). All the E-mails will be possibly processed in the evening and so will be answered with a minimum delay. Be careful, the keyword in the subject is important for automatic filtering. Wrong subjects may result in the accidental loss of the message.