Course Syllabus

Original Thumbnail

CMSC 420 0301 Data Structures

Lectures 

    • Days/TimesTue / Thu 12:30-01:45
    • Location: JMZ (Jimenez) 0220 

 

Course Staff 

Office Hours

- Refer to this Google Sheet. We will be dynamically editing this sheet if we need to cancel or move specific office hours around on a given week.

 

Course Content

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 Comparable data types; Data structures for efficient insertion, deletion and search in 1 dimension.
    • Self-balanced binary search trees (AVL, Splay, R-B)
    • B-Trees (memory-resident)
    • Hash Tables
      • Linear Probing
      • Double Hashing 
      • Quadratic / Exponential Hashing
      • Ordered Hashing
  2. Data structures for efficient string search, storage, insertion, deletion, compression.
    • Tries, Patricia tries
    • Suffix arrays
    • LZW algorithm
  3. Multi-dimensional Data Structures, nearest-neighbor and range queries.
    • KD-Trees
    • QuadTrees
      • Point
      • Point-Region (PR)
        • Ordinary
        • Bucketed
        • Loose
      • Region
      • MX, MX-CIF
    • Multi-Dimensional Hashing
      • MinHash 
      • Locality Sensitive Hashing (LSH)
  4. Electives (if time allows)
    • Priority Queues and Fibonacci Heaps
    • Skiplists
    • Range Trees, Priority Search Trees.
    • Data Structures for implementing Frequent Itemset Mining.
    • Distributed Data Structures.
    • Data Structures for block file management on disk.
    • ...

 

Important Dates:

  • First day of classes: Thursday, 01-25
  • Midterm 1 (in class): Tuesday, 02-27
  • UMD SpringBreak: 03-18 (Sunday) through 03-25 (Sunday)
  • Midterm 2 (in class): 04-17
  • Last day of classes: May 10
  • Reading day: May 11
  • Final: Location TBA by Central Scheduling mid-semester.

 

Assessment / Grading 

  • 4 - 5 Programming projects in Java, tested and auto-graded on CS department's submit server: 40%.
  • Frequent (every 2 or 3 weeks) homeworks uploaded on Gradescope: 10%
  • 2 midterms (70 minutes, in class), both 15%.
  • 1 final (2 hours, location TBA mid-semester): 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 the book and add binding for a meager cost of about $5.

 

Submitting your homeworks

Your homeworks are disseminated electronically on ELMS. Every homework is uploaded in ZIP format and contains at least a .tex source and the resulting .pdf after applying the program pdflatex on the .tex file. Your responses are to be uploaded on Gradescope as a PDF. You can choose any methodology you desire to turn your response into a PDF. You may directly edit the PDF using programs such as Apple Preview, or you can use the Adobe Reader Professional version that is available to all UMD students free of charge on Terpware to convert the PDF into a .docx and work from there. If you write neatly, using a program such as Camscanner to "scan" your handwritten responses can help you create acceptable quality PDFs straight from your phone's camera. To further assist you, we provide the LaTeX: \LaTeX
sources for the homeworks, should you want to directly edit the sources and produce a new PDF to upload. Check this page for resources on LaTeX: \LaTeX
 if you need them. The template is separately maintained here.

 

Course / University Policies

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. Makeup exams can be administered within 1 (one) week of the original exam date.
  • Programming assignments already have a built-in 2-day late submission for 70% credit. 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.
  • Similarly, homeworks can be submitted late for 70% credit through 11:59pm, 2 days after the normal deadline, and further extensions given in exceptional circumstances can only be up to 2 days, as above.
  • 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 

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 subsequent programming project so that students can have a headstart. The deadline for the subsequent project would not be affected by this; in practice, this means that if the class does very well in a project deemed "easy", then they will have more time to complete a subsequent project. If that project is also globally completed ahead of time, the process can be repeated.

 

Firearms in class

Handguns, assault rifles, bazookas and other firearms that require an ignition mechanism are not allowed in class. Please consult the Maryland Firearm Safety Act of 2013 for more information on the subject of firearm laws in the state of Maryland.

Course Summary:

Date Details Due