COP 3530: Data Structures
Fall 2016: Classroom Venue ECS 138
Office: ECS 254A; Phone: (305) 348-3748;
Office Hours: Wed 5-6 PM or by Appt via eMail
Learning Assistant Office Hours: Tue and Thu 12:30 - 2:30 PM @ PG6
Room 106
e-mail: giri@cs.fiu.edu
Final Exam: TBA
ANNOUNCEMENTS
- Dec 2: Tester class for HW #5 is finally
ready. Apologies for the delay. See below.
- Dec 1 FIU Programming Team
Information : As promised, here are the links to the ACM 2016
Southeast USA Regional Programming Competition (Competition Website), the Problem
Sets
(Division 1) and
(Division 2 -- slightly easier), and the Team performance (Standings in
Div 1). The FIU Programming Team website is at: (FIU Prog Team). Please visit these links after your final exams!
- Nov 29: Review questions for final exam: Review
- Nov 23: HW #5. It is due by 11:59 PM on Dec 2. There
will be no extensions for this assignment.
- Nov 15: Deadline for HW #4 has been extended to 11:59 PM on Thursday, Nov 17.
- Nov 14: Tester class for HW #4 is ready. See below.
- Nov 08: HW #4 is ready. It is due on November 16 before class.
- Oct 24: Yes, there was a bug in the tester files for HW #3. They have now been fixed
and the files have been updated. Please refresh your browser and download the tester files again.
The submission deadline has been extended to Oct 26 to allow you to finish the work.
- Oct 22: Review questions for mid term: Review
- Oct 20: Syllabus for midterm is everything covered through Oct 19 [Big-Oh Notation,
Worst-Case Time Complexity, Lists, Stacks, Queues, Binary Trees, Binary Search Trees, AVL Trees,
Priority Queues, Binary Heaps, Recursion, Hashing]
- Oct 12: Your midterm will be on Wednesday, Oct 26. The drop deadline is Oct 31.
- Oct 09: HW #3 is ready. It is due on October 24 before class.
- Oct 05: Class for today is canceled, thanks to Matthew, the hurricane...!
- Oct 01: I have added notes on Assignment 2 below.
- Oct 01: Below you can find the final class file for Assignment 2
called Test2ForAssign2.class. This is the one to submit, not the preliminary
test file given to you earlier.
- Sep 28: Below you can find a class file for a
preliminary test called Test1ForAssign2.class. This is to
enable you to test your program. You will soon get the file
Test2ForAssign2.class with a more comprehensive test of your
implementations. Stay tuned!
- Sep 20: HW #2 is ready. It is due on October 3 before class.
- Sep 19: Tentative Date for your first midterm is Wednesday, October 19
- Sep 10: Quiz #1 Solutions: Click Here
- Sep 06: There will be a 10 minute quiz tomorrow on
the topic of time complexity and big-Oh notation. In future, quizzes
will not be announced.
- Sep 01: HW #1 is ready. See below. It is due on Sep
14. Note that we have no class on Sep 5 -- it's LABOR DAY.
- Aug 24: You will be using an interactive website called
OpenDSA. You have to
first register. Follow the link for the e-book for a "Data
Structures and Algorithms course taken after a traditional CS2
course". This will take you to the Table of Contents. You will find
tha many of the chapters in this e-book mirror those in your
text. Along with links to my lecture slides, I will try to guide you
with the sections of this e-book that you need to read for each
class. PLEASE MAKE SURE THAT YOU READ THESE SECTIONS BEFORE YOUR
NEXT CLASS.
- Aug 22: For Syllabus see below.
- For Policies and Rules and Regulations for this class, see
below. In particular, read the cheating policy.
PROGRAMMING ASSIGNMENTS
- Assignment #5:
Kevin Bacon Game -- Deadline: Dec 2, 11:59
PM; Here is a class file for the test: BaconNumGen.class;
Notes: This test file expects
an unzipped data file (bacon.ser). If you downloaded the zipped
version (bacon.ser.gz), then gunzip it before running this tester
class file. Remember to place the data file in the cop3530
directory, else you will get an exception that the file
bacon.ser was not found. You may use up to 700 MB of
VM. However, you will get extra points for using the smallest VM.
This tester program outputs the VM usage and excution time. Thus, you
do not need to put the fragment of VM usage code in your program.
- Assignment #4:
Hashing -- New deadline: Nov 17, 11:59 PM;
Here is a class file for the test: TestForAssign4.class;
- Assignment #3:
Balanced Binary Search Trees -- Due Oct 26, 2016 (Note the change!) before start of class;
Here is a class file for the test: TestForAssign3.class;
Here is a class file for testing the Extra credit work: XtraTestForAssign3.class.
Note that you have to submit a single zipped file containing the following:
(a) source code (all java files),
(b) class files (all class files),
(c) the tester class files,
(d) the result of running class file TestForAssign3.class, and
(e) [if extra credit works] the result of running class file XtraTestForAssign3.class.
Make sure the files have the appropriate directory structure that is needed.
- Assignment #2:
Priority Queues -- Due Oct 3, 2016 before start of class;
Here is a class file for a preliminary test: Test1ForAssign2.class;
Here is a class file for the real test: Test2ForAssign2.class.
Note that you have to submit the source code (java files) and the result of running
this class file Test2ForAssign2.class, not the preliminary class file Test1ForAssign2.class.
Additional notes on this assignment can be found in Notes on Assignment#2;
- Assignment #1: [pdf] The Perfect Shuffle -- Due Sep
14, 2016 before start of class; Data File: [h1Data.txt]
USEFUL LINKS
LECTURE TRANSPARENCIES & REQUIRED READING
- Aug 22: Lecture 1 [pdf];
OpenDSA -- Chapter 1 and Sections 2.1 - 2.5; Weiss' text: Chapter 1;
- Aug 24: Lecture 2 [pdf];
OpenDSA -- Sections 2.7, 3.1 - 3.6, 3.8 - 3.10; Weiss' text:
Chapter 2;
- Aug 29: Lecture 3 [pdf];
OpenDSA -- Sections 1.2, 4.1 - 4.7;
Weiss' text: Sections 1.4, 3.1 - 3.5;
- Aug 31: Lecture 4 (slides same as for Lec 3) [pdf];
OpenDSA -- Sections 4.1 - 4.7;
Weiss' text: Sections 3.1 - 3.5;
- Sep 05: LABOR DAY! NO CLASS ... [pdf]
- Sep 07: Lecture 5 [pdf];
OpenDSA -- Sections 4.8 - 4.14;
Weiss' text: Sections 3.6, 3.7;
- Sep 12: Lecture 6 [pdf];
OpenDSA -- Sections 6.1 - 6.6;
Weiss' text: Sections 4.1, 4.2;
- Sep 14: Lecture 7 (slides same as for Lec 6) [pdf] Remember to read
OpenDSA -- Sections 6.1 - 6.6;
Weiss' text: Sections 4.1, 4.2;
- Sep 19: Lecture 8 (slides same as for Lec 6);
- Sep 21: Lecture 9 [pdf]; Read
OpenDSA -- Sections 6.8, 6.10, 6.11;
Weiss' text: 4.3.1-4.3.4;
Try visualizations for BST insert and delete operations:
here or Here or Here;
- Sep 26: Lecture 10 [pdf]; Read
Weiss' text: 4.4; Instead of OpenDSA, look at Youtube video: here and the
try the visualizations:
here
- Sep 28: Lecture 11 (slides same as for Lec 10);
- Oct 03: Lecture 12 [pdf (Updated)]; Read
OpenDSA -- Sections 6.16, 6.17; Weiss' text: 6.1 - 6.4;
Try visualizations for Heap operations:
here
- Oct 05: Lecture 13 was canceled due to Hurricane Matthew
- Oct 10: Lecture 14 (slides same as for updated slides Lec 12)
- Oct 12: Lecture 15 [pdf]: Read
OpenDSA -- Chapter 9; Weiss' text: Chapter 5; Try visualizations at: here and: here;
try the different hash functions available there.
- Oct 17: Lecture 16 (slides same as for Lecture 15 (updated
Oct 17)); Check the reading material suggested above;
- Oct 19: Lecture 17 [Review of AVL Trees]
- Oct 24: Lecture 18 [Review for MidTerm]
- Oct 26: Midterm Exam
- Oct 31: Lecture 20 [pdf]; Read Weiss'
text: Chapter 7.1-7.8, 7.11; Also recommend reading Chapter 11
of Morin's online text
- Nov 02: Lecture 21 (Slides same as for previous class)
- Nov 07: Lecture 22 [pdf]; Read Weiss'
text: Chapter 9.1;
- Nov 09: Lecture 23 (Slides same as for previous class);
Read Weiss' text: Chapter 9.2, 9.3;
- Nov 14: Lecture 24 [pdf]
- Nov 16: Lecture 25 [pdf]
- Nov 21: Lecture 26 [pdf]; Read Weiss'
section on MST;
- Nov 23: Lecture 27 [pdf]; Read Weiss'
book Sections 9.6.1 on DFS, and 8.1-8.5 on Disjoint Union Find;
- Nov 28: Lecture 28 [pdf]; Suffix Arrays
and kD-trees; Read Weiss' book Sections 12.4, 12.5;
- Nov 30: Lecture 29 [pdf]
PREREQUISITE KNOWLEDGE EXPECTED
- COP 3337 contents (Links to recent version of this course
taught by other FIU professors:
HERE and
HERE)
- Java programming fundamentals, control structures, IO,
exceptions, Java Programming Environment, debugging.
- Java Classes, Interfaces, Iterators, Inheritance, Polymorphism
- Recursion
- Basic Data Structures in Java: ArrayList, LinkedList
- Discrete Mathematics (Links to recent version of this course
taught by FIU Math professor:
HERE)
- Basics of a Mathematical Proof
- Sets, Relations, Functions, Cardinality
- Logic, Induction, Basic Combinatorics
- Graph Theory Fundamentals
- Boolean Algebra and Functions
TEXTS
STANDARD TEXT: "Data Structures & Algorithm Analysis in
JAVA", 3rd Edition, by Mark Weiss
RECOMMENDED BOOKS FOR BRUSHING UP ON JAVA & DISCRETE MATH BACKGROUND
- Big Java, by Cay Horstmann
- Java, by Eckel
- Discrete Mathematics by Kenneth Rosen, 7th Edition
SYLLABUS
This course will be conducted in Java. If you have not recently
programmed in Java, you will probably have a very difficult time in
this course. You will be expected to use a Java 8 compiler. We will
cover as much of the following as possible:
- Algorithm and algorithm Analysis, big-Oh notation
- Linear Data Structures: Arrays, Stacks, Lists, Queues
- Hierarchical Data Strctures: Trees, Binary Search Trees, AVL
trees, B-trees
- Network Data Structures: Graphs & Graph Algorithms
- Sorting and Searching
- Hashing
COURSE OUTCOMES
- Be familiar with basic techniques of algorithm analysis
- Be familiar with writing recursive algorithms
- Master the implementation of linked data structures such as
linked lists and binary trees
- Be familiar with advanced data structures such as balanced
search trees, hash tables, priority queues and the disjoint set
union/find data structure
- Be familiar with several sub-quadratic sorting algorithms
including quicksort, mergesort and heapsort
- Be familiar with some graph algorithms such as shortest path
and minimum spanning tree
- Master the standard data structure library of a major
programming language (e.g. java.util in Java 1.2)
- Master analyzing problems and writing program solutions to
problems using the above techniques
POLICIES, RULES & REGULATIONS
- Quizzes: You should expect roughly one quiz a
week, with about 10-12 over the entire semester. Quizzes will not be
announced and will happen at the start of a class. If you miss a
quiz, no make up is possible.
- Homework Submission Policies: Programs are due at the start of
class on the date mentioned in the assignment and must be submitted
via moodle. Your submission must be a ZIP file (please use zip, not
rar format), named as y_xxxxxxx.zip (where y is the assignment #
(ranging from 1-6) and xxxxxxx is your seven digit panther IDi); the
file should include source code and sample output. The data file
will be provided or specified on the course website along with the
assignment announcement.
- Cheating Policies: Your work must be your own, and you must
attest to this in a comment that begins each program. See also
FIU's Code of Academic Integrity. CHEATING WILL NOT BE
TOLERATED. Submitted assignments cannot be joint work with
another student in the class; it cannot be joint work with another
student who previously took the class; you cannot pay someone to do
the programs for you; you cannot have someone do the programs for
you for free; you cannot submit code that is based on code submitted
in earlier semesters by others. Absolute honesty is expected, and
there will be significant consequences otherwise. You can assume
that programs will be run through software that detects
inappropriate collaborations.
- FIU's New Grading Policy: The new grading scale is A,
A-, B+, B, B-, C+, C, D, and F. Note that grades C- and D+ will not
be used any more.