CMSC420-0102: Data Structures-Summer I 2017 jasonfil

CMSC420-0102: Data Structures-Summer I 2017 jasonfil

home page banner

CMSC 420: Data Structures 0201

~ syllabus under construction... ~

Lectures

  • Days/Times: MonTueWedThu, 09:30-10:55am
  • Location: CSIC 1121

 

Course Staff

Course Content

(For a live view of how the course is evolving, check out Modules.)

Our course will be semantically and temporally divided into (4) four semantic areas. The list of subtopics is tentative, and individual subtopics might be swapped around or erased, conditioned on available time.

  1. Building dictionaries for Comparables (data structures for efficient insertion, deletion and search in 1 dimension)
    • Self-balanced binary search trees (AVL, Splay, R-B)
    • B-Trees (entirely within memory)
    • Hash Tables
      • Linear Probing
      • Double Hashing 
      • Quadratic / Exponential Hashing
      • Ordered Hashing
  2. Data structures for efficient (sub)string search, storage, insertion, deletion, compression and comparison
    • Tries, Patricia tries
    • Suffix arrays
    • LZW algorithm
    • String matching (very tentative)
      • Naive string matcher
      • KMP
      • Boyer-Moore
      • Rubin-Karp
  3. Multi-dimensional Data Structures
    • KD-Trees
    • QuadTrees
      • Point
      • Point-Region (PR)
        • Ordinary
        • Bucketed
        • Loose
      • Region
    • Multi-Dimensional Hashing
      • MinHash 
      • Locality Sensitive Hashing (LSH)
  4. Electives (if time allows)
    • Priority Queues and Fibonacci Heaps
    • Skiplists
    • Range Trees, Priority Search Trees
    • Advanced quadtrees (e.g MX-CIF)
    • Data Structures for implementing Frequent Itemset Mining.
    • Distributed Data Structures
    • Data Structures for block file management on disk.
    • ...

 

Important Dates:

  • First day of classes: Tuesday, 05-30
  • End of Summer Session I' Drop-Add Period: 06-05 at 4:30pm
  • First exam: Wednesday, 06-15
  • Last day to drop with a 'W' in Summer Session I : 06-22
  • Independence Day (national holiday): 07-04
  • Second exam: Thursday, 07-06
  • Third (final) exam: Thursday, 07-20

 TextBook (recommended)

  • Data Structures & Algorithm Analysis, Cliff Shaffer. Free PDFs with C++ and Java code snippets available from author's website.

Advice: Make any PDF textbook your offline friend to avoid distraction from the Web. Engineering Copy Services can print either book and add binding for a meager cost of about $5 each.

Note that the instructor has considered the OpenDSA version (non-https link for now) of the textbook and is playing around with it in a private sandbox Canvas space. However, they will not have the necessary time to implement the entire course on Canvas within the approximately two weeks that they have to prepare the course within the inter-semester, which is why we will stick with the PDFs this time.

 

Assessment / Grading

  • 3-4 Programming projects in Java, tested and auto-graded on CS department's submit server: 40%.
  • 2 within-semester exams on paper (1hr 20 minutes, in class) 15 and 20%, respectively.
  • 1 final (1 hr 20 minutes, in class): 25%
  • Honors' / Extra Credit programming projects (see below): +50%

 

Websites / Communication

This summer session we will be using the current ELMS - CANVAS page for hosting our gradebook, our files and post static course information, such as this syllabus. For dynamic communication with you, we will be using our Piazza page. Please contact the instructor for an invitation to our Piazza page.

 

Course / University Policies

Conveniently, since the Fall semester of 2016, the Office of Undergraduate Studies has packaged together a comprehensive syllabus which provides the rules, regulations and instructors' / students' rights and obligations for all courses in UMD. It also details important regulations about Academic Dishonesty, Disability Accommodations, Excused Absences, etc. We abide by this set of policies, which we further specify below:

  • Absences from any exam must be accompanied by sufficient documentation (medical or otherwise) which clearly stipulates the date(s) during which the student was not able to adhere to her academic responsibilities. The instructor will then schedule a make-up exam with the student(s) that was/were absent, with potentially altered subjects to ensure academic honesty.
  • Programming assignments already have a 2-day half-credit deadline. Individual extensions beyond that period will only be given in extraneous, documentable circumstances and will only be up to 2 days, to ensure that affected students do not fall behind on their work.
  • The instructor reserves the right to tune the programming assignment deadline in the students' favor, as explained in the subsequent section.

 

Student-friendly flexible programming assignment deadline policy 

 

Please note that the current programming project deadlines, as detailed on our course calendar, are tentative, and will have been finalized by the first day of class (05-30).

The instructor has access to stats about student submission on their Submit Server view. If, a certain number of days before the deadline for a project, the instructor happens to see that all students have passed all unit tests, they reserve the right to immediately release the second programming project so that students can have a headstart.

Course Summary:

Date Details