Course Introduction

• Instructor: Galani Nelson

• Teaching Fellow: Jeffrey

• Contact Email: cs224-df14-staff@cs.harvard.edu

• Mailing List: Importance of signing up via course website

• Course Website: Students are encouraged to frequently check the course website for updates, resources, and announcements.

• Office Hours: Thursdays 3 PM - 5 PM in Room 302, where students can seek help and clarification on course materials.

• Course Materials: Lecture notes and assignment details will be available on the website to aid in your learning.

• Grading Policy: A detailed breakdown of grading criteria will also be posted on the website, ensuring transparency and clarity on how your performance will be evaluated.

Course Logistics

Grading Breakdown

1. Scribing (10%)

   • Students take turns writing lecture notes based on recorded lectures.

   • Notes to be written in LaTeX, template available on the website.

   • Scribe notes due 9:00 AM the following day.

2. Problem Sets (60%)

   • Must be submitted via email.

   • There are specific page limits to encourage concise solutions.

3. Final Project (30%)

   • Proposal due: October 30th.

   • Project due: Last day of reading period.

   • Project is graded by the instructor; feedback is provided on proposals.

   • Students may do practical implementations for the project.

Grading Roles

• Students may take turns grading problem sets. Participation is mandatory but typically required once.

• Scribing and grading slots are limited and filled on a first-come, first-served basis.

Course Structure

Differences from CS124

• CS224 focuses on advanced algorithms, not covered in CS124.

• Emphasizes theoretical analysis, with no programming assignments.

Course Goals

• Develop greater analytical skills in creating and analyzing algorithms.

• Explore various algorithmic techniques not covered in previous courses.

• Consider additional models for efficiency beyond time and space (memory).

Key Topics to be Covered

Algorithmic Efficiency

• Review of sorting fundamentals and limitations.

• Discussion on the static predecessor problem:

  • Static Predecessor Definition: Query returns the maximum element in set S less than a given element.

  • Algorithms explored in terms of space and query time.

Static vs. Dynamic Data Structures

• Static: No insertions or deletions allowed.

• Dynamic: Insertion and deletion operations supported.

• Importance of storage structure, e.g., binary search trees for static predecessor.

Data Structures Overview

Finding Predecessors

• Solutions to predecessor problems:

  • Static: Use binary search on sorted array (log n query time).

  • Dynamic: Use a balanced binary search tree (log n time for queries and updates).

Advanced Data Structures

1. Van Emde Boas Tree

   • Achieves O(log W) query and update times.

   • Space complexity related to universe size U.

2. Fusion Trees

   • Supports O(log base W of n) query time with linear space.

Sorting Techniques

• Improves on O(n log n) comparison-based sorting models.

• Expected time sorting using Fusion trees leads to O(n * square root log n).

• Research explored for potential linear time sorting algorithms.

Conclusion

• Exploration of advanced algorithms remains dynamic and theoretical, within the framework set by CS224. All students are encouraged to actively participate in discussions and work collaboratively.